Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning
Authors: Grigory Malinovsky
Kai Yi
Peter Richtárik
Venue: NeurIPS 2022 Accept (2022)
Keywords: Federated Learning
Variance Reduction
Local SGD
ProxSkip
LSVRG
DIANA
Communication Compression
Local Training

Abstract: We study distributed optimization methods based on the {\em local training (LT)} paradigm, i.e., methods which achieve communication efficiency by performing richer local gradient-based training on the clients before (expensive) parameter averaging is allowed to take place. While these methods were first proposed about a decade ago, and form the algorithmic backbone of federated learning, there is an enormous gap between their practical performance, and our theoretical understanding. Looking back at the progress of the field, we {\em identify 5 generations of LT methods}: 1) heuristic, 2) homogeneous, 3) sublinear, 4) linear, and 5) accelerated. The 5${}^{\rm th}$ generation was initiated by the ProxSkip method of Mishchenko et al. (2022), whose analysis provided the first theoretical confirmation that LT is a communication acceleration mechanism. Inspired by this recent progress, we contribute to the 5${}^{\rm th}$ generation of LT methods by showing that it is possible to enhance ProxSkip further using {\em variance reduction}. While all previous theoretical results for LT methods ignore the cost of local work altogether, and are framed purely in terms of the number of communication rounds, we construct a method that can be substantially faster in terms of the {\em total training time} than the state-of-the-art method ProxSkip in theory and practice in the regime when local computation is sufficiently expensive. We characterize this threshold theoretically, and confirm our theoretical predictions with empirical results. Our treatment of variance reduction is generic, and can work with a large number of variance reduction techniques, which may lead to future applications in the future. Finally, we corroborate our theoretical results with carefully engineered proof-of-concept experiments.

Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning
Grigory Malinovsky
Kai Yi KAUST
KAUST grigory. hngooyyyntlnooskkkkuuuut........
sa Peter Richtárik
pai.yikkause edu.
KAUST
peter wwwerrrccchaiikkkus...cco edu.
Abstract
We study distributed optimization methods based the local training (LT) paradigm: achieving communication efficiency by performing richer local gradient- based training the clients before parameter averaging. Looking back the progress of the field, we identify generations of LT methods: 1) heuristic, 2) homogeneous, 3) sublinear, initiated by the ProxSkip method of Mishchenko et al. [2022] and its analysis, is characterized by the first theoretical confirmation that LT is a communication acceleration mechanism. Inspired by this recent progress, we contribute to the 5th generation of LT methods by showing that is possible to enhance them further using variance reduction. While all previous theoretical results for LT methods ignore cost of local work altogether, and are framed purely terms the number of communication rounds, we show that our methods can be substantially faster in terms of the total Iraining cost than the state-of-the-ae method ProxSkip theory and practice in the regime when local computation is sufficiently expensive. We characterize this threshold theoretically, and confirm our theoretical predictions with empirical results.
linear, and 5) accelerated. The 5th generation,
Introduction
Announced in April 2017 in Google AI blog [McMahan and Ramage, 2017], and citing four foundational papers [Konečný et al., 2016b,a, McMahan et al., 2017, Bonawitz et al., 2017] of what was to become new and rapidly growing interdisciplinary field, federated learning (FL) constitutes a novel paradigm for training supervised machine learning models. The key idea is the acknowledgement that increasing amounts of data are being captured and stored on edge devices, such mobile phones, sensors and hospital workstations, and that moving the data to datacenter for centralized processing may infeasible or undesirable for various reasons, including high energy costs and data privacy concerns [Kairouz et al., 2019, Li et al., 2020a]. FL faces multitude of challenges which being actively addressed by the research community.
1.1 Formalism
We study the standard optimization formulation of federated learning [Konečný et al., 2016a, McMa- han et al., 2017, Kairouz et al., 2019, Wang al., 2021] given by
nl
min d(x),
(xx)
n (I(2),
dx(x)
=
Σ
(1)
(I)
ZERa
1=1
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where M is the number of clients (devices, machines, workers), n; is the number of training data points on client E fI. M) and n == Σ =i= n4 is the total number of training data points collectively owned by this federation of M clients. Note that Φ is the empirical risk over the federated dataset. Perhaps conceptually the simplest method for solving (1) is gradient descent (GD),
M
M
T Vol(z)) - _
n (It Voi(i))
1141 = 21 100-~Vell VV((r) = It
(2)
n2
where > 0 is the stepsize. It will be useful to describe how GD would be implemented in federated environment. First, all clients i E { MM in parallel perform a single local gradient step starting from the current global model Te, arriving at the local models Ttt == It These local models are then communicated to the orchestrating server, which aggregates them via weighted averaging, arriving the new global model x Σ Li=1 n broadcast back to all clients, and the process is repeated until a model of sufficient quality is found.
(Tr), E {1...., M.
mi Tat- This new model is then
1.2 Federated averaging
Proposed by Povey et al. [2015], Moritz et al. [2016], McMahan et al. [2017], federated averaging (FedAvg) is arguably the most popular method for solving the standard FL formulation (1). Motivated by the specific constraints of federated environments, FedAvg can be seen as practical enhancement of GD via the simultaneous application of three techniques: a) data sampling (DS), b) client sampling (CS), and c) local training (LTT). That is,
FedAvg = GD + (DS + CS + L.T..
We will now briefly describe each of these three GD-enhancing techniques separately.
(a) GD + Data Sampling. In situations when the local datasets are so large that the computation of the exact local gradients becomes a bottleneck, it makes sense to approximate them via data sampling. That is, instead of passing through all local data to compute the local gradient (xr(), each client i computes the gradients (x,;(z,,) for j E Dix only, where Di is a suitably chosen small-enough subset of the local dataset {1..... n. These gradients are then used to form gradient estimators gi (zz) ~ (Z;( which are used to perform a
local SGD step all clients. The rest of the procedure is the same as in the case of GD. That is, the local models obtained in this way are sent to the orchestrating server, the server aggregates them via weighted averaging and broadcasts the resulting model back to all clients. Combination GD and DS can be seen as a particular version of SGD, where the stochastic gradient estimator is formed from the gradients Voly (axx) associated with the (i. where j E Dia While DS is still an active area of research, it has been studied for a long time, and is in general well understood [Takáčč et al., 2013, Li et al., 2014, 4, Csiba and Richtárik, 2018, Gower al., 201 9a, Horváth and Richtárik, 2019, Khaled and Richtárik, 2020].
datapoints
(b) GD Client Sampling. In practical federated environments, and especially in cross- device FL [Kairouz et al., 2019], the number of clients is enormous, they are not all available at all times, and the orchestrating server has limited compute and memory capacity. For these and other reasons, practical FL methods need to work in an environment in which small subset S, S fl..... M) of the clients is sampled ("participates") in each communniation/aggregattooo/////
round only. Since only the participating clients i E S, perform a local GD step and communicate the resulting local model to the orchestrating server for aggregation, this induces an error compared to GD, which has an adverse effect on the convergence rate. Combination of GD and CS can be seen as a particular version of SGD, where the stochastic gradient estimator is formed from the gradients V associated with the datapoints (i, where U (1, (1..... m.). While CS is still active area of research, since CS is a special type of DS, much was known about CS long before FedAvg was proposed [Gower et al., 2019a, Horváth and Richtárik, 2019]. Still, CS poses new challenges tackled by the community Eichner et al. [2019], Chen et al. [2020], Gower et al. [2019a], Cho et al. [2020], Charles et al. [2021].
(c) GD + Local Training. In federated learning, the cost of communication between the clients and the orchestrating server forms the key bottleneck. Indeed, in their FedAvg paper, which introduced LT to the world of federated learning, McMahan et al. [2017] wrote:

---

Table 1: Five generations of local training (LT) methods summarizing the progress made by the ML/FL community over the span 7+ years in the understanding the communication acceleration properties of LT.
Generation"
Theory
Assumptions
Comm. Complexity"
Selected Key References
cupirrical results only
LocalSGD Povey et al., 2015]
Ieeuristic
empirical results only
SparkNet [Moritz el 2016]
empirical results only
FodAvg [MeMahan al., 2017]
2. Homogencous
bounded gradients
sublinear
FadAvg cr., 2020b]
bounded grad. diversity
lincar but worse than GD
LFGD [Haddadpour and Mahdavi, 2019]
standard
sublineur
LGD [Khaled al. 2019]
Suhlinear
standard
sublineur
LSGD Khaled et al., 2020]
standard
lincar but worse than GD
Scaffold [Karinireddy ct al., 2020]
Linear
standard
linear but worse than GD
S-Local-GD [Gorbunov et al., 2020al
standard
linear but worse thun GD
FodLin [Mitra el al., 2021]
Accelerated
standard
ProxSki/Scallnne MMsbchenko et al., 2022]
standard
linear & betler than GD
ProxSkip VR [THIS WORK]
(4) Since client sampling and data sampling (DS) only ticoretical communication complexity historical breakdown of the literature generations of methods locuses on fuil cliest partccppation (Le., and exact local gradient l.c., no DS) setting. While some of referenced methods incurporate CS and DS techniques, these are irreevaat for our purposes. Indeed, from the viewpoin of communication complexity all these algocithms enjoy best thcoretical performaace in the ne-CS and no-D5 regime.
the porposes this tible, we consider prablem (1) the moouth and strongfy commes regime only This bocosse the literature on mathods stregples to understand even in this simplest (fumm the puint of view of optimizatioo) regime.
Rowndnd prodient diverity is uniform bound en a spacific notion goalient variance dependinn on cliest sampling probuiiities. However, this resumption (se all homagencity asummptiona) is vary restrictive For example, it not satisfeed the standard class smooth and strong comvex fanctions.
(4) The notorious challenge handling non-iid. by methads solved by Khuled et [2019] (from the viewpoint of optimisatio). genentionn
3 unwurds, there was no need to invoke any data/gradient bomogeniity aosumptions. llanlling noriiid data remains challenge from the point of view of
generatization, typically by considering personalized models.
"In contrast', in federated optimization communication costs dominate". ".
LT is conceptually simple and surprisingly powerful communication-accelle nique. The basic idea behind LT is for the clients to perform multiple local GD steps instead of single step (which how GD operates) before communication and aggregation takes place. The intuitive reasoning used in virtually all papers on this topic is: performing multi- ple local GD steps results in "richer" and ultimately more useful local training in the sense that fewer communication rounds will hopefully suffice to finish the training. McMahan et al. [2017] supported this intuition with ample empirical evidence, and credited LT as the critical component behind the success of FedAvg:
tech-
"Thus, our goal is to use additional computation in order to decrease the number of rounds of communication needed train model... " "Communication costs are the principal construint, and we show a reduction in required communication rounds by 10-100x as compared to synchronized stochastic gradient dexcen."" "... the speedups we achieve are due primarily to adding more computation on each client".
2 Five Generations of Local Training Methods
We now offer several historical comments on the most important developments related to the theoreti- cal understanding of LT. To this end, we have identified 5 distinct generations of LT methods, each with its unique challenges and characteristics. To make the narrative simple, and since we focus on this regime in our paper, we limit our overview to loss functions ov that are p-strongly convex and L-smooth. This is arguably the most studied class of functions in continuous optimization [Nesterov, 2004], and for this reason, it presents a valuable litmus test for any theory of LT.
2.1 Generation 1: Heuristic Age
While LT ideas were used in several machine learning domains before [Povey et al., 2015, Moritz et al., 2016), LT truly rose to prominence as a practically potent communication acceleration technique due to the seminal paper of McMahan et al. [2017] which introduced the FedAvg algorithm. However, no theory was provided in their work, nor in any prior work. L.T-based heuristics, i.e., methods without any thcoretical guarantees, dominated the initial development of the field up to, and including, the FedAvg paper.
'oo datacenter optimization
3

---

2.2 Generation 2: Homogeneous Age
The first theoretical results for LT methods offering explicit convergence rates relied on various data/gradient homogeneity" assumptions. The intuitive rationale behind such assumptions comes from the following thought process. In the extreme case when all the local functions di are identical (this is often referred to as the homogeneous or i.i.d. data regime), there a very simple approach to making GD communication-cnne -efriinnnfffiintt: push the idea of LT to its extreme by running GD on all clients, whatsoever.
independently and in parallel, without any Extrapolating from this, it is reasonable to assume that as we increase heterogeneity, taking multiple local steps should still be beneficial as long as we do not take too many steps. Several authors analyzed various LT methods under such assumptions, and obtained rates [Haddadpour and Mahdavi, 2019, Yu et al., 2019, Li et al., 2019, 2020b]. However, bounded dissimilarity assumptions are highly problematic. First, they do not seem to be satisfied even for some of the simplest function classes, such as strongly convex quadratics [Khaled et al., 2019, 2020], and moreover, it is well known that practical FL datasets are highly heterogeneous/non-i... McMahan et al. [2017], Kairouz et al. [2019]. So, analyses relying on such strong assumptions are both mathematically questionable, and practically irrelevant.
2.3 Generation 3: Sublinear Age
The third generation of LT methods is characterized by the successful removal of the bounded dissim- ilarity assumptions from the convergence theory. Khaled et al. [2019] first achieved this breakthrough by studying the simplest LT method: local gradient descent (LGD) (i.e., a simple combination of GD and LT). While works belonging to this generation elevated LT to the same theoretical footing as GD in terms of the assumptions, which marked an important milestone in our understanding of LT. unfortunately, the obtained communication complexity theory of LGD is pessimistic when compared to vanilla GD. Indeed, the inclusion of LT did not lead to an improvement upon the communication complexity of vanilla GD. Moreover, while GD enjoys linear communication complexity (in the smooth and strongly convex regime), the communication complexity of LGD is sublinear. a follow-up work, Khaled et al. [2020] later analyzed LGD in combination with DS well. Woodworth et al. [2020] and Glasgow et al. [2022] provided lower bounds for LGD with DS showing that it not better than minibatch SGD in heterogeneous setting. See the work of Malinovsky et al. [2020] for fixed-pont exint theory viewpoint.
2.4 Generation 4: Linear Age
The fourth generation of LT methods is characterized by the effort to design linearly converging variants of LT algorithms. In order achieve this, it was important to tame the adverse effect of the so-called client drift [Karimireddy et al., 2020], which was identified as the culprit of the Masse-than-GD theoretical performance of the previous generation of LT methods. The first LT-based method that successfully tamed client drift, and as result obtained a linear convergence rate, was Scaffold [Karimireddy et al., 2020]. Several alternative approaches obtaining the same effect were later proposed by Gorbunov et al. [2020a] and Mitra et al. [2021]. While obtaining linear rate for LT methods under standard assumptions was a major achievement, the communication complexity of these methods is still somewhat worse' than that of vanilla GD, and is at best equal to that of GD.
2.5 Generation 5: Accelerated Age
Finally, the fifth generation of LT methods was initiated recently by Mishchenko et al. [2022] with their ProxSkip method which enjoys accelerated communicution complexity. Acceleration comes from the LT steps coupled with new client drift reduction technique and probabilistic approach to deciding whether communication takes place or not. Mishchenko et al. [2022] first reformulate (I)
We use the term homogeneity to refer to various related assumptions used in the literature, including bounded gradient norms [Li et al., 2020b], bounded gradient variance [Li et al., 2019, Yu et al., 2019] and bounded gradient diversity [Haddadpour and Mahdavi, 2019].
Bott GD, and LT methods such as Scaffold [Karimireddy et al., 2020], S-Local-GD |Gorbunov et al., 2020a] and FedLin [Mitra et al.. 2021] enjoy the linear rate (rr log )). where x is a condition number. However, this condition number is in general slightly worse for the LT methods.

---

Algorithm ProxSkip-VR
1: Parameters: stepsize 0. probability p (0, 1], initial iterate æo E IR initial control vector No E R initial gradient shift ho 12 number of iterations T 2
2: for = 0, 00.....,77
do
3: 9t = g Et)
Sample & and construct unbiased estimator of V (2x) Take gradient-type step adjusted via the shift h4
4: Φi+1 2t 79( h2)
5: Construct new control vector yo+11
6: Flip a coin 0, E {0, } where Prob(O, = 1) = o Decides whether to skip the prox or not
7:
if 0. then
8:
F++1 = prox zr ($1+1 111)
o Apply prox, but only with probability
9:
else
10: Ut++1 = lt+1
Skip the prox!
11: end if
12: lie+1 he + & (34+1 - 12+1)
Update the shift h
13:
end for
into the equivalent consensus form
min f(x) + r(x), ZERd
(3)
where d = .Md, x (I1,...,,IMI E Rd. and
f(x) = Σ (x;)) n2
M
n
r(x)
0
x = TM
(4)
+oo
otherwise.
The ProxSkip method is randomized variant of proximal gradient descent (ProxGD) [Nesterov, 2013, Beck, 2017] for solving (3), with the proximity operator of r, given by
(rox,(x)) = arg min y
r(v) + 2 -1lv-=11?
x112)
being evaluated in each iteration with probability p E (0, 1] only. Remarkably, Mishchenko al. [2022] showed that it is possible to choose p as low as 1/vK, where x. is the condition number of f. without this worsening the rate of its parent method ProxGD. In summary, ProxSkip lets the M clients perform /K local gradient steps in expectation, followed by the evaluation of the prox of which in the case of the consensus reformulation of (1) means averaging across all M nodes.
ProxSkip-VR: A General Variance Reduction Framework for ProxSkip
In this work we contribute to the fifth generation of LT methods by extending the work of Mishchenko et al. [2022] to allow for a very large family of gradient estimators, including variance reduced (VR) ones [Johnson and Zhang, 2013, Defazio et al., 2014, Kovalev et al., 2020a, Mishchenko et al., 2019].
Like ProxSkip, our method ProxSkip-VE VR (Algorithm 1) aimed to solve the composite problem (3) in a more general setting (see Assumptions 1-3), with the special structure (4) coming from the consensus reformulation being special case only. Our method differs from ProxSkip that we replace the gradient V (z,, by an unbiased estimator 9, = g Vc. E.), where & is the source of randomness controlling unbiasedness and y/ a control vector whose role is to progressively reduce the variance of the estimator, so that
E [g. Ft. vil fxx))
There are several motivations behind this endeavor. First, it is a-priori not clear whether the novel proof technique employed by Mishchenko al. [2022] can be combined with the proof techniques used in the analysis of VR methods, and hence it is scientifically significant to investigate the possibility of such a merger of two strands of literature. We show that this is possible. Second, marrying VR estimators with ProxSkip can lead to novel system architectures which are more elaborate than the simplistic client-server architecture (see Section 4). Lastly, while researchers contributing to generations 1-4 of LT methods were preoccupied with trying close the gap GD
5

