SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning
Authors: Paul Mangold
Sergey Samsonov
Safwan Labbi
Ilya Levin
Reda ALAMI
Alexey Naumov
Eric Moulines
Venue: NeurIPS 2024 poster (2024)
Keywords: Stochastic Approximation
Reinforcement learning
Federated Learning
Machine Learning
Primary area: reinforcement_learning
TL;DR: We perform a non-asymptotic analysis of federated LSA, study the impcaft of heterogeneity, and propose a method that mitigates this impact by using control variates while preserving the linear speed-up. We apply the results to federated TD.

Abstract: In this paper, we analyze the sample and communication complexity of the federated linear stochastic approximation (FedLSA) algorithm. We explicitly quantify the effects of local training with agent heterogeneity. We show that the communication complexity of FedLSA scales polynomially with the inverse of the desired accuracy ϵ. To overcome this, we propose SCAFFLSA a new variant of FedLSA that uses control variates to correct for client drift, and establish its sample and communication complexities. We show that for statistically heterogeneous agents, its communication complexity scales logarithmically with the desired accuracy, similar to Scaffnew. An important finding is that, compared to the existing results for Scaffnew, the sample complexity scales with the inverse of the number of agents, a property referred to as linear speed-up. Achieving this linear speed-up requires completely new theoretical arguments. We apply the proposed method to federated temporal difference learning with linear function approximation and analyze the corresponding complexity improvements.

SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning
Paul Mangold CMAP, UMR 7641, Ecole polytechnique
Sergey Samsonov HSE University, Russia
Safwan Labbi CMAP, UMR 7641, École polytechnique
Ilya Levin HSE University, Russia
Reda Alami
Alexey Naumov
Eric Moulines CMAP, UMR 7641, École polytechnique MZBUAI
Technology Innovation Institute, 9639 Masdar City, Abu Dhabi, United Arab Emirates
HSE University,
Steklov Mathematical Institute of Russian Academy of Sciences
Abstract
In this paper, we analyze the sample and communication complexity of the feder- ated linear stochastic approximation (FedLSA) algorithm. We explicitly quantify the effects of local training with agent heterogeneity. We show that the communi- cation complexity of FedLSA scales polynomially with the inverse of the desired accuracy c. To overcome this, we propose SCAFFLSA, a new variant of FedLSA that uses control variates to correct for client drift, and establish its sample and communication complexities. We show that for statistically heterogeneous agents, its communication complexity scales logarithmically with the desired accuracy, similar to Scaffnew [37] An important finding is that, compared to the existing results for Scaffnew, the sample complexity scales with the inverse of the number agents, a property referred to as linear speed-up. Achieving this linear speed-up -up requires completely to federated temporal difference learning with linear function approximation and analyze the corresponding complexity improvements.
theoretical arguments. We apply the proposed method
Introduction
Heterogeneity has a major impact on communication complexity in federated learning (FL)
In FL, multiple agents use different local oracles to update global model together. A central server then performs consensus step to incrementally update the global model. Since communication with the server is costly, reducing the frequency of the consensus steps is central challenge. At the same time, limiting communications induces client drift when agents are heterogeneous, biasing them towards their local solutions. This issue has mostly been discussed for FL with stochastic gradient methods (23 [5]. In this paper, we investigate the impact of heterogeneity in the field of federated linear stochastic approximation (federated LSA). The goal is to solve system of linear equations where (i) the system matrix and the corresponding objective are only accessible via stochastic oracles, and (ii) these oracles are distributed over ensemble of heterogeneous agents. This problem can be solved with the FedLSA method, which performs LSA locally with periodic consensus steps. This approach suffers from two major drawbacks: heterogeneity bias, and high variance of local oracles.
popular means of overcoming heterogeneity problems is the method of control variables, which goes back to the line of research initiated by 23 However, existing results on the complexity of these methods tend to neglect the linear decrease of the mean squared error (MSE) of the algorithm with the number of agents N [37,, or they require a lot of communication 23 In this paper, we
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Communication and sample complexity for finding a solution with MSE lower than e² for FedLSA, Scaffnew, and SCAFFLSA with i..d. samples (see Cor. 4.3 for results with Markovian samples). Our analysis is the first to show that FedLSA exhibits linear speed-up. as well as its variant that reduces bias using control variates.
Algorithm
Communication T
Local updates H
Sample complexity TH
FedLSA 12
0
Na
log !
N² a=c
log _
a²c
FedLSA (Cor.
4.3
log !)
Natez log 4
a
Scaffnew (Cor.
1 log
log 1
SCAFFLSA (Cor.
5.2
a log
Note2 log
show that it is possible to reduce communication complexity using control variates while preserving the linear speed-up up in terms of sample complexity. Our contributions are the following:
We provide the sample and communication complexity of the FedLSA algorithm, inspired by the work of [51]. Our analysis highlights the relationship between the MSE of the FedLSA method and three key factors: the number of local updates, the step size, and the number of agents. We provide an exact analytical formulation of the algorithm's bias, which is confirmed in our numerical study. We also give results under Markovian noise sampling.
We propose SCAFFLSA, a method that provably reduces communication while maintaining linear speed-up in the number of agents. This method uses control variates to allow for extended local training. We establish finite sample and communication complexity for SCAFFLSA. Our study is based on a new analysis technique, that carefully tracks the fluctuations of the parameters and ccommunicationsontro) variates. This allows to prove that SCAFFLSA simultanously maintains linear speedup and reduced communication. To our knowledge, this the first time that these two phenomenons are proven to oceur simultaneously in FI..
We apply both these methods to TD learning with linear function approximation, where heterogeneous agents collaboratively estimate the value function of a common policy.
We provide synthetic overview of this paper's theoretical results in Table in the general federated LSA setting, and we instantiate these results for federated TD learning in Table 2 (Appendix EE) We start by discussing related work in Section [ We then introduce federated LSA in Section 3 and
analyze it in Section 4 In Section 5 we introduce SCAFFLSA, novel strategy to mitigate the bias.
Finally, we illustrate our results numerically in Section 6 Since an important application of ISA
is TD learning [47] with linear function approximation, we instantiate the results of Section 3 5 for
federated TD learning.
Notations.
For matrix A we denote by ||Al its operator norm. Setting N for the number of agents, we use the notation E. [ac] = N ---2a _ de for the average over different clients. For the matrix A T 2 0, E Rddxd and x E Rdd we define the corresponding norm ||ا|| Vx T Ar. For sequences a, and b,, we write an $ b, if there exists a constant >> 0 such that S cb,, for n 2 0.
2 Related Work
Federated Learning. With few exceptions (see e.g. 112). most of the FL literature is devoted to federated stochastic gradient (SG) methods. A strong focus has been placed on the Federated Averaging (FedAvg) algorithm (36), which aims to reduce communication through local training, resulting in local drift when agents are heterogeneous [53]. Sample and communication complexity of FedAvg were investigated under variety of conditions covering both homogencous B1 20) and heterogeneous agents 25, 27.. Different ways of measuring heterogeneity for FedAvg have then 41).
been proposed [1) In 44 it was also shown that FedAvg yields linear speedup in the number of agents when gradients are stochastic, a phenomenon that we prove is still present in FedLSA.
In order to correct the client drift of FedAvg, 23 proposed Scaffold, method that tames hetero- geneity using control variates. 17 38 prove that Scaffold retrieves the rate of convergence of the gradient descent independently of heterogeneity, although without benefit from local training. It has

---

Algorithm 1 FedLSA
Input: 7/ 0, 0n E IR T, N, H
for (. to
do
Initialize 02,0 = 0z
for for h == to H do Receive i and perform local update: 0t,1 = 0T,h-11 '7 (2,,) - (2(
do
Aggregate local updates 0c+1 = + 2. 0f
been shown in 37 (with the analysis of ProxSkip, which generalizes Scaffold) that such methods accelerate training. However, unlike Scaffold, the analysis (37 loses the linear speedup in the number of agents. Several other methods with accelerated rates have been proposed RS 18 21),
albeit all of them lose the linear speedup. Contrary to these papers, we show that our approach to FedLSA with control variates preserves both the acceleration and the linear speedup.
Federated TD learning. Temporal difference (TD) learning has a long history in policy evaluation
47 91. with the asymptotic analysis under linear function approximation (LFA) setting performed in
49 488. Several non non-asymptotic MSE analyses have been carried out in 44 8
32
45). Much
attention has been paid to federated reinforcement learning 33 43 52 and federated TD learning with LFA. [26] 7 34] provides an analysis under the strong homogeneity assumption. Federated TD was also investigated with heterogeneous agents, first without local training [12], then with local training but without linear acceleration [1] [2]. Recently, (50) proposed an analysis federated TD with heterogeneous agents, local training, and linear speed-up in number of agents. However, (50) do not mitigate the local drift effects, and their conclusions are valid only in the low-heterogeneity setting. In high heterogeneity settings, their analysis exhibits large bias. Additionally, their analysis requires the server to project aggregated iterates to a ball of unknown radius. In contrast, our analysis shows that FedLSA converges to the true solution without bias even without such projection.
3 Federated Linear Stochastic Approximation and TD learning
3.1 Federated Linear Stochastic Approximation
In federated linear stochastic approximation, N 'ggents collaboratively solve system linear equation system with the following finite sum structure
A0,- b, where A = Ea Ac, b D= b
where for [M]. A Rdxdd be E Rdd We assume the solution 0, to be unique, and that each local system A c0C = be also has unique solution 0,, The values of A " and bo's can be different, representing the different realities of the agents. federated LSA, neither matrices A nor vectors b are observed directly. Instead, each agent E [N] has access to its own observation sequence (Zi)kEN, that are independent from one agent to another. Agent e obtains estimates (AA()E) b (z())) ( of A and b", where A Z dddd and ba Z Rd are two measurable functions. Naturally, we define the error of estimation of À and 5e as b²(2) b²(z) - b. A ( A (2) - A This
allows to measure the noise at local and global solutions as
(<)) À (=)00 -b((), and (²(2) (²)=0, -b((s),
(2)
together with the associated covariances,
E - (=) dd.(()) E >2- (z) d=)(2), ES - (2) (3)
that are finite whenever one of the following assumptions on the h. hold.
A1. For each agent (Z))keN are i.i.d. random variables with values in (Z, 2) and distribution ne satisfying Ex. [A a (ZE)] = A and Ex, [b(Z]] = be, and define CA sup, ||

---

A2. For each E [ KEN is Markov chain with values in (Z, 2), with Markov kernel P.-- The kernel P. admits a unique invariant distribution Te. Z Tes and P. is uniformly geometrically ergodic, that is, there exist mmix (c) E M, such that for any k E N,
sup (1/2) -P-0-2)) S (1/4) (1/4) [1/Tmx())) 2,-'ZZ
for E [AV, we have 1E,, [A (Z1)] = A and Ex. [((i) = bs, and we define
||e||x = max sup | (z)l < x0, CA max sup [A <0.
=EZ
NE[N] zEZ
Moreover, each of the matrices - A is Hurwitz.
In A2 random matrices (z) and noise variables (2) are almost surely bounded. This necessary for working with the uniformly geometrically ergodic Markov kernels P.. For simplicity, we state most of our results using AT which is classical in finite-time studies of LSA [46] 14]. Nonetheless, we show that our analysis of FedLSA can be extended to the Markovian setting under AB
In a federated environment, agents can only communicate via central server, which is generally costly. Hence, in FedLSA, agents' local updates are only aggregated after given time, During the round 2 the agents start with shared value O, and perform H 0 local updates, for h to H, given by the recurrence
6i =
- - 00 f- (Z,,))
with 0% = 6,, and where we use the alias Zí,; ZHeth to simplify notations. Agents then send 0.H to the server, that aggregates them as 0₂ N -' 05-1. and sends back all agents. We summarize this procedure in Algorithm [ Our next assumption, which holds whenever A is Hurwitz [19 39 13), ensures the stability of the local updates.
A3. There exist a > O, Tee > O, such that 7 I 1/2, and for n E (0; noo), c E [M]. a E Rd, holds for Zg- ~ Te. that E [[[(I - n (2)) Ju s (1 na)[|ul|.
3.2 Federated Temporal Difference Learning
A major application of FedLSA is federated TD learning with linear function approximation. Consider N Markov Decision Processes {(S, A, PMDDe 1" ( with shared state space S, action space A, and discounting factor 7 E (0, 1). Each agent E [N] has its own transition kernel MDP. where ( a) specifies the transition probability from state upon taking action a for this specific agent, as well as its own reward function rf S A + [0, 1], that we assume to be deterministic for simplicity. Agents' heterogeneity lies in the different transition kernels and reward functions, that are specific to each agent.
In federated TD learning, all agents use the same shared policy x, and aim to construct single shared function, that simultaneously approximates all value functions, defined as, for s E S and c [N].
Ve (s) = E Σ E (S A4)] with Sp = s, Ag ~ T (-1Sf), and + ~ Pr (-1S Ag)
In the following, we aim to approximate (s. as linear combination of features built using a mapping & S - Rd. Formally, we look for 0 E Rd such that the function Vo(s) = o (s) properly estimate the true value. For E [NV, we denote je" the invariant distribution over S induced by the policy ग and transition kernel MDD of agent c. Our goal is to find a parameter 0 which is defined as unique solution to the projected Bellman equation, see [49), which defines the best linear approximation of Ve,a This problem can be cast as a federated LSA problem [2 50 by viewing the local optimum parameter 0 the solution of the system A = be where
A Ex (ttp:///....essassosas (1))))))))11(1((((0)(66))7))71)) = and 5 = B (o(s)) (o) (5)
The global optimal parameter is then defined as the solution 0. of the averaged system ( E' A9)0,- = +/2 Ei= bc. As it is the case for federated LSA, this parameter may give better overall estimation of the value function. Indeed, the distribution def of some agents may be

---

strongly biased towards some states, whereas obtaining estimation that is more balanced across all states may be more relevant.
In practice, when computing value functions, the tuples {(S), Ag (1+1)) are sampled along one of the two following rules.
TD 1.
(sg. : Age 1 are generated i.i.d.with Si ~ pe, A x(115)) 11+ Pime (-15% 44)
2. (5 Ag, 1t+1) are generated sequentially with A ~ (-1SE) S1+1 Mar [St, AE)
The generative model assumption TD is common in TD learning 8
is possible to generalize all our results to the more general Assumption TD2 sampling over a single trajectory and leveraging the Markovian noise dynamics. This would have a similar impact on our results TD(0)
30
42
45
as it has on the ones we will present for general FedLSA in Section 4 In our analysis, we require the following assumption on the feature design matrix D E (p(()) ] Rdxd
TD 3. Matrices Nx are non-degenerate with the minimal eigenvalue mince[N] Amin (Eg) > 0. Moreover, the feature mapping (-). satisfies supses
[|<(()]| 1.
This assumption ensures the uniqueness of the optimal parameter 0%. Under TD and TD we check
the LSA assumptions and AB and the following holds.
Claim 3.1. Assume 7
and TD
Then the sequence of TD(O) updates satisfies A7 and A with
CA=1+1
2(1 7)
Tr(2.) s 2(1 7)² (110211 + +1)
(1-22
2
Toc
We prove this claim in Appendix E. and refer to 45 for more details on the link between TD and linear stochastic approximation.
4 Refined Analysis of the FedLSA Algorithm
4.1 Stochastic expansion for FedLSA
We use the error expansion framework
[ [4] for LSA to analyze the MSE of the es-
timates 0r generated by Algorithm
For this purpose, we rewrite local update (4) as (E,,), where e²(2) is defined in 2 Running this
of,, 0f (I - (Zr,) (O in-
recursion until the start of local training, we obtain
0 H
8 r(az) 10f,0 80) E b=1 f (Zi,))
(lan)
where (2) is as and we recall that fi 0,-1, Vc E [N]. We also introduced the notation
(e.n)
f,men = II (1 - ( (2,,,))
1 < m m
with the convention I
(c..)
[.mmn = for m > n. Note that by A ((c.)
Lmmn is exponentially stable. That
is, for any h E N, we have |1/2 |||I [(.))
t,mem u|/= < (1 na ||||| Using the fact 0f 0,-1. and
employing I we obtain that
0, 0,
[()) (0, 0.] + PH + F,11 11Pt.11
with I. - N
- 611
(e.))
(6)
where F = 1 (1-
(c.n) 1,1:8 |000 -0.), FI. =
1 N E H1 (lam)
1.411 (Z,,))
N
are zero-mean fluctuation terms, and
Ph = -I--
0.}
the deterministic heterogeneity bias accumulated in one round of local training. Note that PH vanishes when either (i) agents are homogeneous, or (ii) number of local updates is H 1. To analyze FedLSA, we run the recurrence (6) to obtain the decomposition
0r 0, o(tr) (ibibi) ((1))
Here 0i = II', (n) H (0, - 9.} a transient term that vanishes geometrically, ((()) is zero-mean
fluctuation term, with detailed expression provided in Appendix A and the term (bb.
(l. = E'=1(" pp where r(y) (T s.Hl
and accounts for the bias of FedLSA due to local training, that vanishes whenever #H 0.
5

---

4.2 Convergence rate of FedLSA for ii.d. observation model
First, analyze the rate which FedLSA converges biased solution 04 + + two quantities, which stem from the heterogeneity and stochasticity of the local estimators, play central role in this rate
@(bi.b) The following
o. [Tr(Eg)] Theter
E
|
111e 0-122
Here 0g and theter correspond to the different sources of noise in the error decomposition 7 The term og is related to the variance the local LSA iterate on each the agents, while Uheter controls the bias fluctuation term. In the centralized setting (i.e. if N 1), the theter term disappears, but not the O- term. We now proceed to analyze the MSE of the iterates of FedLSA:
Theorem 4.1. Assume A and A3
Then for any step size 1 E (0, Vho) holds that
E1/2 [10,, @(bi.bi) 1 S
1
3e |1 II]
|
+ nna) [ 0+1
ON
where the bias 0. ((b..bb)) converges in expectation to Tlbi.bi) (b.bb))
(1 F(1)
''pn > pn at a geometric rate, and
uniformly bounded by E E 1 -
a
The proof of Theorem 4.1 relies on bounding each term from We provide a proof with explicit
constants in Appendix A Importantly, the fluctuation terms scale linearly with N. Moreover, in centralized setting (that is, N 1), the bias terms Pr. 0g 0(bibi) and Uheter vanish in Theorem 4. yielding the last-iterate bound
E/2 110 0.11
V n0c + -1-naa)t
na)
2 1,00 9-11
which is known to be sharp in its dependence on v for single-agent LSA (see Theorem in 15 Based Claim 3.1 Theorem 4. translates for federated TD(0) as follows.
Corollary 4.2. Assume 7 and TD TD(O) satisfyy with x(0,, B!................... ..... ON)
Then for any step size 7] E (0, 1-) the iterates of federated
E16 0. 1 (1 Eg A: (T).
E E1/2 1 @(b.bbi)) 0 1 10.0..00 10..........00 (1- (1-2)oN
|P
o(1
cH 1110 0+1l
HN (1->)
The right-hand side of Corollary 4.2 scales linearly with N, allowing for linear speed-up. This is in line with recent results federated TD(O), which shows linear speed-up either without local training 7 or up to a possibly large bias term (50] (see analysis of their Theorem 2). While Corollary 4.2 shows the algorithm's 's convergence to some fixed, biased value, one can the parameters of FedLSA such that this bias is small. This allows to rewrite the result of Theorem 4.1 in order to get sample complexity bound in the following form.
Let H 1, and 0 <e< (Vihoe Vor Teg |10: P. 11)
E. 11 ..
Corollary 4.3. Assume Al A and A3
CC
Set the step size = O Tune Vo
oN
A Aoo) and the number of local steps H = O
1. 9. Ne). Then,
to achieve EE| [[[0 - 0-1
< 2² the required number of communication, for federated LSA is
T == ((-))) Ball00--8111
log |16.-0.1|
07730
the number oracle calls scales as TH 0 Vā log 100-0.1l) which shows No
In Corollary 4.3, that FedLSA has linear speed-up. Importantly, the number of communications 7 required to achieve precision e² scales as -1 In the next section, we will show how this dependence on c can be reduced from polynomial logarithmic. Now state the communication bound of federated TD(0). Corollary 4.4. Assume TD
! and TD
Then for any 0 < << 91 (.)) with
01 ( ||l. E|) 1.)... Set O
(1-))NN2 (.(1EEI1)++1 and H O achieve [[[0T 0.1 [ e², the required number of communications for federated TD(0)
B. 1.110011 +1 1.] Then,
NeE.
o ((1-))
Eellee--o (1-2)"0a
100 [00-0.11]
log
is the first result to show that, even with local training and heterogeneous agents, federated TD()) can converge to 0, with arbitrary precision. Importantly, this result preserves the linear speed-up effect, showing that federated learning indeed accelerates the training.
Corollary
4.4

---

4.3 Convergence of FedLSA under Markovian observations model
The analysis of FedLSA can be generalized the setting where observations { KEN form Markov chain with kernel Pe. To handle the Markovian nature of observations, we propose variant of FedLSA that skips some observations (see the full procedure in Appendix B). This follows classical schemes for Markovian data in optimization [40], adjusting the number of skipped observations (keeping about observation out of Tmix (c)) allows to control the correlation of successive observations. We may now state the counterpart of Corollary 4.3 for the Markovian
setting.
Corollary 4.5 (Corollary
4.3 adjusted to the Markov samples). Assume A2 and A and let 0 <
(V Vol Vo, 1.11 0,
V
-111100-0-111
Set the step size = O oN
A Too A T/x (M))
), where
CC
Shooe Vire
we give the expression of meo is
(M)
(37. Then, for the iterates of Algorithm
in order to achieve
E E[10T 0, 1 S è², the required number of communication is
T=o (( ((=
log 116--0.11 [= ( a=E
t
where the number of local updates H satisfies
maKe Tamix (c) log (1100 +22. 00 (1
0
Dua Be
log H
8
Ne
The proof of Corollary
4.3 follows the idea outlined in [40], using Berbee's lemma [10] We give
all the details in Appendix B This result is very similar to Corollary 4.3 Most crucially, it shows that the communication complexity is the same, regardless of the type of noise. The differences with Corollary 4.3 lie in (i) the number local updates H, that is scaled by Tmix (up to logarithmic factors). and (i)) the additional condition S Tec that allows verifying the stability of random matrix products with Markovian dependence (see Lemma B.2 in the appendix).
Remark 4.6. Although, for clarity of exposition, only state the counterpart of Corollary 4.3 in the Markovian result, all of our results can be extended to Markovian observations using the same ideas.
5 SCAFFLSA: Federated LSA with Bias Correction
5.1 Stochastic Controlled Averaging for Federated LSA
We now introduce the Stochastic Controlled Averaging for Federated LSA algorithm (SCAFFLSA), an improved version of FedLSA SA that mitigates client drift using control variates. This method is inspired by Scaffnew (see 37). SCAFFLSA. each agent e E [N] keeps local variable EE. that remains constant during each communication round t. Agents perform local updates on the current estimates of the parameters 1.0 0g for c E [N], and for h E [H).
f 0 0T 77 A (Zi,, ) bd (Z -
At the end of the round, (i) the agents communicate the current estimate to the central server, (ii) the central server averages local iterates, and (iii) agents update their local control variates; see Algorithm 2 By defining the ideal control variates at the global solution, given by & = A - - A-
we can rewrite the local update as
, 8, (I- AI ( (Z),)))( 0.) + tn(Ef (.) nw (Zi,))
(8)
where (z) is defined in 2 Under All it has finite covariance DS = Jz w (2 (z)w (z)=((2)) TT)
Similarly to the analysis of SA, we use (8) to describe the sequence of aggregated iterates and control variates as, for t > 0 and c [N].
0++1 0, = (()) (0t 0.) + 2 I (
- - - m0++1
{ c E. E. + म (0.+1 0,,
where Oh Σ
(cn) -h=1- 1,++1: and ãet1 1/2 EN Ei th+1:H (ZE,)) We now state the
[(an)
(c.n)
convergence rate, as well as sample and communication complexity of Algorithm 2
7

---

Algorithm 2 SCAFFLSA: Stochastic Controlled FedLSA with deterministic communication
Input: > 0, 0o, Sü E R N,N,H
for 1 1 T do
for c 1 to do
Set 00 = 0r
for h = to H do Receive Zi, and perform local update Di,n -h.h--nn(A- - -b((Z,,)) -{E)
Aggregate local iterates: 0--1 N Σ 05
Update local control variates: Li+1 33 nH (0++1 09,H1)
Theorem 5.1. Assume A7 A3 Let n, H 0 such that 1) S Yoor and H S 9/2200 {ca +1 J. Set SU for all [M]. Then we have
El10r - 0,1191 Ne الس| + (1
naH 2
{1100 0.12 1 || (0, -0.)1(]]
Corollary 5.2. Let O. Set the step size nj ( Noc/=)) fa)) and the number local updates
to = O (max( ([ +I NeI + +1
Then, to achieve B| 1. I e², the required
number communication for SCAFFLSA is
T T= C ++ log
10 +E|IIA (00IIA((00011l00))
We provide detailed proof of these statements Appendix C They are based on a novel analysis, where we study virtual parameters ii,,. that follow the same update as (8. without the last term yuu (Zū,), After each round, virtual parameters are aggregated, and virtual control variate updated as
0++1- - 0.
M 0i, and E Es ES 5c + Hn (0.+1 00.H).
This allows to decompose
0, 0, = 0. 0. + 0e and E - E-- Et E + E
where 0, - O, and & c are transient terms, and O, = O, O, and E = Ef E capture the fluctuations of the parameters and control variates.
We stress that our analysis shows that, comparison with FedLSA. the SCAFFLSA algorithm reduces communication complexity while preserving the linear speed-up in the number of agents. This is in stark contrast with existing analyses of control-variate methods heterogeneous federated learning, that either have large communication cost, or lose the linear speed-up [4 37 21
To obtain
this result, conduct very careful analysis of the propagation of variances and covariances of 9, and & between successive communication rounds. We describe this in full detail Appendix C.2
In Corollary 5.2 we show that the total number of communications depends only logarithmically on the precision This is in stark contrast with Algorithm [ where the necessity of controlling the bias' magnitude prevents from scaling H with l/c. Additionally, this shows that the number of required local updates reduces as the number of agents grows. Thus, in the high precision regime (i.e.small and 7)), using control variates reduces communication complexity compared to FedLSA.
5.2 Application to Federated TD())
Applying SCAFFLSA to TD learning, we obtain SCAFFTD(0) (see Algorithm 5 Appendix E). The analysis of SCAFFLSA directly translates to SCAFFTD())) resulting the following commu- nication complexity bound.
Corollary 5.3. Assume TD and TD and ler < C /8E, +
|c | - 7))). Set the
step size 17 O ( (1-7)uNee) and the number local updates to H O
|
Then, to achieve
||||||
Ne
E 0. [| < 2. the required number of communication for SCAFFTD(O) is
T= 0
( log
[10-0 +(1 +(1-7)=B(11
8

---

10'
10
101
10
10
10
10-
FedESA
10
10-3
10-3
40
10
30
50
10
Communiestioos (X00000)
Communacstions 1x:
Commaniiaioons (xx 1000)
Commamiations (x100)
(a) Heterogeneous.
(b) Heterogeneous.
(c) Heterogeneous.
(d) Heterogeneous.
N 10, H 10
N = 10, H 1000
N 100, H = 10
N 100, H 1000
10
10
10
POIEA
STAFTISA
10-1
10-1-
10-1
10-1
FUEEAAS lio
10
10
10
10-5
0
20
40
13
30
40
50
10
20
30
20
50
0
20
Commaniicctions (x1000)
Communaicttinn
(x10)
Communiicttios (x1000)
Commomictiions (x10)
(c) Homogencous,
(1) Homogeneous,
(g) Homogeneous,
(h) Homogeneous,
N 10, H = 10
N = 10, H = 1000
N 100, H = 10
N = 100, H 1000
Figure 1: MSE as function of the number of communication rounds for FedLSA and SCAFFLSA applied federated TD(O) in homogeneous and heterogeneous settings, for different number of agents and number of local steps. Green dashed line is FedLSA's bias, as predicted by Theorem 4.1 For each algorithm, we report the average MSE and variance over 5 runs.
Corollary 5.3 confirms that, when applied TD(0), SCAFFLSA's communication complexity depends only logarithmically on heterogeneity and on the desired precision. In contrast with existing methods for federated TD(0) [1] 22 50), converges even with many local steps, whose number diminishes linearly with the number of agents N, producing the linear speed-up effect.
Remark 5.4. Appendix F we extend the analysis Scaffnew [37] to the LSA setting. Their analysis does not exploit the fact that agents' estimators are not correlated, and thus lose the linear speed-up. In contrast, our novel analysis technique carefully tracks correlations between parameters and control variates throughout the run of the algorithm.
Numerical Experiments
In this section, we demonstrate the performance of FedLSA and SCAFFLSA under varying levels of heterogeneity. We consider the Garnet problem [2] [6). with n 30 states embedded dimensions, a = 2 actions, and each state is linked to = 2 others in the transition kernel. We aim to estimate the value function of the policy which chooses actions uniformly at random, in homogeneous and heterogeneous setups. In all experiments, we initialize the algorithms in neighborhood of the solution, allowing observe both transient and stationary regimes. We provide all details regarding the experimental setup in Appendix G Our code is available either supplementary material or online on GitHub: httpp:: //github. www.///magood////oooooooooooooee scaffl/f/scfassee/
SCAFFLSA properly handles heterogeneity. This heterogeneous scenario is composed of two different Garnet environments, that are each held by half of the agents, with small perturbations. Such a setting may arise in cases where each agent's environment reflects only a part of the world. For instance, half of the individuals live in the city, while the other half live in the countryside: both have different observations, but learning a shared value function gives better representation of the overall reality. Figures (a) I(d) we plot the MSE with N E (10, 100), H {10, 1000) and 1) = 0.1, with the same total number of updates TH = 500, 000. As predicted by our theory. FedLSA stalls when the number of local updates increases, and its bias (green dashed line Figures [(a) to I(d] is in line with the value predicted by our theory (see Theorem 4.1) For completeness, we plot the error of FedLSA in estimating 0, + 0[...i in Appendix G On the opposite, SCAFFLSA's bias-correction mechanism allows to eliminate all bias, improving the MSE until noise dominates.

---

0.001
0.01
8 0.1
FedLSA
SCAFFLSA
10-2
10-1
10-2
10-1
10-4
10-3
10-
10
10
10f
10a
10
10F
10a
10
10F
10a
10
10
10
Number of agents
Number of agents
Number agents
Number of agents
(a) Homogeneous,
(b) Heterogeneous,
(c) Homogeneous,
(d) Heterogencous,
H
H =
100
H 100
Figure 2: MSE, averaged over 10 runs for last iterates of FedLSA (dashed lines) and SCAFFLSA (solid lines) in the stationary regime, as a function of the number of agents, in different federated TD(O) problems. The black dotted line decreases in I/N, serving as a visual guide for linear speed-up.
Both algorithms behave alike in homogeneous settings. In the homogeneous setting, we create one instance of Garnet environment. Then, each agent receives slightly perturbed variant of this environment. This illustrates situation where all agents solve the same exact problem, but may have small divergences in their measures of states and rewards. We plot the MSE in Figures [(e) to Ih) with N E { 10., 100} agents, 1) = 0.1, and H E f100, 1000), with the same total number of updates TH = 500, 000. In this case, as predicted in Corollary 4.3 the number of local steps H has little influence on the final MSE. Since agents are homogeneous, control variates have virtually no effect, and SCAFFLSA is on par with FedLSA. The MSE is dominated by the noise term, which diminishes with the step size (see additional experiments in Appendix G with smaller v) = 0.01).
Both algorithms enjoy linear speed-up! In Figure 2 we plot the MSE obtained once algorithms reach the stationary regime,
function of the number of agents N E {0.001, 0.01, 0,1, 1} and H E {1, 100], in both homogencous and heterogencous settings. Whenever (i) agents are homogeneous, or (ii) the number of local steps is small, both FedLSA and SCAFFLSA can achieve similar precision with a step size that increases with the number of agents. This allows to use larger step sizes, so as to reach a given precision level faster, resulting in the so-called linear speed-up. However, when agents are heterogeneous and the number of local updates increases, FedLSA loses the speed-up due large bias. Remarkably, and as explained by our theory (see Corollary 5.2). SCAFFLSA maintains this speed-up even in heterogeneous settings.
1000, for step sizes
7 Conclusion
In this paper, we studied the role of heterogeneity in federated linear stochastic approximation. We proposed new analysis of FedLSA, where we formally characterize FedLSA's ' bias. This allows to show that, with proper byperparameter setting, FedLSA (i) can converge to arbitrary precision even with local training. and (ii) enjoys linear speed-up the number of agents. We then proposed a novel algorithm, SCAFFLSA, that uses control variates to allow for extended local training. We analyzed this method using on novel analysis technique, and formally proved that control variates reduce communication complexity of the algorithm. Importantly. our analysis shows that SCAFFLSA preserves the linear speed-up, which is the first time that federated algorithm provably accelerates while preserving this linear speed-up. Finally, we instantiated our results for federated TD learning, and conducted an empirical study that demonstrates the soundness of our theory in this setting.
Acknowledgement
The work of P. Mangold and S. Labbi has been supported by Technology Innovation Institute (TI). project Fed2Learn. The work of E. Moulines has been partly funded by the European Union (ERC- 1022-SG--OCEAN--00001106
Views and opinions expressed are however those of the author(s)
only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. The work of I. Levin, A. Naumov and S. Samsonov prepared within the framework of the
10

---

HSE University Basic Research Program. This research was supported in part through computational resources of HPC facilities at HSE University (29
References
[1] Rafik Aguech, Eric Moulines, and Pierre Priouret On a perturbation approach for the analysis of stochastic tracking algorithms. SIAM Journal on Control and Optimization, 39(3):872-899, 2000.
[2] TW Archibald, KIM McKinnon, and LC Thomas. On the generation of markov decision processes. Journal of the Operational Research Society, 46(3):354 161544--6,111 1995.
[3] H.C.P. Berbee. Random Walks with Stationary Increments and Renewal Theory. Mathematical Centre tracts. Centrum Voor Wiskunde en Informatica, 1979.
[4] J. Bhandari, D. Russo, and R. Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference On Learning Theory, pages 1691-1692, 2018.
[5] Laurent Condat, Ivan Agarsky, and Peter Richtárik. Provably doubly accelerated federated learning: The first theoretically successful combination of local training and compressed communication. arXiv preprint 2xXiv:2210.13277 2022.
[6] Laurent Condat and Peter Richtárik. Randprox: Primal-dual optimization algorithms with randomized proximal updates. arXiv preprint vrXiv22207.12891 2022.
[7] Nicolò Dal Fabbro, Aritra Mitra, and George Pappas. Federated learning over finite-rate erasure channels: Linear speedup under markovian sampling. IEEE Control Systems Letters, 2023.
[8] G. Dalal, Balázs Szörényi, G. Thoppe, and S. Mannor. Finite sample analyses for TD(0) with function approximation. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
[9] Christoph Dann, Gerhard Neumann, Jan Peters, al. Policy evaluation with temporal dif- ferences: A survey and comparison. Journal of Machine Learning Research, 15:809-883, 2014.
[10] Jérôme Dedecker and Sana Louhichi. Maximal inequalities and empirical central limit theorems. In Empirical process techniques for dependent data, pages 137-159. Springer, 2002.
[11] Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-Time Analysis of Distributed TD(0) with Linear Function Approximation on Multi-Agent Reinforcement Learning. In Proceedings of the 36th International Conference on Machine Learning, pages 1626-1635. PMLR, May 2019. ISSN: 2640-3498.
[12] Thinh T Doan. Local stochastic approximation: A unified view of federated learning and distributed multi-task reinforcement learning algorithms. arXiv preprint arXiv:2006. 13460, 2020.
[13] R. Douc, E. Moulines, Priouret, and Soulier. Markov chains. Springer Series Operations Research and Financial Engineering. Springer, 2018
[14] Alain Durmus, Eric Moulines, Alexey Naumov, and Sergey Samsonov. Finite-time high- probability bounds for Polyak-Rupper averaged iterates of linear stochastic approximation. Mathematics of Operations Research, 2024.
[15] Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Kevin Scaman, and Hoi-To Wai. Tight high probability bounds for linear stochastic approximation with fixed stepsize. In M. Ranzato, Beygelzimer, K. Nguyen, P. S. Liang, W. Vaughan, and Y. Dauphin, editors. Advances in Neural Information Processing Systems, volume 34, pages 30063-30074, Curran Associates, Inc., 2021.
[16] Matthie Geist, Bruno Scherrer, et al. Off-policy learning with eligibility traces: a survey. Mach. Learn. Res., 15(1):289 2014.

---

[17] Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pages 3564. PMLR, 2021.
[18] Michal Grudzieñ, Grigory Malinovsky, and Peter Richtárik. Can 5th generation local training methods support client sampling? Yes! In International Conference on Artificial Intelligence and Statistics, pages 1092- PMLR, 2023.
[19] L. Guo and L. Ljung. Exponential stability of general tracking algorithms. IEEE Transactions on Automatic Control, 40(8):1376-1333 1995.
[20] Farzin Haddadpour and Mehrdad Mahdavi. On the Convergence of Local Descent Methods in Federated Learning, December 2019. arXiv: 14425 [cs, stat].
[21] Zhengmian Hu and Heng Huang. Tighter analysis for proxskip. In International Conference on Machine Learning, pages
PMLR, 2023.
[22] Hao Jin, Yang Peng, Wenhao Yang. Shusen Wang, and Zhihua Zhang. Federated Reinforcement Learning with Enviromment Heterogeneity. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 18 18-37. PMLR, May 2022. ISSN:
[23] 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 machine learning, pages 51 5132-5143, PMLR, 2020.
[24] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning, 2021.
[25] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519-4529, PMLR, 2020.
[26] Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated rein- forcement learning: Linear speedup under markovian sampling. International Conference on Machine Learning, pages (0997-11057) PMLR, 2022.
[27] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393. PMLR, 2020.
[28] Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimiza- tion: Distributed machine learning for on-device intelligence. arXiv preprint 1rX.0:1610.02527. 2016.
[29] PS Kostenetskiy, RA Chulkevich, and VI Kozyrev. Hpc resources of the higher school of economics. In Journal of Physics: Conference Series, volume 1740, page 012050. IOP Publishing, 2021.
[30] Gen Li, Weichen Wu, Yuejie Chi, Cong Ma, Alessandro Rinaldo, and Yuting Wei. High- probability sample complexities for policy evaluation with linear function approximation. IEEE Transactions on Information Theory, 5068):5999-5999, 2024.
[31] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE signal processing magazine, 37(3):00-60, 2020.
[32] Tianjiao Li, Guanghui Lan, and Ashwin Pananjady. Accelerated and instance-optimal policy evaluation with linear function approximation. SIAM Journal on Mathematics of Data Science, 5(1):174-200, 2023.
[33] Kyo Lim, Ju- Ju-Bong Kim, Moo-Seong Heo, and Youn-Hee Han. Federated reinforcement learning for training control policies on multiple iot devices. Sensors, 20(5):1359, 2020.
[34] Rui Liu and Alex Olshevsky. Distributed TD(O) with almost no communication. IEEE Control Systems Letters, 7:2892-280 28977, 2023.
12

---

[35] Grigory Malinovsky, Kai Yi, and Peter Richtárik. Variance reduced proxskip: Algorithm, theory and application to federated learning. Advances in Neural Information Processing Systems, 15:15176-15189 2022.
[36] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiiii learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[37] Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference Machine Learning, pages 15750-15769. PMLR, 2022.
[38] Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34: 1464666664669 2021.
[39] Wenlong Mou, Chris Junchi Li, Martin J Wainwright, Peter L Bartlett, and Michael I Jor- dan. On linear stochastic approximation: Fine- sine-grained Volyak-Ruppern and non- -onmssyptooicc concentration. In Conference Learning Theory, pages 2947-2997. PMLR, 2020.
[40] Dheeraj Nagaraj. Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least squares regression with markovian data: Fundamental limits and algorithms. Advances in neural information processing systems, 33: 33:16666-1661 16676, 2020.
[41] Kumar Kshitij Patel, Margalit Glasgow, Lingxiao Wang, Nirmit Joshi, and Nathan Srebro. On the still unreasonable effectiveness of federated averaging for heterogeneous distributed learning. In Federated Learning and Analytics in Practice: Algorithmss, Systems, Applications, and Opportunities, 2023.
[42] Gandhary Patil, LA Prashanth, Dheeraj Nagaraj. and Doina Precup. Finite time analysis of tem- poral difference learning with linear function approximation: Tail averaging and regularisation. In International Conference on Artificial Intelligence and Statistics, pages 5438-5448. PMLR, 2023.
[43] Jiaju Qi. Qihao Zhou, Lei Lei, and Kan Zheng. Federated reinforcement learning: Techniques, applications, and open challenges. arXiv preprint arXiv:2108. / 11887, 2021.
[44] Zhaonan Qu, Kaixiang Lin, Zhaojian Li, and Jiayu Zhou. Federated learning's blessing: Fedavg has linear speedup. ICLR 1021-hokshhpp on Distributed and Private Machine Learning (DPML),202
[45] Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, and Eric Moulines. Improved High- Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 4511-4547. PMLR, 30 Jun Jul 2024.
[46] Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD learning. In Conference on Learning Theory, pages 2803-2830. PMLR, 2019.
[47] Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning. 3:9 44, 1988.
[48] Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast pradient-descent methods for with linear function approximation. In Proceedings of the 26th annual international conference on machine learning, pages 993-1000, 2009.
learning
[49] N. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, (2(5):674669) May 1997.
[50] Han Wang, Aritra Mitra, Hamed Hassani, George J Pappas, and James Anderson. Federated tem- poral difference learning with linear function approximation under environmental heterogeneity. arXiv preprint arXiv:2302.023 2023.
13

---

[51] Jianyu Wang, Rudrajit Das, Gauri Joshi, Satyen Kale, Zheng Xu, and Tong Zhang. On the unreasonable effectiveness of federated averaging with heterogeneous data. arXiv preprint arXiv:2206.04723, 2022.
[52] Zhijie Xie and Shenghui Song. FedKL: Tackling data heterogeneity in federated reinforcement learning by penalizing KL divergence. IEEE Journal on Selected Areas in Communications, 41(4):1227-112 1242, 2023.
[53] Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data, arXiv preprint arXiv:1806. 2018.
14

---

A Analysis of Federated Linear Stochastic Approximation
For the analysis we need to define two filtration: F == oZi 2 8, 2 h $ N). 5.4
corresponding the future events, and F&, o o 8, k S h e N). corresponding to the preceding events. Recall that the local LSA updates written
0 _ = -I- (Z,, ( - 8-) nE 4
Performing H local steps and taking average, we end up with the decomposition
0, 0- - (0:-1 0,) PH + Fr.H1 19..
(10)
where we have defined
[(()) 1,
1 N
r (c,n)
(11)
N
1,1:H
PH
(I - -1 - (1- -0,
N
o=
c=1 [(1 - A - [(an) 1, - 0.}
Ft.
N
I1
plen) 1 (Zin)
PI.
The transient term 1.H (0.-1- responsible for the rate of forgetting the previous iteration error 0 0., and the fluctuation term n reflecting the oscillations of the iterates around 0., are similar to the ones from the standard LSA error decomposition [4]. The two additional terms in (10) reflect the heterogeneity bias. This bias composed of two parts: the true bias Ри. which is non-random, and its fluctuations H.. 1.. To analyze the complexity and communication complexity of FedLSA, we run the recurrence (6) to obtain
02 0, ((tr) + 0 ((bi.bi)
+ (ff..b)) 0(9)
(12)
where we have defined
(())
s. 100 0.1
(13)
((b.b)))
(T PH
(
@(R..b))
Σ II
A (n)
TH
H.aPH
11
( " Σ
II
P...H
1=++1
with the notations (-( H. = 1
EI (1)
nA and A H.st = {IT [()) 8
H
(I yt= The first term, 0. gives the rate at which the initial error is forgotten. The terms 0. bi.bii and (( represent the bias and fluctuation due to statistical heterogeneity across agents. Note that in the special case where agents are homogeneous (i.e. A A for all [N]), these two terms vanish. Finally, the term 0hhh) depicts the fluctuations of 9, around the solution 0,. Now we need to upper bound each of the terms in decomposition (1) This is done in sequence of lemmas below:
d(th) bounded in Lemma A.1 ((A..bi)) Lemma A.2 o(tr) in Lemma A.4 and (....bb) in Lemma A.5
Then we combine the bounds in order to state version of Theorem 4.1 with explicit constants in Theorem A.6
Lemma A.I. Assume A7 and
Then, for any step size 1) E (0, no0) it holds
E 1
np;
< aN e-2)
15

---

Proof. We start from the decomposition
LB
With the definition of 0:a0 and
E²
[[Ti=ot1 1 Pa,H = O, we obtain that
p(n)
|
1J
Σ EIK (=++1
II
p(o 4
Now, using the assumption and Minkowski's inequality, we obtain that
E E [II II
[1?] -
1 N
Σ
E /
(e.n)
II
((0)
(=++1
1=++1
(14)
f-1
(1 - (1-7a) " //2
[I]
II 1=++1
( i.8
In (a) applied that
A3 conditionally on F Hence, by induction we get from the previous formulas
[110 (1) 121 (1 ma) B 11
(15)
Now proceed with bounding E that
[1 H I?² Indeed, since the clients independent, get using
12]
E
(laa)
N
c=
1
N
(em)
2.++1:H ( (2
N
h=l
N
H
na
N2
h=1
Therefore, using
3 and the following inequality,
H [ - (11-na22h
$ H A
for all 2 0. such that nj I 1,
naa
h=
we get
E 11 1121
S
H 1
no o )=
Plugging this inequality in 15
we get
E
||
(t))
122
Eg
Tr(E:)]
( " Σ
(11 naa) 2H((-8)
N
H ^ ")
1
N
1 - (1 n1)211
s nē= a 
(nahl A A
e 2maH
where we used additionally
2+ =1-r5e
(16)
which is valid for [0: 1/2]. Now it remains notice that
- e 2x < 1-e-2
for any x
We proceed with analyzing the fluctuation of the true bias component of the error 0, defined in 13)
The first step towards this to obtain the respective bound for Tx 8 E (1,..., T), where T. defined in (I]. Now we provide upper bound for O (ffbbi).
16

---

Lemma A.2. Assume A7 and A3
Then, for any step size E (0, Noo) it holds
2 2 E Illpa
E [10, ( 17 1
21funeter Na
A
aH1/2N1/22
Proof. Recall that 0, (((..bi))
is given (see
13 by
@(fibbi)
Σ II
inl HH
Σ 1=
(0) 2
(
PH
(17)
where HH and PH defined in 11 We begin with bounding TІ. In order to do it first need to bound Fa Since the different agents are independent, we have
N2 Σ (1
((an) 8,1:H) -
(18)
Applying Lemma D.1 and the fact that {(I 11--AA1-111222 ) -artingale-difference w.r.t. Fesh, we get that
+((++)::H (0) - 0.)]
h=1
E[I(([I 9)
(e,0) s.1: (00 0+31
H = =1/
Σ
A ) s.(h+1): 10, -
-
h=1
1/2
B[I[(T 7 7 A - ) (c.))
2(h+1): 10 - 1-11
Am1
-02
TE((TT(() s.(b+1):H) (AA(Za))) A A (Z (. s. 0.)
Using the tower property conditionally on F+ s. we get
()(H+))::)) (A
(T( (,(h+))
Ex ((..)
(. s,(+1)::
s,(h-1):11
where Σe is the noise covariance matrix defined |/l|| < De ||]]/, we get
Since for any vector E Rd we have
BII[([I n (00 11.111 S n7 (1 na) 2(h 1 (c.n)
(8) - -05--,3113 11
5,(6+
H
< || Σ (1 m7a) 2((-11) (c.m) s.(k+1):HH (0+ - -1
(19)
1=1
(1) E3 11 0.1
Combining the above bounds in 18) yields that
Haf 2
ΣM
|> ||100 0.11
E 12]
(20)
N2
17

---

Thus, proceeding as in together with (0)). we get
E [| =
Blll
[1)) Ts, # !|?!
H1 na) 2 2
-c=1
N
DC 1 - -0111
Á
(1- n7)) m1))2 (t)()
N2
Hn na) na)2(12 (
$
Bell A 11 - -0.1
(1 na) 2 |N
Hane 2Ha
Bell 2 A 10 0.11
aN (1 7)00²
22an
2m
E. X 10 - 0. 112]
Na
In the bound above we used
16 together with the bound
rC -v- 2x
1
S x 2 0.
e
e 2n
Now bound the second part of 0 (fllbbi)
in 17 that is, T2. To begin with, we start with applying
Lemma D.1 and we get for any 8 E [1,
f and E {s + 1 1.....f...... (). that
II (21 (1
EII 1. POO
IH TH
PH
2=s41
r=it1
Note that,
II
pHl =0
(21)
r=++
Proceeding as in 19p
we get using independence between agents for any E Rdd,
N
(r(en)
(ca))
(T- "
1.
N2
8.1:
BlI(T(()))
(I-1Aa) 9) 12
N2
8,1:1
-
Hn (1 na) ((
N
Σ
||u112
N
N
c=1
Hence, using (21). we get
H1 - na) ())))
11
10 112
N
i=a+1 Combining the above estimates in
17 and using Minkowski's 's inequality, we get
E 1
E. Ee
|
(1 - )1-na)m(e (c--))
na)
2
Hane Hon
E. Es A |
//1/2N1/2 1 Han
2
E. Ec ES |
aH1/211/2
where we used that na 1/2 and
0e x
$1,
x 0.
c-
and the statement follows.
18

---

Lemma A.3. Recall that PH = 1
N >c=1 (I - (I )) " 0. it satisfies
- 1 2 N
1i
exp(n A 1 - -.111
(22)
N
Proof. Using the identity,
H-2
H
)+²
1- (111uj) (1-u) Hu u²
(-1)*
*
k + 2 ux
(23)
k=0
and the inequality (+22) I ) we get that
Σ
1-)
R
H at 1
H² H
H
-2
1ul#
H² exp((Il - 2)/ul)
(24)
+
2
K=
k=0
Using 23 with
A for all e, we get
H-2 Hn (A9)
H
Σ
(-1)*
(n)a))
PH N
k: 2
by definition of 0 and 0., we have that E A= 0.) EN
A=
-E A9),
Ee be -E be = O. Using this and 24 we finally get 12
Lemma A.4. Assume A7 and
Then any step size 1) E (0, 7s0) we have
(( 113] < (1 raa) 100 - 0+1
Proof. Proceeding as in 14) for any u E Rdd we have
/
s. u (1 2 ||ll|
Using this result for a 0g 8, we get the statement.
Lemma A.5. Assume Al and A3 Then for any 17 (0, (oo) we have
||0 (i) (I - ( PH || $ (1 - maa H |[ --
Proof. Using AB and Minkowski's incqualitty, we get
|10| bi) (I- 1--(7) -ppll = [[I - -- (I( PHl
$ [1 - ( [T "pll
< (11 - 1 -')))
[[ - 1/ (I 1-1
( ppll
(m))
( PHl
and the statement follows.
Theorem A.6. Assume A and A3
Then for any step size n (0, n00 it holds that
E [ ((bi.bi) -0119] <
1
2mvreer Na
aN
2, Eell DS |1pH
+ 1/1/221/2
+ (1 - 1 - -.11, (25)
where the bias bibbbi) converges (I (I-F((n) Đ
(((b.bb) (1 ((n))) pn < (1 1H ((r)) prr
19

---

Proof. Proof follows by combining the results Lemma A.1
emmma
A.5 above.
In the lemma below we provide simplified sample complexity bound of Corollary 4.3 corresponding to the synchronous setting, that is, with number of local training steps = 1. There, the bias term disappears, and above results directly give simplified sample complexity bound.
Corollary A.7. Assume AD and A Let H 1, then for any 0 < < 1, in order to achieve
E| 0 ] e² the required number of communications
(
Üheter V θe
100 0+1
T =
log
Na2
mumber of commmicctionss, setting the step size
a.e2
TJU
(26)
Uheter
0
Proof. Bounding the first two terms in decomposition
25
we get that the step size should satisfy
a.
Uheter V 0z
From the last term we have
1
100
0+1l
Cneter V og
log 1 0+1
t
log
61)
Naae2
Corollary A.8. Assume 7 and A3
For any
0 0SES C 00 0-1l v
V Whetee V Be 0.1l
2/5
a
a
in order to achieve E 11 - 0.11 < <² the required number of communications is
[Eell0R 0+1l
1100 0-11 - )
T o
log
(27)
a=e
setting the step size
aNe
17 0
Uheter Te
and number of local iterations
Uheter V G
==O
NeE. 10 0-1
Proof. We aim to bound separately all the terms in the r.h.s. of Theorem 4.1 17 no; with no given in (26) in order to fulfiil the bounds
Note that it requires to
nureer aN
nJ aN
Se,
SE.
Now, we should bound the bias term
E |1 bii [|a]
(1 + na)
II - - pH
Thus, using the Neuman series, can bound the norm of the term above
[[ - (1-r()) ((m)) ('p))
PHll =
Cr < Σ (1-
Hk | S 1- 11a)
|
0=
k=0
20

---

Hence, using the bound of Lemmal A.3
we get
E | (i) 122] - 1 (1 v11)
2 PH
naH
MH (expp (exp(1/1 || 11 - 0.
1 r)a)
Hx
H
A
11 - 6-1l] -641l
HHEElll 05 --.1
x
a
where used the fact that the step size 7 is chosen in order to satisfy nH CA 1. Thus in order to fulfill E [2] S & we need choose 1/ and H such that
n HE 11
0+11] Ea.
E
||l
remains to bound the term
of N
Using the bound Lemma A.3
we get
E. De lonll
E. 3/
5/2
a
/H1/2N1/2
a
Cheter V 0
E, [l 0-
Hence, it remains combine the bounds above in order to get the sample complexity result
Corollary A.9. Assume 7D7 and TD3
Then for any
0 OSES 2(V2(1+7) - [100--0v(+=+[10)):1000
23 -000-00 (1-7)u(1+7)
(1-7)/
in order achieve algorithm is
B[1 0.112] < E² the required number communications for federated TD(0)
T T= -aa(a) v E(1l--011) log 11--01)
(1-7)ee)
B Markovian sampling schemes for FedLSA
Note that under each of the matrices A c E [N] is Hurwitz. This guarantees the existence and uniqueness of a positive definite matrix Qe which is a solution of the Lyapunov equation
{ (A Q. + QAA==1
We further introduce the associated quantities, that will be used throughout the proof.
de = ||Q=11 7o0,0 = (1/2) 11/2) A l|Qell
min ag Too min Too.0
cE[N]
cE[N]
k Amax Amax((0)) (Qe)//min(( Amii((Q bqcc = 2V/E, CA KQ
max Ki.c bQ max bq.e
cE[N]
cE[M]
In our statement of A we also required that each of the chains (ZE)RER starts from its invariant distribution тT. This requirement can be removed, and extension to the setting of arbitrary initial distribution can done based on the maximal exact coupling argument [ Lemma 19.3.6 and Theorem 19 3.9]. However, better highlight the main ingredients of the proof, prefer to keep stationary assumption.
Proof of Corollary
4.5 Assume that the total number of local iterations, that is, TH, satisfies
TH = 2gm + k.
0 0 k < 2q.
(29)
where q E N is a parameter that will be determined later. With Lemma B.4 we construct for each c E [N] a sequence of random variables {Z 1 which are i.i.d. with the same distribution Te- Moreover, Lemma B.4 together with union bound imply
P(3j [m],c E [N] 2j4 + ZZz0) S mN((14))
The bound
29 implies that m < (2q( Thus, for any 8 E (0, 1), in order to guarantee that
P(jj [m],cE [N] Z kznz)) <
21

---

Algorithm 3 FedLSA with Markovian data
Input: 7> 0. 0n E IR3, T,N, H > O, time window E N. for 1. to
do
Initialize 02,0 = 0z
for
do
for h = 1 to H do
Receive Zi,,, then check the condition:
if h qi.j E N then Compute local update
0i = -
- -b( (Zi)))))
else Skip current update
Average: 0.+1 N Ee= oi
(28)
it is enough to ensure that
(L(144)/ 3 2N 8..
(30)
Inequality (30) holds for fixed å (0, 3 if we choose
Tiiix log (2N
(31)
log4
Thus, setting the block size q as in (31) p. we get that for total number iterations TH satisfying (29) with probability at least 1 5 the results of Algorithm 3 indistinguishable from the result of its counterpart Algorithm [ applied with number of local steps H/q. We will denote the iterates of the
latter algorithm applied with number of local steps h E N as @fima) in order to make explicit the dependence global parameter upon the number of local iterates. We further denote the event, where oftnn) H// = 0r, by As. Thus, setting
=
Uettrr V o [E 0: 0l] Ne
=
(32)
similarly to the way the number of local updates is set in Corollary
4.3 we obtain that
Bil0r 0. | Ell 6.1 1 + 0[
-.1121 1xl
(33)
|0 (id))) 1/q 0. 2 1A E[||0T
0. 0.11
S < + VOE 1/2 1110 0. 11
where in the last inequality we relied on the special choice of H/q from 332 together with Holder's inequality. Now it remains to bound B||00- 11 and tune the parameter ō appropriately. Note that within this bound we can not rely the estimates based on independent observations {22gg) j=l...,m At the same time, note that the skeleton 2zjq > 0 for any e [N] is Markov chain with the Markov kernel Pa and mixing time Tmix
This allows us to write a simple upper bound on B|| 0-l || based on the stability result for product of random matrices provided in [14] Indeed, applying the result of Lemma B.I we get
2T N
E B 111 < 110
0.11
+
Σ
10
0.1l
nTHHll
and the corresponding bound
33 can be rewritten as
27 N
El -
5 2 5
v8
100 - 0.1l
|00
0.1l + 17 H H
|
N
22

---

Thus, setting
8
HT (100 0-1l + x Ei 10 - 0.1l + 7
we obtain that the corresponding bound for block size q scales
Tmix log (2N /6)
Tmix log H log (NT A c
log 4
where we write $ for inequality up to absolute constant and set
N
100
0.1
2 N
Σ
110 Oall + o||=|1o0
CopY
Combination of the above bounds yields that
Bil0r - 0- 1-12 < 26²
and the proof is completed.
Lemma B.1. Assume and A3
Then, for the iterates 0, of Algorithm with parameters n) H,
satisfying the relation
n
n
12 2 logd d log KQ
(34)
it holds for any probability distribution & on (z, and any t E N. that
11/"1100- - 0-114 s 110 0.1l 21
0-1l + 110
Proof. First we write a counterpart of the error decomposition subsampled iterates of Algorithm 3 Namely, we write that
12
13
for the LSA error of the
02 0, ((..)) (6,-1 0.} + Ht.H + n
(35)
where we have defined
(c,7:9)
II AZ(Zigh))
m I
(36)
m=
( H.H
(c....)
1,1:H
(c.ng) (0 - 0+) 1,1:H
1t. - ΣN N
H
1:1 ( (Zi.g))
(c...))
For notation simplicity have removed the dependence of x4, h on the subsampling parameter g E N. Thus, applying the result of 14] Proposition 7] (see also Lemma B.2) together with Minkowski's inequality, we obtain from the previous bound that for any distribution on (Z, Z),
/ ///JInaaa (c.n.4) (c...))
4,1:1 [1*] S V 2a2/2 n2/2
<
provided that the ratio nll/9 satisfies the relation (34. This bound yields that
E E ||
$1.
N
2
B |1 1|
100
0+1
N
E 11
<
||
Hence, we obtain by running the recurrence
35 that
21 N
1 0-11"1 < 110.
1118--0-111
0.1l
Σ
10
0.1l + HeHHe
N
and the statement follows.
23

---

Then the Stability results on product of random matrices. The results of this paragraph provides the stability bound for the product of random matrices I (((n))) defined in (36). Define the quantities
Too
1/2 CA / (1d) = A A Ane 1/2 CA A Aā/(bero Ca) x [
A ACA 12,
(M)
(37)
Cr 4(K00 CA +ā/6)² 18k0 CA /a/ (a = a/ a/
1/2
Then the following result holds: Lemma B.2 (Proposition 7 from [14. simplified), Assume A2 and A3 Then, for any c E [N], t e E,
step size 17 10. any N. q 2 Tmixi and probability distribution on (2. it holds
1/4 B
[²] Vniq,ced (0 |
(c.-e) imm
Proof. It is enough to note that, since 9 2 Tmixx and we consider q-skeleton of each Markov kernels Pa. each the subsampled kernels Pg will have a mixing time
Berbee's lemma construction. We outline some preliminaries associated with the Berbee's cou- pling lemma 3 construction. We recall first definition of the 8-mixing coefficient. Consider probability space (22, F. P) equipped with o-fields 3 and B such that 3 F, ,F,55 B-mixing coefficient of 3 and @ is defined as
633 B) (1/2) sup
ΣΣ TEI JEJ
IP(A, -(AA))((BB))
and the supremum is taken over all pairs of partitions {Aslier E 3 and (B,}ee E e' of Żς with finite and J.
Now let dz) be a Polish space endowed with its Borel a-field, denoted by Z, and let (Z goN be the corresponding canonical space. Consider Markov kernel P on Z 2 and denote by IPg and Eg the corresponding probability distribution and expectation with initial distribution &. Without loss of generality, we assume that (Zx) (<E) the associated canonical process. By construction, for any A E Z, IPg (2x E A Zx-1)= )- = P(Zg-1, A). Pg-a.s. In the case & 82, z E Z, I'g and Eg are denoted by P. and E,,, respectively. We now make an assumption about the mixing properties of P: UGE 1. The Markov kernel admits и as an invariant distribution and is uniformly geometrically ergodic, that is, there exists Tiix E N such that for all k e N,
APP*) = sup (1/2)[IP*(x.) - p* (2', ) S (1/4) 2,2EZ
For q E N. N, and the Markov chain {Zn)net satisfying the uniform geometric ergodicity constraint UGE we define the o-algebras Fs oZee, k) and Fitt o l 2 k + q). In
such a scenario, using
13 Theorem 3.3], the respective 3-mixing coefficient of F& and Fitt. is
bounded by
B(g) B(Fr, A(P)) (1/4)la/=1.
We rely on the following useful version of Berbee's coupling lemma which is due to 10 Lemma 4.1]:
Theorem B.3 (Lemma 4.1 in [0]). Let X and be two random variables taking their values in
Borel spaces X and Y, respectively, and let U be random variable with uniform distribution [0; 1] that is independent (X, Y). There exists a random variable Y* === f(X, F(X,YYUU Y,U) where f is measurable function from X x y [0, to Y, such that:
1. Y* is independent of X and has the same distribution as Y;
2. IPY #Y) =00(((X),
24

---

Let us now consider the extended measurable space ZN = 2 x [0. 1], equipped with the o-field EN = g @ [8(0, 1].. For each probability measure & on (z, 2), we consider the probability measure Pg PP @ Unif((0, 1]) and denote by Eg the corresponding expected value. Finally, denote by (Zu)REN the canonical process Zx: ((z))iEN, u) ZN + zạ and U: ((Z))EE,, u) Zy H u. Under F.g. hEE is by construction Markov chain with initial distribution and Markov kernel independent of U. Moreover, the distribution U under Pg is uniform over (0, 1]. Using the above construction, we obtain useful blocking lemma, which is also stated in [10]
Lemma B.4. Assume U let Q E N and & be a probability measure on (Z, 2). Then, there exists a random process (Zi)ee defined on (Zx, Zn, Px) such that for any k E N, it holds:
1. For any i, vector Vi (Zigtt.... Zigta) has the same distribution as V; (Zutt...... Zigtz) under P'g;
2. The sequences (V2))200 and (V2+ are iidd.
3. For any P (V, # V/+)= - 3());
Proof. The proof follows from Theorem B.3 and the relations between UGB β-mixing coeffi- cient, see e.g. 11 Theorem 3.3].
C Federated Linear Stochastic Approximation with Control Variates
C.1
Technical Lemmas
Lemma C.1. Assume A and A3
Recall ((t.ec)
Ek
p(c.n) +1h+1:8
Then it holds that
1
(t.c)
2
122
{Ca +
E
n.
H
4
Proof. We rewrite I- - (tt.c)
7.H using Lemma D.1 as
I H
1
Σ
(e.)) 1.+11:ff
Σ
A (Z (Cn)
H
H
h=1
h=1 8=h+1
which can then be decomposed as
H
H H Σ h=
I clt.) H
= 1
" Σ
H h=1
AT(O
+
" H
Σ t=h++1
(A9(Zi)) A ((m)
1.41:
E=
Minkowski's inequality and 3B give E1/2 second term has a reverse martingale structure, and we thus have 1
|1 E 1hm1
ΣH
1411 IP]
S nH
/ | The
28=h+1
I
||]]
< 1222
{ca +1
E
H
4
which is the result of the lemma.
Lemma C.2. Assume All and have
A Recall Õ4+1
(p()n)
1.++1:11 - (1 H- }.
Then we
B [ICE < H2 ( +1Ex
Proof. We start by recalling the definition of Či. that is
N
N H
Öi = Ci+1
B B =
1
Σ
(en)
(I Ac)H-h)]
N
N
(1+1:
1=1
2=1 Am
25

---

Using Lemma D.I.
we have
H
H
(an) 1.+11
{A
A (T A-18-6-1
1+11
N
C=
h= t=h
By Minkowski's inequality and Assumption A
3
we obtain
N
H ΣΣ
H
= 11/2 |12++111]
" N
E
(Z))) A9]
Now, we notice that
E and the result of the lemma follows. Lemma C.3. Assume Al and A3
19 = III A + |A
A C + + ll
Recall ((t,e) n.H = -E ((en)
1. then
E8 44 11] s 2nH { +122% 11
Proof. Denote AG = A A
T = P(+1 - T241
a AAA)
II - (bmnAA))
hm1
hm1
Using Lemma D.I
we can rewrite
14
a (la-nAs)
(AA (AR--AA - A
πI (1 (1- (1-nAA)).
N
1=1
Using triangle inequality and the fact that A3, are independent from each other, we have
N E
k-1
E + [I]
"
ΣΣ
II
E | A
E
II (I (I- 1=k+1
By triangle inequality, and using the definition of CA and 1> |l. we have E[ - Agll S
A A + || A + + A 2CA +2 E ||. Therefore, we obtain
B ++
||| s 21
Σ (1
n
ma) H-1 (CA +1 11)
k=1
and the result follows.
C.2 Proof
The linear structure of SCAFFLSA's updates allow to decompose the updates between transient term, and a fluctuation term. To materialize this, we define the following virtual parameters
0 86,0 = 8 and Eo = 5 for all c E NN.
These parameters are updated similarly to 0,'s 's and Ef's, although without the last fluctuation term. For the virtual parameter Ó. the update similar (8), as follows
0 0, n (Z; (0 0.) + nTEE E
which gives, after H local updates,
0 0. 1':41 0.) + niE -E.)
26

---

where we recall [+1 -1= (Zi,)) and C - Σ h=1 1.+11-8
p(an)
The virtual parameters
obtained after H local updates are then aggregated as
1 N
This is then used to define the virtual control variates, similarly to (9)
č + _ 1/ (0..1 0i.H)
fi+1
These updates can be summarized over one block, which gives
N
δ.+1 - 0, = -0= - -0) +
7
Σ
i - -
N
Śi+1 - - TH (T - Pi (b. 0.) + (I
1 cr C - - + H
Σ
HN
6=1
The analysis of SCAFFLSA can then be decomposed into (i) analysis of the "transient" virtual iterates 0, 's and Ef's, and (ii) analysis of the fluctuations 0g - O, and E - 42
Analysis of the Transient Term. First, we analyze the convergence of the virtual variables 0, and & for 2 0 and c E
Consider the Lyapunov function,
22 N
a = 10, 0.11
Σ -
which is naturally defined as the error in 0, estimation using the virtual iterates, communication rounds, and the average error on the virtual control variates.
Theorem C.4. Assume A7 and A3 Let n, H such that qaH S 1, and H S 2n(C +|11) and ser Si for all E [N]. Then, the sequence (N/))En satisfies, for all t 2 0,
p I (1 naH
Elvol
4
where v0- = 110 0.112 +
nH N
E
A A 0,)
Proof. Expression the Lyapunov function. Since the sum virtual control variates is M Ee
21=1= 0, we have 0.+1 = N Ee H6 n/4 - Hú nH - -.). Applying
Lemma D.3 we obtain
10 1.11
8 0, - E
N
N Σ
| - 0, - n - --111
|1 - -0 + HHH - 1
N
N
c=1
112 N
Σ
|| 10 - 0, - -HEE: - -1)1
Σ
| - E
N
N
since Ei+1 = E5 + n/
1
(0141 ).) Adding
nH N
Σ 11
1ll on both sides, we obtain
1 N
T, - 0 - n 12
(38)
N
27

---

where we defined 0 n.11 プ [(an)
æ=1 1.+11 In the following, we will use the filtration of all events up step F: oZ n,
t H, S c N).
Using Young's s inequality, and Assumption
we can bound
BII (i 0. n/( - 1,1:1 0.) nH( C E
$ [[[[ a |1
+1+
C2 (i, E3)1
Σ (1 + a0) -
" (1) 0.1 (1 oz H E , Cnu)lE =.)19.
Using Lemma
C.I we have
H22
Bll[(I // C (
Bllk: = {cr +1=
4
We thus obtain, for H such that naH I 1, and after setting not and using the facts that
- ---aH)(L + ax) < 1 naff and 0g < 20
2
| H - 0, - nH (E) [
1 naHl
E B| 0,113) + naH
f +1EX ||]
"' H HBIIS =
1 naH
B[16, 0,11 + nH
(CA + EXll B --I
Then, since nH {CA + +|
S 2 we obtain
El 0. H - -) -
naH H
0_11 + 17 2 -c91 10:
(39)
2
and the result follows by plugging 39 back in (38
Analysis of the Fluctuations.
To study the fluctuations, we define the following quantities,
and Our analysis is based on a careful study of the recurrence between variances and covariances of parameters and control variates. We thus start by deriving recurrence properties these quantities. From the update of Oz, we have,
0. = - 0c
ç = - E for 2 0 and e [I....,N}.
N
0 - 0. = (00
7 +
Σ
da
(5) - nEt+1
N
N
= = -0, +r
28
nE++1,
which can be rewritten as a recursive update of the fluctuations
- 1'410 O, + 0 =
- 75++1
(40)
Similarly, we have, for the fluctuations the control variates
0 1 (T+41 1 + (I H Ei = nH
C Σ
H (E1+1 - E
6+1
NH
Remark that, for all 2 0, 0e and Ef's 's are sums of (random) linear operations computed on zero-mean vectors, that are independent from these linear operations. Thus, for all 2 0 and all e E (l..... N} we have
E 0 =
E 0.
(41)
28

---

We now aim recursively finding sequence of upper bounds (b(0.0) ,b(0,5), b= for all 2 0, c. E {I....,N} such that c + c',
"=,b= 1, 3220 such that,
(0.)
- 6,0000
(G))
- ((0.5) and
E
(0.)
]
s (10000
B ((9)
|
bb
(E)
< b5
(Initialization.) ) For t = O, nothing is random the fluctuations are zero, and 6/ bz = O. We also study the first iteration of SCAFFLSA. In the following lemma, we give upper bounds on the variances and covariances of the parameters obtained after one iteration.
(0.5) = b
Lemma C.5. Assume 1 and A3 lies
then the first iterate of SCAFFLSA satisfy the following inequali-
110003 11211 Ewlll 0
- NH
EE51, 0/0.5)
27 N
by
|ww|l
NH
Proof. (Value of ((0.0).) .) From the definition of 01, we have 01 N E
2 w (Zin).
H
((n)
By independence of the agents, and since (Tr(,,)) 1, (Zi,)) = 0 for all c {l,..., N and for all {O.................. H 1}.
N
H
R (((O)(())T]
I
T
1,6+1:4 (Zi,))) (( 14418)
N2
h=1
NN
H
1
E
(ea)
E (T(m 1.++1:4
Eg
1,b-1:H)
N
where the second equality comes from the fact that, for all h E (1...., H - 1}, the matrix p(ea) and the vector w (2f,,, x are independent. Triangle inequality, Jensen's 's inequality, and definition of the operator norm then give
1.
N
H
[((O,)(
2 21 ((..) 1.
1,4+1:H) T]]
<
N2
c=1
n
N2
E
1.
(T(Sm))
1,4+1:H)
n
N
(ea))
E
2
1.++1:8
|2]
Assumption A3 ensures that E
11444::1
< 1, and we have
17 H
72H
[B(O)
ES S
|
N2
(Value of (F-) Let c E (1....,M) N). The definition of E gives the following expression for the
fluctuation Ef NH N Em=
11
(am)
w (ZE,) B
1 E p(ea)
# Therefore,
1
29

---

we have
(((E) E
r tem))
1,54 $ (Z
(ea)
1:+1: (
NH
H
6=1 h=1
h=1
(ZI,))
NH
With similar arguments above, we have
(ED 1
N
Σ
E
(T(en) (e.))
LA+1HH
N E
N
1.h+1:
(en))
E (m(e))
Assuming N 2 2, triangle inequality gives
N N-2 2
N - NH
S
ELلl +
|
NH
NH
For the covariance of çi and 01, we have (Value of ((05))
E
(0
(E1)
]
N
(an)
1 (ZZ
6=
N
H
W (2)
Σ
( (Z)
(I (e.) (1
x
114+1:H)
NH
H
6=1 h=1 h=1
h=1
E
N
1
(6m) 1A+1: 1,8-1:H)
DE
(T (2.n)
TT
E
NH
(ea))
1,
E (T(aa)
1,8+1:
As result, we have
|B (0 {i>
20 N
Ewel
(Value bF Similarly to above, for + d', we have
H1
B((E))
=
(am) i.t+i:
(Zi
1
(cn)
1. ((2 (Zi,n)
NH
H
N
(w (2
(T 11
Σ
(w (Zi
(ill)))((((es)) (r(een)) (T(
x
NH
H
Aml
N
2 (ā:0) ((
E
N
1 1:f1
6m
2
(ca)
1.41
E
(P(an)
N
E
(
1.+11:4 E (T(ea))
(T
Which results in the bound
|
S
3
|Eul
NH
30

---

Lemma C.6. Letv > O, and assume that nH { CA +1 [1/]] S and H²² { C +12 11 -
A
v. Then the following inequalities hold for any ( 2 0.
(0 (0 + 2v h
3r H
(0.00) 1 (1 - -naaa 22 b/ (0.9)
+ Hng
N b + vn 22
|ww|l
N
1/
(0.0) S <2ub/ (0/00) + Hun (0
+ N N" + 2w12 H² 2n H
2v
||
N
n/ b14 s 22bb (0)0)) + 3mmH (1.E) + 4u1 b1 + 30m 11 + +1² #H| |سكلا
1p 1/112 S 2vbb (0,0) + 3mmllbb (0 + w + 4m/ 11
3v
3n H
|لwل|]
N
Proof. (Value of ( .) Replacing 0 by its expression from (40 then expanding the expression,
we have
= (1et10,, (0++))((=1TT===
N
N
C
141
c
mELt1)
+
N
6
441
nELT!) T
2=1
N
01, I 1 +
"
Σ
14 (()E))
(C++1)
1
T
N
N
N
N
n11+100 T (C++1)
"
Σ
E
(Ei)
(C++))
2
N
n
Σ
(EL))))) + (E+())))))44))
N
From the triangle inequality and Jensen's inequality, we have
N
2m
(0++1))))111) "I1 S E|[ 441 10,00
+
E
E
11
III
N
2=1
27
N Elll 1 "IIl +
n
N
N
+
E
1+1
N
N2
+
[B[
(i)) 2+1
Te + nē 0, (()) TII
+
Te + n Te T TIIl
N
Now, we have from that B(o.] = B[E3] = 0. Thus, we have, for all e E (1,...,N),
|||nr T + Ee+ O (() II || (+1 B n6. B
0
|
(A)
T] 0, T1C42
1+1
E+1
|EinC + nEL+1
23 c Till = B + Bl42
T|ll = 0.
Which results in the following inequality
2n N
III
< E 241
E
+
E
1
1/2
11 'IIl
N
T=1
1
N
n
+
E C 4+1
TII
Σ
E
110
1 |لाा III
N
N2
+ 3n²
|B
31

---

Using Lemma
we obtain
10((0+1)(0m+)) III s (1- - (1-
2 |B
2n² N
nH? CA + + 114/2) | ||| +
N2 Σ n H C +1XX|| |1} |BRE "Il
+
N
2 N
N
7 t { C2 +1 } ||[[| III + 3 (B
2
Assuming nHH {CA+1133 +1 [| S v and H2 {ch +| +1 } S v, we obtain
nH
N
22 N
S <11 - 12a)22 2H
|E
|B
2v
|
N
N2
nJ'H²
3r²² H
|
I|I
|
N2
N
This gives our first inequality that links our upper bounds.
(000)) S (1 naa) 2 (1000) un (0+2) 2v H by + 1
3r H
+
N |اw
N
(Value of (11.).)) .) As for 6,0,2) we bound, for e E NJ.
0ct1Get1 T
N
= -(rtt00+
+
ce
C+151
ch -NEEI1)
N
x
1/Hl
The
1+10t Oe + (1
H
1
Ci+1
Et
NH
de 2a
(415t
7 (141
1 Ee
1
N
1
I' 1 D,0y 1+t1
0
1it1
Ec+10 1++11 T
nH
NH
H
N
+ 02 T
1 (1- (1
H i+1
+
7
202e 14151
(1-
_ C(+1 - nE+1151 F0T
T(
(1-1 -
---0+t)
H c++1
1
N
11
NH
T
Ci+1
T
N2H d=1d=1
T
1415151
re2e T
Ce T
NH
E+tl
TT
22
T T
N
T + H E T.
NH
2=1
Now we proceed as above by taking the expectation, then the norm, and using the triangle in-
equality. Note that by 411 we have E[E,+ T TI 0, El T (I -/4///00000 C+++1) | = 0.
BlE E E T Ch.1 T 0, ET 02441 T] 0, and E[ Eee T] = 0. After using
32

---

Jensen's 's inequality, we obtain
N
100++15++1 E0
TIll
1 1
E
E
11 III
n/1
NH
+
+E1/2
|||
1
Ci+1
|IB10.5E
||B
||
" +
N
E
1 Ci +
|B[E "II
H
N
2=1
N
1
E1/2
[10
||B|0.E
π
E
[1ö++all1@2+
71]
|BLETT JII
NH
N
2=
Using Lemma
C.1
Lemma C.2 and Lemma C.3
we obtain
N
< 2 CA + 1 }
1B80000
nlf (CA+
|
NH
+
nH
11 [1]]
|B|0 II ?H²
+|
[1a]
||
"IIl
2
1 N
Σ 2
[CA +1| +1 [(/]] |BB II
NH
N
N
n2
C +| | |ELÍEC "II + +|
H 1 |]
2
N
where we used the two following inequalities
E
1
)1]
SE!//2
c++1 /|
2 EnH? {
CA 1111111111
H
E
[ICH+IIIC
Ti]
S
1
1 ?
+ 1
+1 TIp] s + }
2
This leads to the following inequality
H (0.5) i+1 S 21 { (CA + +| ||
1 (0.0) + 31/² 3 H² { {CA +||>1 | [12 ((05))
+ 1/ H2 (HH| { [CA + -1 11 [1]]] + n7 222 { C +1 11] + + 1 0z)
20
+ N |اال|
| [ c 7] || s 10000 = -- Assuming 7H { CA +1I A [1aa] Sv
where we used
and 122 H2 {c² +1|2 } S u, we obtain the following bound
(0.E) 22bb!00) (0.0) + 30mH1((00)) + 2012212 { bi= + 1 mH1
2 H
+
IN
N
(Value of būp1 and b(t1.)) As above, we start by expanding the matrix product,
T
1
1it1.1 0 + -1- 02
(it1)
544151+1
H
NH
14
H
1
0+
0,
+
(1-
H
i+1
+
NH
1-15
H
1
i+1
33

---

Fe
241 0:0,
T
+
[
C 2+1
500 i+1
T
1 22 H2
r+1
nH
H
N
+
nNH²
1
Ee
141
0 [+1
T
nH2
1
2 B 1i+t T
6=1
+
1
Te T
C+tz) + +11-
1
-
1+1 )
2020 T
(1
1
(1+1)
hH
H
H
G6 2070T
(1-
H (+11 )²
1
xc To T
(1- Cit1)
1
NH
-
H
i+19i
H
NH
(41
T
NH
[
H
1
[++
5i5t
Σ
C T
6=1
ē=1
N
1
1
2
141565
7028
Σ
0+1
T
NH²
se
++15t
c+1
2=1
2=1
T
1
[--
1
Ct+1
Cfein
T
n/H
H
H
1
NH Σ
T
H²
Taking the expectation, then the norm, and using triangle inequality and Jensen's 's inequality, we obtain
|IB 1 2
JIll
2
S
12
BlJ BlJ
(+1
III
1
E
1-
H
C++1
|B
II
N
B1/2
[IC (|c+1l1 [13]
|B
H2
1 n/
E
E1/2
1
C++1
1|]
|100/55
"II
+ E
||
1
C++1
||
1
C++1
||
[IBETEE
TII
1
11
11
1
E
|1
11
||
1
C++1
|BIEEEE "IIl
NH
11
N
B1/2
[|ŚE [+1
T|
||E TIll
H
N
1
1
|| || TI| | T]ll
E
C
NH
H
6=1
N
EE [
Il
11
Til
| IIl + |
TIIl
112
8=10=1
We can now use Lemma C.1
Lemma C.2 and Lemma
C.3 to obtain the following upper bound
1 IIl
< 22{ C2 + +122 }
||
1 nH
{cA+ +1 + [12]]
| III
HH 2
H2 Σ n12 {CA
+122X || [122] ||
1=1
gH
||
TII + 4
T222
{cr +1 | 1 TII
nH 2
34

---

N
nIf? (CA + 112 [1/3] | TIll
NH
N
nH? {CA + [1 | III
NH
1
?H {CA + | | | III
NH
N N
ΣE 2=12=1
1 H
C +12 } | "Il +
H22 1441111411 71
1
N2H
This bound can be simplified as
S2+1 TIl s 2n 2 { { +1 61 ((000 T²
[12 [13 0//00 (10.0)
2
+ H {CA +122% [/2] (105))
12
{CA+1 [1/)) 11 (0.5) + 1
{ (C2 +1 |} | TII
+ 2
+
4
{CA+1I2 [1/2]]
{
1
+
(1-
1
by
N
N
+ (cx +122% [1/2]]
(0.5)) +1 1 {cA +12; [1:22]
N bi + (1-
N ot
+ (ca + }
{
1
bラ +
(1
1 N
1
b
+
||22 B 1 Ti||
1
N
which can be simplified as
n 12 Ec TIl S H2² {
C +11 1 } (1.00 + +3n {CA +| A [1/2]] 11
+ (2nHt
CA + + || 12 + +
2 H²2 {ca +| 11 1) '²H² H2
1 bū + (1
1
N
N
( | (55S Tll +
1
B 3++ T1|
4
H²
We now distinguish two cases, when c = c' and when c c c' First, let d, we obtain
1² 1211 s 212 { C* +12 |1 } 6: (8.0) - 31/ CA +1 ||/2] n/ (0.5)
+ (2nt) {CA +12 11/2] + 1 3 { C + | 11) 12 2
bi + (1 N
oF
N
12212 {C² + A | ,² + H
+ 4
since when = c', we have a 2|EEffEf Till S bi and 1 Bli++1 T|| S N-7 |E
Assuming n/l {CA +1 +122 [ S and 112 { ( +12% 11 } S v, we obtain
12H < 2vb (0.0) + 3 (0.5) + 4mm² 2
H2²b = + 3vm 2 H2² + n" H|
We proceed similarly for c + d, which gives
122 12 S 201(0.0) 3omH1b (0.5) + 3v "² ,, 4un + N
3 HI
""
|ا
since, when c # cd, we have | TII s by and
T//| S of
3 NH
|
35

---

Corollary C.7. Assume that FH {
CA + D 11/2] S + and n ( +12%||
+
210(C + + set w min (1. 1210 - then holds that
wn/2H² H
b WnH
(0.9)
+
bit1 + wny H2
N
1 naH
b (0000)
2
1
w (9.5) +
2 N
1
wnj H
by +
2
2
1
+
9n2
|wwl
Assuming naH S b. we have 1
2/3 - 1- naft
This in turn ensures that
+ wn H2
6/41 + WmmHbtt
(0.5)
b+41 + wry 22
1+1
N
<(1 1
naH
by
(0,0) + w
(0,E) wnj H²
bi
17²
12
+
9n H
N |ww/l
2
N
which gives. for any t 0.
((500) S
1877
Na
Proof. From Lemma C.6 we have, for any 0 < < 1, > 0. and assuming that
n CA - 2 A [1
< v and 17² H22 Ca +1 || } < v, and since w S 1.
wmp H2
610.0) + wmllbb 1+1
(0.E)
bit1 + w/) 2 1 2b
N
(1 --aaa" 2H + GwilH {CA +1 ^ || 1/2 }} (1000)
(0.E) + +10v H22
9r7²
H0
N bن + 10 2 11 +
N
Now, we choose w min (1. 11100+ and obtain
(1 na)* 2 + +wmml CA + 12g [1/]] < nall + HWmH {CA +||28 [1/2] s
noH 2
Additionally, w & 1, thus 3 + 6w S 9 and we obtain
16000) + Hwm [41 + 2 H2
(P.E)
bis + wn² H 6+1
N
< ( nall
+ 10 (0,9)
(0,5)
10v 17 H
bū + 10vn" 2126 + 9n² H
|
Choosing S W S 200 + gives the result.
Complete analysis SCAFFLSA.
We can now state our main theorem, which gives an upper bound on the expected distance between the iterates of SCAFFLSA and the solution 0..
Theorem C.8. Assume AT and A3 Let n, H such that na S 1, and H S 2400tC +1 S6 for all E [N]. Then, the sequence (Nt))eN satisfies. for all 2 0.
and set
[|[ 0. [1] < (1- nall" (--Jaal) )
{ (21100 0.11 2 2nj 22 A (0; 00.1pp}
36d1 Na
Proof. Recall our decomposition 0, 0, 8, 0. + θ. By Young's 's inequality, we have
E | 1 < ||| 0, 0. |1 21
36

---

By Theorem C.4.
we have 0 - 0.113) - (1- naH
Vo, and by Corollary C.7
we have
11 v db
18nd Na
Combine the two results, we obtaín
0.11%1 = 1 naH
36d7
E E1
200 +
|Elll
Na
replacing t/o -100 0.1 " E ||A
0.)112 gives the result of the theorem.
Corollary C.9. Under the Assumptions of Theorem
C.8 one may set the parameter of SCAFFLSA
to
Nac
]2d Ewll
7 min
1loc
11
max
72d Ee|
240
C +
+
Ne
which guarantees Bl[10: -0.113]
e² after number of communication rounds
240
+1
41100 0.
4n
Σ
A A= 0+)]1
T2
log
a²
2
The overall sample complexity of the algorithm is then
240
[2d[[Eel]
4|000 0.112 An
DM
|A
-0.]l1
TH = max
log
7oc
Na
e²
Proof. Let O. Starting from Theorem
C.8
s upper bound, we have Bllla 0.1131 < e² whenever
1 (1-1) 2
naH
2e/o + 36d7
|E S e
Na
where v/- = 110 0, 2 + DH which requires
Ein ||A= - 0.)11 This gives a first condition
36dn No
Ew || S E2,
N
Nac²
1) S 72d Eell
This allows to take any value of H such that H S [ setting, remains to set the number of communication to
With such
210Ne(C
244u 2 =
240
{CA + +||
4tho 2
T nall
log
log
a²
which ensures that (1- noHf 21/0 S 2.
D Technical proofs
Lemma D.1. For any matuex sequences (Un)eN, (Va)neN and for any M E N. it holds that:
M
M
M
k-1
M
II
Ux
- I V/2
U V&
II
VJ}
1=1
k=1
1=1
j=
Lemma D.2 (Stability of the deterministic product). Assume
A
Then, for any E Rd and E N,
[|(T ") S (1 n ||]
Proof. Since (I5)) are i.i.d, we get
E ((. 4.1:h u| = E [1 7 (Z,)))) = IT EE 1- 7 A(()) u- == (1- nuahhu..
The proof then follows from the elementary inequality: for any qquare-integrable random vector U. |[[U]]]| (2)
D
37

---

Lemma D.3. Let (a:) and (wi) be N vectors of of
Denote EN (1/N) Σ Zy and
UN (1/N) i=1 Vi. Then,
N
N IN - (yi U2
MIIN UN|12= = Σ
|0 yill
Σ
10
1=1
1=1
Proof. Define x = [aT 1 projector on
2 N and = 1MT ................................ YN
E RR Nd. Define by P the orthogonal
E fx R xx= [x
T x E Rd)
We show that Px= = JN..... IN a slight abuse of notations, (t, .) denotes the scalar product in Re and R2)
T, Note indeed that for any z = [z ...,,..,??
=J E &, we get (with
xx Px,
Σ (at (IN,
(IN, 2)}
0
The proof follows from Pythagoras identity which shows that
|| P Pyl2 - y 11 I1(x Px) - (y P 113)
Lemma D.4. Assume A4 Let Z be random variable taking values in state space (z, 2) with
distribution Te. Set 2 0, then for any vector u E Rdd we have
E|I - 7/A (l)) S (1 mpa]llu12 - - -
Proof. First, remark that
II(I - 7 (Z) = (
=u =u](1- (1- 2n( (A (2) (FAA()))))))
Since we have E (A) + A (2) al and (1((A (EAA(2)TACCE we obtain
E|l[(1 - - (2))ul
= u u 20pu T 10 A (Z) (Z) n2 (Z) T AZ(Z)
S ||u|| 2 malluul2 F.u (EAA A P B[A*(Z) ([AT()))A<(Z))
= (1 - na)lull - -n( 7, n) E A (Z) (Z)2),
which gives the result.
E TD learning as a federated LSA problem
In this section we specify TD(0) as a particular instance of the LSA algorithm. In the setting of linear functional approximation the problem of estimating V=(s) reduces to the problem of estimating 0, E Rd, which can be done via the LSA procedure. For the agent E [N] the k-th step randomness write A instead of
is given by the tuple Z (S) A St 1 With slight abuse of notation,
A AZZi,) and bf,, instead of b ,., Then the corresponding LSA update equation with constant step size 17 can be written as
8i 1i (AA b(.n),
where A and b are given by
Ai -
- (6(S bi, = (r A(,
(42)
Respective specialisation of FedLSA and SCAFFLSA algorithms to TD learning are stated in Algorithm 4 and Algorithm 5
38

---

Algorithm 4 Federated TD(0): FedLSA applied to TD(O) with linear functional approximation
Input: 7> 0, 0n E IR= N, H > 0 for t to
do
Initialize 0,,0 = 8:
for to do for h == 1 to H do Receive tuple (S i (i,t1) following T and perform local update:
0 fi A b(,n)
where A and b are given in (2)
Average: 0141= 1/2 E 1H
(43)
Algorithm 5 SCAFFTD(O): SCAFFLSA applied to TD(0) with linear functional approximation
Input: 7/> 0. 0n E IR", H 0
do
Initialize 0z,0 = 0z
for to N do for h = 1 to H do Receive tuple (S A 11,++) following TD and perform local update:
0 1i 0 , - g))
where Af,, and by given in 422
Average: 0++1 2/2 E 0f.H
Update local control variates: fi+1 = E3 + nH
(0z+1 (1
The corresponding local agent's 's system writes as A 00 bs, where we have, respectively,
A Egrp, E ( (o()) I
bc (is (o)))
The authors of 50 study the corresponding virtual MDP dynamics with P= N MDDP-
ñ ~N1>> c0=l rf. Next, introducing the invariant distribution of the kernel fú of the averaged state kernel
/ MDP (B]s, ())(da)s)
(Bls) = N Σ
we have as an optimal parameter corresponding to the system ÅO = b. Here
À Eg-p.s ( -6())))
b E (enp
E.1 Proof of Claim 3.1
We prove the following inequalities
CA = =1
(44)
| || < 2)1+7)3
(45)
Tr(E.) - 211 (116) + +1)
(46)
(1-2) 2
(47)
700 (1->)
(48)
39

---

Table Communication and sample complexity for finding solution with MSE lower than e² for
FedLSA, Scaffnew, and SCAFFLSAon the federated TD learning problem. Our analysis is the first show that FedLSA exhibits linear speed-up, well as its variant that reduces bias using control variates.
Algorithm
Communication T
Local updates H
Sample complexity TH
FedTD 12
(1 (1-7jve log
(1 (1-7)ve log 1
FedTD (Cor. 4.4
O
(1 (1-y)ve log
O
O
N(1-7)vc log
SCAFFTD (Cor.
5.3
O
[1 log
O
N(I N(I-yjer log
Ne
The proof below closely follows 42 (Lemma 7) and 45 (Lemma 1). Everywhere in this subsection
we use generic notation A an alias for the random matrix Af, Now, using TD3 and (5). we get
| S (1+1)
almost surely, which implies ||| definition of x that
< 1++1 y for any E [N], giving 44 This implies, using the
[[A A?. (A S 2(1 + 7)²
and the bound
45
follows. Next we observe that
Tr (2)) = [[] - A0 - (bf - 1
< 2(00) [[Ai} Ai]0 21E[(r (S%,A5)) Tr(p(5)))p))) ((S))
$ 2(1 + (09) ( 2 [c]00
$ 7)) (1105112 +1
where the latter inequality follows from TD and thus (46) holds. In order to check the last equation 47), we note first that the bound for a and Too readily follows from the ones presented
[Lemmaa 5] and [42 [Lemma 7J. To check assumption A4 note first that, with s ~ pf, s
pa (-1s), we have
A + [A9T = ((8) - - + (v(()) (())
= 2p(s)p(s) - 7((())((')) + ((s)))(ss)
(2+ +
where we additionally used that
-(wu" T + v) ) I uv
+ Tu T 3 (un" + vo )
for any u, E Rd. Thus, we get that
E[A + (A9T) 2(1 + ~)
The rest of the proof follows from the fact that
E((A() = (A (1 7) 2>minn D
which holds whenever 48 is satisfied; see e.g. in 30 (Lemma 5) or 45 (Lemma 7).
Based these results, instantiate the results summarized Table T to Federated TD learning in Table
F Analysis of Scaffnew for Federated LSA
To mitigate the bias caused by local training, we may control variates. We assume in this section that at each iteration we choose, with probability p. whether agents should communicate or not. Consider the following algorithm, where for k 1, 1...., Típ, we compute
0 =
(ZZ) 1
40

---

Algorithm 6 "Scaffnew": Stochastic Controlled FedLSA with probabilistic communication
Input: > 0, E H.
Set: K T/p
for k to K do
for 1 to do Receive z and perform local update:
Draw Bg Bernoullipp) 0% 0%- (2 b²(2)) - -
if B₁ = then
Average local iterates:
0% N Eam 0%
Update: E - + 2 (0 fg)
else
Set: 0% 0g. S% Ek-
Le. we update the local parameters with LSA adjusted with control variate 6h-1- This control variate is initialized zero, and updated after each communication round. We draw Berouulii random variable B₁ with success probability and then update the parameter as follows:
0x 0g
N
0
B₁ 1,
O
By 0.
We then update the control variate
c 56
2
0g)
1)
where we have set Eú = 0. We state this algorithm in Algorithm 6
Note that, for all E N, Ee E = 0. We now proceed to the proof, which amounts to constructing common Lyapunov function for the sequences {0g)ee) and {Eg) Define the Lyapunov function,
17 p²
10 0.112
E
where 0g is the solution of A0, = b. and E.. then given by
A Ac
0%). A natural measure of heterogeneity is
1
1 N
A heter
|K
AA 12]
To analyze this algorithm, we'll study the decrease of the expected value of the where the expectation over randomness of the communication and stochastic oracles. This requires a stronger assumption than the Assumption AB that we used in Section 4
44. There exist constants a, L > such that for any n E (0, 1/L,, c E [N], it holds for Zi ~ To- that
al E (A (Zf) + (Z))) (Z)) T (Z+))
This assumption is slightly more restrictive than A3 Indeed, whenever A holds, AB also holds with
the same constant a (see 42 45). In the case of TD, this assumption holds with L
1ta
(1-a)w'
Lemma F.1 (One step progress). Assume Al and 44 Assume that 1j S algorithm described above satisfy
1 21-
The iterates of the
27/²
N
E[pbk] s (1- min (1a, E E(Va-1]+
Σ Tr(E9)
N
Proof. Decomposition of the update. Remark that the update can be reformulated
0 - 0, (I 7 (ZE)) -0.) + + E.) 1 (Z()
(49)
41

---

where (2) (z)00 (x). This comes from the fact that, for all
(²(2) + 6h-1 = b + (2(2) 1
A + (z + Eh-1
= A90, + (9()) + + -
=A'(=)0, (=))), +b((z) + fh-1 - 5
A=)0), (2) -h-1 -5.
Expression of communication steps. Using that Ee 5h-1
and Ee
0, get
N
1
10% 0.112 = 1 ((1) (B&)) - 0-11 + 100 (Bx)
Σ
10g 1
N
N
1 N
Σ 05 11 1
1 N
Σ (0, "
"( + 1 to) (B&)
>
110g 0-11
N
The first term can upper bounded by using Lemma D.3 which gives
1 (1)(Ba (B&) - 111
N
N 0
= -Io)(Bb)
10
" "(h-1 - -(-) - -
(0%
- 1) +
7 2011
N
p
N
p
c=1
1
(Ba)
Σ
|
! (Eh-1 -E5) 0.
Σ
|1
E
p
p²
We now expand the first term in the right-hand side of the previous equation. This gives
N
100
(EE
-E.) - 1.2
N
P
cm
1
110g 0.113
27 54, 0:
(5g-1
0.) +
7? 1155_1
--12
N
p
p²
which yields
172 N
((g(B)) fibt
(Bx)
100- - -0.11++++
1sc - E
p2 N c=1
(Ba)((a))
1 N
Σ
10g- 0.112
2n
15h
Eh 0% 0.)
1/2 1
Σ
| -
E2112
(50)
p
p2 N
On the other hand, note that
1 N
y/2 1 p² N
N
[oy (Bx) (thx)
1 (0) (Bx)
1109
0_112
+
Σ
-5 E
N
1
v² 1 22
103 (Bk)
110g
0-112 +
Σ
||5
E51
(51)
N
N
By combining
51
and
50
we get
N
N
2
thk
10%
1
+
15 - 2
N
2 N
A=
N
172 N
1
16
0
2 7
1
(Bx (SE
Es 0 - 0.) +
15 - E-1 (52)
N
P
2 N
42

---

Progress in local updates. We now bound the first term of the sum in (52) For c E [M] 49 gives
l10 - -0.1l = [I(1 - n ( - 0.) + n({i-1 - {.) - mp (2)))
= - / (Z - 0.) - (Z))) + 1111--111 E2
+ + - i (1 (1- (1-AA()))))
- 0.] (ZE)
= |(( n- ( (OE - 0.) - mo m 12 + +2n(5h_1 -5x, 0 - 02) - 1 E-ll?
(53)
Define the o-algebra Gk-1 = BBB. 8 S k - 15, S k- 1,c E [N]). We now bound the conditional expectation Ti
E [Ti]
0.311- 27 1 (2)) - 0.), w (z + (Z))) = E [[[(1- n (ZK)
= E [I[(1 -
- [
0.31 + -
(A 0.}, (ZE)) + (2
where used the fact that (I, (zІ)) = O. Using Young's inequality for products, and Lemma D.4
with 7 S 27.
and u = 0% 0., we then obtain
E [
S E [[[(1 - 7/ A ( - 0.312 + (Z)) -
+ + +
S 10- 0,1 ( 27) ||I 9 (0) - 0-H131 20 [1]W
(54)
Plugging
(4 in (53) and using the assumption 1) <
I II we obtain
ES
[10g - 0.1 2 - 21 - E. 0g 0.) $ (1 ) - 0-11 1/² |55 - Eا11 + Tr{E)
(55)
Bounding the Lyapunov function. Taking the condtional expectation of (22) and using 55 for c= 1 to N, we obtain the following bound on the Lyapunov function
NV
N - E911
E [w'n]
E
100
0.112- 2n(E6-1 e,, 0% - -0.}
1 1
p2
N
N
na)l
- - -2112-112100 -1? E + 211² Tr(22)]
17
1 E512
N
p2 N
N
N
2T²² N
(1 na)
1
100 0.11 + +11 (1-p²
7 1
1 E.12+
Σ
Tr
p²
N
N
and the result of the Lemma follows from the Tower property.
Theorem F.2 (Convergence rate). Assume A[ and A3 2). Then, for any 17 S 1
and T > 0, it holds
2L
[lwk]= S (1 (x) (180- (100-0.12- 12
172 A Aneter) 8
2n²²
+
Tr(2)),
C
where Ç = min p?),
Corollary F.3 (Iteration complexity). Let > 0. Set 1 = min
(L 88
and p
TTa (so that
Ç = na). Then, E[yhk] S 2 as long as the number of iterations is
2L 40, : Pa²
|10g - 11 + min
2 8n Ahoter
1
K max
log
2e
which corresponds to an expected number of communication rounds
(v
2L
40
|100 - 0,1 + min 1
2 80 heter
T Z max
log
a
??a
2ea
43

---

Theorem F.4 (No linear speedup in the probabilistic communication setting with control variates).
The bounds obtained in Theorem F.2 are minimax optimal up constants that are independent from the problem. Precisely, for every (p. 1) there exists a FLSSA problem such that
Eluk] = (1- (100- - 0.112 + Tf p
2n1²
beter + 3e
C
where we have defined Ç min (2na, p²)).
Proof. Define for all c e [M]
A al,
b bolt.
where is vector whom all coordinates are equal to 1. We also consider the sequence of i.i.d random
variables (Zg) such that that for all c E [M]and S S T, z follows Rademacher distribution. Moreover, we define
A (Z A (Z( = 5e ZZu.
In particular this implies
(2)2)
Zeu
We follow the same proof of Lemma F.1 until the chain of equalities breaks. Thereby, we start from
172 p²
E p/
E
10%
0.112
E|l
N
1
E
II - (Z)) 0.} - n (Z)))l + +(1 - p²)
1152 - =
p c=1
N
72
E
[I(1 - A 10 - 0.} mw (2)))1 + (1 - pマ
| E
11a
c=1
1a))1 0.112 (Z)) + (1 - p²) 11²
E
146-1
E
where we used that (Z)))) = A Unrolling the recursion gives the desired result.
G Experimental Details and Additional Experiments
G.1 Experimental Details
Here, we give additional details regarding the numerical experiments. The environments used are instances of Garnet, where we use 30 states, embedded via random projection in d = 8- dimensional space. We use two actions, and consider branching factor of two, meaning that, from each state, one can transition to two different states with some probability. The rewards are then drawn uniformly randomly from the interval [0, 1].
In the homogencous setting, we sample one Garnet environment. Each client then receives perturbation of this instance, where we perturb all non-zeros probabilities of transition from one state to another and all rewards with a random variable ~ (0, 0.02).
In the heterogeneous setting, environments, with the same parameters. Half of the agents receive the first environment, and the second half receive the second environment. As in the homogeneous setting, each agent's environment slightly differs from the base environment by a small perturbation ~ 14(0, 0.02).
proceed similarly, except that sample two different Garnet
All the experiments presented in this paper can be run single laptop in just few hours.
44

---

101
1071
3011
10"h
10-1
10 10
10
16
10
30
10
50
16
30
30
10
90 20 10
Gommmna atane [x (0000)
Commiicatiooe (=1000)
Commizatio (x
Communattion (x
Communiittinne
(a) Homogeneous,
(h) Homogencous,
(c) Homogeneous,
(d) Homogenenus,
(c) Homogeneous,
H =
H 10
H 100
H 1000
10000
101
107
101
RIESA SOAFFESA
10
10
-31 Homogeneous, = 10000
(=1000)
(f) Homogeneous,
g H = 10
Homogeneous,
(h) Homogeneous,
(i) Homogeneous,
N =
H = 100
H 1000
Figure 3: MSE function of the number of communication rounds for FedLSA and SCAFFLSA applied to federated TD(0) in homogeneous settings with 7 = 0.1, for different number of agents (N = 10 on the first line, N = 100 on the second line) and different number of local steps. Green For each algorithm, we report the average
dashed line FedLSA's bias, as predicted by Theorem 4.1
MSE and variance over 5 runs.
10"1
11-1
00
30-1
10-1
30
10
30
0
10
100
Communicatier (0000)
Commun instime (x1000)
Commuizaaiion (x100)
Commmnsations (x100)
Commintinttio
(a) Heterogeneous, (b) Heterogeneous,
(c) Heterogeneous,
(d) Heterogeneous, (e) Heterogeneous,
H =
= 10
H 100
H 1000
10000
06
R-ESA
1071
10"1
10"5
(=1000)
Commmnaattion
Heterogeneous,
Heterogeneous,
(h) Heterogeneous,
Heterogeneous,
Heterogeneous.
H =111
H 100
H 1000
= 10000
Figure 4: MSE as function of the number of communication rounds for FedL and SCAFFLSA applied to federated TD(0) heterogeneous settings with 17 = 0.1, for different number of agents (N 10 on the first line, N = 100 on the second line) and different number of local steps. Green dashed line FedLSA's bias, predicted by Theorem 4.1 For each algorithm, we report the average MSE and variance over 5 runs.
G.2 Additional Experiments: Number of Local Steps and Smaller Step-Size
In this section, we give more experimental results for FedLSA and SCAFFLSA. We use the same setting as in Section 6 but use more settings of local steps.
In Figure and Figure we give report the counterpart of Figure I with a wider ranger of number of local updates H E {I, 10, 100, 1000, 10000). The results obtained here match with observations from Section 6 in homogeneous settings, FedL SCAFFLSAexhibii very similar behavior. In both methods, increasing the number of local steps speeds-up the training, until the stochas- tie noise dominates. At this point, both algorithms reach a stationary regime with similar error. In heterogeneous settings, while FedLSA's bias is smaller than the variance of its iterates, train-
45

---

10
10
10"2
10 Gommoniattor wwwaannwxxiio (x110000)
30
10 30
70 Communiiotitee
Commariee instime (x1000)
Commiization (x100)
Comminstiion (x100)
(a) Homogencous,
(b) Homogencous,
(c) Homogeneous,
(d) Homogencous,
(c) Homogencous,
H
=1
H 10
H = 100
H 1000
H 10000
10-5
011
30
10m1
10 30
16
10
30
1n
50
16
30
10
90
10
100 Communiiotitnne
Gommmnettare (xc (C000)))
Commiicatione (=1000)
Commiiatio (>
Communittiion (x
(f) Homogencous,
(g) Homogencous,
(h) Homogeneous,
Homogenenus,
Homogenenus, 10000
#=1
=
H 100
H 1000
Figure 5: MSE as function of the number communication rounds for FedLSA and SCAFFLSA applied to federated TD(0) in homogeneous settings with 0.01, for different number of agents (N 10 on the first line, N 100 on the second line) and different number of local steps. Green dashed line is FedLSA's A's bias, predicted by Theorem 4.1 For each algorithm, report the average MSE and variance over 5 runs.
1r9
30"2
10"2
11r4
10
30
20 Communictt
(0000))
(+1000)
(x100)
(a) Heterogeneous,
(b) Heterogeneous,
(c) Heterogeneous,
(d) Heterogeneous,
(e) Heterogeneous,
H
==
H = 10
H = 100
H 1000
H = 10000
ROSPBERs didd
11"
10
11-
10
10
0 36 Cosminicatauus (x (0000)
10 20
31
0 10 21 30 10 (0
10
23 30
20
21 Comcunabation (XII)
10 20
20
20
60
Commoniettoon (+1000)
Commanaattion (x 100)
Commeniiattoo kone
(f) Heterogeneous, (g) Heteeoogeeeous, (h) Heeterogeneous.
(i Heterogeneous,
Heterogeneous,
H- ===1
= 10
H 100
H 1000
10000
Figure 6: MSE function of the number communication rounds for FedLSA and SCAFFLSA applied to federated TD(0) in heterogeneous settings with 17 = 0.01, for different number of agents (N 10 on the first line, N 100 on the second line) and different number of local steps. Green dashed line is FedLSA's bias, predicted by Theorem 4.1 For each algorithm, we report the average MSE and variance over 5 runs.
ing speeds up when the number of local steps increases. After that point, bias dominates, while SCAFFLSApreserves the speed-up by eliminating this bias.
Finally, report in Figure and Figure 6 the results when running the same experiments using a smaller step size = 0.01 for different number of agents and local updates. this setting, all algorithms manage find better estimators, since the amount of variance depends on the step size (as seen Theorem 4.1 and Theorem 5.1p. Additionally, FedLSA's bias smaller than in Figure 7
which is also in line with the upper bound @| bi) [|]
nHE[||0-00 -A1l from Theorem 4.1
46

---

10'
10
131
10
10"
Desti
10
10-3
10-2
40
30
50
30
40
Commoniiestiors (x:0000)
Commmnacstions (x]
Conmrmaections (x:1000)
Commamiations (x100)
(a) Homogeneous,
(b) Homogeneous.
(c) Homogeneous,
(d) Homogeneous,
N 10, H 10
= 10, H 1000
N 100, H 10
N
100, 1000
10a
10
10
10
FaRLSA
SCAFFFII
10
10
10"1
10
FaITD cillaua lio
PAlLEN'S
10
10
10
10
30
10
211
30
0
20
40
10
30
50
Communication 10000)
Communications (x100)
Conmmnications (x000))
Communicstion (x10)
(c) Heterogeneous,
(f) Heterogeneous,
(g) Heterogeneous,
(h) Heterogeneous,
N = 10, H = 10
N 10, H 1000
N 100, H 10
N 100, H 1000
Figure 7: MSE function of the number of communication rounds for FedLSA and SCAFFLSA applied to federated TD(0) in homogeneous and heterogeneous settings, for different number of agents and number of local steps. Green dashed line is FedLSA's bias, as predicted by Theorem For each algorithm, we report the average MSE and variance over 5 runs.
10"
10
1/
10"
FaILSA
SCAPFLSAA
FellD
10-2.
10-5.
10-9
10-
10
10
10
0
10
20
20
10
50
10
20
30
00
50
01
10
20
30
00
50
0
10
20
30
00
50
Conmomiiottioes (x1000)
Commmniiottions (x10)
Communmictions (x1003)
Cocurniictioos (x10)
(a) Homogencous,
(b) Homogencous,
(c) Homogencous,
(d) Homogencous,
N
10, H 10
N 10, H = 1000
N 100, H = 10
N 100, 1000
102
10"
RolLSA SCAFFFISA
10-2
10"2
10
10
10
10
10
10
10
30
50
10
20
30
40
50
0
20
30
40
10
20
30
50
Commmiications (x 1000)
Commuiicttinn
(x100
Communications
(x100)
Comminications
(x10)
(e) Heterogeneous,
(1) Heterogeneous,
Heterogeneous, 100,
(h) Heterogeneous,
10,
10,
1000
100, H 1000
Figure 8: MSE as function of the number communication rounds for FedLSA and SCAFFLSA applied to federated TD(0) in homogeneous and heterogeneous settings, for different number of agents and number of local steps, using a smaller step size 17 = 0.01. Green dashed line is FedLSA's bias, predicted by Theorem 4.1 For each algorithm, we report the average MSE and variance over runs.
G.3 Additional Experiments: Convergence of FedLSA
In Figure 7 and Figure
give the counterpart of Figure T where we additionally plot the MSE the estimator de + (bi.bi) for different settings of all parameters. We recall that (bi.bi) I (n)) ( #H is the bias of FedLSA, proved in Theorem 4.1 Therefore, Or + (bbibb) is
47

---

proper estimator of 0., although, of course, it cannot be computed in practice since the bias (bbi.i is unknown. and we see in Figure 7 that, in homogeneous settings, we recover the same error as FedLSA and SCAFFLSA. Moreover, in heterogeneous settings, it has error similar the one of SCAFFLSA, meaning that FedLSA, once its bias is removed, converges similarly to SCAFFLSA. The latter, however, does not require to remove unknown bias, and directly estimates the right quantity.
48

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract, we claim (i) to analyze the FedLSA algorithm. with exact caracterization of the bias (see Section 4). (ii) to propose and analyze SCAFFLSA (see
Section 5 and apply it federated TD (see Corollary 4.4 Corollary 5.3 We also
propose results in the markovian sampling scheme in Corollary 4.5 and perform numerical
analysis of our method applied to federated TD in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The main limitation of our paper is that the numerical analysis is done on federated TD on synthetic dataset. Nonetheless, we emphasize that our paper a theoretical paper, and that these experiments rightfully serve the purpose of illustrating the theoretical results.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
49

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All our theoretical results are provided with clear references to assumptions, that all state in Section ensure that these assumptions easy to find. All results given with proofs, that are correctly references for each theorem and corollary.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Numerical results are stated with complete description of the environments that are used, as well as the precise sets of hyperparameters that we used. We stress that the code (in Python) is provided as supplementary with the paper, making it easy for one to reproduce our numerical experiments. Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
50

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open tions to faithfully reproduce the main experimental results, as described in supplemental material?
the data and code, with sufficient instruc-
Answer: [Yes]
Justification:
All the code is open source, and available at https://githu: com/
gmangold/scaffls.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
public/ poolic/guides// CodeSubmissionoolooo
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https wttp:/iccggiiee//eeeeeeeee htte:/gguuudee/oeCSuubbiiiii www.oodeuumiiisoonnee..
/ //nips.
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The algorithm used in the numerical experiments exactly the algorithms described in the paper. The Garnet environements are given with the parameters used for generation, and with reference the original problem.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All experimental results are given with error bars that consist either in the standard deviation over multiple independent runs, or the minimal/maximal values obtained over multiple independent runs.
51

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments in this paper are ran on a single laptop, and can casily be reproduced by anyone with very limited computational power.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't 'tttt make it into the paper).
paper (e.g., preliminary or failed experiments that
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttpp////aarrrps..c//////l/llls
Answer: [Yes]
Justification: This paper of purely theoretical nature, and the proposed methods do not deal with sensitive attributes that could induce unfairness privacy issues.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
52

---

Answer: [NA]
Justification: This paper is of purely theoretical nature, and although the proposed methods could help deploy more federated learning solutions, this does not constitute risk for societal harm.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: N/A.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
N/A since no existing assets used.
Guidelines:
The answer NA means that the paper does not existing assets.
53

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
N/A since the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: N/A since the paper does not involve crowdsourcing nor research on human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
54

---

Justification: Justification: N/A since the paper does not involve crowdsourcing nor research on human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
55


Reviews:
[{"review_id": "rSaisjilzM", "reviewer": "Reviewer_WekN", "summary": "This paper first analyzed the performance of federated linear stochastic approximation or FedLSA algorithm. Second, it proposed a new algorithm called stochastic controlled averaging for Federated LAS or SCAFFLSA and analyzed its performance. The key idea of SCAFFLSA is to use a control variable to mitigate the client drift. The performance of the proposed algorithm was verified using experiments.", "questions": "What are the functions $\\boldsymbol{A}^c()$ and $\\boldsymbol{b}^c()$ like in practice? Could you please provide some examples?", "limitations": "There was no discussion on the limitations of the proposed algorithm.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposed a new analytical framework to analyze the sample and communication complexity of FedLSA. Using this approach, the paper analyzed the performance of SCAFFLSA. The paper also extended the analytical framework to Federated TD learning. \n\n2. The paper proposed a new algorithm, SCAFFLSA, which mitigate the client drift using a control variable. The sample and communication complexity of SCAFFLSA is significantly better than that of FedLSA and Scaffnew. The performance analysis of SCAFFLSA was also extended to Federated TD.", "weaknesses": "The experiments are relatively weak. It will be more beneficial if the authors could provide more applications of the proposed algorithm to other problems, especially for federated TD learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**The experiments are relatively weak. It will be more beneficial if the authors could provide more applications of the proposed algorithm to other problems, especially for federated TD learning.**\nThe Garnet problems used in our experiments are common in the TD literature and serve the purpose of illustrating numerically our theoretical findings. \nNonetheless, we are happy to add more experiments on other problems if the reviewer has some specific problems to suggest.\n\n**What are the functions $A^c()$ and $b^c()$ like in practice? Could you please provide some examples?**\nIn TD learning, the system is given by $\\bar{A}^c = \\mathbb{E} [\\phi(s)\\{\\phi(s)-\\gamma \\phi(s')\\}^{\\top}]$ and $\\bar{b}^c = \\mathbb{E}[\\phi(s) r^c(s,a)]$, where $s \\sim \\mu^c, s' \\sim P^{\\pi,c}(\\cdot|s)$.\nThus, taking the sampling set $\\mathsf{Z} = \\mathcal{S} \\times \\mathcal{A} \\times \\mathcal{S}$, we can define $A^c(s, a, s') = \\phi(s)\\{\\phi(s)-\\gamma \\phi(s')\\}^{\\top}$ and $b^c(s, a, s') = \\phi(s) r^c(s,a)$.\nThe points $s, a, s'$ are then either i.i.d. samples (following Assumption TD1) or a Markov chain (following Assumption TD2).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ds0tSOvgoA", "reviewer": "Reviewer_bpaa", "summary": "This paper provides a non-asymptotic analysis of Federated Linear Stochastic Approximation. The authors provide (biased and unbiased) finite-time MSE bounds for general LSA and TD learning under the assumption that the noise is i.i.d.. For Markovian noise, only an unbiased MSE bound is provided. Most importantly is that these bounds express this error as a function of the step-size used, number of agents and number of local updates. Finally, a new algorithmic variant, namely, SCAFFLSA is introduced, reducing communication between agents while maintaining the linear speed up in the algorithm. The contributions of the paper are illustrated through numerical studies.", "questions": "- Is it possible for the authors provide a table similar to Table 1 in order to illustrate and compare the different outcomes between the three different scenarios analyzed by the paper (i.r. the i.i.d. , Markov and TD setting)? \n\n-Do the authors believe that their analysis could be extended to federated learning algorithms with vanishing step-size?\n\n- It is possible that I missed this in the main text, but are any drawbacks to using SCAFFLSA instead of Federated LSA?", "limitations": "The authors identify and state which assumptions are necessary to hold for each of the results to be true, so the limitations of this work are objectively identified.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The reviewer is not very familiar with the federated learning literature, but as far as they are aware, most of the ideas of the paper are new. \n\nThe reviewer was unable to look at all proofs in detail, but have not identified any issues with respect to correctness.", "weaknesses": "The organization of the paper is not great. First, it is very hard to follow the main text given the amount of symbols and equations. Secondly, contributions related to i.i.d and Markovian noise and TD learning seemed to be scrambled together. I particularly think that splitting the results into different sections (one for i.i.d. noise, one for Markovian noise and one tailored to TD learning) would improved the readability of the paper a lot.\n\nAlso, there is a missing \"c\" superscript right above equation (1) in Algorithm 1.\n\nThe paper should be revised for clarity and typos.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Is it possible for the authors provide a table similar to Table 1 in order to illustrate and compare the different outcomes between the three different scenarios analyzed by the paper (i.r. the i.i.d. , Markov and TD setting)?**\nThank you for the suggestion, which will greatly help to improve the readability of our paper. We will add the following table, instantiating our results for TD learning, in the camera ready version. In this table, we highlight the dependence on the discount factor $\\gamma$ and on the smallest eigenvalue of the $\\Sigma_\\varphi^c$ (see Assumption TD3).\nRegarding Markovian sampling, complexity is the same as i.i.d. setting up to a multiplicative factor $\\max_c \\tau_{mix}(c)$ (as defined in Assumption A2) in the number of local samples $H$. We will add a sentence in both tables' captions mentioning this.\n\n| Algorithm                   | Communication complexity $T$                                                                                         | Local updates $H$                               | Sample complexity $TH$                                                                                           |\n|-----------------------------|------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------|---------------------------------------------------------------------------------------------------------------------|\n| FedTD (Doan 2020)          | $\\mathcal{O}\\left(\\tfrac{N^2}{(1-\\gamma)^{2} \\nu^{2} \\epsilon^2} \\log \\tfrac{1}{\\epsilon}\\right)$                    | $1$                                            | $\\mathcal{O}\\left(\\tfrac{N^2}{(1-\\gamma)^{2} \\nu^{2} \\epsilon^2} \\log \\tfrac{1}{\\epsilon}\\right)$                 |\n| FedTD (Cor 4.4)            | $\\mathcal{O} \\left({\\tfrac{1}{ (1-\\gamma)^{2} \\nu^{2} \\epsilon}} \\log\\tfrac{1}{\\epsilon} \\right)$                     | $\\mathcal{O}\\bigl(\\tfrac{1}{ N \\epsilon } \\bigr)$ | $\\mathcal{O}\\left(\\tfrac{1}{N (1-\\gamma)^2\\nu^2\\epsilon^2} \\log\\tfrac{1}{\\epsilon}\\right)$                        |\n| SCAFFTD (Cor. 5.3)      | $\\mathcal{O}\\left(\\tfrac{1}{(1-\\gamma)^2\\nu^2} \\log\\tfrac{1}{\\epsilon}\\right)$                                        | $\\mathcal{O}\\bigl(\\tfrac{1}{N\\epsilon^2} \\bigr)$ | $\\mathcal{O}\\left(\\tfrac{1}{N (1-\\gamma)^2\\nu^2\\epsilon^2} \\log\\tfrac{1}{\\epsilon}\\right)$                         |\n\n**The organization of the paper is not great. First, it is very hard to follow the main text given the amount of symbols and equations. Secondly, contributions related to i.i.d and Markovian noise and TD learning seemed to be scrambled together. I particularly think that splitting the results into different sections (one for i.i.d. noise, one for Markovian noise and one tailored to TD learning) would improved the readability of the paper a lot.**\nWe will make the separation between results on general federated LSA and federated TD more clear, by stating first the general results in i.i.d. and markovian settings (in two different paragraph), then moving to federated TD. We will also use the additional page in the camera ready to give more details regarding equations and mathematical symbols. If you have any additional suggestion regarding presentation, we are happy to hear it to try to make the paper as clear as possible.\n\n**Do the authors believe that their analysis could be extended to federated learning algorithms with vanishing step-size?**\nThe analysis could indeed easily be extended to federated linear stochastic approximation with vanishing step sizes, using the same technique. We refrained from doing so due to space limitation.\n\nRegarding extension to more general \"federated learning\", we want to emphasize that our analysis already works for the special case of quadratic problems $\\min_\\theta \\| X \\theta - y \\|^2$, that can be cast as $X^\\top X \\theta = X^\\top y$, and fit our assumptions as long as $X^\\top X$ is invertible. Still, we stress that our analysis is more general since we do not assume $\\bar{A}^c$ to be symmetric.\nExtending our analysis to other settings, e.g. for strongly-convex and smooth problems is much more technical, and is a very interesting direction for future research.\n\n**It is possible that I missed this in the main text, but are any drawbacks to using SCAFFLSA instead of Federated LSA?**\nThis is the main claim of our paper: in terms of sample and communication complexity, SCAFFLSA is guaranteed to perform as good as FedLSA in all settings, and can significantly reduce communication cost in heterogeneous settings. We show this theoretically, and illustrate it numerically; we refer the reviewer to the pdf attached to the general rebuttal for additional numerical evidence of this.\n\nThe only drawback of SCAFFLSA lies in the fact that each agent is required to store an additional vector (the local control variate), which increases the cost in terms of memory for each agent. This drawback is shared with all control variates methods (such as Scaffold, Scaffnew...), and is generally not a problem provided agents have access to sufficiently large memory.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Dqd05tOID5", "reviewer": "Reviewer_czvr", "summary": "This paper analyzes the convergence of scaffnew in the quadratic setup and achieves a linear speedup in the number of clients.  It is not attained by the original paper of Scaffnew. Additionaly, the author find an application of the federated quadratic problem -- Federated\nLinear Stochastic Approximation and TD Learning.", "questions": "According to my understanding, this work saves more communication complexity compared with scaffnew, while it is not claimed by the authors. This is observed in Table 1. Is it another advantage of this analysis? \n\nCan the theoretical analysis be extended to a general case?\n\nThe comparison in Figure 1 is hard to catch. Can you plot them in one figure for comparison, at least using the same legend? And considering more value of H and N.", "limitations": "The achieved speedup holds only for quadratic setup and the application of the quadratic loss function is quite limited.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper tries to analyze the convergence of scaffnew in the quadratic setup and achieves a linear speedup in the number of clients.  It is not attained by the original paper of Scaffnew.", "weaknesses": "The achieved speedup holds only for quadratic setup and the application of the quadratic loss function is quite limited. \nThe experiments are a little simple.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**The achieved speedup holds only for quadratic setup and the application of the quadratic loss function is quite limited.**\nWe emphasize that our analysis holds for the general setting of linear stochastic approximation, which encompasses minimization of quadratic functions, but also works for other settings where the system matrix is not symmetric. This is crucial, as the matrices involved in TD learning are not symmetric. We stress that our analysis is the first of its kind for federated LSA.\n\n**The experiments are a little simple.**\nThe Garnet problems used in our experiments are common for federated TD, and the only problem that we are aware of in the federated TD literature. We stress that our paper is a theoretical paper, and the purpose of our experiment is thus only to illustrate our theory numerically.\nNonetheless, we are happy to add more experiments on other problems if the reviewer has some specific problems to suggest.\n\n**According to my understanding, this work saves more communication complexity compared with scaffnew, while it is not claimed by the authors. This is observed in Table 1. Is it another advantage of this analysis?**\nThis is indeed the case, thank you for pointing it out. We will make sure to add a sentence about this in the discussion after Corollaries 5.2 and 5.3.\n\n**Can the theoretical analysis be extended to a general case?**\nExtending our analysis to other settings, e.g. for strongly-convex and smooth problems is much more technical, and is a very interesting direction for future research.\n\n**The comparison in Figure 1 is hard to catch. Can you plot them in one figure for comparison, at least using the same legend? And considering more value of H and N.**\nThank you for pointing this issue, we will update the plots in the camera ready version, making sure that the y-axis is the same each time. We will also provide addditional plots for $H \\in \\\\{1, 10, 100, 1000, 10000\\\\}$ and $N \\in \\\\{10, 100\\\\}$ in the appendix; we add these additional plots to the pdf attached to the global rebuttal. If you have any additional suggestions to improve the experiments in the camera ready, we will be happy to integrate them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their thorough feedback. We are pleased that reviewers deemed our contributions as new ("new analytical framework", "new algorithm", reviewer WekN; and "the ideas of the paper are new", reviewer bpaa), and that our analysis technique is the first to show that Scaffnew has linear speed-up ("and achieves a linear speedup in the number of clients. It is not attained by the original paper of Scaffnew", reviewer czvr).

Reviewers WekN and czvr found our experiments a little bit too simple. Although we stress that this paper is a theoretical paper, we understand the concern and provide some more experiments, with different settings of number of agents $N$ and number of local steps $H$ on a federated Garnet problem. The results can be found in the file attached: when agents are homogeneous, both algorithms perform very similarly; when agents are heterogeneous, FedLSA gets more and more biased as the number of iterations grow, while SCAFFLSA still reaches the same precision even when number of communication is divided by 1000.

We remark that the experimental setup that we used is very common in federated temporal difference learning, and we are not aware of other problems used in the literature. If reviewers have suggestions for other problems, we will be happy to add them to the manuscript.

We address the other more specific concerns directly in the rebuttal to each reviews.

Meta-review: This paper employs control variates to correct for client drift, thereby improving the sample and communication complexity of the federated linear stochastic approximation (FedLSA) algorithm. All reviewers concur that it is a strong paper with significant contributions. We therefore recommend its acceptance.
Decision: Accept (poster)