FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
Authors: Haoyu Zhao
Zhize Li
Peter Richtárik
Venue: ICLR 2022 Submitted (2022)
Keywords: federated learning
nonconvex optimization
convex optimization
local gradient method

Abstract: Federated Averaging (FedAvg, also known as Local-SGD) (McMahan et al., 2017) is a classical federated learning algorithm in which clients run multiple local SGD steps before communicating their update to an orchestrating server. We propose a new federated learning algorithm, FedPAGE, able to further reduce the communication complexity by utilizing the recent optimal PAGE method (Li et al., 2021) instead of plain SGD in FedAvg. We show that FedPAGE uses much fewer communication rounds than previous local methods for both federated convex and nonconvex optimization. Concretely, 1) in the convex setting, the number of communication rounds of FedPAGE is $O(\frac{N^{3/4}}{S\epsilon})$, improving the best-known result $O(\frac{N}{S\epsilon})$ of SCAFFOLD (Karimireddy et al.,2020) by a factor of $N^{1/4}$, where $N$ is the total number of clients (usually is very large in federated learning), $S$ is the sampled subset of clients in each communication round, and $\epsilon$ is the target error; 2) in the nonconvex setting, the number of communication rounds of FedPAGE is $O(\frac{\sqrt{N}+S}{S\epsilon^2})$, improving the best-known result $O(\frac{N^{2/3}}{S^{2/3}\epsilon^2})$ of SCAFFOLD (Karimireddy et al.,2020) by a factor of $N^{1/6}S^{1/3}$, if the sampled clients $S\leq \sqrt{N}$. Note that in both settings, the communication cost for each round is the same for both FedPAGE and SCAFFOLD. As a result, FedPAGE achieves new state-of-the-art results in terms of communication complexity for both federated convex and nonconvex optimization.

Under review conference paper at ICLR 2022
FedPAGE: A FAST LOCAL STOCHASTIC GRADIENT METHOD FOR COMMUNICATION--EFFICEENN FEDER- ATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Federated Averaging (FedAvg, also known Local-SGD) (McMahan et al. 2017 is a classical federated learning algorithm in which clients run multiple local SGD steps before communicating their update to an orchestrating server. We propose a new federated learning algorithm, FedPAGE, able to further reduce the communication complexity by utilizing the recent optimal PAGE method (Li et al.) 202T). We show that FedPAGE uses much fewer communication rounds than previous local methods for both federated convex and nonconvex optimization. Concretely, 1) in the convex setting, the number of communication rounds of
FedPAGE is O Na/4
improving the best-known result O St) of SCAFFOLD (Karimiredyy et al. 2020) by factor of N1/4, where N is the total number of
Sic
clients (usually is very large in federated learning), is the sampled subset
clients in each communication round, and é is the target error; 2) in the nonconvex
setting, the number of communication rounds of FedPAGE O (N+5)) improving
the best-known result O N2/3 53/3,2) ) of SCAFFOLD (Karimireddy al. 2020) by factor of / 51/3 if the sampled clients 5 S /N. Note that in both settings, the communication cost for each round the same for both FedPAGE and SCAFFOLD. As a result, FedPAGE achieves new theoretical state-of-the- results in terms of communication complexity for both federated convex and nonconvex optimization.
INTRODUCTION
With the rise in the proliferation of mobile and edge devices, and their ever-increasing ability to capture, store and process data, federated learning (Konečný et al. 2016b; McMahan et al. 2017] Kairouz et al. 2019) has recently emerged as a new machine paradigm for training machine learning models over vast amount of geographically distributed and heterogeneous devices. Federated learning aims to augment the traditional centralized datacenter focused approach to training machine learning models (Dean al., 2012 landola al.) 2016)) Goyal et al. 2017) with new decentralized modality that aims to be more energy effiiienfiiient, and mainly, more privacy crvvacyconscious with respect to the private data stored on these devices. federated learning, the data stored over a large number of clients, for example, phones, hospitals, or corporations (Konečný et al. [01 b McMahan et al.) 2017 Mohri et al., 2019). Orchestrated by centralized trusted entity, these diverse data and compute resources come together to train a single global model to be deployed on all devices. This is done without the sensitive and private data ever leaving the devices.
One of the key challenges in federated learning comes from the fact that communication over heterogeneous network is extremely slow, which leads to significant slowdowns in training time. While centralized model may train in matter of hours days, comparable federated learning model may require days or weeks for the same task. For this reason, it is imperative that the design of federated learning algorithms designs communication-effin -effiiiinneffiettttt learning protocols capable of producing a good model.
focuses special attention the communication bottleneck, and
There two popular lines of work for tackling this communication-effici federated learning problem. The first makes use of general and also bespoke lossy compression operators to compress the communicated messages (such as local stochastic gradients) before they sent over the net-

---

Under review as a conference paper at ICLR 2022
work (Mishchenko et al. 2019 Li and Richtárik] 2020 Li al. 2020
Gorbunov et al. 2021
and Richtárik 202 and the second line bets on increasing the local workload by performing multiple local update steps, e.g., multiple SGD steps, before communicating with the orchestrating
server (Stich 2020 Woodworth al. 2020 Gorbunov et al. 2020 Karimireddy al. 2020).
In this paper, we focus on the latter approach (multiple local update steps in each round) to alleviating the communication bottleneck in federated learning. One of the earliest and classical methods
proposed in this context is FedAvg/local-Se BGD (McMahan et al. [2017: Sahu et al.
2018 Yu et al.
2019: Li et al. 2019 Haddadpour and Mahdavi 2019; Stich 2020 Gorbunov et al.
2020 However,
the method has remained a heuristic until recently, even in its simplest form as local gradient descent, particularly in the important heterogeneous data regime (Khaled et al. 2020: Woodworth al., 2020). Further improvements on vanilla Local-SGD have been proposed, leading to methods such as Local--VRG (Gorbunov et al. 2020) and SCAFFOLD (Karimireddy et al., 2022).. In particular, Gorbunov et al. (2020) also provide unified framework for the analysis of many local methods in the strongly convex and convex settings.
1.1 OUR CONTRIBUTIONS
Although there are many works on local gradient- type methods, the communication complexity in existing works on local methods is still far from optimal. In this paper, we introduce novel local method FedPAGE, significantly improving the best-known results for both federated convex and nonconvex settings (see Table I Now, summarize main contributions follows:
1.
We develop and analyze. FedPAGE, a fast local method for communication-effiiii fed- erated learning. FedPAGE can be loosely seen as a local/federated version of the PAGE algorithm of al. (202T), which is a recently proposed optimal optimization method for solving smooth nonconvex problems. Our analysis of FedPAGE also recovers the optimal results of PAGE (see Theorem []. thus FedPAGE substantially improves the best-known non-optimal result of SCAFFOLD (Karimireddy et al. 2020) by a factor of // (see Table for more details).
2. For the convex setting, we provide the convergence results for FedPAGE in Theorem Moreover, FedPAGE also improves the best-known result of SCAFFOLD (Karimireddy et al. 2020 by a large factor of 11/4 (see Table 1b.
3. Finally, we first conduct the numerical experiments for showing the effectiveness of multiple local update steps (see Section 6.1p. The experiments indeed demonstrate that FedPAGE with multiple local steps K 2 is better than that with K = 1 (no multiple local updates). Then we also conduct experiments for comparing the performance of different local methods such as FedAvg (McMahan et al.) (0177). SCAFFOLD (Karimireddy et al.) 20200 and our FedPAGE (see Section (..2). The experiments show that FedPAGE always converges much faster than FedAvg, and at least as fast as SCAFFOLD (usually much better than SCAFFOLD), confirming the practical superiority of FedPAGE.
1.2 RELATED WORKS
Optimization algorithms for federated learning have a close relationship with the algorithms designed for standard finite-sum problem min. 1 - (ar). In the federated learning setting, we can think of the loss function of the data on a single client as function fú, and the optimization problem becomes finite-sum problem. The SGD is perhaps the most famous algorithm for solving the finite-sum problem, and in one variant or another, it is widely applied in training deep neural networks. However, the convergence rates of plain SGD in the convex and nonconvex settings are not optimal. This motivated a feverish research activity in the optimization and machine learning communities over the last decade, and these efforts led to theoretically and practically improved variants of SGD, such as SVRG, SAGA, SARAH, SPIDER, and PAGE (Johnson and Zhang 2013 Defazio et al. 2014 14
Nguyen et al.] 2017: Fang et al. 2018 8 Li et al., 2021) and many of their variants possibly with auceleration/mommnntts
(Allen- 1hlln--2hul
2017 Lan and Zhou 2018 Lei et al. 2017 Li and Li
2018
Zhou et al.) 2018 Wang et al. 2018 Kovalev et al. 2020 Ge et al. 2019
2019
Lan et al.
2019
Li and Li 2020 Li 2021a).
2

---

Under review conference paper at ICLR 2022
Table I: Number of communication rounds for finding an e-solution of federated convex and non- convex problems 1 where [x) - f S for convex setting and V I for nonconvex setting. In the last column, (G. BBBGD means that Σ ( < G2 B f(z) ()- BGD means B = 0, and (0, B- means G = 0. BV denotes the "Bounded Variance" assumption, i.e., ( and Smooth stands for standard smoothness assumption, e.g., Assumption [
Other notations
(i.e., N, S, M, K) are summarized in Table 2
Algorithm
Convex setting
Nonconvex setting
Assumption
FedAvg
NK
Smooth, BV,
Yu al. 2019
NKet
(G.0)-Bo -GG
FedAvg
G²
G
B
G²
B2
Smooth, BV.
Karimireddy et al.
2020
SK22
Set
SK
(G, BGB
FedPrrox
B²
Smooth, S N,
(Sahu et al. 2018
B)-BD)
VRL-SCD
+ No²
Smooth, BV,
Liang ct al. 2019)
$ == N
S-Local-SV/RC
M/ /1/3. /MNK33
Smooth, (BV), $= N, K S M
Gorbunov 2020)
Karimireddy et al.
SCAFFOLD
2020)
Se
+
SK.3
o²
$2/3
N2/3
+
o²2 SKct
Smooth, BV
FedPAGE (this paper)
Na/4
N1/2 Sea
Smooth, (BV)
Sc
However, the above well-studied finite-sum problem is not equivalent the federated learning problem ④ as one needs to account for the communication, which forms the main bottleneck. As we discussed before, there are last two sets of ideas for solving this problem: communication compression, and local computation. There are lots of works belonging to these two categories. In particular, for the first category, the current state-of-the-art results strongly convex, convex, and nonconvex settings are given by [.i et al. (2020); [i and Richtárik (2021a) Gorbunov et al. (202T). respectively. For the second category, local methods such as FedAvg (McMahan et al. 2017) and SCAFFOLD (Karimireddy et al. 2020) perform multiple local update steps each communication round in the hope that these are useful to decrease the number communication rounds needed to train the model. In this paper, provide new state-of-the-art results of local methods for both federated convex and nonconvex settings, which significantly improves the previous best- results of SCAFFOLD (Karimireddy et al. 2020) (See Table T))
SETUP AND NOTATION
We formalize the problem as minimizing finite-sum sum functions:
{ f(x) f(x)==
NV Σ fo f((()) -
min ZERd
where fa(x) 1 Em f(z(z).
(1)
In this formulation, each function f((-) stands for the loss function with respect to the data stored on client/device/maccinee i, and each function ft, stands for the loss function with respect to the j-th data client i. Besides, we assume that the minimum of exists, and we use f and x to denote the minimum of function I and the optimal point respectively.
We point out that S-Local-SVRG Goorbnnov et al. 2020) only considered the case where S = N and K < M,, i.e., the sampled clients S always is the whole set of clients N for all communication rounds. As result, the total communication complexity (i.e., number of rounds communicated clients S in each round)
of S-Local-SVRR -oocal-SRGGia is O(NN21/3 /Kt///////// + /NM/K" /2)))) (note that here K < M), which is worse than
O(N/e) of SCAFFOLD Karimireddy et al. 2020) and O(N3//4 /e) of our FedPAGE.
"In convex setting, we state the result FedPAGE presentation, where N is the total number of clients and S is the number of sampled subset clients in each communication round (see Table 2.. Please see Theorem for other results of FedPAGE in the cases
case S VN (typical in practice) for simple
vN. FedPAGE also works under the BV assumption by using moderate minibatches for local clients, and more importantly the number of communication rounds of FedPAGE still remains the same in the last row of Table for hoth convex (sec Theorem and nonconvex (see Theorem settings.
3

---

Under review conference paper at ICLR 2022
Table Summary of notation used in this paper
N, i
total number, sampled number, and index of clients total number of data in each client
M
R
total number and index of communication rounds total number and index of local update steps model parameters before round r
K,
x²
g
server update within round
V.A
i-th client's model in round r before local step i-th client's update in round within local step kt estimator of V ((xz) using sampled minibatch I Vzf(x)== = 1/ ČEEz (t,
G
Vzf((z)
We will [ni] to denote the 21, n., || to denote the Euclidean norm for vector, and (u, v) to denote the inner product of and v. We use O-)) and (2(-) to hide the absolute constants.
In this paper, we consider two cases: nonconvex case and convex case. In the nonconvex case, each individual function fi and the average function f can be nonconvex, and we assume that the functions (EsghNeM))JE((A]] are L-smooth.
Assumption (L-smoothness), All functions fú, Rd + for all [N].j E [M] are L-smooth. That is, there exists L 2 0 such that for all æ1, E Rd and all i [M],j E [M].
[iis(<)) - (x2( < L 2 =22ll-
the functions (fa MeatheeNeeee are L-smooth, we can conclude that functions {fi} are also L- smooth and function ff is L-smooth. In this nonconvex setting, the optimization algorithm aims to find a point such that the expectation of the gradient norm is small enough: f(>)l( S c.
Then, in the convex case, each individual function can be nonconvex, but require that the average function if to be convex. We also assume that the functions {frr} are L-smooth (Assumption [T] Under this convex setting, the algorithm will find point such that the expectation of the function value is close to the minimum: E.f(x) - S <.
If the number of data single client is very large and one cannot compute the local full gradients of clients, one needs the following assumption in which the gradient variance on each client is bounded.
Assumption 2 (Bounded Variance). There exists o 2 0 such that for any client i E [N] and x E IR.
M
(/) ( 50
M
THE FedPAGE ALGORITHM
In this section, we introduce our FedPAGE algorithm. To some extent, our FedPAGE algorithm is the local version of PAGE (Li et al, 2021): when the clients communicate with the server, FedPAGE behaves similar PAGE, and when the clients update the model locally, each client updates several steps. If we set the number of local updates to one, FedPAGE reduces to the original PAGE algorithm.
Our FedPAGE algorithm is given in Algorithm [ There are two cases in each round r: 1) with probability pr (typically very small), the server communicates with all clients in order to get more accurate gradient of function f (Line 9 2) with probability 1 Pr. the server communicates with subset of clients with size S and the local clients perform K local steps (Line 10 24).
For Case 1), the server broadcasts the current model parameters x" to all of the clients. Then, each client computes the estimator Vz, fa("") of the gradient fa(x²") and sends to the server. The estimator takes b minibatch samples ([Z, bb) to estimate the gradient of fr and different clients sample different sets I₁. Here, want Vz, fe(=") to be as closed to ff((=") possible, choosing a moderate size b, usually is enough. The server average all of the gradient and get the averaged gradient 9" = N ΣieNN) Vz, fx(x") and takes step with global step size fl (see Line 9 26
4

---

Under review conference paper at ICLR 2022
Algorithm 1 FedPAGE
server input: initial point æº, global step size Ig. probabilities (pr): sampled clients size S client i's input: local step size Mtt minibatch sizes b,, b2. by
do 1: for r = 0, Bernoull((p.)
2:
sample
3: if = then
4:
clients S IM. communicate x" all 5 on client E 5" in parallel do
5:
6:
uniformly sample minibatch Iι C [M] with size bj compute the gradient estimator g VI,,i(r)
7:
8:
end on client
9:
g" c CiENN g
else
11:
sample clients S" S [N] with size S, communicate ( x"-"" to all i S on client E S" in parallel do
12:
13:
Koo0 + x²
14:
uniformly sample minibatch I2 C [M] with size by H. VTzl(x=") Vi,li(x' + g"-1
16:
Vi,1 f- V. 19
for k 2.......
18:
uniformly sample minibatch Z3 C [M] with size by Gi, - VIgl((((..) Vz, Vi + Di,k-1
20:
Vi,k+1 t Vi n end for Ayf t x² Vi.
21:
23:
end on client
24:
g" +- KmS Exes Av!
25:
end if
x1+1 <=x" "99g"
27: end for
For Case 2), the server first broadcasts "="",="1____ "-==1 to the sampled subset clients S", and the clients initialize yro + <-.". Here, y i-th client's model round before local step k, and gf, denotes i-th client's gradient estimator for step & in round r. Then for the first local step of client the local gradient estimator is computed in L5
K.o VT,fi(x²) ((z"((="=))+
where Vz, f-() )) is the gradient estimator of V.((-) with minibatch size by. Here, we also want fz, f-() to be as closed to v-((-) as possible, similarly choosing moderate size b2 usually is enough. This update rule is similar to PAGE (Li et al. 2021) and in particular if the local steps K = 1. our FedPAGE algorithm reduces to PAGE.
For client i's local step i such that 1 < k 1, the gradient estimator is computed in Line 19 as + -
K. Fig
Here Ig a minibatch of functions with size by that we used to compute the gradient estimator ge,-- Different from the previous gradient estimators using minibatches with size by and b2, here we want by be small enough to reduce the computation cost as there are K local steps (Line 21. In particular, we can choose by = 1, i.c., just sample an index from [M] and the estimator becomes
g V Ji. V Si + -6
The local model update is given by vh V. no where yp is the local step size. After K local steps, client computes the local changes Ay = V xx within round r and sends back to the server. After receiving the local changes Ayj for the selected clients E S", the server computes the average gradient estimator these selected clients in Line 24 g" Kms Eies- Avi.
5

---

Under review conference paper at ICLR 2022
9 or 24p. the server updates the model using global step size f/g in Line 26 as x=+1 x" x== "1g9"
After obtaining the gradient estimator g" (in Line
The intuition of FedPAGE works as follow: when the local step size yi is not too large, we can expect that the local model updates are close to the original model, that is Vi R x", and the gradient is also close to each other, V Vi,
(as)(a"). Then each local gradient estimator gi, is close to Hh (V (V..) fi (Vi,,=))) -i
gi Pi 95,0
and the aggregated global gradient estimator g" is close to
g
Σ IEST
(Vf((z)
g"
This biased recursive gradient estimator g" is similar to the gradient estimator in SARAH (Nguyen al. 2017) PAGE (Li et al., (022), and thus the performance of FedPAGE in terms of communica-
tion rounds should be similar to the optimal convergence results of PAGE (Li et al. 2021
4 FedPAGE IN NONCONVEX SETTING
In this section, we provide the general result of our FedPAGE with any local steps K > 1 in the nonconvex setting, Here we assume that the functions {fi,} are L-smooth (Assumption and we obtain the following theorem.
Theorem (Convergence of FedPAGE in nonconvex setting). Under Assumption (and Assumption 2). if we choose the sampling probability Pr p N for every r 2 1 and pa 1, the minibatch
sizes bj min M,
24 Sez
J. b2 min M, 48o² pSzz and the global and local step sizes
V2p
ng
T S
3(1 p/3)
24 'AVSK'
1
2p8
then FedPAGE will find a point æ such that EE VV S within the following number of communication rounds:
R= L(VN+ +
Sea
Now compare the communication cost of FedPAGE (Theorem I with previous state sfate-of-the-ar SCAFFOLD (Karimireddy et al. 2020). The number of communication round for SCAFFOLD to
find a point æ such that V (xx) (the original SCAFFOLD (Karimireddy al. 2020) uses
V (z)) < é) is bounded by
RSCAFFOLD (1V/S)313 L12).
(3)
Beyond the number of communication rounds in FedPAGE and SCAFFOLD, we also need compare the communication cost during each round (i.e., number of clients communicated with the server in the round). For our FedPAGE, in each round, with probability p = S N the server communicates with all clients N, and with probability p, the server communicates with sampled subset clients with size S. and the communicated clients within each round is N x + (1 N x < 2S in expectation. For SCAFFOLD, in each round, the server communicates with S sampled clients. Thus the communication cost for each round is the same O(S) for both FedPAGE and SCAFFOLD. As result, to compare the communication complexity of FedPAGE and SCAFFOLD, it is equivalent to compare the number of communication rounds. According to (3) and Theorem ] (c.g., with sampled clients S < VN), then the communication rounds of FedPAGE is smaller than previous state-of-ther oh-tte-art SCAFFOLD by a factor of 11/3 Also note that the number of clients is usually very large in the federated learning problems.

---

Under review as a conference paper at ICLR 2022
5 FedPAGE IN CONVEX SETTING
In this section, we show the convergence results of FedPAGE in the convex setting. Here the algorithms aim find a point x such that (=(x)) - f I e for convex case instead of V I e for nonconvex case. In this part, we assume that f is convex and the functions (ft,} satisfy L-smoothness assumption (Assumption I
Theorem (Convergence of FedPAGE in convex setting). Under Assumption D and Assumption 2 we choose the sampling probability pr = p = & for every r 2 1 and po the minibatch sizes
bj mimmin M,
pS/2 }, b2 m 480" p3/2//e ), and the global and local step size
24
( (S+ ) )
S
fg =
=
T1S T(S + VVN)
No/4KTL
then FedPAGE satisfies
N3/4L
0
+
VN
SR
1 R Σ
NL/AL.
-
+
IfNN < SSSNNAL
R
NL
SR +
, <S
As discussed before, the expected communication cost of FedPAGE is the same SCAFFOLD in each communication round. Then if the sampled clients S S v N,, FedPAGE can find solution such that Ef(x) f(x)) < within O Na/4L number of communication rounds, improving the previous state-of-the-ar O N (S)) of SCAFFOLD Karimireddy et al. 2020) by large factor of 1/4
Se
Recall that N denotes the total number of clients.
6 NUMERICAL EXPERIMENTS
In this section, we present our numerical experiments. We conducted two experiments: the first shows the effectiveness of the local steps (Section (6.I). and the second compares FedPAGE with SCAFFOLD and FedAvg (Section 6.2]. Before we present the results of these two experiments, we first state the general experiment setups. The detailed experiment setups are deferred to the appendix.
Experiment setup We run experiments on two nonconvex problems used in e.g. (Wang et al. 2018 Li and Richtárik] 2021b): robust linear regression and logistic regression with nonconvex regularizer. The standard datasets a 9a (32,561 samples) and w8a (49,749 samples) are downloaded from LIBSVM (Chang and Lin 201T). The objective function for robust linear regression is
f(z) = - E(x a b;),
where E(t) = log(1 + 5. Here 6, E {+1} is a binary label.
The objective function for logistic regression with nonconvex regularizer is
f(x) = Σ log (1 exp(epp-bba a:)) + Σ x
1t
Here, the last term is the regularizer term and we set = 0.1.
Besides, different algorithms have different definitions of the local step size and global step size, thus we compare these algorithms with the 'effective step size" ij. Here for FedPAGE, the effective step size is just the global step size 7j = 77. and for SCAFFOLD and FedAvg, the effective step size is defined as 'n,, Th. We run experiments with 7j 0.1, 0.03, 0.01. If the effective step size is larger, the algorithms may diverge. Also note that although we compare these algorithms with the same effective step size, FedPAGE we select the total number of communication rounds such that the algorithms converge or we can distinguish their performance difference.
use larger step size from theoretical results. Finally
7

---

Under review conference paper at ICLR 2022
3250 Clanni
325 Clients
Clients
100
10"
PedPAGE-1
FodRAGE
Grediemt Norm
Greditmn Nom
10-
Groullare Norm 10-
10t
10-
2000 2000 4000 5000
Communcation Rounds
Communication Rounds
Cormuniiaaion Rounds
(a) a a9a.
10
Grollnt Norms
Grodknt Norm
FodPAGE
10-
Oepolcnt No
10-2
10-3
20-3
2000
8000
Communiction
Communicatin
(b) wB a.
Figure I: FedPAGE with different number of local steps on different datasets.
6.1 EFFECTIVENESS OF LOCAL STEPS
In this experiment we compare the convergence performance FedPAGE using different number of local update steps: K 1, 10, 20 (see Line 17 of Algorithm Tp. FedPAGE-1 means that the number of local step K = 1, which reduces to the original PAGE (Li et al. (021). and FedPAGE-10 and FedPAGE-20 represent FedPAGE with 10 and 20 local steps respectively.
The experimental results are presented in Figure ! Figure shows the robust linear regression results of FedPAGE using different number of local steps K 10, 20 a dataset, and Figure Tb shows the result on w8a dataset.
Local steps speed up the convergence rate The experimental results in Figure show that the multiple local steps of FedPAGE can speed up the convergence in terms of the communication rounds. Although there are some fluctuations when the number of communication round is not large (carly-stage), FedPAGE-10 and FedPAGE-20 outperform FedPAGE-1 1 in the end.
Algorithm with multiple local steps can choose a larger effective step size From our hyperpa- rameter optimization results, also find that FedPAGE with multiple local steps choose larger effective step size (7, in FedPAGE). On a9a dataset, when there are 3250 clients, the effective step size for FedPAGE-1, FedPAGE-10. and FedPAGE-20 are optimized to be 0.3, 0.4, 0.4 respectively; when there are 325 clients, the effective step size for FedPAGE-1, FedPAGE-10 10, and FedPAGE-20 are optimized be 0.2, 0.4, 0.5; when there are 10 clients, the effective step size for FedPAGE-1, FedPAGE-10, and FedPAGE-22 are optimized to be 0.3, 0.5, 0.6. The experiments on w dataset also support this finding.
6.2 COMPARISON WITH PREVIOUS METHODS
Now, we compare our FedPAGE with two other methods: SCAFFOLD (Kaimireedy et al., 2020) and FedAvg (McMahan et al. 2017). The experimental results are presented in Figure and the gradient norm versus the number of communication rounds. Figures 2a 2b and show the performance of each algorithm using different objective functions and different datasets.
We plot
Performance of different methods The experiments show that FedPAGE > SCAFFOLD > FedAvg. Among all the cases, under the same effective step size, we find that both FedPAGE and SCAFFOLD converge faster than FedAvg. FedPAGE converges at least as fast as SCAFFOLD, and in most of the cases FedPAGE converges faster than SCAFFOLD.
8

---

Under review conference paper at ICLR 2022
B 0.1
Effective LK 0.03
Effective LA 0.01
Feshng
SCAPFOLD
Gradent Nurm
It"
Cratt t Ntm
FoSPAGE
10
12
1000 2000 3000
4000
5000
1000
2000
3002
4000
5000
5000
30000
23000 20000
Robust linear regression on a dataset.
Eflective
Effective
10
Fedhug
Cradiurt Norm
Dna 1aanre Norm 10
10
10-
10"
10-
Commun
Rounds
Rounds
(b) Robust linear regression on w&a dataset.
Figure 2: Comparison of different methods with robust linear regression.
thecziee
Effective
Effectov 18
10-11
Coudeet Merre 10th 10- 10-11
SCAFFOLD
Coudeets harm
Groderr
10-11 10- 115 T 15"
Comman calin founds
Commun cadon hounds
Communicatoo on Rounds
(a) Logistic regression with nonconvex regularizer on a9a dataset.
10"
FesAng
SCAPFOLD
20""
Crudkeme aotddannt Noom
10 10-11
Credkee Wom
FosPAGE
Guddent
10-4
100
10-
1000 2000 3000 4000 5000
2000 4020
5000 0000 10000
5000
10000 25000 20000
Commun Caton Rounds
Casmunccaoo Rounds
Commuricat on Rounds
(b) Logistic regression with nonconvex regularizer on w8a dataset.
Figure 3: Comparison of different methods with logistic regression with nonconvex regularizer.
Larger effective step size converges faster The experiments also show that a larger effective step size leads to a faster convergence as long as the algorithm converges. Note that FedPAGE can use choose the same
larger step size with theoretical guarantee compared with SCAFFOLD, parameters of the objective function (c.g. the same smoothness constant) and use the step size with theoretical guarantees, FedPAGE converges faster than SCAFFOLD than FedAvg.
CONCLUSION
In this paper, we propose new federated learning algorithm, FedPAGE, providing much better state-of-the- communication complexity for both federated convex and nonconvex optimization. We also conduct several numerical experiments showing the effectiveness of multiple local update steps in FedPAGE and verifying the practical superiority of FedPAGE over other classical methods.

---

Under review conference paper at ICLR 2022
REFERENCES
Zeyuan Allen-Zhu. Katyusha: the first direct acceleration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1200- 1205. ACM, 2017.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM transactions intelligent systems and technology (TIST), 2(3):1-27, 2011.
Jeffrey Dean, Greg S Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V Le, Mark Z Mao, Mare Aurelio Ranzato, Andrew Senior, Paul Tucker, et al. Large scale distributed deep networks. 2012.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, pages 1646-1654, 2014.
Cong Fang, Chris Junchi Li. Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex op- timization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pages 2018 2018.
Rong Ge, Zhize Li, Weiyao Wang, and Xiang Wang. Stabilized SVRG: for nonconvex optimization. In Conference on Learning Theory, pages 1394-1448, 2019.
Simple variance reduction
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local SGD: Unified theory and new efficient methods. arXiv preprint 1.Xix:2011.022220 2020.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- convex distributed learning with compression. In International Conference on Machine Learning, pages 3788-3798. PMLR, arXiv:2102.07845, 2021.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training ImageNet in hour. arXiv preprint
2017.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint 1IXi:11900.14425 2019.
Forrest N landola, Matthew W Moskewicz. Khalid Ashraf, and Kurt Keutzer, Firecaffe: near-linear acceleration of deep neural network training on compute clusters. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2592-2600, 2016.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pages 315-323, 2013.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:/9/2.044: 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143 5143. PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. International Conference on Artificial Intelligence and Statistics, pages 4529, PMLR, 2020.
Jakub Konečný; H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv: 1610.022.1 2016a.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv: 161.000000 2016b.
10

---

Under review conference paper at ICLR 2022
Dmitry Kovalev, Samuel Horväth, and Peter 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, 2020.
Guanghui Lan and Yi Zhou. Random gradiieneextrapolation for distributed and stochastic optimization. SIAM Journal on Optimization, 28(4))2753-27882 2018
Guanghui Lan, Zhize Li, and Zhou, unified variance-reduced accelerated gradient method for convex optimization. In Advances in Neural Information Processing Systems, pages 10462-10472, 2019.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via SCSG methods. In Advances in Neural Information Processing Systems, pages 2345-2355, 2017.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg non-iid data. arXiv preprini arXiv: 2019..
Zhize Li. SSRGD: Simple stochastic recursive gradient descent for escaping saddle points. In Advances in Neural Information Processing Systems, pages 1521-1531, arXiv: wtt.:/904999.66 2019.
Zhize Li. ANITA: An optimal loopless accelerated variance-reduced gradient method. arXiv preprint arXiv:2103. 1333, 2021a.
Zhize Li. A short note of PAGE: Optimal convergence rates for nonconvex optimization. arXiv preprint arXiv:2106.0966 096633 2021b.
Zhize Li and Jian Li. A simple proximal stochastic gradient method for nonsmooth noncon- vex optimization. In Advances in Neural Information Processing Systems, pages 5569-5579, arXiv:/802.0m /04.://00204477, 2018.
Zhize Li and Jian Li. A fast Anderson-Chebyshev acceleration for nonlinear optimization. In International Conference on Artificial Intelligence and Statistics, pages 1047-1057. PMLR, arXiv: wwXiv:1809002.. 809.00339, 2020.
Zhize Li and Peter Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint arXiv:2006.07013 2020.
Zhize Li and Peter Richtárik. CANITA: Faster rates for distributed convex optimization with communication compression. arXiv preprint arXiv:2107.09455 2021a.
Zhize Li and Peter Richtárik. ZeroSARAH: Efficient nonconvex finite-sum sum optimization with zero full gradient computation. arXiv preprint arXiv:2103.01447, 2021b.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Accelcration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning, pages 5904. PMLR, arXiv:2002. 1364, 2020.
Zhize Li. Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pages 6286-6295, PMLR, arXiv:2008. 10898, 2021.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local SGD with lower communication complexity. arXiv preprint arXiv: 1912. 12844, 2019.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. Communication-effciie efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics, pages 1273-1282, 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 000209 2019.

---

Under review conference paper at ICLR 2022
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- tional Conference Machine Learning, pages 4615-4625 PMLR, 2019.
Lam M Nguyen. Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: novel method for machine learning problems using stochastic recursive gradient. In International Conference Machine Learning, pages 2613-2621, 2017.
Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. On the convergence of federated optimization in heterogeneous networks. arXiv preprint arXiv: 18/2.06/27, 3, 2018.
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2020.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. SpiderBoost and momentum: Faster stochastic variance reduction algorithms. arXiv preprint arXiv: 10690, 2018
Blake Woodworth, Kumar Kshitij Patel, Sebastian U. Stich, Zhen Dai. Brian Bullins, H. Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? arXiv preprint arXiv:2002.07839 2020.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5693-5700, 2019.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems, pages 3925-3936, 2018.
12

---

Under review as a conference paper at ICLR 2022
A MORE EXPERIMENTS
In this section we describe the detailed experiment setting for Section and present more numerical experiments. We perform two different experiments: the first is to compare the performance of different algorithm with different number of clients and data on a single client (Section A.2), and the second is to compare different algorithm with local full gradient computations, which shows the limitation of different algorithms (Section A.3).
A.1 DETAILED EXPERIMENT SETTING IN SECTION 6
We use the robust linear regression as the objective function. We run experiment the a a dataset in which the total number of data samples is 32500 (here we drop the last 61 samples for easy implementation of different number of clients). We choose the number of clients to be 3250, 325, 10, and the numbers of data on a single client are 10, 100, and 3250, respectively. When the number of clients is 3250, we choose S = 10, i.c. the server communicates with 10 clients in each communication round, and when the number of clients is 325 or 10, we set 5 = 1. For all settings, we optimize the global step size fg and choose the local step size 'It heuristically such that the algorithms converge as fast as possible. For FedPAGE-1 (or PAGE), the local step size does not matter and choosing the optimal global step size achieves its best convergence rate, however for FedPAGE-10 and FedPAGE-20, choosing 7g. 77 with some heuristics does not guarantee the best performance. We also perform the similar experiments on another dataset wBa.
Detailed experiment setting in Section 6.1
For the experiments with a 9a dataset, we omit the last 61 samples and set the number of clients to be 3250, and for experiments with wBa, we omit the last 1749 samples and there are 4800 clients in total. Here we omit the samples because it is more convenient to change the number of clients. We let each 'client' contains 10 samples from the datasets. For SCAFFOLD and FedAvg, each communication round, the server will communicate with 20 clients (S = 20 in their algorithms). For FedPAGE, we set S = 10 because FedPAGE will communicate with all clients with probability S and the expected communication for all three algorithms in each round are almost the same. We choose the local steps of all these three methods to be 10. For FedPAGE, we choose the minibatch size by 1 and for SCAFFOLD and FedAvg, we choose the minibatch size that estimate the local full gradient to be 4. In this way, the local computations are nearly the same for all methods.
Detailed experiment setting in Section 6.2
A.2 COMPARISON OF DIFFERENT METHODS WITH DIFFERENT NUMBER OF CLIENTS
A.2.1 EXPERIMENT SETUP
In previous Section 6 we compare different methods with large number of clients (on 9 dataset, there are 3250 clients, and on wBa dataset, there are 4800 clients). In this experiment, we vary the number of clients and compare the performance of FedPAGE, SCAFFOLD, and FedAvg.
For the number of clients, we choose the number of clients to be 325 and 10, and the number of data on a single client are 100 and 3250. We choose the number of local steps to be 10 for all three methods. When the number of clients are 325 and 10, we set 5 = 1 for FedPAGE and 5 = 2 for SCAFFOLD and FedAvg, making the communication cost in each round to be nearly the same. We set FedPAGE to compute the full local gradient for the first local step, and choose only one sample to estimate the gradient for the following local steps. For SCAFFOLD and FedAvg. we set the minibatch size estimating the local full gradient to be 22 when the number of client is 325 and 652 when the number of client 10. When the number of client is 325, there are 100 data on a single client. FedPAGE need to compute two full gradient at the beginning of each local computations, costing 200 number of gradient computations. Then it needs to compute two gradient (the gradient of a same sample at different points), and it cost about 220 gradient computations in total. Choosing the minibatch size to be 22 in SCAFFOLD and FedAvg makes the local computations nearly the same, because SCAFFOLD and FedAvg use the same minibatch size in every local step. When the number of client is 10, the minibatch size for SCAFFOLD and FedAvg can be computed as 3250 x 2/10 + 2 = 652. This makes the local computations of these three algorithms be nearly the same.
13

---

Under review as a conference paper at ICLR 2022
For the step sizes, we choose the effective step sizes be 0.1, 0.03, and 0.01.
A.2.2 EXPERIMENT RESULTS
The experimental results are presented in Figure 4 with 325 clients and 10 clients on a dataset. We also include Figure 44 (i.e., Figure 2a in Section 6.2) with 3250 clients for better comparison. Similar to the experimental results in Section 6 Figure also demonstrates that FedPAGE typically converges faster than SCAFFOLD faster than FedAvg.
Figure 4b and 4c shows the experiment results
Effective LR 0.1
Effective LR 0.0.3
Effective 0.00
FedAAg
SCAFFOLD
Ceatlenn Nomm
10r-
Gradient Norm
FedPAGE
Gradient
10-1
10"
10
10-3
1000 2000
3000 4000
5000
1000 2000 3000 4000 5000 Communication Rounds
5000
10000
15000 20000
Communication Rounds
Communication Rouncs
(a) 3250 clients (10 data per client).
Effective
Effective 0.03
Effective
100
FedAva
SCAFFOLD
Coadent Norm Norm
Cradient Norm Norm
Gradient Norm Norm
FedPAGE
10 10
1 10-
10
1000 2000 3000 4000 5000
1000 2000 3000 4000 5000 Communication Rounds
5000
1 10000
15000
20000
Communication Rounds
Communication Rounes
(b) 325 clients (100 data per client).
Effective LR 0.1
Effective LA 0.03
Effective LA 0.01
FedAyg
SCAFFOLD
Gradiet Norm
FedPAGE
Godient
Coudient
10-
10
10
10-
10--
1000 2000 3000 4000
5000
1000 2000 3000 4000 5000 Communication Rounds
1000
2000 3000 4000 5000
Communication Rounds
Communication Rounds
(c) 10 clients (3250 data per client).
Figure 4: Experiment results of different methods with different number of clients.
A.3 COMPARISON OF DIFFERENT METHODS WITH LOCAL FULL GRADIENT COMPUTATION
A.3.1 EXPERIMENT SETUP
In this section, we design another experiment observe the performance limitation of FedPAGE, SCAFFOLD, and FedAvg. We substitute all the steps that use minibatch to estimate the local full gradient to the actual full gradient computation. In FedPAGE, we choose by = 1 in the previous experiments and now set by M, the number of data
single client. We also choose bi = b2 M. We denote the resulting algorithm FedPAGE-Full. Similarly, for SCAFFOLD and FedAvg, they choose minibatch estimate the local full gradient, and we change them to computing the local full gradient, i.e., = M. We denote the resulting algorithms as SCAFFOLD-FUR and FedAvg-Full.
We then compare four different methods: FedPAGE, FedPAGE-Full, SCAFFOLD-FUR and FedAvg-Full We perform the experiments 9 and w datasets with robust linear regression objective and
14

---

Under review conference paper at ICLR 2022
logistic regression with nonconvex regularizer objective. We let each 'client' contains 10 samples from the dataset. We set all the algorithm to run with 10 local steps (K 10). We run the experiments with effective step size 0,1, 0.03, and 0.01. For experiment on w& dataset with logistic regression with nonconvex regularizer, and FedPAGE-Full, we set = and for SCAFFOLD-Full and FedAvg-Full, we set S = 20 to make the communication cost in each round be nearly the same.
also test the algorithms with effective step size 0.3. For FedPAGE
A.3.2 EXPERIMENT RESULTS
The experimental results are presented in Figure 5 and 6 Figure
Da
5b ba and [boshow the results
of different methods on different problems and different datasets stated in their captions.
Fedtyg Full
SCAFFOLD-Ful
Codlent Nome
Norm Nom.
Coddent Nom
FedPAGE FedPAGE-Full
M Mmy MMN
Conduntt
M
10
10
10
1000 2000 3000 4000
5000
1000 2000
3000 4000 5000
1000
2000
3000
4000 5000
Communication Rounds
Communication Rounds
Communication Rounds
(a) Robust linear regression a dataset.
Effective LR 0
Effective LR 0.03
Li
Gradlent 10a
Feskug-Full
Gradlet
Gradlent Norm
FedPAGE
FedPAGE-Full
MMM
10-3
1000
3000
5000
1000 3000 5000
5000
10000
15000 20000
Communication Bounds
Communication
Communication
(b) Robust linear regression on w8a datasct.
Figure 5: Comparison of different methods with robust linear regression.
Fed/vg Full
10-210- 10 10-11010000
SCAFFOLD-Ful
Gradlint Nome
Cradiien Nom
Cradient Nomm Nom,
FedPAGE
FedPAGE-Full
10-10 10-
10
WW
1000 2000 3000
5000
1000 3000 4000 5000
1000
2000 3000 4000 5000
Communication Rounds
Communication Rounds
Communication Rounds
(a) Logistic regression with nonconvex regularizer a9a dataset.
Effective LR 0.3
Effective LR 0.1.1
Li
Festug-Full
Goddent Norm
Gradlent Nome
Gradient Norm
FedPAGE
10-40 100
10-3
FedPAtiE-Full
10
10-3
1000 2000 3000 4000
5000
3000 4000 1000 2000 Communication Rounds
5000
1000
2000 3000 4000 5000 Communication Rouncs
Communication Reunds
(b) Logistic regression with nonconvex regularizer on w8a dataset.
Figure 6: Comparison of different methods with logistic regression with nonconvex regularizer.
15

---

Under review conference paper at ICLR 2022
FedPAGE FedPAGE-Full First, the experiments show that the convergence performance of FedPAGE and FedPAGE-Full are nearly the same under the same effective step size. Although there are some fluctuations in the convergence process, the fluctuations are not large enough to conclude any difference between the convergence speed of FedPAGE and FedPAGE-Full.
FedPAGE-Full 2 SCAFFOLD-FuIl > FedAvg-Full Next, the experiments show that FedPAGE-FIT converges at least as fast as (usually outperforms) SCAFFOLD-Full and both of them converge faster than FedAvg-Full in all cases. Using the robust linear regression objective in Figure FedPAGE- Full and SCAFFOLD-Full converges nearly at the same speed, but in the experiments with logistic regression with nonconvex regularizer in Figure [ FedPAGE-Full usually outperforms SCAFFOLD Full especially when the effective step size is large. From the experiments, FedPAGE either has faster convergence performance under the same local computation cost, can use less local computational resources and achieve the same or even better performance.
B GRADIENT COMPLEXITY OF DIFFERENT METHODS
In previous Table we show the number of communication rounds of different methods. In this section, compare the gradient complexity among different methods. Table summarizes the gradient complexity per client of different methods under different assumptions.
For SCAFFOLD, in each communication round, S selected clients need perform K local steps, and the gradient computations of local client is the number communication round times SK/N. For FedPAGE, in each communication round, selected clients need to first compute two full/moderate minibatch gradients, and then performs K local steps computing only 0(1) number of gradient in each step. The gradient complexity per client of FedPAGE the number communication round times S(M + K)/N. In the BV setting, the full gradient may not be available, then FedPAGE uses a moderate minibatch gradient estimate the full gradient, and one only needs change M the moderate minibatch size in order to obtain the corresponding gradient complexity (See the last two rows in Table
In particular, if the number of data on a single client/device is not very large (M is not very large), one can choose K such that M + K O(K). Then the number of gradient computed by FedPAGE during communication round is similar to that computed by SCAFFOLD, and also the number of communication rounds of FedPAGE is much smaller than that of SCAFFOLD regardless of settings (see Table D.. As result, FedPAGE is strictly much better than SCAFFOLD in terms of both communication complexity and computation complexity, both by factor of N/14 in the convex setting and //////// in the nonconvex setting. Thus, FedPAGE is more suitable for the federated
Table 3: Number of gradient computations per client for finding an e-solution of federated convex and nonconvex problems
Algorithm
Convex setting
Nonconvex setting
Assumption
FedAvg
o² +
Smooth, BV (G, (G,0)-BGD Smooth, BV (G, BGD Smooth, N, (0, B)BB Smooth, BV,
Yuu et al. 2019
2
Ne
Karimiredyy et al.
FedAvg
2020
G No2
N/
GSK
Nc
+
Ne
o²
G Net
Ne3
B2SK a2
Ne²
Ne
FedlProx
B²
(Sahu al. 2018
VRL-SGD
NK Ng²
(Liang et al.
2019
S S= N Smooth, (BV), S- N, < M
S-Local-SVRRC
K+y 1/9
Gorbunov et al.
2020
SCAFFOLD
K + Ne3
gt/3K 22
Smooth, BV
Karimireddy et al.
2020)
N1/322 Ne
FedPAGE (this paper)
Na/4 No
(M + K)
N1/2 (M + K)
Smooth
FedPAGE (this paper)
N3/4
No
3.z -
/N3/2_²
+ K
N1/248 No*
No²
+ K 3.2
Smooth, BV
16

---

Under review conference paper at ICLR 2022
learning tasks that have many devices and each device has limited number of data, e.g. mobile phones.
C USEFUL INEQUALITIES
In this part we recall some classical inequalities that helps our derivation. Proposition 1. Let {UI..... 3 be vectors in 12d. Then,
(vi, wz) S 2 2ell + 2c
1ell 00
(4)
|0 + u5ll² - (1 + (1+a))0011++ + (1 a) 10,113, Va > 0.
(5)
l 2
U
Proposition 2. If X E IRd a random variable, then
R E| X
EXI |X
Besides, have
B| - 2 - 1|
(9)
X E Rd are independent random variables and EY O, then we have
+ x If "......, Xn E IRd are independent random variables and EXX; 0 for all then
E X|2 + E|
(10)
E
X;
2
(11)
Proposition X Rdd are two random variables (possibly dependent), then
X X Y [X EYI 21E EXI -1EIIY 112
(12)
Proof.
B|JX- 2
|EX + EY| B|X + E(X + Y)
EX + EY| 2E| - 2 + 2E Y - 2
D FedPAGE WITH K =
In this section, we discuss and analyze a special case (i.e., the local steps K = 1) of our FedPAGE algorithm. When discuss the special case under the nonconvex and convex setting, we do need all of the functions {fi} to be L-smooth. Instead, we only need the following average L-smoothness assumption, which a weaker assumption compared with the smoothness Assumption !
Assumption 3 (Average L- L-smoothnesss, A function f Rd - R is average L-smooth there exists 2 O such that for all 01,02 E IRd,
[.V((( vf < 1 x2|12.
If the functions (fi) are average L-smooth (Assumption 3). then f(x) + I. fi(x) is also T-smooth, i.e., for all 31 E Rd, [V)()1) (x(2))] & T|| x2ll2-
17

---

Under review conference paper at ICLR 2022
D.1 FedPAGE WITH LOCAL STEP K
In this section, review the convergence theorem is directly derived from Theorem 1 in eLi al. 2021 20215).
of PAGE in the nonconvex setting. The following
Theorem (Theorem in ct. al. 2021)). Suppose that Assumption
holds, i.e. {fi} are average
L-smooth. If we choose the sampling probability Po = and p, = p N for every 2 1, the global step size
fg
Li1+
then FedPAGE with (PAGE) will find a point x such that E Vf(x)ll S e with the number of communication rounds bounded by
L(VN+S) Sea
R =
Li et al. 2021) also provide the tight lower bound (Theorem of [L al. 2021 indicating that the
convergence result of PAGE (i.e., Theorem 3) is optimal in this nonconvex setting.
D.2
FedPAGE WITH LOCAL STEP K =
Now we show the convergence result of FedPAGE with 1 (PAGE) in the convex setting. We assume that the functions (fi) average L-smooth and function
E fi(x) is convex. Theorem (Convergence of FedPAGE in convex setting when K 1). Suppose that is convex and Assumption holds, i.e. {fi) are average L-smooth. If we choose the sampling probability
Po = 1 and p, = p= N for every 2 1, the number of local steps 1, the minibatch sizes
bi b2 M, the global step size
(S+N"/*)
S θ
L(S+VN)
then FedPAGE will find point x such that Ef(()) f with the number of communication rounds bounded by
N3/2
ifS VN
Sc
NI/A
0
V/N < S
NL
if N3/1 < S
Se
To understand this result, can S 1, i.e., in each round long the server does
communicate with all clients, it only selects one client to communicate. Then, the total communication cost of FedPAGE (here also the convergence result for PAGE) becomes Na/4
Recall that
convex setting, SVRG/SAGA has convergence result O ( ). Thus FedPAGE/PAGE has much better convergence result compared with SVRG/SAGA in terms of the total number of clients N.
E MISSING PROOFS IN SECTION
In this section, we prove the convergence result of FedPAGE in the nonconvex setting (Theorem I use E,, to denote the expectation after x" is determined. Recall that we assume that (Jigg are L-smooth, and formally, we have the following assumption
Assumption (L-smoothness), All functions St, .Rd + for all E [N].j E [M] are L-smooth. That is, there exists L 2 0 such that for all æ1, x2 E Rd and all i [N],j E [M].
|| [a)((()) (2,,(12))
D| xall.
18

---

Under review as a conference paper at ICLR 2022
Lemma 1. Under Assumption I if we choose by and the local step size m - FedPAGE, we have for any i, k.
<2p in
24/SKL
E, Eglgg F.oll
(o2T(bs < <M}
<12K2L?>h
+ 1211x"
-x--11 11g--1 vf(="~1)112 + [[
b2
Proof. For any i, r, we have
E. 11 0fol2
= E,
V Is (1 VIa.i((((--1) + - Rhall
1
1 1
11oā - 00,011 + KK,, (Is ViDh(UAA---11'
K
1
1+ K
B - g.ol1 KLL - VfAA-11
(13)
1
1+ K K-1
B - 2 KL 1E
1
1+ K --1
B - 0.oll + KL2 1/ E, 111.g Pi,0 + g
1
1+ K -1
B - 0-011 KL2 mp E. |1 Fioa + VIzf((=") - VVz,f(ix" g11
1
1 K - 1
B -o E, 34,0 + Vfi(z' - 1)((=--1++ + -
I2Ibb2 < <M}
+ 4K L 2
b2
1
o2I(22 < <M}
+
Er Er - 0.ol11 +4KL2 m
K - 1)
b2
+ K KT,,,1 n
B, 1996 5. + V/((=') V5i(x--11 + + - (/(x--1) + v5(x
1 1
E.lloh,n-1 - 02112 4KI,2 02I(b2 2
<M} + 4KI,2 1 1, gf
-1
b2
+ 4KLL 2 n8
[Vf((=)) V + 4KL m 1111""0 r-1 vf(x + 4KL /
1
B. 0.o11 + 1KI,2 0² 201122 < <M}
+ +4K
K 1
b
+ 4KL22 7/ V f((x'))
I|1 4KL 77 V Vf
021lb2 < M}
<AKL2
+ +1X,
b2
Σ
(1+ K-1
1
1kL
2 < .M}
<AKL2
+[V[i((>"> - - 11---1 - + +
bz
K-1
Σ k=0
(1+
+ AKI2'p)""
K 1
0 02I < M
<12K2L?
- vf((='
- + -
b2
(14)
19

---

Under review as a conference paper at ICLR 2022
I12K2L"n ( < M
+ x1- 1lg
Vf + V 111)
b2
In the derivation, 13) fact that if we choose m S
comes from the smoothness assumption (Assumption
comes from the
v2p then we have 24/SKT."
1 K
+ 4KT2.12
k=0
+
1 K-1
+ 4KL2
+ 44K 12
k-1
(1+xx=) + 4
S(K 11)
-1)
(1+ K-1 + 36K
S(K 1)
-1
<3K,
for any K 2 2. Then we take the average over k, we get
k 1
E, 11 Koll2
K
k=0
< M} + - + 11g--~
<12
\[(x"1)) + |V (1=²)))13)
b2
and we conclude the proof of this lemma.
Lemma 2. Under Assumption if we choose 63- = 1 in FedPAGE, the local step size mp S
Epp
21V5KL'
the batch sizes bj = min(M, MM,
240² pNe2
}. by min(M, M, pSe²
21o"
}. then we have
11119 10-19~~V/00 VV )1 S (1 111-))1s
1|
1 1/3
11" -
1
12
P
V
fx
-1
1|
pe?
S
65
8
Proof.
Ey 11g" - (x)x²))1
K
=(1 - B,
1
----1- VS(x')
+ p
1 Vzz((+²) - V((o')
Σ
K|ST
N
KE km
SE[N]
=(1 -,)
1
Σ
K
12
popT(bi M/
K|ST
Nbi
iEST A=
=(1 - B
1
K
(g - F. + 5.o - V\(27))
+ po01l(b cM}
KIST
No,
KEST
1=1
K
=(1 - E,
Σ
(of.-11 - K. + - --
KIST
YEST 1=1
T < <M}
Nb1
p)
Er
1
Σ
K
(gh.-1 - Kh + -- vf(o--11)
+ pooT(bi < <M}
(15)
K|ST
Nb
KES k=1
20

---

Under review as a conference paper at ICLR 2022
K ( 01.-1-9.0) - EE, K|ST
K
+ (1 - By
P---I- -
K S"
iEST k=1
iES" k=1
1
(2, - Vi(a7) + V - VIgJi
K|Sa
iES"
(1 - p){ (1+ ?") 11g" 11g" -Vf(='1)1 1|| po < <
Nb1
+ (1 - p) (1+?)
?))
K
p)
Br
K K|ST
Σ jEST kml
Σ
(g Kiod
K Σ
+ +11 - p) ((,))E E
(Vz,f((')) - -Vf(2)) + - -v 1))
KIST|
iEST k=1
+ +(1- - p) (1 2)
K
K
Er
- - - Ey
(KA-- - g5.0
p
K K"S"
K|SS
IEST 1=1
iEST k=1
(f(x"-1)1 + po ITbb < M)
=(1 - p) (1+ 7)) 11g"~1
Nb1
(1-p) p) (1 2)
K
2
E, S EEST k=1
(of - gi,o)
p
2
+ +11 - p) (1+ 2)
E,p
(VI,f((x') - vf(x²) + Vf(=-11) - vz
|SST|
iES"
+ - +(1-p) p) (1+ 2 Tr
K
K
2
ko - 0%/0) - E,
(g - F5o0
p
K S'S"
K S|S
iEST k=1
iE. k=1
p) (1 (1+ p)
2) 11g vf(a" -1122 +
po T1bb <M}
Nb
+ (1 -p) (1+2) 2) E, K|Sr
K ΣΣ (gi Kho!
1EST k=1
1-P
(1+ ()
E, VTTJ((x") - Vs(x") + v - Vizli(u-11) 112
(16)
S
2
K
K
1- P
2) (1
E,
1 - -%,0) - EE, K
(f/ Kio)
S
p
K 1=1
k=1
v ||]1 2 11b1 M
p) (1+ 7)
|1g
Nb1
+ (1 pp) p) (1+2)
Σ K
2
(oh g2.o
K|S-
1EST k=1
1- P (1+ "0 E, (V') Vf(x') + v vf((x-11))
S
1 1-p P (1+
p
1021(12 < <M}
+
S
2
b2
1 K
1-p p S
1 1+ p
2)
E,
Σ
(o - 0%.0) Er K k=1
Σ
g g.o))
K k=1
21

---

Under review conference paper at ICLR 2022
P
r-
ff(a== ||1 pod < M
2
Nb1
2
1
+
E,
(g g4.
p
K ST
iEST
p/2
1 1
p/2 4o
2021(12 < M
+
Er
[I(vfi(x²' Vfi(2')
+
S
S
b2
+ E,
2 ps
Σ
( k..
(17)
In the previous derivations, a random variable (Equation In (16). we define 2t to be VT, [(((")) VV(x'')) Vz,fi(x² and then apply Here, are ii.d. random variables.
15 comes from the fact that we separate the mean and the variance of
Then we plug in Lemma and by setting m S 24//KL'
vBp
we have
Egl1g" [[(x')1
-[(xx' )12 po 116b < M}
1
P
1
2
Nbi
2
+
E,
(gi sioo) -koo)
p
K| S'
kml
1
p/2
p/2
(2 < M
+
Erll
(Vi((x") (s((x--11 112 +
S
S
b2
2
1
+ ps
Er
-g gt.0)
K
< <(1
2)
P
11gh~ vf(x"11111
po 1ob1 M}
(18)
Nbi
1 1-p/2 L2
-1--112++ 1 ppp2 40 I < M}
5
b2
4 12K2
(021(b2 < M1 + L -2'100" - -x-11 + - -11))
+
p
Plug in 1j
P 211ls
\1(2-1)111 llb < <M}
(1
Nbi
1- 1/p/2
1 1 p/2 102111222 < M}
L,2r,l1t 1//1111 -x-1112
5
b2
+
p 0²I(b2
< <M}
2L2
|x"""
x='
r- 11
P
19 V1(2" )112 48K² [ 1/12
65
b2
65
6S
<(1
P
"1g" -vf(x" 1|2
1- p/3
1, 11"" - x.' 1111 + 48K21,21 [
3
S
p
+ p a T
< M]
1
p/2
40
T < M) 1ob < M}
+
+
65
b2
S
b
Nb
where in 18 we apply Lemma 1
and Eq.
Plugging in the batch sizes bj min M, 24o
pNea }. by
min (M,
4
and recall T/ 5
/2p 24/SKL'
we get
pSc
E, 22(2')12
< <(1 <11-2) 3
1 11 1- p/3
L' 1|
x²
11
48K L
1|
pc
5
8
(19)
22

---

Under review conference paper at ICLR 2022
P 2(1 - 3
-
1 1-p/3 S
L'E 1|,1 x² 21=
P 65
Vf(x
I|
pc
8
Then, combining with the following descent lemma, we can prove Theorem
Lemma (Lemma 2 in PAGE Li et al. 2021)). Suppose that f is L-smooth and let x x+1 = x'' -nng. Then we have
7 2 |VS(x'1122
2nj -
2 -|att1--918- -
Theorem (Convergence of FedPAGE in nonconvex setting). Under Assumption (and Assumption 2). if we choose the sampling probability pr p & for every T 2 1 and po = L, the minibatch J. b2 min M, 18o2 pSc }. and the global and local step sizes
sizes bj = min M, 21o²
Se
22p
ng I
m S
(1
3(1p//3 2p8
24
then FedPAGE will find a point x such that E V S e within the following number of communication rounds:
LIVN +
R R=O 0
Sea
Proof. When 1)1 <
U2p
Lemma
holds. If we choose the batch sizes b =
24
24o² Mi, pNez }. .b min M,, pscz }. we have
18
f(x") - - 31a
E
و ff("")
2p
L
SR.
1(x"-1) p
| ||(x
|1"
x
112 + 11
V
)11
22g
2
(20)
+ 2p
311g E
(1- P | n²'
112 +
(1 p)
L
E,2E, 11 - x-' x1-1111-
E,
V
/
(x"
1|
3
5
3
GS
8
<Eff(x - -f - Mg
||
L
311g
1
1 2 L2 |1 1| x'
11-
2119
2p
5
31g 11g Vf(a || +
(21)
2p
where in (0 we plug in Lemma and Lemma 3 and in we rearrange the terms.
Choosing fg
and N. the coefficient of || - 1|2 is greater than zero,
30 5 2p5
1+
and we can throw that term away (since || 1
x-111| 1| 2 0 and the sign is minus). Then we have
31g llg" {2(x")1
E f(x²)
f( f"
2p
< [(x' - - 37g
و|ا -1 vʃ(ar 12
3nge²
7
V
112
2p
16
We also know that in the first round,
N
0²
2c
E
V v(,)(()))
- vf(29)
<
N
Nb
24
23

---

Under review conference paper at ICLR 2022
and we have
-(x)) 5
371 2p
119" - vs(x")1 S [(x9) -5 + 3rg pe
3rnge e
1g
E
((x')|?
2p 24
16
4
1=0
which leads
1l E
V S [(x0)- -
3/g p
3rd
2p 24
16
==
where we use the fact that || and f(x) 20.
So in O(1/(1,=*) number of rounds. FedPAGE can find a point x such that EE S e, which leads to a point x such that (x) Then since
S
1 1
3(1 3(1-p/3) o (1 2pS
(1(1+
VN VN )) =0 =0
VN VVN+ S
f2
know that FedPAGE can find point such that E|v()) S i 0 ((V++S) communication rounds.
(
number of
F MISSING PROOF IN SECTION 5
this section, we show the convergence result of FedPAGE the convex setting. first show result when the number of local steps is I (K = 1), where FedPAGE reduces to PAGE algorithm (Section[F.] F.T). Then, we show the result of FedPAGE in the convex setting with general number of local steps.
F.1 PROOF OF THEOREM
Similar to the notations in the proof for the nonconvex setting, we use Fr to denote the filtration when we determine the "ggradien"" g--1 but not g", i.c. x² is determined but =++1 is not determined. We use E to denote F[]]
Recall that in this section, assume the objective function f is convex and all the functions {ff} are averaged L-mohhhh
Assumption (Average L-smoothness), A function f IRd - is average L-smooth if there exists I 2 0 such that for all #1, IRd
E, [ V/( L ( x2|12
The main difficult to prove Theorem is that FedPAGE uses biased gradient estimator, i.e.
Eg + EVf(x"),
for most of the rounds During the derivation, will encounter the following inner product term
B(VS(x--1) g" xx)).
If the gradient estimator is unbiased, the above inner product is zero and we don't have to worry about this term. But when the gradient estimator is biased, we need to bound this term.
However, since the server using FedPAGE will communicate with all of the clients with probability p. round get the full gradient f=(("), ), the following property holds.
Lemma 4. When the number of local steps (K- 1) and we choose the probability pr = p. for all FedPAGE satisfies for any 2 1,
Exlg" v((x')
p) (1-p)
v((x--1))-
24

---

Under review as a conference paper at ICLR 2022
Proof. If in round r, the server does not communicate with all the client and only communicate with subset of clients S", then from the definition of FedPAGE, Ayj - and we can get
1
Au!
K.
K
Sm
S
PEST
iEST
We use Ez to denote the expectation over the minibatch Iz to estimate the local full gradient. Then we have
Eg vf(x*) E
Lh,0
Vf(a")
+ PE,
Σ
S
N
iEST
KE[N]
=(1
p)
E2
EI ( vs(aT))
1S
VES"
=(1 p)
E
E1 Vz,fix²') vznf(e""1) -
1
LES"
=(1 p)
E
EI Vzzli<²') VIaJi(E'11) + g v)(2')
S
EES"
=(1 p)
Er
[[ V/i((-11) + 5f -
SS
iES"
=(1 1) (/ )
where we use the fact that S" is uniformly chosen from [N] and fI, is a gradient estimator of fx()).
Lemma (Lemma 3 of (Li al. )). When the number of local steps is I and we choose pr- = for all r, FedPAGE satisfies for any 1,
B V)(x = (1 - p>llg" Vf(x 112
1-
S
Then, control the inner product term using the following lemma.
Lemma 6. For any t 2 2 and any >> O, we have
- - x²) S E
xx-
cIVf(x--1)
-g--212
11 + ||"" - 2-1
2p
1=1
Proof.
B B(V 9¹ g--1 0-_100 xx= x*)
=B(VS(x> ) - -g" r-1 xx x x111) + EE, (V/(2' g x x²)
-) - --- 2c
E11 - x"
(1-
x x" x²),
where the last inequality comes from Young's 's inequality and Lemma 4 For r = 1, we know that
(V_((V((> -1 x=11_ - x*) Unrolling the inequality recursively, we have
B[Vf(x-'1) 9" 1,"" - xx)
c "B]S(( -"00--1111 112 + E 1 -
1
-- +
- x²)
2
2c
1
11 + El x- - x x-11 cg
2c
1- PP
1
cllf(z> - 2) 9" 212 +
||
x
-
213
(1 (1-p) 2)
3) و" r
3 x
xx
25

---

Under review as a conference paper at ICLR 2022
p)"
9-1 +
Σ
p)- 1
18 1811"0" xx" x=''111 122
2
r==1
Then we sum up the inequalities from to i,, we have
B(Vf(z²-)) -g- x²-
x²) - E 2p
cIVf(x='1)
--- 11-1 + 1
112" - 11))
11)
Given these lemmas, we can now prove Theorem We first prove lemmas related to the function decent of each step, and then show the proof of Theorem 2
Lemma 7. For any r 2 0 and any À > O, we have
0 S T 1r - [xxxx
ng Br V[('2)1
1 - Er Er1| =|= ==11++
2 22210"" x012
2L
11 [g]((+1) 1 E, 1r|1x:11
1²11 + + -1)(V(=>>>> -- xx =x").
Here, we define g V O.
Proof. For any 2 0, we have
ng(f(=') - f(x"))
Sng(Vf(z"),2 x,="=x") xx")
(Vf(²') -11-)) (1-p)(V5(<"))
- + ( - - x²)
En (g", x= -x") + (T((1 (x==1 -g- =x")
-n (g", xx x111)== + n1 Ey (g x²111 x²) + og (V ( g" 1 ), ) xx= - x²)
SnylE (9),, x- x11 11111=+1 - x²1
Br,l 211 1E, 1| 1--=-11--- - x ==1
11,1111
1
2
+ 1, (VF 1 x" x---- - x²).
We also have
By (g", x² - x1+11
En (g" - ff(x"), ),²" x² - 21t1) + BV - x1
S Da Er 11g vf(x")112 + AoAL Br||o" - no 2XL
+ (=(x"))) ff(xx=1)) + 774
2 1| +1 x² x²12.
2
Summing up the inequalities we conclude the proof.
Lemma 8. For any 2 0 and any À > O, we have
N1 (ngL(A+1) -1) -1) 12-- - 1122
0 S (f((')) f(xx+))) + Dg 1lo" f(x")12
2LX
2
Proof.
== x² - x111 my x r+ --1--") =²))
( ) - x1+11 + m1 16666 - V l (xx): ) - x1)1)- || - 121
1g - 1 |11---1--""" 11-1-x11 x111
<ng(((²²) -1x + 1g 'g' v5(x'), x. - - +
2
Sna(s(>)) - f(xrt1)) + By و|g - vf(x")12 + N [ + 1)
|| - x212
2XL
26

---

Under review conference paper at ICLR 2022
Theorem (Convergence of FedPAGE convex setting when K 1). Suppose that f convex and Assumption 3 holds, ie.. (Ji) are average T-smooth. If we choose the sampling probability
Po = 1 and Pr = N for every 2 1, the number of local steps K = 1, the minibatch sizes
bj by M, the global step size
(S+N9/4)
Mg S
L(8+VN)
then FedPAGE will find point x such that Rf(()) - 5 S with the number of communication rounds bounded by
N3/AL
isS VN
Se
NUAA
R
0
ifVN <S N3/4
NL
Nf < S
Se
Proof of Theurem
From Lemma 7 and Lemma for any 8 > 0, we have
1g [f
f(x") + f(x*+1))]
Ng + 5)
Er --(=")12-
Br
-
11x
x11 2 || x²1
2LD
2
1)((++
11g [()
1)(++))(++))
20
+
1²1 + ( p) () - x² x²).
2
Summing up the inequalities from r 0 to T and taking the expectation, we have
mg
f(x9)]
1
T-1
Mg (1 + 8)
< -
18|"0"" - =1= + 2 1,000 x=112
TEllg (((("))
2
2LA
T-1
L(A + 1)m9 -
+
Σ
(1 8)
Bl1 +1
xx" 112 + 7g 1D-p)BB(V/
[(x D)B -----_1_- xx x²))
0=
1
1g (1 (1
+ To p)c
- 1=1 _
+ 2
1200 -1*112+ Σ
Ellg" vf(x')12
2
2LA
2p
T-1 + (1+0)
[ong (A 1)
My (1 p)
El x 1=
2cp(1 + 6)
where we apply Lemma to bound the inner product term. Then using Lemma and Assumption 3 we can get the following result.
LI-PEE - PS
(1 L)
E - v(()))
EE,
)1
E
" x0 112
pS
T=0
Plugging into the previous inequality, we have
Σ
m B(f - f(x*)1 + TT]((( f(x")]
==0
1 2 El|xT 11
11100 11 Σ
Bl| - 112
27

---

Under review as a conference paper at ICLR 2022
where
LM -1 77 mo(1- p)
No (1(1)))
+ mo p)c)
(1- P)L
w- w= (1+6)
+
2
2cp 1 + +,))
2LX
2p
Ps
By choosing
VI/(Sp),c= c= /Sp/L2, L2, we have
(1 + ( 1/(pp) +1)
1+5 no -p)
(1 + 8)
11 pD)p Sp/
(1 (1-p) L2
+
2
20//S/112
21 /1(5)
2p
PS
Lia (1/(s) +1)
1
l1 -p)L
noVSp
7o D)v/Sp)
(1-D)L2
(1 - D))L
=(1 6)
2
2
2p1/2 +6)
2L
2pT((1 + +5)
Ps
Img (A((((1()))) + +1)
1
No - -
1/g + (1 - p)
2p(1 + +6) )
(1 - p)
=(1 6)
+
2
2
2p2/22/55 + 6)
2
vpS
L (Mg(V1/C5 11(pp) + 1)
Bg (1 - p)
fl (1 p)L
(g - p) (1 - -p)L 1
-)
+
2
2p / (S + 8)
2
vpS
2p(1 + 6) vpS 2
B
If 12g 50
(1+68pp
and 8 S 1/p, we have
1(1+)1/(5p)
LMg (MplV///C VI/(Sp) +1) =0 L( [(V///(D)) +1) I//p/(Sp) + +1)
(1/p)p
A
-0(1)
2
B (1 P)L =0
P 222/avs L(1 + v1/(Sp))
(1 (1-D)L
-0)),
2p²/2 258/2/5(110 +0)
C 11 (1 T.) =0
(0111 p)L (1/D)p
(1 (1-p)z.
=0(),
2 VPS
VPS L[VI/(SP) +1)
D (1 p) (1 L.
O(1).
2p vpS L(1+ + vI/(Sp)
In this way, we can choose fl with small constant such that w is non-positive, and we can throw that term. In this way,
1 || x²1 + +lf(=²) - f(x")1 -
1
Lg 2
Σ ((f( -(x))) -
1|
x²1
21a
2nh
Then set d 1/(81/4/3/4) and p- S/N. We first verify that 8 $ 1/p. We have
N3/4
N3/4
N
8 = S1/4
<
53/4
S
S
Then we choose
S
ifs S VN,
N3/4L
N-/4 (1+
(S (5/1
n1g = θ
=
iFVN < <S/
VN L(1+
L(S+ VN)
NI/A
8
S NT.
if N3/4 S
Then, the number of communication round is bounded by
N3/4L
if
Se
R ==
if VN
<SSN
(NN
NL
0
N3/
<S
Sc
28

---

Under review conference paper at ICLR 2022
F.2 PROOF OF THEBOREM
The proof idea of Theorem 2 is similar to that of Theorem 4 The difference between these two proof comes from the fact that in the convex setting with general local steps, the local steps between the communication rounds introduce some local error and we need to take the error into account.
In this section, we assume that all the functions (fis} are T-smooth.
Assumption (L-smoothness). All functions ft. E2 R for all E [N] E [M] are L-smooth. That is, there exists L 2 0 such that for all x2, E 12d and all i [N], E [M].
(i V fi.j (22) S L| -x2ll:
Similar to the proof with K = 1, we first prove lemmas related to the function decent of each step. The following lemma is very similar Lemma do not have Lemma
7 except the last term, since in the general case,
Lemma 9. For any 2 0 and any À > O, we have
1 "21l0" - x²11 Tl 11g" v((x")|1 _ - x=112 +
- Vo (5 - [(x')(
2LA
119 [(
Ey E 1²1 + ng (V (V - -g., -²²))
2 2)
Here, we define g g- V fx =0
Proof. For any 2 1, we have
(f(" - f(x)))
Sny (Vfx")) x² - x²)
(ng((( - -(V((x') g-), x- + + (Vf(2²))) g -x")
=n xx' - -x)) ) + M19 (Vf(x)) - - x² x²)
En (0"
",''"""" xx' - -x²th, 111 + 1 (f xx x²) + ng (ffx') g", ",--=x" -xxxx x²)
1
Eny (g" x" +1 E, ++ x² x²1 1p+ 2
Erllx" xx
E, 10 121
2
+ no fxx')
When = 0, the inequality also holds. We also have
"n",, - =x
E, (g" - Vf(x"), - x x1+1) " x
I 1/ Egllg ff(="|1 + Ag T Er|1z" +1 + +n - f(x--1)) + ng
2 1 - 1²112
2XL
2
Summing up the two incqualities we conclude the proof.
Lemma 10. For any 2 0 and any O. have
N1 [nn(A++1) 110" [(x))11+
-1) ( -111-11) -x-
< no((x²)) [(x*+1))
2LX
2
Proof.
011 (g" xx x1+11 Tly (g" x - x²)
(V)(2) ), x x1 + 1g Vf(x)) ), - x122) || xx-
17/6
(nn([(²²) -1(x + ng 'g' vs(x'), x- - -1 +
-
2
(ng(((1)) ((x)+))) 1l
11g [gg((+ + -1
|| 1--1-111 17112
2XL.
29

---

Under review a conference paper at ICLR 2022
Then we bound the inner product term.
Lemma 11. For any 2 and any e, d' we have
B(V((x)) xx==
d' K
E
- -
+ -11 -110² - x²"
1
+
0Toll + x 21100=1 x²
2p
KS
k= 1ES"
Proof.
(VV((x)) ,x =x)
=E(ff(x') 9" xx' xx +
g" ,x,x"" x²)
-)11((=)) 9' - x- +(V((()) 9¹, x - x²),
2c
where the last inequality comes from Eq.
44
We also have
((V)(x)) x²,="=1_ x²)
-(1 (11-))E([ ---g-- --)
x²).
Then compute the second term in the previous inequality.
BVf((=) o" (1 - (Vf))(((("""
), -x")
K
=(1 - E)
Vf(x') 1
Σ
Σ
Di + Σ
1
Ko
Σ iESt
Foo + +g" g--11 vf(x"1)),
KS
k=0
iEST
K Σ
=(1 P)E
Dipk +
Σ
F Fooxx" x0=1 xz
+ E
Vf(x")
1 Σ
o +
g--= xx x
KS K=DiES"
S
S
LEST
BEST
=(1 E)
Σ
Di + Σ
Pho0 x0 x
KS
k=
iEST
Σ
11-011
1²12 -
KS
S
2c
K=OTES"
SES
where we use the fact that E [V](x") - 3 Eies Fúp + + g=- [ = 0 and Eq. (4).
Combining the computations together, we get for any c, > 0,
E(Vs(a") - gx,x"" x²)
<(1- (1) -g"
x²)
+ (Ellf(") g" -01122
_
111 x² 12
2
2c
+ 2 KS
d
K
gh
1
Σ
22 +
1
||--- =11
S
2c
1E
iE
5(1 - p) ([{((=
-
- 5 -1 x x- x²)
+ El [l])(x)) - -g""l1
112
E|| - x--112
2
2c
d'
K
+ 2KS
Σ 02 +
| - x² 111
2c
K=0 ST
SEST
We also know that ( f (x
90, x0
x²) = 0, and we can get for any t 2 1,
B(Vf(z") g², x x²)
30

---

Under review as conference paper at ICLR 2022
d K
E
- 1 -
+ - -110" - 1-11
+
11
0.oll
+ z
- 2011
2p
KS
Lemma 12. For any c, c' > 0 such that Bhg
S 1/2, we have
pet
B(V((x")
-²,x"" x²)
r=1
( c
+ b
11 xx11² +
E
- 9²
V
-
pC
2p
p²c
r=l
( 1
+ tc ng
c'
+
E
11-""
x
1 11
E
11 00.011
2cp
pd
p²c
2p
p²c²
KS
1mm0 iEST
Proof.
|,00 x²" 1|2
-1 x² 11g
"/gg"11"" 1
||00 1 0²1 + 1g 19" 10---11 1|2 211 (g 1- xx - =x²)
=||x--1 1 - x²12 + ||=" - 112 - 2n (Vx(2' ) x - x²) - (g - Vf(x" Vf(x"11, r-1 x²)
S|10-1 - 2²12 + ||=" 112 + 2ng (f(²)) 1(x"" (xx-11) + 2/1 V 15 g" xx x²)
(
S11x-=1 - z²12 + || - 112 + 2n (f(xx-1) 9-- x--1 - x²)
S||000 - 12 + |0" - 11 + 2n
Vilaa 0" -1 x -1 x²)
P=1
M=1
For simplicity, we define the following notations,
A E
V [f(x-11 1 - ((a--1)---11
r=1
B =E
|| - x 1
C2 =E
1g 002
KS
k=0 iE
D³
=E
| - 2²11
D =E
Σ
c || - x x11
1
From Lemma we know that for any < L, we have
1 (Ag Be + o D
E E(V((x)) g",x"" -x") "-,--='1
<
2p
v (Ar + B¹ + cr + D',)
2p
and for any S f, we can bound ||-"" - -x- 122 by
El| 112
31

---

Under review as a conference paper at ICLR 2022
<BI
x² x²11
R.}
1 xx' 11 + 27 EF
(/ - - x²)
r==1
r'=1
<BI22 2²11 + EET
1,00 - x²' -112 + 27 2p
(A + B + C/2 + D'))
M=1
<BI - x 11 + cB¹
Tg (A' + Bº + + + D'a)
p
Then we bound D', we have
D³= Σ | x² x²11
$ >
E1|00 x²112 + cB
Fg p
(A + + C.. + D2)))
B
r=1
Lgg A + c+
B + Ug C.e + Ug D
<t|l x²112 + p
p
p
pc
As long as tig S 1/2, we have
D' S 2t 20000000 x²1|
11
26
A + 2t
c+
?1 p
B +
26n C2.
p
p
Then we plug this inequality into Lemma
1T
we get
B(VS(x*)
g²xx" xx)
d'
K
1 - - x²113
E
[ - -9" + - || x²
12 +
19 g0 +
2p
KS
k= VEST
K
1
E3
clV 1 - g" -12 + || - x² 1 12 +
c|
11 - scoll?)
2p
KS
r=1
k= DiES"
+
1
(2/1/00 - =x'11 211g
A + 2t
(e+
ng
1²d +
217g Ct
2pc
p
P
S
1.
11
-
+
c 2p
+
egge
E
f 11 )
112
pe
p²c
K
+
1
1
ngt
E.
1|00"
x
1 +
Lagg
E.
11
2cp
pd
pecee
2p
KS
k=0 dEst
Theorem 2 (Convergence of FedPAGE in convex setting). Under Assumption 7 (and Assumption 2 if we choose the sampling probability p. = p = 5 for every r 2 1 and po I, the minibatch sizes /B ), and the global and local step size
by m-nnnn
20
} b2 = minn (M, 480"
( ng = ((S NS/+
S (NS//AAR
L(S+ WN++ M ==
then FedPAGE satisfies
N3/4L
SR +E
iiSS VN
R-1
N1/4L
Σ -(()))
0
R +
if VN < SS
R
NL
,1/N8/1 <S
SR +
32

---

Under review as a conference paper at ICLR 2022
Proof. First we have
ng B1 +((0))) - [xx)]
(1 + 6)
Er"lg" ff(x")]1- 1 BB - =011 11:2+ + -110" - x²12
-
1
2LA
11 +0)
1+ 20
1Erl
- xm113 + no (V g", x² - x²)
2
}.b2 = min 180 Summing up the inequality and choosing b1 min(M, 2102/8) cpi/
/p3/s },
1g E[ - 8 [(x')] + 11 (x()) - [(x9)]
(1 + 8)
<
E1l0T T - xx1 xx11 11++ + 2
11 x²1
Σ
Bllg" - (
2
2LA
+
T-1
Σ
(1 + 8)
L(A+
+
1
B11x
x²112 + Σ (V g" 1 - xx))
2
+=0
r=0
2
1
E1
x² 2²112+
+
1
11
x²11
ng + 5)
cgg The pdd
Ellg" V fz())1
2
2LX
2p
+
T-1
Σ (1+
LoggAd + 1)
7g
Tng
n
E E| - x01
2
2cp(1 (1 + 6)
pc + 5)
pPcce' + 8)
0=
The
T-1
K
Tı pc
+
+
E
1 Fo,0ll +
2 x111
2p
12
KS
r=0
k=0 i
1
Tmg pd
(
T
To < M
B11TT
T 2²112 + 11 xz')
|| xx' 112 + 6K 23
+
2
2p
p²
b2
in E E|g" {)
(1 + 8) . W2 . El|x --+11xx1p xn11
Tul
T-1
+ 12
+
I (z')),
2p
1
19
Tily pc
(1 + (VSp31aTe)
Tog
- 10
+
11 x=" $12
|1 - 101 + 6K2
2
2
2p p²
31 - p/3
+
Σ 0=
(1 5) W22
+
wi
El - 1²1
D
S
('
The
144K21212
3cTp3/2 8V8
12K
+
+
[Vf()))1
W1-
2p
p2
p²
where we define
W1
+ (g(1+8)
Cgg
+
Tng pdd
+ 12K2 L?ni
c'ng
Tui
21A
2p
2p
p2
Lm + 1) -
n9
Tng
VTT
12K?L
Tne p²
W2
2cp 1 + 8)
pcc
p²ece1 +8)
1+5
2p
33

---

Under review conference paper at ICLR 2022
By choosing p
..A V1/Sp.c
VSp/L2.8
1/(5\/4p3/+),,
0
(1+8)p
c 2h 11 =
NNOKKLVT
we get
((+V/1((50)
1n + +0)
(L 1J+SN S
S
-11+800
=10+6)
2LA
L VNV//SS /SN/
N4//5T2
ag (1 + 810
S L' VN/S)
=(1 +1+
S2
p
NL
Thge = -(1 + 8)0 yºc
S
S²
61+
N3/2
T1g
Trg
2T
=2 p²
=0
2p
p2
L
Then, we can verify that un N/8 (1 6) 0(1). Similar the proof of Theorem we can also verify that w22 O(1), and we can choose fg and with a small constant such that
3 p/3
(1 01+
U2
+
50,
D
S
c
T
S CT
LKZL?T
2p
1r
16
12K2L
TTis
144K 2 L2
TT
1lg
2p
+
22
p2
W1
4T.
3TT
31g cT
W1
8v5
Then we have
Σ
Elf(x r1 f(x))]
r=0
<SE[f(z0) {xx7)1
11 x=11|
eT
+
1
Σ
[Vff(')]|
3*T
79
16
4L
8
r=)
T-1
7eT
< f(x +
11.00
x²
122+
+
B[f(x") - f(x*))
2
16
Then we know that
T Σ -
(2 (1()
8
-{(x)))
2
11000
x11
7e
16'
Recall that
S
if S VN
N3/AL
(1+ N3/4
= (S ( 5
7g 0
5 N
+
if < <SS
L(1+ N
L18 + VN)
NI/4
3
S
.if <S
NL
34

---

Under review as a conference paper at ICLR 2022
We have
N3/4L
0
+E
if VN
SR
R 1
NW/A
Σ E 0=0
+
R
R
NT
Nif <S
+
SR
35


Reviews:
[{"review_id": "yDEkBlj51vp", "reviewer": "Reviewer_uLBz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The theoretical part of the paper is relatively well-written and clear.\n- The overall contribution of the paper is very clear. The paper takes a recent distributed algorithm with a good convergence rate, and adds local computation to the algorithm (which is very common in FL), and shows it still achieves a good convergence rate. And because the original algorithm has superior convergence results, the FedPAGE also enjoys the same superiority over other analyzed FL methods. But if one steps back a bit here, actually the convergence guarantee of the FedPAGE algorithm is not better than the PAGE algorithm. This is clear from the approach in the proof (Lemma 1) and Table 3, where K=1 would give the best convergence guarantee for FedPAGE. This is important because adding local updates is at the heart of most FL algorithms despite the fact that there is little theoretical evidence that they improve the method. Unfortunately, these points are not very clearly conveyed in the main text. Also, due to this fact, it is important to accompany the theoretical results of the paper with solid experimental results that can support the use of local steps in FedPAGE under different circumstances (heterogeneity levels) and against many solid FL algorithms. As I will point out later, this part is very much lacking in the paper.\n- It seems that the paper assumes the same number of data points per client and I am not sure if this can be easily relaxed. Such an assumption is unrealistic because in FL clients are heterogeneous.\n- One part of the FedPAGE that in my opinion makes it basically impractical (for large N practical FL problems) is the need for rounds that communicate with all the nodes. In spite of the fact that these rounds are very rare (due to low p) during the run of the algorithm, they are not possible in practice mainly because 1) not all devices are available at the same time for an update (update usually happen only when devices are on wifi and connected to power).  And 2) the delay for the responses has a very long tail; meaning that waiting for all the devices to respond in a round takes a long time. And 3) the devices can drop out during any round which means that you cannot count on all devices for a round. This means that the few rounds that need complete device participation might never finish (or take a very long time to do so).\n- It is not very clear to me why in FedPAGE the effective step-size is $\\eta_g$ (as opposed to FedAvg and SCAFFOLD). It would be great if the authors can elaborate.\n- Regarding the experiments (For the importance of the experimental section for this paper see my first point):\n  - No comparison is done at different heterogeneity levels of data (which are known to have a great effect on FL algorithms).\n  - Not a single result is reported for the achieved test accuracy or other metrics that are relevant to ML\n  - For the comparison against other FL methods, no comparison is done for state-of-the-art methods such as the one that uses momentum, ... ! SCAFFOLD and FedAvg are not empirically the state-of-the-art methods.\n  - I had a very hard time understanding how the HP tuning has happened. What parameters were tuned for each algorithm and how (what were the metrics and possible values). This is important in all the results but esp important for Fig 2 and 3 where there are other algorithms and their HPs are also involved and the comparison needs to be fair.\n\nIt is worth noting that I did not check the proofs of the paper thoroughly, but the claims and results seem reasonable and correct.\n\nMinor comments:\n\n- last paragraph of the introduction is not very well connected to the rest of the intro.\n- The algorithm does not summarize how a solution (x) is returned. I had to go through the appendix theorems and proofs to understand that the authors assume the return of one of the x^r (probably at random based on the convergence guarantee). \n\n===== After rebuttal =====\n\nI read the responses and other reviews/comments and have decided to reduce my score to 5. I agree with other reviewers that the paper has flaws and issues that have not been addressed and it is not ready to be published. I encourage the authors to strengthen the theoretical results by looking at the possible benefits of local steps and also include more informative experiments.\n\n", "summary_of_the_paper": "The paper considers a federated variant of the PAGE algorithm, called FedPAGE that utilizes local steps. The authors analyze the convergence behavior of FedPAGE algorithm and show that it is very similar to PAGE. And as PAGE has good convergence guarantees, compared to other distributed optimization methods, FedPAGE shows good convergence results compared to other federated learning methods with guarantees. The authors have a limited set of experiments to compare FedPAGE with other federated methods and also PAGE.", "summary_of_the_review": "Based on the above points, I would say the current version of the paper is slightly above the acceptance threshold. I would be willing to increase the paper's score based on the authors' responses/updates to my comments/concerns (mainly around novelty, assumptions, practicality, and experiments).  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "chiuTd8x6b4", "reviewer": "Reviewer_Gwh9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper contains following strengths and weaknesses.\n\nStrength:\n- The use of PAGE estimator in federated learning is new. However, this idea is rather incremental as it is a direct application of the PAGE estimator to local method in federated learning.\n- The convergence results for nonconvex setting is better than existing results in terms of dependence on the number of workers.\n\nWeaknesses:\n- The result in convex setting is not rigorous enough. See details below.\n- The method requires to have communication to all clients for every $\\frac{1}{p_r}$ iterations on average. This is similar to the full participation requirements for methods like FedSplit or FedPD. This appears to be not realistic as clients in federated learning might get disconnected from the server. It is better to just use a subset of clients to update as in FedAvg.\n- Numerical experiment only consider one nonconvex objective while theoretical results include both convex and nonconvex. Also, only SCAFFOLD and FedAvg.\n\nRegarding the theoretical results for convex setting, in the proof of Theorem 4, page 28, first the authors need $\\eta_g \\leq O\\left( \\frac{(1+\\delta)p}{L(1+\\sqrt{1/(Sp)}} \\right)$ and select some small constant to satisfy the condition that $w$ is non-positive. However, when deriving the rate for communication round, they actually use $\\eta_g \\leq \\Theta\\left( \\frac{(1+\\delta)p}{L(1+\\sqrt{1/(Sp)}} \\right)$, i.e. $\\eta_g$ has the same order of the term in the bracket, and plug in the choice of $\\delta$ and $p$. How can you guarantee that when $\\eta_g$ is in the same order of $\\frac{(1+\\delta)p}{L(1+\\sqrt{1/(Sp)}} $, $w$ is still non-positive.\n\nSome minor comments:\n- In equation (1), it should be $\\frac{1}{M}\\sum_{j=1}^M$.\n- Appendix, end of page 23, the first equality should be $\\frac{\\sigma^2}{Nb_1} \\mathbb{I}[b_1 < M]$.\n- Appendix, page 28, there are 3 cases for $\\eta_g$ under different range of $S$, instead of $\\Theta(\\cdot)$, they should be $\\Omega(\\cdot)$ as it should be least in the order of $(\\cdot)$ or higher.", "summary_of_the_paper": "The paper proposes a new federated learning method, called FedPAGE, which uses the PAGE gradient estimator in local update and provides convergence analysis for both convex and nonconvex setting. The paper shows that the convergence rates achieved in both cases are better than existing results. Numerical experiments are included to illustrate the performance of proposed method.", "summary_of_the_review": "The paper does have contribution towards the development of FedPAGE and its analysis for convex and nonconvex setting. While the nonconvex result is shown to be better than existing ones, the convex result is not rigorous enough to me. Numerical experiments appear to not fully verify the theoretical results as they only contain nonconvex example.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XcpGQCyqVDX", "reviewer": "Reviewer_oGr1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n1. FedPAGE can handle larger effective learning rate.\n2. Theoretiacally FedPAGE improves over variance reduction-based SCAFFOLD algorithm in both smooth convex and smooth non-convex settings. \n3. Empirically FedPAGE is better than FedAvg. It is also comparable or better than SCAFFOLD.\n\n### Weaknesses\n1. Table 1: What should we focus on total communication bandwidth (S*R) or number of communication rounds (R)?\n\n2. Table 1:  Assumption $S \\leq \\sqrt{N}$ should be explicitely stated. Otherwise, FedPAGE may even only match SCAFFOLD’s round complexity.\n\n3. Not a lot of discussion on the limitations. \n\ni. SCAFFOLD never samples all clients at the synchronization rounds. That could be a too expensive waiting for this many clients to communication. Is this a necessity for FedPAGE? Is it possible to weaken this requirement?\n\nii. b1 and b2 are large. Negative effects of these are not discussed in this text. For example in convex, since b3=1, effective K=K+b2=K+ min(M,N^3/2/S^2). Even for S=\\sqrt{N}, this is equal to K+min(M,\\sqrt{N}). It is expected that authors discuss all such  cases.\n\n4. Experimental results are not comprehensive enough.  \n\ni. even though non-convex rate seems to be the main highlighted theoretical results, experiments are for convex optimization. \n\nii. It is not clear if comparing the algorithms at the same effective LR is appropriate, ideally they should all be tuned separately and the best stepsize choices for each algorithm should be compared against each other.\n\niii. Can the authors please provide comparison with more standard benchmark datasets like EMNIST.\n\niv. Since, in theory, FedPAGE is not improving PAGE, more comprehensive experiments could be useful for making a case for the former.\n\n5. Assumption b3=1 should be explicitly stated in the theorems.\n\n6. There are no rate comparison to non-local method like Accelerated SGD, PAGE, etc. From the results, FedPAGE and PAGE seems to have the exactly same round complexity. So it is not clear if the given theory is non-trivial. But the limited experiments seem promising since they show a constant but diminishing improvement when increasing K.\n\n7. It would useful if the authors can provide a discussion of any technical novelty in their analysis.\n\n### Other\n1. Table 1: What is this expectation $\\mathbb{E}[f]$ over?\n\n———————————————————————— \n### FINAL:\n\nI thank the authors for the response. However, after reading all the reviews, author response and public comments carefully, I have concluded that in this current state this paper cannot be publishable at this venue. Overall it seems there are many holes in the arguments of the paper. These are some additional comments detailing my reasoning.\n\n1. I acknowledge that the authors want to position this as a theoretical paper. However, in my opinion most of the theory of FL algorithms fail to explain their success in practice. Because of this it is hard to accept the usefulness of the algorithms or the theory without extensive experimental results. A prime example for theory not explaining practice is present in this paper itself! PAGE (FedPAGE with K=1) has the same convergence rate as FedPAGE (K != 1). This is possibly due to the fact that the proofs mainly show that FedPAGE is not worse than PAGE. However, experiments show that FedPAGE (K != 1) may be faster than PAGE. In fact this has been pointed out by other reviewers too. This is never addressed by the authors. \n\n2. Most of my concerns about the experiments are not addressed? Authors promise new experiments but doesn’t provide plots or data.\n\n3. I can agree with the fact that large(could be full)-batch local computations may be okay when optimizing number of communication rounds. But ideally this limitation should be discussed upfront in the paper. Public commenter “Durmus Alp Emre Acar” also raises an important point where SACFFOLD (with full-gradient and K=1) gets better rate than what is given in Table 1 for convex problems! Therefore the experimental and theoretical comparisons may not be fair.\n\n4.  Critical concern of Reviewer Gwh9 about the proof is not addressed. \n\n5. New concern: It is not clear were “Assumption 2” is being used in the proofs.\n\n6. Thanks for pointing out the technical novelty, although they are a bit limited.\n", "summary_of_the_paper": "This paper provides a new federated optimization method: FedPAGE, based on the recent variance-reduction based PAGE method. Latter is designed to solves smooth non-convex optimization problem. FedPAGE improves over variance reduction-based SCAFFOLD algorithm in both smooth convex and smooth non-convex settings. Finally the paper provides some numerical experiments to compare FedPAGE, PAGE, FedAvg, and SCAFFOLD.", "summary_of_the_review": "Results seems promising. However there isn’t enough discussion of limitations, novelty, and comparison to some baselines.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ALjdmT_8UKp", "reviewer": "Reviewer_tXTB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1)  Adapting PAGE algorithm into federated setting with probabilistic local updates reduces the communication complexity on both federated convex and nonconvex optimization.\n2) Numerical experiments demonstrates the effectiveness of multiples local update steps.\n\nWeaknesses:\n1) Lack of analysis on test performance. Numerical experiments show that FedPAGE converges much faster than the comparison methods. How is the performance on test settings? Does the proposed optimization method achieve comparable or even better performance beyond convergence speed?", "summary_of_the_paper": "This paper proposes a new federated learning algorithm to reduce the communication cost on both federated convex and nonconvex optimization by applying optimal PAGE method into the federated setting and running multiple local update steps on clients before communicating to the orchestrating server. Experiments verifies the effectiveness of multiple local update steps and its superiority over other methods.\nContributions:\n1)  Adapting PAGE algorithm into federated setting with probabilistic local updates reduces the communication complexity on both federated convex and nonconvex optimization.\n2) Numerical experiments demonstrates the effectiveness of multiples local update steps.\n", "summary_of_the_review": " Reducing the communication cost  with multiple local updates by applying PAGE in federated optimization.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8Zp7bMbHiY", "reviewer": "Reviewer_Xsi6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Table 1: the convergence round does not account for the full-participation round. a) This communication round should be included as communication rounds b) the comparison with other algorithms is *unfair* since the other algorithms never allow for a full participation round.\n    - To make the above point clearer, let us consider Distributed-SVRG (with, say only 1 local step). Distributed-SVRG only requires O(1/ε) rounds of full participation, and O(L/ε) rounds of sampling. The total communication round is only O(L/ε).\n\n2. The paper assumes a strong, non-standard assumption (in FL study) that each client can access the *deterministic* gradient oracle of the local objective. The table 1 compares their results with FedAvg / SCAFFOLD, but all these methods are tailored for stochastic gradient oracle.\n\n3. Significancy: The main Theorem 1 and Theorem 2, are trivial applications of the PAGE with no local steps. The argument follows by the statement that running K > 1 of local steps are not worse than running K = 1 step. As a result of this trivial application, running K>1 local step gives no improvement.\n\n===\n\nI read the response and decided to keep my initial score.", "summary_of_the_paper": "This paper proposes FedPAGE, a federated variant of PAGE, which is claimed to attain the SOTA communication efficiency theoretically.", "summary_of_the_review": " My main concern of this work lies in the significancy of the results, and improper comparison with other algorithms.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new federated learning method which uses the recently developed PAGE gradient estimator in the local updates, and provides convergence analysis for both convex and nonconvex loss functions. There are several technical questions raised by the reviewers that are not addressed by the author rebuttal. Given such technical issues and limited novelty and empirical evidence, I cannot recommend acceptance.
Decision: Reject