---

in terms of communication efficiency, they ignored the number of the local steps appearing in their algorithms, and reported their bounds primarily in terms of the numher of communication rounds. Bounds reported this way make complete sense in the scenario when the cost of local work (e.g.. one SGD step w.r.t. a single data point), say 6, is negligible compared to the cost of communication, which can w.l.o.g, assume be I, and when the number of local steps small. With the advent of the fifth generation of LT methods, we can (to a large degree) stop worrying about communication efficiency, and can now ask more refined questions, such as:
Are there gradient estimators which, when combined with ProxSkip, lead to faster algorithms in terms of the total cost, which includes the communication cost as well as the cost of local training?
We give an affirmative answer to the question in Sections and 5.
3.1 Standard assumptions
We assume throughout that f' is differentiable, and let Dy(r, == fx) (())) (V)(), v) denote the Bregman divergence of f. Throughout the work we make the following assumptions:
Assumption (L-smoothness). 3L > 0 such that 2D, y) S L 1|x - y11 for all x, y E R..
Assumption 2 (μ-convexity). 3u > 0 such that f || vll² S (x, v) for all v,y E Rd.
Assumption 3. The regularizer r B - R U {+oo} is proper, closed and convex.
Under the above assumptions, (3) has a unique minimizer x., Let h, == Vf(x))).
3.2 Modelling variance reduced gradient estimators
Our next assumption, initially introduced by Gorbunov et al. [2020b], postulates several parametric inequalities characterizing the behavior and ultimately the quality of gradient estimator. Similar assumptions appeared later in [Gorbunov et al., 2020a.c].
Assumption 4. Let {ar) } be iterates produced by ProxSkip VR. First, we assume that the stochastic gradients g. g(a,, Vt. Vt.Ea) E,) unbiased for all t 2 0, namely
E [g It. yt]
((xx).
(5)
Second, we assume that there exist non-negative constants A, B, C, A, C, Ć, with B < 1, and nonnegative mapping Yt + o(y.) == og such that the following two relations hold for all 2 0,
E |19e ff(x))1 Fea Vt
2ADy(II, + Bo, + C,
E [0t+1 Øt, Vel
< 2AD)(I....) + Bo, + Õ.
(7)
Assumption 4 covers a very large collection of gradient estimators, including an infinite variety of subsampling/miiibatch estimators, gradient sparsification and quantization estimators, and their combinations; see [Gorbunov et al., 2020b] for examples. VR estimators are characterized by
C' = Ö = 0; most non-VR estimators by À = B = C = B = 0 and C > 0 [Gower et al., 2019b].
3.3 Main result
We are now ready formulate our main result.
Theorem 5. Let Assumptions 2 and 3 hold, and let gr be a gradient estimator satisfin Assumption 4. B > 0, choose any W > B/(1-B) B) and B = (B+W B/Ww If = 0, let W = 0 and 3 = B. Choose stepsize 0 < 7 S min (1/p, 3/(++W))) Then the iterates of ProxSkip-VVR DR for any p (0. 1] satisfy
(c W 72
E [ < max {(1 - , ,0,,"11110 (1- -1-p3)") vo + min {YH, p2, 1 B)
(8)
where the Lyapunov function is defined by v ||,0, x. 1|2 3/t /1ke h..12 + 72W or.

---

Table 2: Special cases of ProxSkip-VR. depending on the choice of the gradient estimator gr.
Communication Complexity
Iteration Complesity
Curollaries of Theorem 5
Estimator of V
of ProxSkip-V
of ProxSHip-VR
th
1// 1/
(4/4 V-)
Theorem
SGD
VAye + v20/en²) log 1/)
O ((A/a + 20/en") log log 1/e)
Theorem 8
HUB INEW]
O
V //mma// (1 - =/-) log %/2
O (Lrmar/ (1 + w/+) log 1/4
Theorem 9
LSVRG [NEW]
Tarsy log 1/-)
O (Krr)/ log 1/x)
Conollary
[NEW]
o
//ma//u (1 - 4/ar) log 1/)
(1 (1 + w/Mr log 1/e)
Conollary
Any estimator satsfying Assumption 4
01 ProxSkip-VR with the GD extimater reduces the ProxSkip method of Mishchenkko et al. [2022]
ProxSkip-VR with the SGD estimatur saissying Assumption 7 reduces the SProxSkip method of Mistachenko al. (2022)
L(T) = F[m-1] Amax +(m-= 13
L, where is mini batch size and the number of clients belonging bub
3.4 Two examples of gradient estimators
Here we give two illustrating examples of estimators satisfying Assumption 4. Theorem 6 (GD estimator), Let Assumption 1, 2 and 3 hold. Then for the trivial estimator ge (xx)). Assumption 4 holds with the following parameters:
A= B 0, C²=
= 0, B 0, Č=
a; = 0.
Choose stepsize satisfying 0 < 7 S 1/L. Then the iterates of ProxSkip-VR for any p E (0, 1] satisfy
E [ S max {1 Tu)T, (1 p²) Vo:
(9)
where 1 == ||2 - 112 + lhe 11112. Let 7 1/1, and p VulT. then the communication and #iters = O (1 log log iteration complexities of ProxSkip- VR are #comms = O (v (
This recovers the result obtained by Mishchenko et al. [2022] for their ProxSkip method. The next assumption holds for virtually all (non-VR) estimators based on subsampling [Gower et al., 2019b].
Assumption 7 (Expected smoothness). We say that an unbiased estimator g(:: () IRd + R of the gradient V (x) satisfies the expected smoothness inequality if there exists A" > 0 such that
E [11g(2;; E) ((x+;:))1?) S Dx),, Vx E RRd
Theorem 8 (SGD estimator). Let g(x, satisfy Assumption 7 and define 9t g( Ee). where & is chosen independently at time t. Then Assumption holds with the following parameters:
A 2A", 0 C =VVaaa(g(x.... E)), A= B=0, 0, Ö 0, o2 0.
Moreover, assume that Assumption holds. Choose stepsize 0 << S min 1/A3. Then the iterates of ProxSkip-VR for any probability p E (0,1) satisfy
vo + 72 2 (a.,g((z..))
E [ S max {(1 - (11- - p")="
(10)
min (7/4, p2}
where the Lyapunov function is defined by Vi ||,, - x. 12 12 3 ll, 1.112. R. If we choose
y min (1/A, su/2c) and = Vyp then the communication and iteration complexities of ProxSkip-
VR are #comms = O ((V2 A
log H) Hitters = O (( - log ) respectively.
This recovers the result obtained by Mishchenko et al. [2022] for their stochastic variant of ProxSkip. which they call SProxSkip.
4 New FL Architecture: Regional Hubs Connecting the Clients to the Server
We now illustrate the versatility of our ProxSkip-VR framework by designing a new "FL. architecture" and proposing an algorithm that efficiently operate in this setting.
In particular, we consider the situation where the clients are clustered (c.g., based on region), and where hub is placed in between each cluster and the central server. Clients communicate with their regional hub only, which can communicate with the central server (see Figure 1). There are M hubs, hub handles n, clients, and client associated with hub i owns loss function Øiz-
7

---

Mathematically, this can be modeled by problem (I). In this situation, we care about two sources of communication cost: the server and the hubs, and between the hubs and the clients. We propose to handle this via local training (LT) between the server and the hubs, and via client sampling (CS) and compressed communication (CC) between the hubs and the clients. Algorithmically, from the server-hubs perspective, we are applying particular variant of ProxSkip-VFi to (3)- (4), where Φ; is the aggregate loss handles by hub i. This takes care of communication efficiency between the server and the hub. Note also that we need not worry about partial participation of hubs, as these are designed to be always available. However, in this situation, it is costly for hub i to compute the gradient of o, as this involves communication with all the clients handles.
Figure 1: Server-hubs-clienss FL. ar- chitecture with 4 hubs and 12 clients.
4.1 Handling of client sampling (CS) and compressed communication (CC)
In order to alleviate this burden, we propose a combination of CS and CC. However, we need to be very careful about how to do this. Indeed, both CS and CC, even when applied in isolation, and without ProxSkip the mix, can lead to a substantial slowdown convergence. For example, one will typically lose linear convergence in the strongly convex regime. However, techniques for preserving linear convergence in the presence CS and CC exist: this is what variance reduction strategies are designed to do. For example, LSVRG [Hofmann et al., 2015, Kovalev et al., 2020a] is VR technique for reducing the variance due to CS, and DIANA [Mishchenko et al., 2019] a VR technique for reducing the variance due to CC. However, we are not aware of any VR method that combines CS (applied first) and CC (applied second).
We now propose such technique. In iteration t. every hub E (1, M selects random subset S S {1, n2 of the clients it handles of cardinality Ty. chosen uniformly at random. and estimates the hub gradient via
Vol(I.) 2 ol
Σ ox (Vor((x) Voi(())) Vol(v)), JESt
(11)
where Q² R - Rd is a randomized compression (e.g.. sparsification or quantization) opera- tor [Alistarh al., 2017, Khirirat al., 2018, Horváth et al., 2019b.a, Philippenko and Dieuleveut, 2020], i.e., a mapping satisfying
E
[f =x, E (0) =11]] sw||> Va e Rd,,
(12)
and the control vector Y/ is updated probabilistically as follows:
{
It with probability q
Vc++
with probability
1-4
(13)
The global gradient estimator (a vector RMdd' ), which we call HUB, is construcuted as a concatena- tion of the above hub estimators:
v (xx) = -" Voz i=1 g. = g( Mr, &.) = 14
(14)
i=1
where & represents the combined randomness from the compressors { and random sets {
In order to analyze ProxSkip-VR in the consensus form, from now on we assume that nı n/M and T; = r E (1, m) for all i, and rely on slightly different, more general reformulation:
min ZER" m
Σ [)())) j=1
m
3,(x)
Σ
M
Sig (x+), r(x) = { +o0
fo
if .... 2M
M
otherwise.
Our proposed method ProxSkip-HUB ProxSkip-Vee VR combined with the novel HUB estimator (14), applied to the above reformulation; see Algorithm 2.
8

---

4.2
Theory for ProxSkip-HÜB
In the following result we first claim that the above estimator satisfies Assumption 4 with C== C 0 (i.e., it is variance-reduced), and the rest of the claim follows by application of our general theorem Theorem 5.
Theorem 9. Assume that VØj is Ly-smooth for all j and let Assumptions 2 and 3 hold. Then for the gradient estimator (14), Assumption 4 holds with the following constants:
A= 4 ((T))
3 -Laxxx B = 4 (1+ C= Ā= gLmax
B B Ö 0,
and 0, = (wt), o(y) = 1
m -3= [ト) - ( Lmax = max, Lj. Set W = BB/
and 0 < S min (4/n, ((AWW))} Then the iterates of ProxSkip-VR VR for any E (0, 1| satisfy {
E E S max {a- -1-1p) (1
(1- 2) 2')
2 Yo.
where the Lyapunov function is defined by V; == ||: x. 112 + pz l1 1-1 + 7 (1+ +)
We now consider two special cases. In the first, specialize to the compression regime, and in the second, to the full participation regime.
Corollary 1 (No compression). If we do not use compression (i.e., w 0), then the communica- tion and iteration complexities are #comms =0 (v (me log ! #iiters O /Lس log t)=
respectively. However, if we use the estimator (11) in Theorem 5 directly, then the communication
and iteration complexities are #comms = O (v log log!) #iters = O (ir) log t)) where
L(r)
L(r) r(m-1) Tomax ma(7-1) L. 7(m-1)
Notice that Imax 2 L, and that I(T) Limax for r = and L(T) = L for T = m.. Moreover, L(T) decreases as the minibatch size increases.
Corollary 2 (No client sampling). If we do not use client sampling (i.e., m)) then the com- munication and iteration complexities are #comms = O (V Liax (1+ M log :) #iters =
O
Lmaax P
(1
37 ! respectively.
(z) = x, then w O, and we restore the well-known LSVRG method [Hof- mann al., 2015, Kovalev al., 2020b], assuming that the functions Φ.j have the same smoothness constant. We can recover the same rate exactly as well, but with a slightly more refined analysis, one in which we do not need to work with compressors (LSVRG does not involve any), which makes for a tighter analysis. If 7 m, we restore the rate of the well-known DIANA [Mishchenko et al., 2019, Horváth et al., 2019h) method and its sibling Rand-DIAND [Shulgin and Richtárik, 2021].
Assume rxx) O. If (x)
5 Experiments
To illustrate the predictive power of our theory, it suffices to consider Te-rrgglariieee logistic regression in the distributed setting (1), with
A n4 Σ log (1 + exp (-bijatjz)) |==1/,
de(x))
where n, is the number of data points per worker aij ddd and by E {-1,+1} are the data samples and labels. We choose
m = n/as for all i. We set the regularization parameter A= 5- 10 L by default, where is the smoothness constant of f. We conduct several experiments on the w8a dataset from LibSVM library [Chang and Lin, 2011]. In Figure 2 (first row), we compare various LTT baselines* for three choices of mini-batch sizes (7 = 16, 32, 64) with our method ProxSkip-VR combined with the LSVRG estimator, which is special case of the HUB estimator when

---

194
19
27"
2103
-00
Conmuniontar
133 1337
2013
2213
X013
Communicntoo
1337 1037 2013
3007
(a) 16
(b) 32
(C) 64
20:
Compputsiion con percancle
Compusiioon con prrcle
Compusatoon cott per comple
Figure 2: The top row shows the convergence results compared with baselines and the second row is the total cost ratio of ProxSkip over our ProxSkip-VR.
(x) for all i.j. We see that our method outperforms all other methods significantly due its communication-zccleriiio properties.
Next, derive the total cost, which includes communication cost (assumed to be 1, for normalization purposes), and computational cost (assumed to be 8; and equal to the cost of performing one SGD step with single data point). Let consider the total cost of ProxSkip- VR in the case of the LSVRG estimator: in each iteration we compute stochastic gradient, and with probability we compute the exact gradient. We do not need to compute second stochastic gradient since and the relation 3/++1 = Tt. The total cost for ProxSkip-VR. is equal to
memory
Cost(ProxSkip- VR) Tomm.. (ProxSkip-Ve) VR) + 5 (qm + (1 q)r + r) Titer (ProxSkip-VPP ProxSkip requires full/exact gradient computation each iteration, the total cost of ProxSkip is
(Pro(Sk)) == -coomm (ProxSkip) + SnmTner(PoooSSKi
Using Theorems 6 and and the value L(r) == r(m-1) Lmax + m(r-1)
r(m-1) L of the expected smoothness
constant for sampling with minibatch size uniformly at random, we get the following expression for the cost ratio, expressed as a function of 8:
Cost(ProxSkipp Cost(ProxSkip
V mLS
Cost rātio(5)
(15)
VuL(T) + (2mp (2L(T) 2
We can easily calculate the limits of this expression:
mL
Cost ratio(ō 0) -V T(7)'
Cost ratio(ō + 00) 2(mp (I(T) -1))))))77) T)
In Figure (second row), we depict the theoretical cost ratio according to (15) and the corresponding experimental cost ratio obtained by an actual run of both methods to achieve e-accuracy, with e 10-6 and ε 10- Remarkably, the experimental results follows the same pattern as our theoretical prediction. The empirical curves appear lower because we use approximations for Lmaxx and μ. As we can see, starting from 10-4 ProxSkip-VFF starts to outperform ProxSkip. As grows, the advantage of variance reduction embedded in ProxSkip-V VR over vanilla ProxSkip grows. These results suggest that variance reduction of practical utility terms of the total cost, even for small values of 6, and its effectiveness grows with 8.
Acknowledgements
We would like thank Eduard Gorbunov for useful discussions related some aspects of the theory.
With the exception of LocalSGD, all use client drift comection.
10

---

References
D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication-cfficienn SGD via gradient quantization and encoding. Advances in Neural Information Processing Systems, pages 1709-1722 1720, 2017.
A. Beck. First order methods in optimization. MOS- NOS-SIAM Series on Optimization, 2017.
K. Bonawitz, Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. Practical secure aggregation for privacy-presersy machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1175- 1191, 2017.
C.-.. Chang and C.-J Lin. LibSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):27, 2011.
Z. Charles, Z. Garrett, Z. Huo, S. Shmulyian, and V. Smith. On large-cohort training for federated learning, arXiv preprint arXiv:2106.07822 2021.
W. Chen, S. Horváth, and P. Richtárik. Optimal client sampling for federated learning. Privacy Preserving Machine Learning (NeurIPS 2020 Workshop), 2020.
Y. J. Cho, J. Wang, and G. Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. arXiv preprint arXiv:2010.01243, 2020.
D. Csiba and P. Richtárik. Importance sampling for minibatches. Journal of Machine Learning Research, 19(27)11-111 2018.
A. Defazio, F. Bach, and S. Lacoste-Julien. SAGA: fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems 27, 2014.
H. Eichner, T. Koren, H. B. McMahan, N. Srebro, and K. Talwar. Semi-cyclic stochastic gradient descent. In International Conference on Machine Learning, 2019.
M. R. Glasgow, H. Yuan, and T. Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. In International Conference Artificial Intelligence and Statistics, pages 9050-9090. PMLR, 2022.
E. Gorbunov, F. Hanzely, and P. Richtárik. Local SGD: unified theory and new efficient methods. In NeurIPS, 2020a.
E. Gorbunov, F. Hanzely, and P. Richtárik, unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics, pages 680-690. PMLR, 2020b.
E. Gorbunov, D. Kovalev, D. Makarenko, and Richtárik. Linearly converging error compensated SGD. Advances in Neural Information Processing Systems, 33:20889 -0908, 2020c.
R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtárik. SGD: General analysis and improved rates. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2200-5209, Long Beach, California, USA, 09-15 Jun 2019a. PMLR. URL /ttp::/prost http://proceedings mlr press/v97/ http//99//////ngg///// qian19b. html.
R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and Richtárik. Sgd: General analysis and improved rates. In International Conference on Machine Learning, pages 5200-5209, PMLR, 2019h
Haddadpour and Mahdavi. On the convergence of local descent methods infederated learning. arXiv preprint 191011410 2019.

---

T. Hofmann, A. Lucchi, S. Lacoste-Julien, and B. McWilliams. Variance reduced stochastic gradient descent with neighbors. Advances in Neural Information Processing Systems, 28, 2015.
S. Horváth and P. Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. In Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 2781- 2789, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http::ttpppeeee httt::/pproceedingg mml.. press/ Bataassv9///hrrrrr http//oovaattta...a html.
S. Horváth, C.-Y. Ho, L'udovít Horváth, A. N. Sahu, M. Canini, and P. Richtárik. Natural compression for distributed deep learning. arXiv preprint arXiv: 1905. 10988, 2019a.
S. Horváth, D. Kovalev, K. Mishchenko, S. Stich, and P. Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:190.005115, 2019b.
R. Johnson and Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems 26, pages 315-323, 2013.
P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. D'Oliveira, H. Eichner, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Özgür, R. Pagh, M. Raykova, H. Qi, D. Ramage, R. Raskar, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang, F. X. Yu, H. Yu, and S. Zhao. Advances and open problems in federated learning. Foundations and Trends@in Machine Learning. 14(1-2)11-210, 2019.
S. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. Suresh. SCAFFOLD: Stochastic controlled averaging for on-device federated learning. In ICML, 2020,
A. Khaled and P. Richtárik. Better theory for SGD in the nonconvex world. arXiv Preprint urXiv:2002.03329 2020.
A. Khaled, K. Mishchenko, and P. Richtárík. First analysis of local GD on heterogencous data. In NeurIPS Workshop on Federated Learning for Data Privacy and Confidentiality, pages 1-11, 2019.
A. Khaled, K. Mishchenko, and P. Richtárik. Tighter theory for local SGD on identical and het- erogeneous data, In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.
S. Khirirat, H. R. Feyzmahdavian, and M. Johansson. Distributed learning with compressed gradients. arXiv preprint arXiv:1806.06:3 2018.
J. Konečny, H. B. McMahan, D. Ramage, and P. Richtárik. Federated optimization: distributed machine learning for on-device intelligence. arXiv:1610.025277 2016a.
J. Konečný, H. B. McMahan, F. Yu, Richtárik, A. T. Suresh, and D. Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016b.
D. Kovalev, S. Horváth, and P. Richtárik. Don't jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, 2020a.
D. Kovalev, S. Horváth, and P. Richtárik. Don't jump through hoops and remove those loops: Svrg and katyusha are better without the outer loop. In Algorithmic Learning Theory, pages 451-467. PMLR, 2020b.
12

---

M. Li, T. Zhang. Y. Chen, and A. J. Smola. Efficient mini-batch training for stochastic optimization. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, pages 661-670, New York, NY, USA, 2014, ACM. ISBN 978-1- 4503-2956-9, doi: 10.1145/26223330222226000 URL http://///doi acm. org/ 10 10..111222121..3. 2623612.
T. Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated learning: challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60) 2020a. doi: 10. 10.1100 109.///..2. 2975749.
X. Li, W. Yang, S. Wang, and Z. Zhang. Communicationn-fficccnnn local decentralized SGD methods. arXiv preprint arXiv: wrXiv:1910.09126 2019.
X. Li, K. Huang, W. Yang, S. Wang, and 7. Zhang. On the conver-gence of FedAvg non-IID data. In International Conference on Learning Representations, 2020b.
G. Malinovsky, D. Kovalev, E. Gasanov, L. Condat, and P. Richtárik. From local SGD to local fixed point methods for federated learning. In International Conference on Machine Learning, 2020.
B. McMahan and D. Ramage. Federated learning: Collaborative machine learning without centralized training data. GoogleAIBlog, Apr. 2017.
H. B. McMahan, E. Moore, D. Ramage, Hampson, and B. Agüera Arcas. Communication- efficient learning of deep networks from decentralized data. In Proceedings of the 20th Interna- tional Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
K. Mishchenko, H. Gorbunov, M. Takáč, and P. Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.0922 2019.
K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtárik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! In 39th International Conference on Machine Learning (ICML 2022), 2022.
A. Mitra, Jaafar, G. Pappas, and H. Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. In Advances in Neural Information Processing Systems 34, 2021.
P. Moritz, R. Nishihara, I. Stoica, and M. I. Jordan. SparkNet: International Conference on Learning Representations (ICLR), 2016.
Training deep networks in Spark. In
Y. Nesterov, Introductory lectures on convex optimization: a basic course (Applied Optimization). Kluwer Academic Publishers, 2004.
Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical Programming, 140(1):125-161, 2013.
C. Philippenko and A. Dieuleveut. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006. 14591, 2020.
D. Povey, X. Zhang, and S. Khudanpur. Parallel training of DNNs with natural gradient and parameter averaging. In ICLR Workshop, 2015.
E. Shulgin and P. Richtárik. Shifted compression framework: Generalizations and improvements. In OPT2021: 13th Annual Workshop Optimization for Machine Learning, 2021.
M. Takáč, Bijral, P. Richtárik, and Srebro. Mini-batch primal and dual methods for SVMs, In 30th International Conference Machine Learning, pages 537-552, 2013.
13

---

J. Wang, Z. Charles, Z. Xu, G. Joshi, H. B. McMahan, B. A. y Arcas, M. Al-Shedivat, G. Andrew, S. Avestimehr, K. Daly, D. Data, S. Diggavi, H. Eichner, A. Gadhikar, Z. Garrett, A. M. Girgis, F. Hanzely, A. Hard, C. He, S. Horvath, Z. Huo, A. Ingerman, M. Jaggi, T. Javidi, P. Kairouz, S. Kale, S. P. Karimireddy, J. Konecny. S. Koyejo, T. Li, L. Liu, M. Mohri, H. Qi. S. J. Reddi, P. Richtarik, K. Singhal, V. Smith, M. Soltanolkotabi, W. Song, A. Suresh, S. U. Stich, A. Tal- walkar, H. Wang, B. worth, S. Wu, F. X. Yu, H. Yuan, M. Zaheer, M. Zhang, T. Zhang, C. Zheng, C. Zhu, and W. Zhu. A field guide to federated optimization. arXiv preprint arXiv:2107.06917, 2021.
B. Woodworth, K. K. Patel, and N. Srebro. Minibatch vs local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33:6281 33x628166992, 2020.
H. Yu, R. Jin, and S. Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In International Conference on Machine Learning (ICML), 2019.
14


Reviews:
[{"review_id": "x1rdpL4zwYg", "reviewer": "Reviewer_RRdw", "summary": "The paper proposes a new variance reduced variant to ProxSkip, called ProxSkip-VR, for federated learning. It possesses a combination of preferable techniques in federated learning including data sampling, client sampling and local training. The variance reduced estimator is general and covers numerous existing estimators. Linear convergence is proved for the strongly convex objective. More importantly, the paper take a closer look on the cost of training FL methods by incorporating local training cost and communication cost whereas most existing FL methods only consider communication cost in convergence results. Numerical experiments on regularized logistic regression is presented to illustrate the performance of ProxSkip-VR compared to existing methods.", "questions": "- ProxSkip-VR assumes that the stochastic gradient $g_t$ is unbiased. Can the theory be generalized to biased estimators to cover this type of gradient estimators?\n- Does the proof of ProxSkip-VR in Appendix C hold for any choice of $y_t$ or it has to be a certain choice so that $g_t$ satisfies Assumption  4?", "limitations": "With the definition of $r$ in (4), I think assumption 3 is not needed.\nI hope to see more discussion on how to select $y_t$ in the main text.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well-written. I can see the history of FL methods evolving over different generations.\n- ProxSkip-VR possesses several important properties for an FL method: client sampling, data sampling, and variance reduced local update step.\n- The paper proposes a new architecture for FL which contains hubs between server and workers. This architecture is reasonable and it represents many real-world applications.\n- Convergence results are provided which cover different type of gradient estimators.\n- The evaluation considers the total cost which consists of communication cost and local training cost which has not been considered in existing works. This also help show the advantage of using variance reduced estimator in local training.\n\nCocerns:\n- Table 1 summarizes results of ProxSkip-VR w.r.t. existing works. It shows that communication complexity of ProxSkip-VR is better than GD but it does not explicitly discuss how it is better and the reader needs to go back and check the other paper to learn about this comparison.\n- I do not see how the control vector $y_t$ is chosen in the proof of ProxSkip-VR (Theorem 5). I wonder if $y_t$ is chosen the same as in (11).\n\nMinor comments:\n- The experiments has a non-zero value for the penalty parameter $\\lambda$ for $\\{x\\}^2$ regularizer but the code appears to set it to 0. I am not sure if the code precisely reflect the setting of the experiments described in the paper.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bqRBhmVCBqq", "reviewer": "Reviewer_2cyy", "summary": "This work theoretically studies the heterogeneous cross-silo federated optimization problem. Previously,  Mishchenko et al. [2022] had shown that SCAFFOLD with randomized number of local steps (which they call Prox-Skip / ScaffNew) enjoyed an accelerated communication complexity, proving improvement due to local steps. \n\nThis paper extends their framework to employ variance reduction and compressed communication at the client level, while maintaining the accelerated communication complexity. They also propose an hierarchical federated model where clients are attached to always-available hubs for which their algorithms are particularly well suited.", "questions": "# Suggestions for improvement\n\n1. Section 4 is way too terse and hard to comprehend. The setting of the hub model and the algorithm description should be separated (perhaps with pseudo-code). I had to work hard to reconstruct what was being conveyed. E.g. of confusions: why is the global gradient a concatenation of estimators in eq (12)? control vector y_t is used before it is defined (in fact it is never properly defined or initialized) etc.\n2. It is also unclear how Theorem 9 relates to Theorem 5?  Why can we not use VR and CC directly in Section 3 with Thm. 5? Thms 6 and 8 are definitely direct corollaries of Thm 5 and it would be clearer if stated as such.\n3. More time should be spent explaining the results in Corollaries 1 and 2 - what is $\\omega$ and how should we think about it? why does it scale as $\\omega / M$ and is the optimal scaling? The latter relies on the independence of the compression randomness, which is not stated. Overall, I think the paper would greatly benefit from moving some of the exposition in Section 2 to the Appendix and instead expanding on the results in Sections 3 and 4, with greater discussion about the implications of the theoretical rates.\n3. The result for the setting with C > 0 is not optimal since there is no speed-up wrt to number of clients. The optimal rate likely scales as C/M (as SCAFFOLD obtains).\n4. Also, while client and data sampling are discussed in detail in Sec 1.2, their effect on ProxSkip-VR is never discussed.\n5. It should be made clear that all the discussion in the paper is for cross-silo FL and does not apply to cross-device FL.\n6. Nitpick (feel free to ignore): the colors used in the text (e.g. in math symbols like W and E in Thm 5, and algorithm names) made it visually busy, confusing and harder to read for me. I would suggest using such colors sparsely in text - more as a shorthand (e.g. red is always error terms) rather than for emphasis or drawing attention. ", "limitations": "The limitations of the method are not adequately discussed. The questions section above goes into detail.\n\nNote: I am willing to raise my score on an assurance from the authors that the writing and presentation will be improved. The results are otherwise technically sound and interesting.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n1. The approach is well motivated and forms a natural line of inquiry - combining communication compression + variance reduction with ProxSkip. \n2. The results obtained by the authors, though not surprising in the light of ProxSkip, are significant and technically involved. It is a result of synthesizing several state of the art analysis techniques, and recover most of them as state of the art.\n3. I also enjoyed the motivation of the local variance reduction via the hub model and can see it being useful.\n\n# Weaknesses\n\nMost of the weaknesses stem from poor writing (see questions section for detailed feedback) - i) section 4 is very terse and not elaborated well , and ii) the limitations of the method and comparison with prior work is not well carried out.\nThe most impactful aspect of this paper might be the new hierarchical FL model proposed. But unfortunately, there is almost no discussion on its unique aspects, optimality etc.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JoysD2aCTJC", "reviewer": "Reviewer_VKkX", "summary": "This paper investigates applications of the variance-reduced technique in Federated Learning and proposed a new algorithm based on **ProxSkip** in [Mishchenko et al. 2022]. The method constructed by the authors can be substantially faster in terms of the *total training time* than ProxSkip in theory and practice in the regime when local computation is sufficiently expensive. The authors also corroborate their theoretical results through experiments.", "questions": "1. Table 1 says the communication complexity of **FedLin** is worse than GD. But the communication complexity of FedLin is also reduced by a factor of $H$ compared with GD, where $H$ is the number of local updates (see the discussion below Eq. (9) of [Mitra et al., 2021]). Therefore, the communication complexity of FedLin can also attain $O(\\sqrt{L/\\mu}\\log(1/\\epsilon))$ by setting $H = \\sqrt{L/\\mu}$.\n\n2. In [Mitra et al., 2021], the authors show that FedLin converges much faster than SCAFFOLD in experiments of the linear model. However, the performance of FedLin in Section 5 is worse than SCAFFOLD and Local SGD, which is unreasonable since FedLin has a *linear convergence rate*. And I don't think the difference between logistic regression and linear regression is the reason. So I doubt the results in Section 5, could you explain the reason?", "limitations": "This paper identifies 5 distinct generations of LT methods and classifies ProxSkip and ProxSkip-VR in Generation 5: Accelerated Age, but I don't think the full-gradient and variance-reduced methods are practical and popular in FL. Considering large-scale machine learning models, stochastic gradient descent (and its variants) with the *constant batch size* is a prevalent training scheme. So the summarization in this paper may be less appropriate.\n\nConsidering existing works [Mitra et al., 2021] and [Mishchenko et al. 2022], the contribution and novelty are limited. More importantly, the experiment results are not convincing.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The proposed method **ProxSkip-VR** enjoys a lower communication complexity than gradient descent.\n\n2. This paper proposed a new FL architecture, where ProxSkip-VR can be substantially faster in terms of the *total training time* than ProxSkip.\n\n3. The authors corroborate their theoretical results with carefully engineered proof-of-concept experiments.\n\n**Weaknesses**\n\n1. The algorithm can be impractical since we can not control the communication timestamp.\n\n2.  Attributing to combine L-SVRG [Hofmann et al., 2015, Kovalev et al., 2020a] and DIANA [Mishchenko et al., 2019] techniques, the improvement over ProxSkip is natural. Hence the novelty is limitted.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept