SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning

Authors: paul  mangold
sergey  samsonov
reda  alami
alexey  naumov
eric  moulines
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 19:04:53

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.

Main paper: 
 introduction: 
 Heterogeneity has a major impact on communication complexity in federated learning (FL) [28, 36] . In FL, multiple agents use different local oracles to update a global model together. A central server then performs a consensus step to incrementally update the global model. Since communication with the server is costly, reducing the frequency of the consensus steps is a 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, 51] . In this paper, we investigate the impact of heterogeneity in the field of federated linear stochastic approximation (federated LSA). The goal is to solve a 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 an 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.A 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 Table 1 : Communication and sample complexity for finding a solution with MSE lower than ϵ 2 for FedLSA, Scaffnew, and SCAFFLSA with i.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.Communication T Local updates H Sample complexity T HFedLSA [12] O N 2 a 2 ϵ 2 log 1 ϵ 1 O N 2 a 2 ϵ 2 log 1 ϵ FedLSA (Cor. 4.3) O 1 a 2 ϵ log 1 ϵ O 1 N ϵ O 1 N a 2 ϵ 2 log 1 ϵ Scaffnew (Cor. F.3) O 1 aϵ log 1 ϵ O 1 aϵ O 1 a 2 ϵ 2 log 1 ϵ SCAFFLSA (Cor. 5.2) O 1 a 2 log 1 ϵ O 1 N ϵ 2 O 1 N a 2 ϵ 2 log 1 ϵshow that it is possible to reduce communication complexity using control variates while preserving the linear speed-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 ccommunicationsontrol variates. This allows to prove that SCAFFLSA simultanously maintains linear speedup and reduced communication.To our knowledge, this is the first time that these two phenomenons are proven to occur simultaneously in FL. • 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 a synthetic overview of this paper's theoretical results in Table 1 in the general federated LSA setting, and we instantiate these results for federated TD learning in Table 2 (Appendix E). We start by discussing related work in Section 2. We then introduce federated LSA in Section 3, and analyze it in Section 4. In Section 5 we introduce SCAFFLSA, a novel strategy to mitigate the bias. Finally, we illustrate our results numerically in Section 6. Since an important application of LSA 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 ∥A∥ its operator norm. Setting N for the number of agents, we use the notation E c [a c ] = N -1 N c=1 a c for the average over different clients. For the matrix A = A ⊤ ⪰ 0, A ∈ R d×d and x ∈ R d we define the corresponding norm ∥x∥ A = √ x ⊤ Ax. For sequences a n and b n , we write a n ≲ b n if there exists a constant c > 0 such that a n ≤ cb n for n ≥ 0. 
related work: 
 Federated Learning. With few exceptions (see e.g. [12] ), 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 a variety of conditions covering both homogeneous [31, 20] and heterogeneous agents [25, 27] . Different ways of measuring heterogeneity for FedAvg have then been proposed [51, 41] . 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, a method that tames heterogeneity 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 hasInput: η > 0, θ 0 ∈ R d , T, N, H > 0 for t = 0 to T -1 do Initialize θ t,0 = θ t for c = 1 to N do for h = 1 to H do Receive Z c t,h and perform local update:EQUATIONbeen shown in [37] (with the analysis of ProxSkip, which generalizes Scaffold) that such methods accelerate training. However, unlike Scaffold, the analysis of [37] loses the linear speedup in the number of agents. Several other methods with accelerated rates have been proposed [35, 5, 6, 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, 9] , with the asymptotic analysis under linear function approximation (LFA) setting performed in [49, 48] . Several non-asymptotic MSE analyses have been carried out in [4, 8, 42, 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 [11, 22] . Recently, [50] proposed an analysis of 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 a 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 
federated linear stochastic approximation: 
 In federated linear stochastic approximation, N agents collaboratively solve a system linear equation system with the following finite sum structureĀθ ⋆ = b , where Ā = 1 N N c=1 Āc , b = 1 N N c=1 bc ,where for c ∈ [N ], Āc ∈ R d×d , bc ∈ R d . We assume the solution θ ⋆ to be unique, and that each local system Āc θ c ⋆ = bc also has a unique solution θ c ⋆ . The values of Āc 's and bc 's can be different, representing the different realities of the agents. In federated LSA, neither matrices Āc nor vectors bc are observed directly. Instead, each agent c ∈ [N ] has access to its own observation sequence (Z c k ) k∈N , that are independent from one agent to another. Agent c obtains estimates {(A c (Z c k ), b c (Z c k ))} k∈N of Āc and bc , where A c : Z → R d×d and b c : Z → R d are two measurable functions. Naturally, we define the error of estimation of Āc and bc as b c (z) = b c (z) -bc , A c (z) = A c (z) -Āc . This allows to measure the noise at local and global solutions asEQUATIONtogether with the associated covariances,EQUATIONthat are finite whenever one of the following assumptions on the {Z c t,h } t,h≥0 hold. ∞ = max c∈[N ] sup z∈Z ∥ε c (z)∥ < ∞ , C A = max c∈[N ] sup z∈Z ∥A c (z)∥ < ∞ .Moreover, each of the matrices -Āc is Hurwitz.In A2, random matrices A c (z) and noise variables ε c (z) are almost surely bounded. This is necessary for working with the uniformly geometrically ergodic Markov kernels P c . For simplicity, we state most of our results using A1, 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 A2.In a federated environment, agents can only communicate via a central server, which is generally costly. Hence, in FedLSA, agents' local updates are only aggregated after a given time. During the round t ≥ 0, the agents start with a shared value θ t and perform H > 0 local updates, for h = 1 to H, given by the recurrenceEQUATIONwith θ c t,0 = θ t , and where we use the alias Z c t,h = Z Ht+h to simplify notations. Agents then send θ t,H to the server, that aggregates them as θ t = N -1 N c=1 θ c t-1,H and sends it back to all agents. We summarize this procedure in Algorithm 1. Our next assumption, which holds whenever Āc is Hurwitz [19, 39, 15] , ensures the stability of the local updates. A3. There exist a > 0, η ∞ > 0, such that η ∞ a ≤ 1/2, and for η∈ (0; η ∞ ), c ∈ [N ], u ∈ R d , it holds for Z c 0 ∼ π c , that E 1/2 ∥(I -ηA c (Z c 0 ))u∥ 2 ≤ (1 -ηa)∥u∥.A major application of FedLSA is federated TD learning with linear function approximation.Consider N Markov Decision Processes {(S, A, P c MDP , r c , γ)} c∈[N ] with shared state space S, action space A, and discounting factor γ ∈ (0, 1). Each agent c ∈ [N ] has its own transition kernel P c MDP , where P c MDP (•|s, a) specifies the transition probability from state s upon taking action a for this specific agent, as well as its own reward function r c : 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 π, and aim to construct a single shared function, that simultaneously approximates all value functions, defined as, for s ∈ S and c ∈[N ], V c,π (s) = E ∞ k=0 γ k r c (S c k , A c k ) , with S c 0 = s, A c k ∼ π(•|S c k ), and S c k+1 ∼ P c MDP (•|S c k , A c k ) .In the following, we aim to approximate V c,π (s) as a linear combination of features built using a mapping φ : S → R d . Formally, we look for θ ∈ R d such that the function V θ (s) = φ ⊤ (s)θ properly estimate the true value. For c ∈ [N ], we denote µ c the invariant distribution over S induced by the policy π and transition kernel P c MDP of agent c. Our goal is to find a parameter θ c ⋆ which is defined as a unique solution to the projected Bellman equation, see [49] , which defines the best linear approximation of V c,π . This problem can be cast as a federated LSA problem [42, 50] by viewing the local optimum parameter θ c ⋆ as the solution of the system Āc θ c ⋆ = bc , whereĀc = E s∼µ c ,s ′ ∼P π,c (•|s) [ϕ(s){ϕ(s)-γϕ(s ′ )} ⊤ ] , and bc = E s∼µ c ,a∼π(•|s) [ϕ(s)r c (s, a)] . (5)The global optimal parameter is then defined as the solution θ ⋆ of the averaged system( 1 N N c=1 Āc )θ ⋆ = 1 N N c=1bc . As it is the case for federated LSA, this parameter may give a better overall estimation of the value function. Indeed, the distribution µ c of some agents may be strongly biased towards some states, whereas obtaining an estimation that is more balanced across all states may be more relevant.In practice, when computing value functions, the tuples {(S c k , A c k , S c k+1 )} k∈N are sampled along one of the two following rules.TD 1. (S c k , A c k , S c k+1 ) are generated i.i.d.with S c k ∼ µ c , A c k ∼ π(•|S c k ), S c k+1 ∼ P c MDP (•|S c k , A c k ) . TD 2. (S c k , A c k , S c k+1 ) are generated sequentially with A c k ∼ π(•|S c k ), S c k+1 ∼ P c MDP (•|S c k , A c k) . The generative model assumption TD 1 is common in TD learning [8, 30, 42, 45] . It is possible to generalize all our results to the more general Assumption TD 2, sampling over a single trajectory and leveraging the Markovian noise dynamics. This would have a similar impact on our results on TD(0) 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Σ c φ = E µ c [φ(S c 0 )φ(S c 0 ) ⊤ ] ∈ R d×d . TD 3. Matrices Σ c φ are non-degenerate with the minimal eigenvalue ν = min c∈[N ] λ min (Σ c φ ) > 0. Moreover, the feature mapping φ(•) satisfies sup s∈S ∥φ(s)∥ ≤ 1.This assumption ensures the uniqueness of the optimal parameter θ c ⋆ . Under TD 1 and TD 3 we check the LSA assumptions A1 and A3, and the following holds. Claim 3.1. Assume TD 1 and TD 3. Then the sequence of TD(0) updates satisfies A1 and A3 withC A = 1 + γ , ∥Σ c A ∥ ≤ 2(1 + γ) 2 , Tr(Σ c ε ) ≤ 2(1 + γ) 2 ∥θ c ⋆ ∥ 2 + 1 , a = (1-γ)ν 2 , η ∞ = (1-γ) 4 .We prove this claim in Appendix E.1, and refer to [45, 42] for more details on the link between TD and linear stochastic approximation.4 Refined Analysis of the FedLSA Algorithm 
stochastic expansion for fedlsa: 
 We use the error expansion framework [1, 14] for LSA to analyze the MSE of the estimates θ t generated by Algorithm 1. For this purpose, we rewrite local update (4) asθ c t,h -θ c ⋆ = (I -ηA(Z c t,h ))(θ c t,h-1 -θ c ⋆ ) -ηε c (Z c t,h), where ε c (z) is defined in (2) . Running this recursion until the start of local training, we obtainθ c t,H -θ c ⋆ = Γ (c,η) t,1:H {θ c t,0 -θ c ⋆ } -η H h=1 Γ (c,η) t,h+1:H ε c (Z c t,h) , where ε c (z) is as in (3), and we recall that θ c t,0 = θ t-1 , ∀c ∈ [N ]. We also introduced the notationΓ (c,η) t,m:n = n h=m (I -ηA(Z c t,h )) , 1 ≤ m ≤ n ≤ H , with the convention Γ (c,η) t,m:n = I for m > n. Note that by A3, Γ (c,η) t,m:n is exponentially stable. That is, for any h ∈ N, we have E 1/2 ∥Γ (c,η)t,m:m+h u∥ 2 ≤ (1ηa) h ∥u∥. Using the fact θ c t,0 = θ t-1 , and employing (1), we obtain thatθ t -θ ⋆ = Γ(η) t,H {θ t-1 -θ ⋆ } + ρH + τt,H -η φt,H , with Γ(η) t,H = N -1 N c=1 Γ (c,η) t,1:H , (6) where τt,H = 1 N N c=1 {(I -η Āc ) H -Γ (c,η) t,1:H }{θ c ⋆ -θ ⋆ }, φt,H = 1 N N c=1 H h=1 Γ (c,η) t,h+1:H ε c (Z c t,h) are zero-mean fluctuation terms, andρH = 1 N N c=1 (I -(I -η Āc ) H ){θ c⋆θ ⋆ } is the deterministic heterogeneity bias accumulated in one round of local training. Note that ρH 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 decompositionEQUATIONHere θ(tr)EQUATIONt is a zero-mean fluctuation term, with detailed expression provided in Appendix A, and the term θ(bi,bi) t is θ(bi,bi) t = t s=1 ( Γ(η) H ) t-s ρH , where Γ(η) H = E[ Γ(η)σε = E c [Tr(Σ c ε )] , ṽheter = E c ∥Σ c A ∥∥θ c ⋆ -θ ⋆ ∥ 2 .Here σε and ṽheter correspond to the different sources of noise in the error decomposition (7) . The term σε is related to the variance of the local LSA iterate on each of the agents, while ṽheter controls the bias fluctuation term. In the centralized setting (i.e. if N = 1), the ṽheter term disappears, but not the σε term. We now proceed to analyze the MSE of the iterates of FedLSA : Theorem 4.1. Assume A1 and A3. Then for any step size η ∈ (0, η ∞ ) it holds thatE 1/2 ∥θ t - θ(bi,bi) t -θ ⋆ ∥ 2 ≲ ηṽheter aN + η σε aN + Ec[∥Σ c A ∥] HN ∥ ρH ∥ a + (1 -ηa) tH ∥θ 0 -θ ⋆ ∥ ,where the bias θ(bi,bi)t converges in expectation to θ(bi,bi) ∞ = (I - Γ(η) H ) -1ρH at a geometric rate, and is uniformly bounded byE 1/2 [∥ θ(bi,bi) t ∥ 2 ] ≲ ηHEc[∥θ c ⋆ -θ⋆∥] a .The proof of Theorem 4.1 relies on bounding each term from (7) . We provide a proof with explicit constants in Appendix A. Importantly, the fluctuation terms scale linearly with N . Moreover, in the centralized setting (that is, N = 1), the bias terms ρH , θ(bi,bi) t and ṽheter vanish in Theorem 4.1, yielding the last-iterate boundE 1/2 ∥θ t -θ ⋆ ∥ 2 ≲ η σε a + (1 -ηa) tH ∥θ 0 -θ ⋆ ∥, which is known to be sharp in its dependence on η for single-agent LSA (see Theorem 5 in [15] ). Based on Claim 3.1, Theorem 4.1 translates for federated TD(0) as follows. Corollary 4.2. Assume TD 1 and TD 3. Then for any step size η ∈ (0, 1-γ 4 ), the iterates of federated TD(0) satisfy, withχ(θ ⋆ , θ 1 ⋆ , . . . , θ N ⋆ ) = E c [∥θ c ⋆ -θ ⋆ ∥ 2 ] ∨ (1 + E c [∥θ c ⋆ ∥ 2 ]), E 1/2 ∥θ t - θ(bi,bi) t -θ ⋆ ∥ 2 ≲ ηχ(θ⋆,θ 1 ⋆ ,...,θ N ⋆ ) (1-γ)νN + 1 HN ∥ ρH ∥ (1-γ)ν + (1 -η(1-γ)ν 2 ) tH ∥θ 0 -θ ⋆ ∥ .The right-hand side of Corollary 4.2 scales linearly with N , allowing for linear speed-up. This is in line with recent results on federated TD(0), 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 convergence to some fixed, biased value, one can set the parameters of FedLSA such that this bias is small. This allows to rewrite the result of Theorem 4.1 in order to get a sample complexity bound in the following form. N ϵ . Then, to achieve E ∥θ Tθ ⋆ ∥ 2 < ϵ 2 the required number of communications for federated LSA isT = O 1 aη∞ ∨ Ec[∥θ c ⋆ -θ⋆∥] a 2 ϵ log ∥θ0-θ⋆∥ ϵ .In Corollary 4.3, the number of oracle calls scales asT H = O ṽheter∨σε N a 2 ϵ 2 log ∥θ0-θ⋆∥ ϵ, which shows that FedLSA has linear speed-up. Importantly, the number of communications T required to achieve precision ϵ 2 scales as ϵ -1 . In the next section, we will show how this dependence on ϵ -1 can be reduced from polynomial to logarithmic. Now we state the communication bound of federated TD(0). Corollary 4.4. Assume TD 1 and TD 3.Then for any 0 < ϵ <g1(θ c ⋆ ,θ⋆) (1-γ)ν with g 1 = O((1 + ∥θ ⋆ ∥)E c [∥θ c ⋆ -θ ⋆ ∥]). Set η = O (1-γ)νN ϵ 2 Ec[∥θ c ⋆ ∥ 2 ]+1 and H = O Ec[∥θ c ⋆ ∥ 2 +1] N ϵEc[∥θ c ⋆ -θ⋆∥ 2 ] . Then, to achieve E ∥θ T -θ ⋆ ∥ 2 < ϵ 2 ,the required number of communications for federated TD(0) isT = O 1 (1-γ) 2 ν ∨ Ec[∥θ c ⋆ -θ⋆∥] (1-γ) 2 ν 2 ϵ log ∥θ0-θ⋆∥ ϵ .Corollary 4.4 is the first result to show that, even with local training and heterogeneous agents, federated TD(0) can converge to θ ⋆ with arbitrary precision. Importantly, this result preserves the linear speed-up effect, showing that federated learning indeed accelerates the training.The analysis of FedLSA can be generalized to the setting where observations {Z c k } k∈N form a Markov chain with kernel P c . To handle the Markovian nature of observations, we propose a variant of FedLSA that skips some observations (see the full procedure in Appendix B). This follows classical schemes for Markovian data in optimization [40] , as adjusting the number of skipped observations (keeping about 1 observation out of τ mix (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 A 2 and A 3 and let 0 < ϵ < (√ ṽheter∨σεEc[∥θ c ⋆ -θ⋆∥]) 2/5 a ∨ Ec[∥θ c ⋆ -θ⋆∥] a C A . Set the step size η = O aN ϵ 2 ṽheter∨σε ∧ η ∞ ∧ η (M) ∞, where we give the expression of η(M)∞ is (37) . Then, for the iterates of Algorithm 3, in order to achieveE ∥θ T -θ ⋆ ∥ 2 ≤ ϵ 2 , the required number of communication is T = O 1 aη∞ ∨ Ec[∥θ c ⋆ -θ⋆∥] a 2 ϵ log ∥θ0-θ⋆∥ ϵ ,where the number of local updates H satisfiesH log H = O ṽheter∨σε Ec[∥θ c ⋆ -θ⋆∥] maxc τmix(c) log (NT 3 (∥θ0-θ⋆∥+2Ec[∥θ c ⋆ -θ⋆∥]+η∥ε∥∞)/ϵ 2 ) N ϵ.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. = θc t,h-1 -η(A c (Z c t,h ) θc t,h-1 -b c (Z c t,h ) -ξ c t ), 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 ξEQUATIONwhere ω c (z) is defined in (2) . Under A1, it has finite covariance Σ c ω = Z ω c (z)ω c (z) ⊤ dπ c (z). Similarly to the analysis of FedLSA, we use (8) to describe the sequence of aggregated iterates and control variates as, for t ≥ 0 and c ∈ [N ],EQUATIONwhereC c t+1 = H h=1 Γ (c,η)t,h+1:H and ωt+1 = = θc t,h-1 -η(A c (Z c t,h ) θc t,h-1 -b c (Z c t,h ) -ξ c t ) Aggregate local iterates: θ t+1 = 1 N N c=1 θc t,H Update local control variates: ξ c t+1 = ξ c t + 1 ηH (θ t+1 -θc t,H ) Theorem 5.1. Assume A1, A3. Let η, H > 0 such that η ≤ η ∞ , and H ≤ a /240η C 2 A +∥Σ c A ∥ . Set ξ c 0 = 0 for all c ∈ [N ]. Then we have E[∥θ T -θ ⋆ ∥ 2 ] ≲ η N a ∥Σ ω ∥ + 1 -ηaH 2 T ∥θ 0 -θ ⋆ ∥ 2 + η 2 H 2 E c [∥ Āc (θ c ⋆ -θ ⋆ )∥ 2 ] .Corollary 5.2. Let ϵ > 0. Set the step size η = O(min(η ∞ , N aϵ 2 /σω)) and the number local updates toH = O max a η∞(C 2 A +∥Σ A ∥) , ∥Σω∥ N ϵ 2 (C 2 A +∥Σ A ∥) . Then, to achieve E[∥θ T -θ ⋆ ∥ 2 ] ≤ ϵ 2 , the required number of communication for SCAFFLSA is T = O C 2 A +∥Σ A ∥ a 2 log ∥θ0-θ⋆∥ 2 +Ec [∥ Āc (θ c ⋆ -θ⋆)∥ 2 ]a 2 /C 2 A ϵ 2 .We provide detailed proof of these statements in Appendix C. They are based on a novel analysis, where we study virtual parameters θc t,h , that follow the same update as (8) , without the last term ηω c (Z c t,h ). After each round, virtual parameters are aggregated, and virtual control variate updated asθt+1 -θ ⋆ = 1 N N c=1 θc t,H , and ξc t+1 -ξ c ⋆ = ξc t -ξ c ⋆ + 1 ηH ( θt+1 -θt,H) . This allows to decompose We stress that our analysis shows that, in 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 in heterogeneous federated learning, that either have large communication cost, or lose the linear speed-up [24, 37, 21] . To obtain this result, we conduct a very careful analysis of the propagation of variances and covariances of θ t and ξ c t between successive communication rounds. We describe this in full detail in 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 1, where the necessity of controlling the bias' magnitude prevents from scaling H with 1 /ϵ 2 . 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 η), using control variates reduces communication complexity compared to FedLSA.θ t -θ ⋆ = θt -θ ⋆ + θ t , 
application to federated td(0): 
 Applying SCAFFLSA to TD learning, we obtain SCAFFTD(0) (see Algorithm 5 in Appendix E). The analysis of SCAFFLSA directly translates to SCAFFTD(0), resulting in the following communication complexity bound. Corollary 5.3. Assume TD 1 and TD 3 and let 0 < ϵ≤ 8E c [1 + ∥θ c ⋆ ∥ 2 ]/((1 -γ)ν). Set the step size η = O( (1-γ)νN ϵ 2 ∥θ⋆ ∥ 2 +1) and the number local updates toH = O ∥θ⋆ ∥ 2 +1 N ϵ 2. Then, to achieveE[∥θ T -θ ⋆ ∥ 2 ] ≤ ϵ 2, the required number of communication for SCAFFTD(0) is For each algorithm, we report the average MSE and variance over 5 runs.T = O 1 (1-γ) 2 ν 2 log ∥θ0 -θ⋆ ∥ 2 +(1-γ) 2 ν 2 Ec [∥θ c ⋆ -θ⋆ ∥ 2 ] ϵ 2Corollary 5.3 confirms that, when applied to 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) [11, 22, 50] , it 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. In Appendix F, we extend the analysis of 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, 16] , with n = 30 states embedded in d = 8 dimensions, a = 2 actions, and each state is linked to b = 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 a neighborhood of the solution, allowing to observe both transient and stationary regimes. We provide all details regarding the experimental setup in Appendix G. Our code is available either as supplementary material or online on GitHub: https://github.com/pmangold/scafflsa.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, if 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 a better representation of the overall reality. In Figures 1(a ) to 1(d), we plot the MSE with N ∈ {10, 100}, H ∈ {10, 1000} and η = 0.1, with the same total number of updates T H = 500, 000. As predicted by our theory, FedLSA stalls when the number of local updates increases, and its bias (green dashed line in Figures 1(a ) to 1(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 θ ⋆ + θ(bi,bi)∞ in Appendix G. On the opposite, SCAFFLSA's bias-correction mechanism allows to eliminate all bias, improving the MSE until noise dominates. Both algorithms behave alike in homogeneous settings. In the homogeneous setting, we create one instance of a Garnet environment. Then, each agent receives a slightly perturbed variant of this environment. This illustrates a 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 1(e Both algorithms enjoy linear speed-up! In Figure 2 , we plot the MSE obtained once algorithms reach the stationary regime, as a function of the number of agents N = 1 to 1000, for step sizes η ∈ {0.001, 0.01, 0.1, 1} and H ∈ {1, 100}, in both homogeneous and heterogeneous 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 to large bias. Remarkably, and as explained by our theory (see Corollary 5.2), SCAFFLSA maintains this speed-up even in heterogeneous settings. 
conclusion: 
 In this paper, we studied the role of heterogeneity in federated linear stochastic approximation. We proposed a new analysis of FedLSA, where we formally characterize FedLSA's bias. This allows to show that, with proper hyperparameter setting, FedLSA (i) can converge to arbitrary precision even with local training, and (ii) enjoys linear speed-up in 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 a 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 a 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.HSE University Basic Research Program. This research was supported in part through computational resources of HPC facilities at HSE University [29] .[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-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.00582, 2018. 
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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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 as 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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]  
 
 Appendix: For the analysis we need to define two filtration:F + s,h := σ(Z c t,k , t ≥ s, k ≥ h, 1 ≤ c ≤ N), corresponding to the future events, andF - s,h := σ(Z c t,k , t ≤ s, k ≤ h, 1 ≤ c ≤ N ), corresponding to the preceding events. Recall that the local LSA updates are written asθ c t,h -θ c ⋆ = (I -ηA(Z c t,h ))(θ c t,h-1 -θ c ⋆ ) -ηε c (Z c t,h) . Performing H local steps and taking average, we end up with the decompositionEQUATIONwhere we have definedEQUATIONρH = 1 N N c=1 (I -(I -η Āc ) H ){θ c ⋆ -θ ⋆ } , τt,H = 1 N N c=1 {(I -η Āc ) H -Γ (c,η) t,1:H }{θ c ⋆ -θ ⋆ } , φt,H = - 1 N N c=1 H h=1 Γ (c,η) t,h+1:H ε c (Z c t,h ) . The transient term Γ(η) t,H (θ t-1 -θ ⋆ ), responsible for the rate of forgetting the previous iteration error θ t-1θ ⋆ , and the fluctuation term η φt,H , reflecting the oscillations of the iterates around θ ⋆ , are similar to the ones from the standard LSA error decomposition [14] . The two additional terms in (10) reflect the heterogeneity bias. This bias is composed of two parts: the true bias ρH , which is non-random, and its fluctuations τt,H . To analyze the complexity and communication complexity of FedLSA, we run the recurrence ( 6) to obtainEQUATIONwhere we have defined θ(tr)EQUATIONθ(bi,bi)EQUATIONtgives the rate at which the initial error is forgotten. The terms θ(bi,bi) t and θ(fl,bi) t represent the bias and fluctuation due to statistical heterogeneity across agents. Note that in the special case where agents are homogeneous (i.e. Āc = Ā for all c ∈ [N ]), these two terms vanish. Finally, the term θ(fl) t depicts the fluctuations of θ t around the solution θ ⋆ . Now we need to upper bound each of the terms in decomposition (12) . This is done in a sequence of lemmas below: EQUATION∈ (0, η ∞ ) it holds E ∥ θ(fl) t ∥ 2 ≤ ησ ε aN (1 -e -2 ).Proof. We start from the decomposition (13) .With the definition of θ(fl)t andE F + s+1,1 t i=s+1 Γ(η) i,H φs,H = 0, we obtain that E ∥ θ(fl) t ∥ 2 = η 2 t s=1 E ∥ t i=s+1 Γ(η) i,H φs,H ∥ 2 .Now, using the assumption A3 and Minkowski's inequality, we obtain thatEQUATIONIn (a) applied A3 conditionally on F - t-1,H . Hence, by induction we get from the previous formulas thatEQUATIONNow we proceed with bounding E ∥ φs,H ∥ 2 . Indeed, since the clients are independent, we get using ( 11) thatE ∥ φs,H ∥ 2 = 1 N 2 N c=1 E ∥ H h=1 Γ (c,η) s,h+1:H ε c (Z c s,h )∥ 2 = 1 N 2 N c=1 H h=1 E ∥Γ (c,η) s,h+1:H ε c (Z c s,h )∥ 2 ≤ 1 N 2 N c=1 H h=1 (1 -ηa) 2(H-h) E ∥ε c (Z c s,h )∥ 2 .Therefore, using (3) and the following inequality,H-1 h=0 (1 -ηa) 2h ≤ H ∧ 1 ηa , for all η ≥ 0, such that ηa ≤ 1,we getE ∥ φs,H ∥ 2 ≤ 1 N H ∧ 1 ηa σε . Plugging this inequality in (15), we get E ∥ θ(fl) t ∥ 2 ≤ E c [Tr(Σ c ε )] N η 2 H ∧ η a t s=1 (1 -ηa) 2H(t-s) ≤ σε N η 2 H ∧ η a 1 1 -(1 -ηa) 2H ≤ ησ ε aN (ηaH ∧ 1) 1 1 -e -2ηaH, where we used additionallyEQUATIONwhich is valid for x ∈ [0; 1/2]. Now it remains to notice thatx ∧ 1 1 -e -2x ≤ 1 1 -e -2for any x > 0.We proceed with analyzing the fluctuation of the true bias component of the error θ t defined in (13) . The first step towards this is to obtain the respective bound for τs,H , s ∈ {1, . . . , T }, where τs,H is defined in (11) . Now we provide an upper bound for θ(fl,bi) t :Lemma A.2. Assume A1 and A3. Then, for any step size η ∈ (0, η ∞ ) it holdsE 1/2 ∥ θ(fl,bi) t ∥ 2 ≤ 2ηṽ heter N a + 2 E c ∥Σ c A ∥∥ρ H ∥ aH 1/2 N 1/2 .Proof. Recall that θ(fl,bi) t is given (see (13) ) by θ(fl,bi)EQUATIONwhere τs,H and ρH are defined in (11) . We begin with bounding T 1 . In order to do it we first need to bound τs,H . Since the different agents are independent, we haveEQUATIONApplying Lemma D.1 and the fact that(I -η Āc ) h-1 A c (Z c s,h )Γ (c,η) s,(h+1):H (θ c ⋆ -θ ⋆ ) H h=1 is a martingale-difference w.r.t. F - s,h , we get that E[∥((I -η Āc ) H -Γ (c,η) s,1:H ){θ c ⋆ -θ ⋆ }∥ 2 ] = η 2 E[∥ H h=1 (I -η Āc ) h-1 A c (Z c s,h )Γ (c,η) s,(h+1):H {θ c ⋆ -θ ⋆ }∥ 2 ] = η 2 H h=1 E[∥(I -η Āc ) h-1 A c (Z c s,h )Γ (c,η) s,(h+1):H {θ c ⋆ -θ ⋆ }∥ 2 ] ≤ η 2 H h=1 (1-ηa) 2(h-1) {θ c ⋆ -θ ⋆ } ⊤ E[(Γ (c,η) s,(h+1):H ) ⊤ ( A c (Z c s,h )) ⊤ A c (Z c s,h )Γ (c,η) s,(h+1):H ]{θ c ⋆ -θ ⋆ } .Using the tower property conditionally on F + s,h+1 , we getE[(Γ (c,η) s,(h+1):H ) ⊤ ( A c (Z c s,h )) ⊤ A c (Z c s,h )Γ (c,η) s,(h+1):H ] = E[(Γ (c,η) s,(h+1):H ) ⊤ Σ c A Γ (c,η) s,(h+1):H ] ,where Σ c A is the noise covariance matrix defined in (3). Since for any vector u ∈ R d we have∥u∥ Σ c A ≤ ∥Σ c A ∥ 1/2 ∥u∥, we get E[∥((I -η Āc ) H -Γ (c,η) s,1:H ){θ c ⋆ -θ ⋆ }∥ 2 ] ≤ η 2 H h=1 (1 -ηa) 2(h-1) E ∥Γ (c,η) s,(h+1):H {θ c ⋆ -θ ⋆ }∥ 2 Σ c A ≤ η 2 ∥Σ c A ∥ H h=1 (1 -ηa) 2(h-1) E ∥Γ (c,η) s,(h+1):H {θ c ⋆ -θ ⋆ }∥ 2 (19) ≤ Hη 2 (1 -ηa) 2(H-1) ∥Σ c A ∥∥θ c ⋆ -θ ⋆ ∥ 2 .Combining the above bounds in (18) yields thatEQUATION)Thus, proceeding as in (14) together with (20), we getE[∥T 1 ∥ 2 ] = t s=1 E[∥ t i=s+1 Γ(η) i,H τs,H ∥ 2 ] ≤ t s=1 Hη 2 (1 -ηa) 2(H-1) N c=1 ∥Σ c A ∥∥θ c ⋆ -θ ⋆ ∥ 2 N 2 (1 -ηa) 2H(t-s) ≤ Hη 2 (1 -ηa) 2(H-1) (1 -(1 -ηa) 2H )N E c [∥Σ c A ∥∥θ c ⋆ -θ ⋆ ∥ 2 ] ≤ η aN (1 -ηa) 2 Haηe -2Haη 1 -e -2Haη E c [∥Σ c A ∥∥θ c ⋆ -θ ⋆ ∥ 2 ] ≤ 2η N a E c [∥Σ c A ∥∥θ c ⋆ -θ ⋆ ∥ 2 ] .In the bound above we used (16) together with the boundxe -2x 1 -e -2x ≤ 1 2 , x ≥ 0 .Now we bound the second part of θ(fl,bi) t in (17) , that is, T 2 . To begin with, we start with applying Lemma D.1 and we get for any s ∈ {1, . . . , t} and i ∈ {s + 1, . . . , t}, thatt i=s+1 Γ(η) i,H -( Γ(η) H ) t-s )ρ H = t i=s+1 t r=i+1 Γ(η) r,H ( Γ(η) i,H - Γ(η) H )( Γ(η) H ) i-s-1 ρH .Note that,EQUATIONProceeding as in (19) , we get using independence between agents for any u ∈ R d ,E[∥( Γ(η) i,H - Γ(η) H )u∥ 2 ] = 1 N 2 E[∥ N c=1 (Γ (c,η) s,1:H -(I -η Āc ) H )u∥ 2 ] = 1 N 2 N c=1 E[∥(Γ (c,η) s,1:H -(I -η Āc ) H )u∥ 2 ] ≤ Hη 2 (1 -ηa) 2(H-1) N 1 N N c=1 ∥Σ c A ∥ ∥u∥ 2 .Hence, using (21) , we getE[∥ t i=s+1 Γ(η) i,H -( Γ(η) H ) t-s ρH ∥ 2 ] = Hη 2 (1 -ηa) 2H(t-s)-2 E c ∥Σ c A ∥ N ∥ρ H ∥ 2 .Combining the above estimates in (17) , and using Minkowski's inequality, we getE 1/2 [∥T 2 ∥ 2 ] ≤ H 1/2 η (1 -ηa)N 1/2 E c ∥Σ c A ∥∥ρ H ∥ t-1 s=1 (1 -ηa) H(t-s) ≤ 2 aH 1/2 N 1/2 Haηe -Haη 1 -e -Haη E c ∥Σ c A ∥∥ρ H ∥ ≤ 2 aH 1/2 N 1/2 E c ∥Σ c A ∥∥ρ H ∥ ,where we used that ηa ≤ 1/2 and xe -x 1e -x ≤ 1 , x ≥ 0 . and the statement follows.EQUATIONProof. Using the identity,EQUATIONand the inequalityEQUATIONUsing ( 23) with u = η Āc for all c, we getρH = 1 N N c=1 Hη Āc -η 2 ( Āc ) 2 H-2 k=0 (-1) k H k + 2 (η Āc ) k ,by definition of θ c ⋆ and θ ⋆ , we have thatN c=1 Āc (θ c ⋆ -θ ⋆ ) = N c=1 Āc θ c ⋆ -( N c=1 Āc )θ ⋆ = N c=1 bc - N c=1bc = 0. Using this and ( 24), we finally get (22) .Lemma A.4. Assume A1 and A3. Then for any step size η ∈ (0, η ∞ ) we haveE 1/2 [∥ θ(tr) t ∥ 2 ] ≤ (1 -ηa) tH ∥θ 0 -θ ⋆ ∥Proof. Proceeding as in (14) for any u ∈ R d we haveE 1/2 [∥ t s=1 Γ(η) s,H u∥ 2 ] ≤ (1 -ηa) tH ∥u∥Using this result for u = θ 0θ ⋆ we get the statement.Lemma A.5. Assume A1 and A3. Then for any η ∈ (0, η ∞ ) we have∥ θ(bi,bi) t -(I - Γ(η) H ) -1 ρH ∥ ≤ (1 -ηa) tH ∥(I - Γ(η) H ) -1 ∥∥ρ H ∥Proof. Using A3 and Minkowski's inequalitty, we get∥ θ(bi,bi) t -(I - Γ(η) H ) -1 ρH ∥ = ∥(I - Γ(η) H ) -1 ( Γ(η) H ) t ρH ∥ ≤ ∥(I - Γ(η) H ) -1 ∥∥( Γ(η) H ) t ρH ∥ ≤ ∥(I - Γ(η) H ) -1 ∥ 1 N N c=1 ∥(I -η Āc ) H ( Γ(η) H ) t-1 ρH ∥ ≤ (1 -ηa) H ∥(I - Γ(η) H ) -1 ∥∥( Γ(η) H ) t-1ρH ∥ and the statement follows.Theorem A.6. Assume A1 and A3. Then for any step size η ∈ (0, η ∞ ) it holds thatEQUATION)where the bias θ(bi,bi)t converges to (I - Γ(η) H ) -1 ρH at a rate ∥ θ(bi,bi) t -(I - Γ(η) H ) -1 ρH ∥ ≤ (1 -ηa) tH ∥(I - Γ(η) H ) -1 ∥∥ρ H ∥ .Proof. Proof follows by combining the results Lemma A.1-Lemma A.5 above.In the lemma below we provide a simplified sample complexity bound of Corollary 4.3 corresponding to the synchronous setting, that is, with number of local training steps H = 1. There, the bias term disappears, and above results directly give a simplified sample complexity bound. Corollary A.7. Assume A 1 and A 3. Let H = 1, then for any 0 < ϵ < 1, in order to achieveE ∥θ T -θ ⋆ ∥ 2 ≤ ϵ 2 the required number of communications is T = O ṽheter ∨ σε N a 2 ϵ 2 log ∥θ 0 -θ ⋆ ∥ ϵnumber of communications, setting the step sizeEQUATION)Proof. Bounding the first two terms in decomposition (25) we get that the step size should satisfyη ≤ aN ϵ 2 ṽheter ∨ σε .From the last term we havet ≥ 1 aη log ∥θ 0 -θ ⋆ ∥ ϵ ≥ ṽheter ∨ σε N a 2 ϵ 2 log ∥θ 0 -θ ⋆ ∥ ϵCorollary A.8. Assume A1 and A3. For any0 ≤ ϵ ≤ C -1 A E c ∥θ c ⋆ -θ ⋆ ∥ a ∨ √ ṽheter ∨ σε E c ∥θ c ⋆ -θ ⋆ ∥ a 2/5in order to achieve E ∥θ Tθ ⋆ ∥ 2 < ϵ 2 the required number of communications isEQUATIONsetting the step size η = O aN ϵ 2 ṽheter ∨ σε and number of local iterationsH = O ṽheter ∨ σε N ϵE c ∥θ c ⋆ -θ ⋆ ∥Proof. We aim to bound separately all the terms in the r.h.s. of Theorem 4.1. Note that it requires to set η ∈ (0; η 0 ) with η 0 given in (26) in order to fulfill the boundsηṽ heter aN ≲ ε , ησ ε aN ≲ ε .Now, we should bound the bias termE 1/2 [∥ θ(bi,bi) t ∥ 2 ] ≤ (1 + (1 -ηa) tH )∥(I - Γ(η) H ) -1 ρH ∥ ≤ 2∥(I - Γ(η) H ) -1 ρH ∥ .Thus, using the Neuman series, we can bound the norm of the term above as∥(I - Γ(η) H ) -1 ρH ∥ = ∥ ∞ k=0 ( Γ(η) H ) k ρH ∥ ≤ ∞ k=0 (1 -ηa) Hk ∥ρ H ∥ ≤ ∥ρ H ∥ 1 -(1 -ηa) H .Hence, using the bound of Lemma A.3, we getE 1/2 [∥ θ(bi,bi) t ∥ 2 ] ≤ 2∥ρ H ∥ 1 -(1 -ηa) H ≤ ηaH 1 -(1 -ηa) H ηHE c [exp(ηH∥ Āc ∥)∥θ c ⋆ -θ ⋆ ∥] a ≤ 2ηHE c [exp(ηH∥ Āc ∥)∥θ c ⋆ -θ ⋆ ∥] a ≲ ηHE c [∥θ c ⋆ -θ ⋆ ∥] a ,where we used the fact that the step size η is chosen in order to satisfy ηH C A ≤ 1. Thus in order to fulfillE 1/2 [∥ θ(bi,bi) t ∥ 2] ≲ ε we need to choose η and H such thatηHE c [∥θ c ⋆ -θ ⋆ ∥] ≤ εa .It remains to bound the term√ Ec ∥Σ c A ∥∥ ρH ∥ aH 1/2 N 1/2. Using the bound of Lemma A.3, we getE c ∥Σ c A ∥∥ρ H ∥ aH 1/2 N 1/2 ≤ η N × E c ∥Σ c A ∥(ηH) 3/2 a ≲ ε 5/2 1 ṽheter ∨ σε a E c [∥θ c ⋆ -θ ⋆ ∥].Hence, it remains to combine the bounds above in order to get the sample complexity result (27) .Corollary A.9. Assume TD 1 and TD 3. Then for any0 ≤ ϵ ≤ 2 √ 2(1+γ) √ Ec ∥θ c ⋆ -θ⋆ ∥ 2 ∨(1+Ec [∥θ⋆ ∥ 2 ])Ec [∥θ c ⋆ -θ⋆ ∥] 2/5 (1-γ)ν ∨ 2Ec [∥θ c ⋆ -θ⋆ ∥] (1-γ)ν(1+γ) ,in order to achieve E ∥θ Tθ ⋆ ∥ 2 < ϵ 2 the required number of communications for federated TD(0) algorithm isT = O 1 (1-γ) 2 ν ∨ Ec [∥θ c ⋆ -θ⋆ ∥] (1-γ) 2 ν 2 ϵ log ∥θ0 -θ⋆ ∥ ϵ .Note that under A2 each of the matrices Āc , c ∈ [N ] is Hurwitz. This guarantees the existence and uniqueness of a positive definite matrix Q c which is a solution of the Lyapunov equation{ Āc } ⊤ Q c + Q c Āc = I .We further introduce the associated quantities, that will be used throughout the proof.a c = ∥Q c ∥ -1 /2 , η∞,c = (1/2)∥ Āc ∥ -2 Qc ∥Q c ∥ -1 ∧ ∥Q c ∥ , ã = min c∈[N ] a c , η∞ = min c∈[N ] η∞,c , κ Q,c = λ max (Q c )/λ min (Q c ) , b Q,c = 2 √ κ Q,c C A , κ Q = max c∈[N ] κ Q,c , b Q = max c∈[N ] b Q,c .In our statement of A2 we also required that each of the chains (Z c k ) k∈N starts from its invariant distribution π c . This requirement can be removed, and extension to the setting of arbitrary initial distribution can be done based on the maximal exact coupling argument [13, Lemma 19.3.6 and Theorem 19 3.9]. However, to better highlight the main ingredients of the proof, we prefer to keep stationary assumption.Proof of Corollary 4.5. Assume that the total number of local iterations, that is, T H, satisfiesEQUATIONwhere q ∈ N is a parameter that will be determined later. With Lemma B.4 we construct for each c ∈ [N ] a sequence of random variables { Z⋆,c 2jq } j=1,...,m , which are i.i.d. with the same distribution π c . Moreover, Lemma B.4 together with union bound implyP(∃j ∈ [m], c ∈ [N ] : Z⋆,c 2jq ̸ = Z c 2jq ) ≤ mN (1/4) ⌊q/τm ix ⌋ .The bound (29) implies that m ≤ T H/(2q). Thus, for any δ ∈ (0, 1), in order to guarantee thatEQUATIONit is enough to ensure thatEQUATIONInequality (30) holds for fixed δ ∈ (0, 1), if we chooseEQUATIONThus, setting the block size q as in (31), we get that for total number iterations T H satisfying (29) , with probability at least 1δ the results of Algorithm 3 are indistinguishable from the result of its counterpart Algorithm 1 applied with number of local steps H/q. We will denote the iterates of the latter algorithm applied with number of local steps h ∈ N as θ (ind),h T in order to make explicit the dependence of global parameter upon the number of local iterates. We further denote the event, where θ (ind),H/q T = θ T , by A δ . Thus, settingEQUATIONsimilarly to the way the number of local updates is set in Corollary 4.3, we obtain thatEQUATION= E[∥θ(ind),H/q T -θ ⋆ ∥ 2 1 Aδ ] + E[∥θ T -θ ⋆ ∥ 2 1 Aδ ] ≤ ϵ 2 + √ δE 1/2 [∥θ T -θ ⋆ ∥ 4 ] ,where in the last inequality we relied on the special choice of H/q from (32) together with Holder's inequality. Now it remains to bound E[∥θ Tθ ⋆ ∥ 4 ] and tune the parameter δ appropriately. Note that within this bound we can not rely on the estimates based on independent observations { Z⋆,c 2jq } j=1,...,m . At the same time, note that the skeleton Z c 2jq , j ≥ 0 for any c ∈ [N ] is a Markov chain with the Markov kernel P q c and mixing time τ mix = 1. This allows us to write a simple upper bound on E[∥θ Tθ ⋆ ∥ 4 ] based on the stability result for product of random matrices provided in [14] . Indeed, applying the result of Lemma B.1, we getE 1/2 [∥θ T -θ ⋆ ∥ 4 ] ≤ ∥θ 0 -θ ⋆ ∥ + 2T N N c=1 ∥θ c ⋆ -θ ⋆ ∥ + ηT H∥ε∥ ∞ 2 ,and the corresponding bound (33) can be rewritten asE[∥θ T -θ ⋆ ∥ 2 ] ≤ ϵ 2 + √ δ ∥θ 0 -θ ⋆ ∥ + 2T N N c=1 ∥θ 0 -θ ⋆ ∥ + ηT H∥ε∥ ∞ 2 .Thus, settingδ = ϵ 4 H 4 T 4 ∥θ 0 -θ ⋆ ∥ + 2 N N c=1 ∥θ c ⋆ -θ ⋆ ∥ + η∥ε∥ ∞ 2 ,we obtain that the corresponding bound for block size q scales asq = τ mix log (2N HT /δ) log 4 ≲ τ mix log H log N T 5 ∆ corr /ϵ 2 ,where we write ≲ for inequality up to an absolute constant and set∆ corr = ∥θ 0 -θ ⋆ ∥ + 2 N N c=1 ∥θ c ⋆ -θ ⋆ ∥ + η∥ε∥ ∞ 2 .Combination of the above bounds yields thatE[∥θ T -θ ⋆ ∥ 2 ] ≤ 2ϵ 2, and the proof is completed.Lemma B.1. Assume A2 and A3. Then, for the iterates θ t of Algorithm 3 run with parameters η, H, q satisfying the relationEQUATION)it holds for any probability distribution ξ on (Z, Z) and any t ∈ N, thatE 1/4 ξ [∥θ t -θ ⋆ ∥ 4 ] ≤ ∥θ 0 -θ ⋆ ∥ + 2t N N c=1 ∥θ c ⋆ -θ ⋆ ∥ + ηtH∥ε∥ ∞ .Proof. First we write a counterpart of the error decomposition ( 12) -( 13) for the LSA error of the subsampled iterates of Algorithm 3. Namely, we write thatEQUATIONwhere we have definedEQUATIONΓ(η,q) t,H = 1 N N c=1 Γ (c,η,q) t,1:H , κ t,H = 1 N N c=1 (I -Γ (c,η,q) t,1:H ){θ c ⋆ -θ ⋆ } , φt,H = -1 N N c=1 H h=1 Γ (c,η,q) t,h+1:H ε c (Z c t,qh) . For notation simplicity we have removed the dependence of κ t,H on the subsampling parameter q ∈ 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),E 1/4 ξ [∥Γ (c,η,q) t,1:H ∥ 4 ] ≤ √ κ Q,c e 2 d 1/2 e -ηãH/(12q) ≤ 1 ,provided that the ratio ηH/q satisfies the relation (34) . This bound yields thatE 1/4 ξ [∥ Γ(η,q) t,H ∥ 4 ] ≤ 1 , E 1/4 ξ [∥κ t,H ∥ 4 ] ≤ 2 N N c=1 ∥θ c ⋆ -θ ⋆ ∥ , E 1/4 ξ [∥ φt,H ∥ 4 ] ≤ H∥ε∥ ∞ .Hence, we obtain by running the recurrence (35) , thatE 1/4 ξ [∥θ t -θ ⋆ ∥ 4 ] ≤ ∥θ 0 -θ ⋆ ∥ + 2t N N c=1 ∥θ c ⋆ -θ ⋆ ∥ + ηtH∥ε∥ ∞ ,and the statement follows.Stability results on product of random matrices. The results of this paragraph provides the stability bound for the product of random matrices Γ (c,η,q) t,m:n defined in (36) . Define the quantitiesEQUATIONC Γ = 4(κ 1/2 Q C A +ã/6) 2 × ⌈8κ 1/2 Q C A /ã⌉ , c (M) A = ã/{12 C Γ } .Then the following result holds:Lemma B.2 (Proposition 7 from [14] , simplified). Assume A2 and A3. Then, for any c ∈ [N ], t ∈ N,step size η ∈ 0, η (M) ∞, any n ∈ N, q ≥ τ mix , and probability distribution ξ on (Z, Z), it holdsE 1/4 ξ ∥Γ (c,η,q) t,m:n ∥ 4 ≤ √ κ Q,c e 2 d 1/2 e -ãη(n-m)/12 .Proof. It is enough to note that, since q ≥ τ mix , and we consider q-skeleton of each Markov kernels P c , each of the subsampled kernels P q c will have a mixing time 1.Berbee's lemma construction. We outline some preliminaries associated with the Berbee's coupling lemma [3] construction. We recall first a definition of the β-mixing coefficient. Consider a probability space (Ω, F, P) equipped with σ-fields F and G such that F ⊆ F , G ⊆ F. Then the β-mixing coefficient of F and G is defined asβ(F, G) = (1/2) sup i∈I j∈J |P(A i ∩ B j ) -P(A i )P(B j )| ,and the supremum is taken over all pairs of partitions {A i } i∈I ∈ F I and {B j } j∈J ∈ G J of ZN with finite I and J.Now let (Z, d Z ) be a Polish space endowed with its Borel σ-field, denoted by Z, and let (Z N , Z ⊗N ) be the corresponding canonical space. Consider a Markov kernel P on Z × Z and denote by P ξ and E ξ the corresponding probability distribution and expectation with initial distribution ξ. Without loss of generality, we assume that (Z k ) k∈N is the associated canonical process. By construction, for any A ∈ Z, P ξ ( Z k ∈ A | Z k-1 ) = P(Z k-1 , A), P ξ -a.s. In the case ξ = δ z , z ∈ Z, P ξ and E ξ are denoted by P z and E z , respectively. We now make an assumption about the mixing properties of P: UGE 1. The Markov kernel P admits π as an invariant distribution and is uniformly geometrically ergodic, that is, there exists τ mix ∈ N such that for all k ∈ N,∆(P k ) = sup z,z ′ ∈Z (1/2)∥P k (z, •) -P k (z ′ , •)∥ TV ≤ (1/4) ⌊k/τm ix ⌋ .For q ∈ N, k ∈ N, and the Markov chain {Z n } n∈N satisfying the uniform geometric ergodicity constraint UGE 1, we define the σ-algebrasF k = σ(Z ℓ , ℓ ≤ k) and F + k+q = σ(Z ℓ , ℓ ≥ k + q).In such a scenario, using [13, Theorem 3.3], the respective β-mixing coefficient of F k and F + k+q is bounded byβ(q) ≡ β(F k , F + k+q ) ≤ ∆(P k ) = (1/4) ⌊q/τm ix ⌋ .We rely on the following useful version of Berbee's coupling lemma [3] , which is due to [10, Lemma 4.1]:Theorem B.3 (Lemma 4.1 in [10]). Let X and Y be two random variables taking their values in Borel spaces X and Y, respectively, and let U be a random variable with uniform distribution on [0; 1] that is independent of (X, Y ). There exists a random variableY ⋆ = f (X, Y, U ) where f is a measurable function from X × Y × [0, 1] to Y, such that:1. Y ⋆ is independent of X and has the same distribution as Y ;2. P(Y ⋆ ̸ = Y ) = β(σ(X), σ(Y )).Let us now consider the extended measurable space ZN = Z N × [0, 1], equipped with the σ-field ZN = Z ⊗N ⊗ B([0, 1]). For each probability measure ξ on (Z, Z), we consider the probability measure Pξ = P ξ ⊗ Unif ([0, 1]) and denote by Ẽξ the corresponding expected value. Finally, we denote by ( Zk ) k∈N the canonical process Zk : ((z i ) i∈N , u) ∈ ZN → z k and U : ((z i ) i∈N , u) ∈ ZN → u. Under Pξ , { Zk } k∈N is by construction a Markov chain with initial distribution ξ and Markov kernel P independent of U . Moreover, the distribution of U under Pξ is uniform over [0, 1]. Using the above construction, we obtain a useful blocking lemma, which is also stated in [10] . Lemma B.4. Assume UGE 1, let q ∈ N and ξ be a probability measure on (Z, Z). Then, there exists a random process ( Z⋆ k ) k∈N defined on ( ZN , ZN , Pξ ) such that for any k ∈ N, it holds:1. For any i, vector V ⋆ i = ( Z⋆ iq+1 , . . . , Z⋆ iq+q ) has the same distribution as V i = (Z iq+1 , . . . , Z iq+q ) under Pξ ; 2. The sequences (V ⋆ 2i ) i≥0 and (V ⋆ 2i+1 ) i≥0 are i.i.d. ;3. For any i, Pξ (V i ̸ = V ⋆ i ) ≤ β(q); Proof.E I - 1 H C (t,c) η,H 2 ≤ η 2 H 2 4 C 2 A +∥Σ c A ∥ .Proof. We rewrite I -C (t,c) η,H using Lemma D.1 asI - 1 H C (t,c) η,H = 1 H H h=1 I -Γ (c,η) t,h+1:H = η H H h=1 H ℓ=h+1 A c (Z c t,ℓ )Γ (c,η)t,ℓ+1:H , which can then be decomposed asI - 1 H C (t,c) η,H = η H H h=1 H ℓ=h+1 Āc Γ (c,η) t,ℓ+1:H + η H H h=1 H ℓ=h+1 A c (Z c t,ℓ ) -Āc Γ (c,η)t,ℓ+1:H .E 1/2 ∥ η H H h=1 H ℓ=h+1 Āc Γ (c,η) t,ℓ+1:H ∥ 2 ≤ ηH 2 ∥ Āc ∥.The second term has a reverse martingale structure, and we thus haveE I - 1 H C (t,c) η,H 2 ≤ η 2 H 2 4 C 2 A +∥Σ c A ∥ ,which is the result of the lemma.Lemma C.2. Assume A1 and A3. RecallC c t+1 = H h=1 Γ (c,η) t,h+1:H -(I -Āc ) H-h . Then we have E ∥ C c t+1 ∥ 2 ≤ η 2 H 4 C 2 A +∥Σ c A ∥ .Proof. We start by recalling the definition of C c t+1 , that isC c t+1 = C c t+1 - 1 N N c=1 E[C c t+1 ] = 1 N N c=1 H h=1 Γ (c,η) t,h+1:H -(I -Āc ) H-h .Using Lemma D.1, we haveC c t+1 = η N N c=1 H h=1 H ℓ=h Γ (c,η) t,h+1:ℓ A c (Z c t,ℓ ) -Āc (I -Āc ) H-ℓ-1 .By Minkowski's inequality and Assumption A3, we obtainE 1/2 ∥ C c t+1 ∥ 2 = η N N c=1 H h=1 H ℓ=h E 1/2 ∥A c (Z c t,ℓ ) -Āc ∥ 2 .Now, we notice thatE ∥A c (Z c t,ℓ ) -Āc ∥ 2 = E ∥A c (Z c t,ℓ ) -Āc ∥ 2 + ∥ Āc -Āc ∥ 2 ≤ C 2 A +∥Σ c A ∥, and the result of the lemma follows.Lemma C.3. Assume A1 and A3. RecallC (t,c) η,H = H h=1 Γ (c,η) t,h+1:H then E[∥ Γ c t+1 ∥] ≤ 2ηH C 2 A +∥Σ c A ∥ . Proof. Denote A c h = A c (Z c t+1,h ), Γ c t+1 = Γ t+1 -Γ c t+1 = 1 N N c ′ =1 H h=1 (I -ηA c ′ h ) - H h=1 (I -ηA c h ) .Using Lemma D.1, we can rewriteΓ c t+1 = η N N c ′ =1 H k=1 k-1 h=1 (I -ηA c ′ h ) {A c k -A c ′ k } H h=k+1 (I -ηA c h ) .Using triangle inequality and the fact that A c h 's are independent from each other, we haveE[∥ Γ c t+1 ∥] = η N N c ′ =1 H k=1 E k-1 h=1 (I -ηA c ′ h ) E A c k -A c ′ k E H h=k+1 (I -ηA c h ) .c A ∥, we have E[∥A c k -A c ′ k ∥] ≤ E[∥A c k -Āc ∥ + ∥ Āc -Āc ′ ∥ + ∥A c ′ k -Āc ′ ∥] ≤ 2 C A +2∥Σ c A ∥. Therefore, we obtain E[∥ Γ c t+1 ∥] ≤ 2η H k=1 (1 -ηa) H-1 C A +∥Σ c A ∥ ,and the result follows.The linear structure of SCAFFLSA's updates allow to decompose the updates between a transient term, and a fluctuation term. To materialize this, we define the following virtual parameters θ0 = θ 0 , θc 0,0 = θ0 , and ξc 0 = ξ c 0 , for all c ∈ {1, . . . , N } . These parameters are updated similarly to θ t 's and ξ c t 's, although without the last fluctuation term. For the virtual parameter θ, the update is similar to (8), as followsθc t,h -θ ⋆ = (I -ηA c (Z c t,h ))( θc t,h-1 -θ ⋆ ) + η(ξ c t -ξ c ⋆ ) , which gives, after H local updates, θc t,H -θ ⋆ = Γ c t+1 ( θc t -θ ⋆ ) + ηC c t+1 (ξ c t -ξ c ⋆ ) ,where we recallΓ c t+1 = H h=1 (I -ηA(Z c t,h )) and C c t+1 = H h=1 Γ (c,η)t,h+1:H . The virtual parameters obtained after H local updates are then aggregated asθt+1 = 1 N N c=1 θc t,H .This is then used to define the virtual control variates, similarly to (9) ,ξc t+1 = ξc t + 1 ηH ( θt+1 -θc t,H ) .These updates can be summarized over one block, which givesθt+1 -θ⋆ = Γ t+1 ( θt -θ ⋆ ) + η N N c=1 C c t+1 ( ξc t -ξ c ⋆ ) , ξc t+1 -ξ c ⋆ = 1 ηH (Γ t+1 -Γ c t+1 )( θt -θ ⋆ ) + I - 1 H C c t+1 ( ξc t -ξ c ⋆ ) + 1 HN N c=1 C c t+1 ( ξc t -ξ c ⋆ ) .The analysis of SCAFFLSA can then be decomposed into (i) analysis of the "transient" virtual iterates θt 's and ξc t 's, and (ii) analysis of the fluctuations θ t -θt and ξ c t -ξc t .Analysis of the Transient Term. First, we analyze the convergence of the virtual variables θt and ξc t for t ≥ 0 and c ∈ {1, . . . , N }. Consider the Lyapunov function,ψ t = ∥ θt -θ ⋆ ∥ 2 + η 2 H 2 N N c=1 ∥ ξc t -ξ c ⋆ ∥ 2 ,which is naturally defined as the error in θ ⋆ estimation using the virtual iterates, on communication rounds, and the average error on the virtual control variates. Then, the sequence (ψ t ) t∈N satisfies, for all t ≥ 0,E[ψ t ] ≤ 1 - ηaH 4 t E[ψ 0 ] ,whereψ 0 = ∥θ 0 -θ ⋆ ∥ 2 + η 2 H 2 N N c=1 ∥ Āc (θ c ⋆ -θ ⋆ )∥ 2 .Proof. Expression of the Lyapunov function. Since the sum virtual control variates isN t=1 ξc t = N t=1 ξ⋆ c = 0, we have θt+1 = 1 N N c=1 θc t,H = 1 N N c=1 θc t,H -ηH(ξ c t -ξ c ⋆ ). Applying Lemma D.3, we obtain ∥ θt+1 -θ ⋆ ∥ 2 = ∥ 1 N N c=1 θc t,H -θ ⋆ -ηH( ξc t -ξ c ⋆ )∥ 2 = 1 N N c=1 ∥ θc t,H -θ ⋆ -ηH( ξc t -ξ c ⋆ )∥ 2 - 1 N N c=1 ∥ θt+1 -θc t,H + ηH( ξc t -ξ c ⋆ )∥ 2 = 1 N N c=1 ∥ θc t,H -θ ⋆ -ηH( ξc t -ξ c ⋆ )∥ 2 - η 2 H 2 N N c=1 ∥ ξc t+1 -ξ c ⋆ ∥ 2 , since ξc t+1 = ξc t + 1 ηH ( θt+1 -θc t,H ). Adding η 2 H 2 N N c=1 ∥ ξc t+1 -ξ c ⋆ ∥ 2on both sides, we obtainEQUATIONwhere we definedC c η,H = H h=1 Γ (c,η)t,h+1:H . In the following, we will use the filtration of all events up to step t, F t := σ(Z c s,h , 0 ≤ s ≤ t, 0 ≤ h ≤ H, 1 ≤ c ≤ N ). Using Young's inequality, and Assumption A3, we can boundE[∥ θc t,H -θ ⋆ -ηH( ξc t -ξ c ⋆ )∥ 2 ] = ∥Γ (c,η) t,1:H ( θt -θ ⋆ ) -ηH(I -1 H C c η,H )( ξc t -ξ c ⋆ )∥ 2 ≤ E[(1 + α 0 )∥Γ (c,η) t,1:H ( θt -θ ⋆ )∥ 2 ] + (1 + α -1 0 )η 2 H 2 E[∥(I -1 H C c η,H )( ξc t -ξ c ⋆ )∥ 2 ] ≤ (1 + α 0 )(1 -ηa) 2H E[∥ θt -θ ⋆ ∥ 2 ] + (1 + α -1 0 )η 2 H 2 E[∥(I -1 H C c η,H )( ξc t -ξ c ⋆ )∥ 2 ] . Using Lemma C.1, we have E[∥(I -1 H C c η,H )( ξc t -ξ c ⋆ )∥ 2 ] ≤ η 2 H 2 4 C 2 A +∥Σ c A ∥ E[∥ ξc t -ξ c ⋆ ∥ 2 ] .We thus obtain, for H such that ηaH ≤ 1, and after setting α 0 = ηaH 2 and using the facts thatEQUATIONand the result follows by plugging (39) back in (38) .Analysis of the Fluctuations. To study the fluctuations, we define the following quantities, θ t = θ t -θt , and ξ c t = ξ c t -ξc t , for t ≥ 0 , and c ∈ {1, . . . , N } . 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 on these quantities. From the update of θ t , we have,θ t+1 -θ ⋆ = Γ t+1 (θ t -θ ⋆ ) + η N N c=1 C c t+1 (ξ c t -ξ c ⋆ ) -η εt+1 = θt+1 -θ ⋆ + Γ t+1 θ t + η N N c=1 C c t+1 ξ c t -η εt+1 ,which can be rewritten as a recursive update of the fluctuationsEQUATIONSimilarly, we have, for the fluctuations of the control variatesξ c t+1 = 1 ηH (Γ t+1 -Γ c t+1 ) θ t + I - 1 H C c t+1 ξ c t + 1 N H N c=1 C c t+1 ξ c t - 1 H (ε t+1 -ε c t+1 ) .Remark that, for all t ≥ 0, θ t and ξ c t 's are sums of (random) linear operations computed on zero-mean vectors, that are independent from these linear operations. Thus, for all t ≥ 0 and all c ∈ {1, . . . , N } we haveEQUATIONWe now aim at recursively finding a sequence of upper bounds {b(θ,θ) t , b (θ,ξ) , b = , b ̸ = } t≥0 such that, for all t ≥ 0, c, c ′ ∈ {1, . . . , N } such that c ̸ = c ′ , E ( θ t )( θ t ) ⊤ ≤ b (θ,θ) t , E ( θ t )( ξ c t ) ⊤ ≤ b (θ,ξ) t and E ( ξ c t )( θ t ) ⊤ ≤ b (θ,ξ) t , E ( ξ c t )( ξ c t ) ⊤ ≤ b ̸ = t , E ( ξ c t )( ξ c ′ t ) ⊤ ≤ b = t .(Initialization.) For t = 0, nothing is random so the fluctuations are zero, and b(θ,θ) 0 = b (θ,ξ) 0 = b = = b ̸ = = 0.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.Lemma C.5. Assume A1 and A3, then the first iterate of SCAFFLSA satisfy the following inequalitiesEQUATION.) From the definition of θ 1 , we haveθ 1 = η N N c=1 H h=1 Γ (c,η) 1,h+1:H ω c (Z c 1,h ).E[Γ (c,η) 1,h+1:H ω(Z c1,h )] = 0 for all c ∈ {1, . . . , N }, and for all h ∈ {0, . . . , H -1},E[( θ 1 )( θ 1 ) ⊤ ] = η 2 N 2 N c=1 H h=1 E Γ (c,η) 1,h+1:H ω c (Z c 1,h )ω c (Z c 1,h ) ⊤ (Γ (c,η) 1,h+1:H ) ⊤ = η 2 N 2 N c=1 H h=1 E Γ (c,η) 1,h+1:H Σ c ω (Γ (c,η) 1,h+1:H ) ⊤ ,where the second equality comes from the fact that, for all h ∈ {1, . . . , H -1}, the matrix Γ (c,η) 1,h+1:H and the vector ω c (Z c 1,h ) are independent. Triangle inequality, Jensen's inequality, and definition of the operator norm then giveE[( θ 1 )( θ 1 ) ⊤ ] ≤ η 2 N 2 N c=1 H h=1 E Γ (c,η) 1,h+1:H Σ c ω (Γ (c,η) 1,h+1:H ) ⊤ ≤ η 2 N 2 N c=1 H h=1 E Γ (c,η) 1,h+1:H Σ c ω (Γ (c,η) 1,h+1:H ) ⊤ ≤ η 2 N 2 N c=1 H h=1 E Γ (c,η) 1,h+1:H 2 ∥Σ c ω ∥ . Assumption A3 ensures that E Γ (c,η) 1,h+1:H 2 ≤1, and we haveE[( θ 1 )( θ 1 ) ⊤ ] ≤ η 2 H N 2 N c=1 ∥Σ c ω ∥ ≤ η 2 H N ∥Σ ω ∥ .(Value of b = 1 .) Let c ∈ {1, . . . , N }. The definition of ξ c 1 gives the following expression for the fluctuationξ c 1 = 1 N H N c=1 H h=1 Γ (c,η) 1,h+1:H ω c(Z c 1,h ) -1 H H h=1 Γ (c,η) 1,h+1:H ω c (Z c 1,h ). Therefore,we haveE[( ξ c 1 )( ξ c 1 ) ⊤ ] = E 1 N H N c=1 H h=1 Γ (c,η) 1,h+1:H ω c(Z c 1,h ) - 1 H H h=1 Γ (c,η) 1,h+1:H ω c (Z c 1,h ) × 1 N H N c=1 H h=1 (ω c(Z c 1,h )) ⊤ (Γ (c,η) 1,h+1:H ) ⊤ - 1 H H h=1 (ω c (Z c 1,h )) ⊤ (Γ (c,η) 1,h+1:H ) ⊤ .With similar arguments as above, we haveE[( ξ c 1 )( ξ c 1 ) ⊤ ] ≤ 1 N 2 H 2 N c=1 E Γ (c,η) 1,h+1:H Σ c ω (Γ (c,η) 1,h+1:H ) ⊤ + N -2 N H 2 E Γ (c,η) 1,h+1:H Σ c ω (Γ (c,η) 1,h+1:H ) ⊤ .Assuming N ≥ 2, triangle inequality givesEQUATION.) For the covariance of ξ c 1 and θ 1 , we haveE ( θ 1 )( ξ c 1 ) ⊤ = E η N N c=1 H h=1 Γ (c,η) 1,h+1:H ω c(Z c 1,h ) × 1 N H N c=1 H h=1 (ω c(Z c 1,h )) ⊤ (Γ (c,η) 1,h+1:H ) ⊤ - 1 H H h=1 (ω c (Z c 1,h )) ⊤ (Γ (c,η) 1,h+1:H ) ⊤ = E η N 2 H N c=1 H h=1 Γ (c,η) 1,h+1:H Σ c ω (Γ (c,η) 1,h+1:H ) ⊤ -E η N H H h=1 Γ (c,η) 1,h+1:H Σ c ω (Γ (c,η) 1,h+1:H ) ⊤ .As a result, we haveE ⟨ θ 1 , ξ c 1 ⟩ ≤ 2η N ∥Σ ω ∥ .(Value of b ̸ = .) Similarly to above, for c ̸ = c ′ , we haveE[( ξ c 1 )( ξ c ′ 1 ) ⊤ ] = E 1 N H N c=1 H h=1 Γ (c,η) 1,h+1:H ω c(Z c 1,h ) - 1 H H h=1 Γ (c,η) 1,h+1:H ω c (Z c 1,h ) × 1 N H N c=1 H h=1 (ω c(Z c 1,h )) ⊤ (Γ (c,η) 1,h+1:H ) ⊤ - 1 H H h=1 (ω c ′ (Z c ′ 1,h )) ⊤ (Γ (c ′ ,η) 1,h+1:H ) ⊤ = 1 N 2 H 2 N c=1 E Γ (c,η) 1,h+1:H Σ c ω (Γ (c,η) 1,h+1:H ) ⊤ - 1 N H 2 E Γ (c,η) 1,h+1:H Σ c ω (Γ (c,η) 1,h+1:H ) ⊤ - 1 N H 2 E Γ (c ′ ,η) 1,h+1:H Σ c ′ ω (Γ (c ′ ,η) 1,h+1:H ) ⊤ .Which results in the boundE[( ξ c 1 )( ξ c ′ 1 ) ⊤ ] ≤ 3 N H ∥Σ ω ∥ .Lemma C.6. Let ν > 0, and assume that ηHC A +∥Σ c A ∥ 1/2 ≤ ν and η 2 H 2 C 2 A +∥Σ c A ∥ ≤ ν. Then the following inequalities hold for any t ≥ 0, b (θ,θ) t+1 ≤ (1 -ηa) 2H b (θ,θ) t + νηHb (θ,ξ) t + 2ν ηH N b = t + νη 2 H 2 b ̸ = t + 3η 2 H N ∥Σ ω ∥ , ηHb (θ,ξ) t+1 ≤ 2νb (θ,θ) t + 3νηHb (θ,ξ) t + 2ν N η 2 H 2 b = t + 2νη 2 H 2 b ̸ = t + 2η 2 H N ∥Σ ω ∥ , η 2 H 2 b = t+1 ≤ 2νb (θ,θ) t + 3νηHb (θ,ξ) t + 4νη 2 H 2 b = t + 3νη 2 H 2 b ̸ = t + η 2 H∥Σ ω ∥ , η 2 H 2 b ̸ = t+1 ≤ 2νb (θ,θ) t + 3νηHb (θ,ξ) t + 3ν N η 2 H 2 b = t + 4νη 2 H 2 b ̸ = t + 3η 2 H N ∥Σ ω ∥ , Proof. (Value of b (θ,θ)t+1 .) Replacing θ t+1 by its expression from (40) , then expanding the expression, we have( θ t+1 )( θ t+1 ) ⊤ = Γ t+1 θ t + η N N c=1 C c t+1 ξ c t -η εt+1 Γ t+1 θ t + η N N c=1 C c t+1 ξ c t -η εt+1 ⊤ = Γ t+1 θ t θ ⊤ t Γ ⊤ t+1 + η N N c=1 Γ t+1 θ t ( ξ c t ) ⊤ ( C c t+1 ) ⊤ + η N N c=1 C c t+1 ξ c t ( θ t ) ⊤ Γ ⊤ t+1 + η 2 N 2 N c=1 N c′ =1 C c t+1 ξ c t ( ξ c′ t ) ⊤ ( C c′ t+1 ) ⊤ -η εt+1 θ ⊤ t Γ ⊤ t+1 - η N N c=1 εt+1 ( ξ c t ) ⊤ ( C c t+1 ) ⊤ -ηΓ t+1 θ t (ε t+1 ) ⊤ - η N N c=1 ( C c t+1 )( ξ c t )(ε t+1 ) ⊤ + η 2 (ε t+1 )(ε t+1 ) ⊤ .From the triangle inequality and Jensen's inequality, we have∥E[( θ t+1 )( θ t+1 ) ⊤ ]∥ ≤ E[∥Γ t+1 ∥ 2 ]∥E[ θ t θ ⊤ t ]∥ + 2η N N c=1 E 1/2 [∥ C c t+1 ∥ 2 ]∥E[ θ t ξ c t ⊤ ]∥ + η 2 N 2 N c=1 E[∥ C c t+1 ∥ 2 ]∥E[ ξ c t ξ c t ⊤ ]∥ + η 2 N 2 N c=1 N c′ =1 c′ ̸ =c E 1/2 [∥ C c t+1 ∥ 2 ]E 1/2 [∥ C c′ t+1 ∥ 2 ]∥E[ ξ c t ξ c′ t ⊤ ]∥ + ∥E[ηΓ (fl) t+1 θ t ε⊤ t+1 + η εt+1 θ ⊤ t Γ (fl) t+1 ⊤ ]∥ + 1 N N c=1 ∥E[η C c t+1 ξ c t ε⊤ t+1 + η εt+1 ξ c t ⊤ C c t+1 ⊤ ]∥ + η 2 ∥E[ε t+1 ε⊤ t+1 ]∥ . Now, we have from (41) that E[ θ t ] = E[ ξ c t ] = 0. Thus, we have, for all c ∈ {1, . . . , N }, ∥E[ηΓ (fl) t+1 θ t ε⊤ t+1 + η εt+1 θ ⊤ t Γ (fl) t+1 ⊤ ]∥ = ∥E[ηΓ (fl) t+1 E[ θ t ]ε ⊤ t+1 + η εt+1 E[ θ ⊤ t ]Γ (fl) t+1 ⊤ ]∥ = 0 , ∥E[η C c t+1 ξ c t ε⊤ t+1 + η εt+1 ξ c t ⊤ C c t+1 ⊤ ]∥ = ∥E[η C c t+1 E[ ξ c t ]ε ⊤ t+1 + η εt+1 E[ ξ c t ⊤ ] C c t+1 ⊤ ]∥ = 0 .Which results in the following inequality∥E[( θ t+1 )( θ t+1 ) ⊤ ]∥ ≤ E[∥Γ t+1 ∥ 2 ]∥E[ θ t θ ⊤ t ]∥ + 2η N N c=1 E 1/2 [∥ C c t+1 ∥ 2 ]∥E[ θ t ξ c t ⊤ ]∥ + η 2 N 2 N c=1 E[∥ C c t+1 ∥ 2 ]∥E[ ξ c t ξ c t ⊤ ]∥ + η 2 N 2 N c=1 N c′ =1 c′ ̸ =c E 1/2 [∥ C c t+1 ∥ 2 ]E 1/2 [∥ C c′ t+1 ∥ 2 ]∥E[ ξ c t ξ c′ t ⊤ ]∥ + 3η 2 ∥E[ε t+1 ε⊤ t+1 ]∥ .Using Lemma C.2, we obtain∥E[( θ t+1 )( θ t+1 ) ⊤ ]∥ ≤ (1 -ηa) 2H ∥E[ θ t θ ⊤ t ]∥ + η N N c=1 ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ θ t ξ c t ⊤ ]∥ + 2η 2 N 2 N c=1 η 2 H 4 C 2 A +∥Σ c A ∥ ∥E[ ξ c t ξ c t ⊤ ]∥ + η 2 N 2 N c=1 N c′ =1 c′ ̸ =c η 2 H 4 C 2 A +∥Σ c A ∥ ∥E[ ξ c t ξ c′ t ⊤ ]∥ + 3η 2 ∥E[ε t+1 ε⊤ t+1 ]∥ . Assuming ηH C A +∥Σ c A ∥ 1/2 ≤ ν and η 2 H 2 C 2 A +∥Σ c A ∥ ≤ ν, we obtain ∥E[( θ t+1 )( θ t+1 ) ⊤ ]∥ ≤ (1 -ηa) 2H ∥E[ θ t θ ⊤ t ]∥ +ν ηH N N c=1 ∥E[ θ t ξ c t ⊤ ]∥ +2ν η 2 H 2 N 2 N c=1 ∥E[ ξ c t ξ c t ⊤ ]∥ + ν η 2 H 2 N 2 N c=1 N c′ =1 c′ ̸ =c ∥E[ ξ c t ξ c′ t ⊤ ]∥ + 3η 2 H N ∥Σ ω ∥ .This gives our first inequality that links our upper bounds, b (θ,θ) t+1 ≤ (1 -ηa) 2H b (θ,θ) t + νηHb (θ,ξ) t + 2ν ηH N b = t + νη 2 H 2 b ̸ = t + 3η 2 H N ∥Σ ω ∥ .θ t+1 ξ c t+1 ⊤ = Γ t+1 θ t + η N N c=1 C c t+1 ξ c t -η εt+1 × 1 ηH Γ c t+1 θ t + I - 1 H C c t+1 ξ c t + 1 N H N c=1 C c t+1 ξ c t - 1 H ε c t+1 ⊤ = 1 ηH Γ t+1 θ t θ ⊤ t Γ c t+1 ⊤ + 1 N H N c=1 C c t+1 ξ c t θ ⊤ t Γ c t+1 ⊤ - 1 H εt+1 θ ⊤ t Γ c t+1 ⊤ + Γ t+1 θ t ξ c t ⊤ I - 1 H C c t+1 ⊤ + η N N c=1 C c t+1 ξ c t ξ c t ⊤ I - 1 H C c t+1 ⊤ -η εt+1 ξ c t ⊤ I - 1 H C c t+1 ⊤ + 1 N H N c=1 Γ t+1 θ t ξ c t ⊤ C c t+1 ⊤ + η N 2 H N c=1 N c=1 C c t+1 ξ c t ξ c t ⊤ C c t+1 ⊤ - η N H εt+1 N c=1 ξ c t ⊤ C c t+1 ⊤ - 1 H Γ t+1 θ t ε c t+1 ⊤ - η N H N c=1 C c t+1 ξ c t ε c t+1 ⊤ + η H εt+1 ε c t+1 ⊤ .Now we proceed as above by taking the expectation, then the norm, and using the triangle inequality. Note that by (41) , we haveE[ε t+1 θ ⊤ t Γ c t+1 ⊤ ] = 0, E[ε t+1 ξ c t ⊤ I -1 H C c t+1 ⊤ ] = 0, E[ε t+1 N c=1 ξ c t ⊤ C c t+1 ⊤ ] = 0, E[Γ t+1 θ t ε c t+1 ⊤ ] = 0, and E[ C c t+1 ξ c t ε c t+1 ⊤ ] = 0. After usingJensen's inequality, we obtain∥E[ θ t+1 ξ c t+1 ⊤ ]∥ ≤ 1 ηH E 1/2 [∥ Γ c t+1 ∥ 2 ]∥E[ θ t θ ⊤ t ]∥ + 1 N H N c=1 E 1/2 [∥ C c t+1 ∥ 2 ]∥E[ ξ c t θ ⊤ t ]∥ + E 1/2 I - 1 H C c t+1 2 ∥E[ θ t ξ c t ⊤ ]∥ + η N N c=1 E C c t+1 I - 1 H C c t+1 ∥E[ ξ c t ξ c t ⊤ ]∥ + 1 N H N c=1 E 1/2 ∥ C c t+1 ∥ 2 ∥E[ θ t ξ c t ⊤ ]∥ + η N 2 H N c=1 N c=1 E ∥ C c t+1 ∥∥ C c t+1 ⊤ ∥ ∥E[ ξ c t ξ c t ⊤ ]∥ + E η H εt+1 ε c t+1 ⊤ .Using Lemma C.1, Lemma C.2, and Lemma C.3, we obtain∥E[ θ t+1 ξ c t+1 ⊤ ]∥ ≤ 2 C A +∥Σ c A ∥ 1/2 ∥E[ θ t θ ⊤ t ]∥ + 1 N H N c=1 ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ ξ c t θ ⊤ t ]∥ + ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ θ t ξ c t ⊤ ]∥ + η N N c=1 ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ ξ c t ξ c t ⊤ ]∥ + 1 N H N c=1 ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ θ t ξ c t ⊤ ]∥ + η N 2 H N c=1 N c′ =1 η 2 H 4 C 2 A +∥Σ c A ∥ ∥E[ ξ c t ξ c′ t ⊤ ]∥ + E η H εt+1 ε c t+1 ⊤ ,where we used the two following inequalitiesE C c t+1 I - 1 H C c t+1 ≤ E 1/2 C c t+1 2 ≤ ηH 2 C A +∥Σ c A ∥ 1/2 , E ∥ C c t+1 ∥∥ C c t+1 ⊤ ∥ ≤ E 1 2 ∥ C c t+1 ∥ 2 + 1 2 ∥ C c t+1 ⊤ ∥ 2 ≤ η 2 H 4 C 2 A +∥Σ c A ∥This leads to the following inequalityηHb (θ,ξ) t+1 ≤ 2ηH C A +∥Σ c A ∥ 1/2 b (θ,θ) t + 3η 2 H 2 C A +∥Σ c A ∥ 1/2 b (θ,ξ) t + η 2 H 2 ηH C A +∥Σ c A ∥ 1/2 + η 2 H 2 C 2 A +∥Σ c A ∥ 1 N b = t + 1 - 1 N b ̸ = t + 2η 2 H N ∥Σ ω ∥ ,where we usedE η H εt+1 ε c t+1 ⊤ ≤ b (θ,ξ) 1 = 2η N ∥Σ ω ∥. Assuming ηH C A +∥Σ c A ∥ 1/2 ≤ ν and η 2 H 2 C 2 A +∥Σ c A ∥ ≤ ν, we obtain the following bound ηHb (θ,ξ) t+1 ≤ 2νb (θ,θ) t + 3νηHb (θ,ξ) t + 2νη 2 H 2 1 N b = t + 1 - 1 N b ̸ = t + 2η 2 H N ∥Σ ω ∥ .(Value of b = t+1 and b ̸ = t+1 .) As above, we start by expanding the matrix product,ξ c t+1 ξ c ′ t+1 ⊤ = 1 ηH Γ c t+1 θ t + I - 1 H C c t+1 ξ c t + 1 N H N c=1 C c t+1 ξ c t - 1 H ε c t+1 1 ηH Γ c ′ t+1 θ t + I - 1 H C c ′ t+1 ξ c ′ t + 1 N H N c′ =1 C c′ t+1 ξ c′ t - 1 H ε c ′ t+1 ⊤ = 1 η 2 H 2 Γ c t+1 θ t θ ⊤ t Γ c ′ t+1 ⊤ + 1 ηH I - 1 H C c t+1 ξ c t θ ⊤ t Γ c ′ t+1 ⊤ + 1 ηN H 2 N c=1 C c t+1 ξ c t θ ⊤ t Γ c ′ t+1 ⊤ - 1 ηH 2 ε c t+1 θ ⊤ t Γ c ′ t+1 ⊤ + 1 ηH Γ c t+1 θ t ξ c ′ t ⊤ I - 1 H C c ′ t+1 ⊤ + I - 1 H C c t+1 ξ c t ξ c ′ t ⊤ I - 1 H C c ′ t+1 ⊤ + 1 N H N c=1 C c t+1 ξ c t ξ c ′ t ⊤ I - 1 H C c ′ t+1 ⊤ - 1 H ε c t+1 ξ c ′ t ⊤ I - 1 H C c ′ t+1 ⊤ + 1 ηN H 2 Γ c t+1 θ t ξ c′ t ⊤ N c′ =1 C c′ t+1 ⊤ + 1 N H I - 1 H C c t+1 ξ c t ξ c′ t ⊤ N c′ =1 C c′ t+1 ⊤ + 1 N 2 H 2 N c=1 C c t+1 ξ c t ξ c′ t ⊤ N c′ =1 C c′ t+1 ⊤ - 1 N H 2 ε c t+1 ξ c′ t ⊤ N c′ =1 C c′ t+1 ⊤ + 1 ηH 2 Γ c t+1 θ t ε c ′ t+1 ⊤ + 1 H I - 1 H C c t+1 ξ c t ε c ′ t+1 ⊤ + 1 N H 2 N c=1 C c t+1 ξ c t ε c ′ t+1 ⊤ - 1 H 2 ε c t+1 ε c ′ t+1 ⊤ .Taking the expectation, then the norm, and using triangle inequality and Jensen's inequality, we obtain∥E[ ξ c t+1 ξ c ′ t+1 ⊤ ]∥ ≤ 1 η 2 H 2 E[∥ Γ c t+1 ∥ 2 ]∥E[ θ t θ ⊤ t ]∥ + 1 ηH E 1/2 I - 1 H C c t+1 2 ∥E[ ξ c t θ ⊤ t ]∥ + 1 ηN H 2 N c=1 E 1/2 ∥ C c t+1 ∥ 2 ∥E[ ξ c t θ ⊤ t ]∥ + 1 ηH E 1/2 I - 1 H C c ′ t+1 2 ∥E[ θ t ξ c ′ t ⊤ ]∥ + E I - 1 H C c t+1 I - 1 H C c ′ t+1 ∥E[ ξ c t ξ c ′ t ⊤ ]∥ + 1 N H N c=1 E ∥ C c t+1 ∥ I - 1 H C c ′ t+1 ∥E[ ξ c t ξ c ′ t ⊤ ]∥ + 1 ηN H 2 N c′ =1 E 1/2 ∥ C c′ t+1 ⊤ ∥ 2 ∥E[ θ t ξ c′ t ⊤ ]∥ + 1 N H N c′ =1 E I - 1 H C c t+1 ∥ C c′ t+1 ⊤ ∥ ∥E[ ξ c t ξ c′ t ⊤ ]∥ + 1 N 2 H 2 N c=1 N c′ =1 E ∥ C c t+1 ∥∥ C c′ t+1 ⊤ ∥ ∥E[ ξ c t ξ c′ t ⊤ ]∥ + ∥E[ 1 H 2 ε c t+1 ε c ′ t+1 ⊤ ]∥ .We can now use Lemma C.1, Lemma C.2, and Lemma C.3 to obtain the following upper bound∥E[ ξ c t+1 ξ c ′ t+1 ⊤ ]∥ ≤ 2 C 2 A +∥Σ c A ∥ ∥E[ θ t θ ⊤ t ]∥ + 1 ηH ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ ξ c t θ ⊤ t ]∥ + 1 ηN H 2 N c=1 ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ ξ c t θ ⊤ t ]∥ + 1 ηH ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ θ t ξ c ′ t ⊤ ]∥ + η 2 H 2 4 C 2 A +∥Σ c A ∥ ∥E[ ξ c t ξ c ′ t ⊤ ]∥ + 1 N H N c=1 ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ ξ c t ξ c ′ t ⊤ ]∥ + 1 ηN H 2 N c′ =1 ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ θ t ξ c′ t ⊤ ]∥ + 1 N H N c′ =1 ηH 2 C A +∥Σ c A ∥ 1/2 ∥E[ ξ c t ξ c′ t ⊤ ]∥ + 1 N 2 H 2 N c=1 N c′ =1 η 2 H 4 C 2 A +∥Σ c A ∥ ∥E[ ξ c t ξ c′ t ⊤ ]∥ + 1 H 2 E[ ε c t+1 ε c ′ t+1 ⊤ ] .This bound can be simplified asη 2 H 2 ∥E[ ξ c t+1 ξ c ′ t+1 ⊤ ]∥ ≤ 2η 2 H 2 C 2 A +∥Σ c A ∥ b (θ,θ) t + η 2 H 2 2 C A +∥Σ c A ∥ 1/2 b (θ,ξ) t + η 2 H 2 C A +∥Σ c A ∥ 1/2 b (θ,ξ) t + η 2 H 2 2 C A +∥Σ c A ∥ 1/2 b (θ,ξ) t + η 4 H 4 4 C 2 A +∥Σ c A ∥ ∥E[ ξ c t ξ c ′ t ⊤ ]∥ + η 3 H 3 C A +∥Σ c A ∥ 1/2 1 N b = t + 1 - 1 N b ̸ = t + η 2 H 2 C A +∥Σ c A ∥ 1/2 b (θ,ξ) t + η 3 H 3 C A +∥Σ c A ∥ 1/2 1 N b = t + 1 - 1 N b ̸ = t + η 4 H 4 C 2 A +∥Σ c A ∥ 1 N b = t + 1 - 1 N b ̸ = t + 1 H 2 E[ ε c t+1 ε c ′ t+1 ⊤ ] ,which can be simplified asη 2 H 2 ∥E[ ξ c t+1 ξ c ′ t+1 ⊤ ]∥ ≤ 2η 2 H 2 C 2 A +∥Σ c A ∥ b (θ,θ) t + 3ηH C A +∥Σ c A ∥ 1/2 ηHb (θ,ξ) t + 2ηH C A +∥Σ c A ∥ 1/2 + η 2 H 2 C 2 A +∥Σ c A ∥ η 2 H 2 1 N b = t + 1 - 1 N b ̸ = t + η 4 H 4 4 C 2 A +∥Σ c A ∥ ∥E[ ξ c t ξ c ′ t ⊤ ]∥ + 1 H 2 E[ ε c t+1 ε c ′ t+1 ⊤ ] .We now distinguish two cases, when c = c ′ and when c ̸ = c ′ . First, let c = c ′ , we obtainη 2 H 2 b = t+1 ≤ 2η 2 H 2 C 2 A +∥Σ c A ∥ b (θ,θ) t + 3ηH C A +∥Σ c A ∥ 1/2 ηHb (θ,ξ) t + 2ηH C A +∥Σ c A ∥ 1/2 + η 2 H 2 C 2 A +∥Σ c A ∥ η 2 H 2 1 N b = t + 1 - 1 N b ̸ = t + η 2 H 2 4 C 2 A +∥Σ c A ∥ η 2 H 2 b = t + η 2 H∥Σ ω ∥ , since when c = c ′ , we have à∥E[ ξ c t ξ c ′ t ⊤ ]∥ ≤ b = t and 1 H 2 E[ ε c t+1 ε c ′ t+1 ⊤ ] ≤ b = 1 = N -1 N H ∥Σ ω ∥. Assuming ηH C A +∥Σ c A ∥ 1/2 ≤ ν and η 2 H 2 C 2 A +∥Σ c A ∥ ≤ ν, we obtain η 2 H 2 b = t+1 ≤ 2νb (θ,θ) t + 3νηHb (θ,ξ) t + 4νη 2 H 2 b = t + 3νη 2 H 2 b ̸ = t + η 2 H∥Σ ω ∥ . We proceed similarly for c ̸ = c ′ , which gives η 2 H 2 b ̸ = t+1 ≤ 2νb (θ,θ) t + 3νηHb (θ,ξ) t + 3ν N η 2 H 2 b = t + 4νη 2 H 2 b ̸ = t + 3η 2 H N ∥Σ ω ∥ , since, when c ̸ = c ′ , we have ∥E[ ξ c t ξ c ′ t ⊤ ]∥ ≤ b ̸ = t and 1 H 2 E[ ε c t+1 ε c ′ t+1 ⊤ ] ≤ b ̸ = 1 = 3 N H ∥Σ ω ∥. Corollary C.7. Assume that ηH C A +∥Σ c A ∥ 1/2 ≤ a 240(CA +∥Σ c A ∥ 1/2 ) and η 2 H 2 C 2 A +∥Σ c A ∥ ≤ a 240(CA +∥Σ c A ∥ 1/2 ) , set ω = min 1, a 12(CA +∥Σ c A ∥ 1/2 ) , then it holds that b (θ,θ) t+1 + ωηHb (θ,ξ) t+1 + ωη 2 H 2 N b = t+1 + ωη 2 H 2 b ̸ = t+1 ≤ 1 - ηaH 2 b (θ,θ) t + 1 2 ωηHb (θ,ξ) t + 1 2 ωη 2 H 2 N b = t + 1 2 η 2 H 2 b ̸ = t + 9η 2 H N ∥Σ ω ∥ . Assuming ηaH ≤ 1 2 , we have 1 -1 2 ≤ 1 -ηaH 2 . This in turn ensures that b (θ,θ) t+1 + ωηHb (θ,ξ) t+1 + ωη 2 H 2 N b = t+1 + ωη 2 H 2 b ̸ = t+1 ≤ 1 - ηaH 2 b (θ,θ) t + ωηHb (θ,ξ) t + ωη 2 H 2 N b = t + η 2 H 2 b ̸ = t + 9η 2 H N ∥Σ ω ∥ , which gives, for any t ≥ 0, b (θ,θ) t ≤ 18η N a ∥Σ ω ∥ .Proof. From Lemma C.6, we have, for any 0 < ω < 1, ν > 0, and assuming that ηHEQUATION+ ωη 2 H 2 N b = t+1 + ωη 2 H 2 b ̸ = t+1 ≤ (1 -ηa) 2H + 6ωηH C A +∥Σ c A ∥ 1/2 b (θ,θ) t + 10νηHb (θ,ξ) t + 10ν η 2 H 2 N b = t + 10νη 2 H 2 b ̸ = t + 9η 2 H N ∥Σ ω ∥ . Now, we choose ω = min 1, a 12(CA +∥Σ c A ∥ 1/2 ) and obtain (1 -ηa) 2H + 6ωηH C A +∥Σ c A ∥ 1/2 ≤ 1 -ηaH + 6ωηH C A +∥Σ c A ∥ 1/2 ≤ 1 - ηaH 2 .Additionally, ω ≤ 1, thus 3 + 6ω ≤ 9 and we obtain b(θ,θ) t+1 + ωηHb (θ,ξ) t+1 + ωη 2 H 2 N b = t+1 + ωη 2 H 2 b ̸ = t+1 ≤ 1 - ηaH 2 b (θ,θ) t + 10νηHb (θ,ξ) t + 10ν η 2 H 2 N b = t + 10νη 2 H 2 b ̸ = t + 9η 2 H N ∥Σ ω ∥ . Choosing ν ≤ ω 20 ≤ a 240(CA +∥Σ c A ∥ 1/2 ) gives the result.Complete analysis of 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 θ ⋆ . Theorem C.8. Assume A1 and A3. Let η, H such that ηaH ≤ 1, and H ≤ a 240η{C Then, the sequence (ψ t ) t∈N satisfies, for all t ≥ 0,E[∥θ t -θ ⋆ ∥ 2 ] ≤ 1 - ηaH 2 t 2∥θ 0 -θ ⋆ ∥ 2 + 2η 2 H 2 E c [∥ Āc (θ c ⋆ -θ ⋆ )∥ 2 ] + 36dη N a ∥Σ ω ∥ .Proof. Recall our decomposition θ tθ ⋆ = θtθ ⋆ + θ. By Young's inequality, we haveE[∥θ t -θ ⋆ ∥ 2 ] ≤ 2E[∥ θt -θ ⋆ ∥ 2 ] + 2E[∥ θ t ∥ 2 ] . By Theorem C.4, we have E[∥ θt -θ ⋆ ∥ 2 ] ≤ 1 -ηaH 2 tψ 0 , and by Corollary C.7, we haveE[∥ θ t ∥ 2 ] ≤ db (θ,θ) t ≤ 18ηd N a ∥Σ ω ∥.Combine the two results, we obtainE[∥θ t -θ ⋆ ∥ 2 ] ≤ 1 - ηaH 2 t 2ψ 0 + 36dη N a ∥Σ ω ∥ , replacing ψ 0 = ∥θ 0 -θ ⋆ ∥ 2 + η 2 H 2 N N c=1 ∥ Āc (θ c ⋆ -θ ⋆ )∥ 2gives the result of the theorem. Corollary C.9. Under the Assumptions of Theorem C.8, one may set the parameter of SCAFFLSA toη = min η ∞ , N aϵ 2 72d∥Σ ε ∥ , H = 1 240 C 2 A +∥Σ A ∥ max a η ∞ , 72d∥Σ ω ∥ N ϵ 2 , which guarantees E[∥θ t -θ ⋆ ∥ 2 ] ≤ ϵ 2 after a number of communication rounds T ≥ 240 C 2 A +∥Σ A ∥ a 2 log 4∥θ 0 -θ ⋆ ∥ 2 + 4η 2 H 2 N N c=1 ∥ Āc (θ c ⋆ -θ ⋆ )∥ 2 ϵ 2 .The overall sample complexity of the algorithm is thenT H = max 240 η ∞ a , 72d∥Σ ε ∥ N a 2 ϵ 2 log 4∥θ 0 -θ ⋆ ∥ 2 + 4η 2 H 2 N N c=1 ∥ Āc (θ c ⋆ -θ ⋆ )∥ 2 ϵ 2 . Proof. Let ϵ > 0. Starting from Theorem C.8's upper bound, we have E[∥θ t -θ ⋆ ∥ 2 ] ≤ ϵ 2 whenever 1 - ηaH 2 t 2ψ 0 + 36dη N a ∥Σ ω ∥ ≤ ϵ 2 ,whereψ 0 = ∥θ 0 -θ ⋆ ∥ 2 + η 2 H 2 N N c=1 ∥ Āc (θ c ⋆ -θ ⋆ )∥ 2 . This gives a first condition 36dη N a ∥Σ ω ∥ ≤ ϵ 2 , which requires η ≤ N aϵ 2 72d∥Σ ε ∥ .This allows to take any value ofH such that H ≤ a 240η{C 2 A +∥Σ c ε ∥} = 72 240N ϵ 2 {C 2 A +∥Σ c ε ∥} .With such setting, it remains to set the number of communication T toT ≥ 1 ηaH log 2ψ 0 ϵ 2 = 240 C 2 A +∥Σ c ε ∥ a 2 log 4ψ 0 ϵ 2 , which ensures that 1 -ηaH 2 t 2ψ 0 ≤ ϵ 2 2 .Lemma D.1. For any matrix-valued sequences (U n ) n∈N , (V n ) n∈N and for any M ∈ N, it holds that:M k=1 U k - M k=1 V k = M k=1 { k-1 j=1 U j }(U k -V k ){ M j=k+1 V j } .Lemma D.2 (Stability of the deterministic product). Assume A3. Then, for any u ∈ R d and h ∈ N,∥(I -η Āc ) h u∥ ≤ (1 -ηa) h ∥u∥ . Proof. Since (Z c t,h ) 1≤h≤H are i.i.d, we get E Γ (c,η) t,1:h u = E h l=1 (I -ηA(Z c t,l ))u = h l=1 E I -ηA(Z c t,l ) u = (I -η Āc ) h u .The proof then follows from the elementary inequality: for any square-integrable random vector U ,∥E[U ]∥ ≤ (E[∥U ∥ 2 ]) 1/2 . Lemma D.3. Let (x i ) N i=1 , and (y i ) N i=1 be N vectors of R d . Denote xN = (1/N ) N i=1 x i and ȳN = (1/N ) N i=1 y i . Then, N ∥x N -ȳN ∥ 2 = N i=1 ∥x i -y i ∥ 2 - N i=1 ∥x i -xN -(y i -ȳN )∥ 2 Proof. Define x = [x ⊤ 1 , . . . , x ⊤ N ] ⊤ and y = [y ⊤ 1 , . . . , y ⊤ N ] ⊤ ∈ R N d . Define by P the orthogonal projector on E = x ∈ R N d : x = [x ⊤ , . . . , x ⊤ ] ⊤ , x ∈ R d .We show that P x = [x ⊤ N , . . . , x⊤ N ] ⊤ . Note indeed that for any z = [z ⊤ , . . . , z ⊤ ] ⊤ ∈ E, we get (with a slight abuse of notations, ⟨• , •⟩ denotes the scalar product in R N d and R d )⟨x -P x , z⟩ = N i=1 {⟨x i , z⟩ -⟨x N , z⟩} = 0 .The proof follows from Pythagoras identity which shows that∥ P x -P y ∥ 2 = ∥ x -y ∥ 2 -∥(x -P x) -(y -P y ∥ 2 ). Lemma D.4. Assume A4. Let Z be a random variable taking values in a state space (Z, Z) with distribution π c . Set η ≥ 0, then for any vector u ∈ R d , we haveE[∥(I -ηA c (Z))u∥ 2 ] ≤ (1 -ηa)∥u∥ 2 -η( 1 L -η)E[∥A c (Z)u∥ 2 ] .Proof. First, remark that∥(I -ηA c (Z))u∥ 2 = u ⊤ (I -ηA c (Z)) ⊤ (I -ηA c (Z))u = u ⊤ I -2η( 1 2 (A c (Z) + A c (Z) ⊤ )) + η 2 A c (Z) ⊤ A c (Z) u . Since we have E[ 1 2 (A c (Z) + A c (Z) ⊤ )] ≽ aI and E[ 1 2 (A c (Z) + A c (Z) ⊤ )] ≽ 1 L E[A c (Z) ⊤ A c (Z)], we obtain E[∥(I -ηA c (Z))u∥ 2 ] = u ⊤ u -2ηu ⊤ E[ 1 2 (A c (Z) + A c (Z) ⊤ )]u + η 2 u ⊤ E[A c (Z) ⊤ A c (Z)]u ≤ ∥u∥ 2 -ηa∥u∥ 2 -η L u ⊤ E[A c (Z) ⊤ A c (Z)]u + η 2 u ⊤ E[A c (Z) ⊤ A c (Z)]u = (1 -ηa)∥u∥ 2 -η( 1 L -η)u ⊤ E[A c (Z) ⊤ A c (Z)]u , which gives the result.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 θ ⋆ ∈ R d , which can be done via the LSA procedure. For the agent c ∈ [N ] the k-th step randomness is given by the tuple Z c k = (S c k , A c k , S c k+1 ). With slight abuse of notation, we write A c t,h instead of A(Z c t,h ), and b c t,h instead of b(Z c t,h ). Then the corresponding LSA update equation with constant step size η can be written asθ c t,h = θ c t,h-1 -η(A c t,h θ c t,h-1 -b c t,h ) ,where A c t,h and b c t,h are given byEQUATIONRespective specialisation of FedLSA and SCAFFLSA algorithms to TD learning are stated in Algorithm 4 and Algorithm 5.Table 2 : Communication and sample complexity for finding a solution with MSE lower than ϵ 2 for FedLSA, Scaffnew, and SCAFFLSAon the federated TD learning problem. Our analysis is the first to show that FedLSA exhibits linear speed-up, as well as its variant that reduces bias using control variates.Local updates H Sample complexity T HFedTD [12] O N 2 (1-γ) 2 ν 2 ϵ 2 log 1 ϵ 1 O N 2 (1-γ) 2 ν 2 ϵ 2 log 1 ϵ FedTD (Cor. 4.4) O 1 (1-γ) 2 ν 2 ϵ log 1 ϵ O 1 N ϵ O 1 N (1-γ) 2 ν 2 ϵ 2 log 1 ϵ SCAFFTD (Cor. 5.3) O 1 (1-γ) 2 ν 2 log 1 ϵ O 1 N ϵ 2 O 1 N (1-γ) 2 ν 2 ϵ 2 log 1 ϵThe proof below closely follows [42] (Lemma 7) and [45] (Lemma 1). Everywhere in this subsection we use a generic notation A c 1 as an alias for the random matrix A c 1,1 . Now, using TD 3 and ( 5), we get ∥A c 1 ∥ ≤ (1 + γ) almost surely, which implies ∥ Āc ∥ ≤ 1 + γ for any c ∈ [N ], giving (44) . This implies, using the definition of Σ c A , that∥Σ c A ∥ = ∥E[{A c 1 } ⊤ A c 1 ] -{ Āc } ⊤ Āc ∥ ≤ 2(1 + γ) 2, and the bound (45) follows. Next we observe thatTr(Σ c ε ) = E[∥(A c 1 -Āc )θ c ⋆ -(b c 1 -bc )∥ 2 ] ≤ 2{θ c ⋆ } ⊤ E[{A c 1 } ⊤ A c 1 ]θ c ⋆ + 2E[(r s (S s 0 , A c 0 )) 2 Tr(φ(S c 0 )φ ⊤ (S c 0 ))] ≤ 2(1 + γ) 2 {θ c ⋆ } ⊤ Σ φ [c]θ c ⋆ + 2 ≤ 2(1 + γ) 2 ∥θ c ⋆ ∥ 2 + 1, where the latter inequality follows from TD 3, and thus (46) holds. In order to check the last equation (47) , we note first that the bound for a and η ∞ readily follows from the ones presented in [42] [ Lemma 5 ] and [42] [ Lemma 7] . To check assumption A4, note first that, with s ∼ µ c , s ′ ∼ P π (•|s), we haveA c + {A c } ⊤ = φ(s){φ(s) -γφ(s ′ )} ⊤ + {φ(s) -γφ(s ′ )}φ(s) ⊤ = 2φ(s)φ(s) ⊤ -γ{φ(s)φ(s ′ ) ⊤ + φ(s ′ )φ(s) ⊤ } ⪯ (2 + γ)φ(s)φ(s) ⊤ + γφ(s ′ )φ(s ′ ) ⊤ ,where we additionally used that-(uu ⊤ + vv ⊤ ) ⪯ uv ⊤ + vu ⊤ ⪯ (uu ⊤ + vv ⊤ )for any u, v ∈ R d . Thus, we get thatE[A c + {A c } ⊤ ] ⪯ 2(1 + γ)Σ cφ . The rest of the proof follows from the fact thatE[{A c 1 } ⊤ A c 1 ] ⪰ { Āc } ⊤ Āc ⪰ (1 -γ) 2 λ min Σ cφ , which holds whenever (48) is satisfied; see e.g. in [30] (Lemma 5) or [45] (Lemma 7).Based on these results, we instantiate the results summarized in Table 1 to Federated TD learning in Table 2 .To mitigate the bias caused by local training, we may use 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, . . . , T /p, we computeθc k = θ c k-1 -η(A c (Z c k )θ c k-1 -b c (Z c k ) -ξ c k-1 ) ,where ω c (z) = A c (z)θ ⋆b c (z). This comes from the fact that, for all z,b c (z) + ξ c k-1 = bc + b c (z) + ξ c k-1 = Āc θ c ⋆ + b c (z) + ξ c k-1 = Āc θ ⋆ + b c (z) + ξ c k-1 -ξ c ⋆ = A c (z)θ ⋆ -A c (z)θ ⋆ + b c (z) + ξ c k-1 -ξ c ⋆ = A c (z)θ ⋆ -ω c (z) + ξ c k-1 -ξ c ⋆ .Expression of communication steps. Using thatN c=1 ξ c k-1 = 0 and N c=1 ξ c ⋆ = 0, we get 1 N N c=1 ∥θ c k -θ ⋆ ∥ 2 = 1 {1} (B k )∥ θk -θ ⋆ ∥ 2 + 1 {0} (B k ) 1 N N c=1 ∥ θc k -θ ⋆ ∥ 2 = 1 {1} (B k )∥ 1 N N c=1 ( θc k - η p ξ c k-1 ) - 1 N N c=1 (θ ⋆ - η p ξ c ⋆ )∥ 2 + 1 {0} (B k ) 1 N N c=1 ∥ θc k -θ ⋆ ∥ 2 .The first term can be upper bounded by using Lemma D.3, which gives1 {1} (B k )∥ θk -θ ⋆ ∥ 2 = 1 {1} (B k ) 1 N N c=1 ∥ θc k - η p (ξ c k-1 -ξ c ⋆ ) -θ ⋆ ∥ 2 - 1 N N c=1 ∥ θk -( θc k - η p ξ c k-1 ) + η p ξ c ⋆ ∥ 2 = 1 {1} (B k ) 1 N N c=1 ∥ θc k - η p (ξ c k-1 -ξ c ⋆ ) -θ ⋆ ∥ 2 - η 2 p 2 1 N N c=1 ∥ξ c k -ξ c ⋆ ∥ 2 .We now expand the first term in the right-hand side of the previous equation. This gives1 N N c=1 ∥ θc k - η p (ξ c k-1 -ξ c ⋆ ) -θ ⋆ ∥ 2 = 1 N N c=1 ∥ θc k -θ ⋆ ∥ 2 - 2η p ⟨ξ c k-1 -ξ c ⋆ , θc k -θ ⋆ ⟩ + η 2 p 2 ∥ξ c k-1 -ξ c ⋆ ∥ 2 ,which yieldsEQUATION)On the other hand, note thatEQUATION)By combining (51) and (50), we getEQUATION)Progress in local updates. We now bound the first term of the sum in (52). For c ∈ [N ], (49) givesEQUATION) Define the σ-algebra G k-1 = σ(B s , s ≤ k -1, Z c s , s ≤ k -1, c ∈ [N ]). We now bound the conditional expectation of T 1E Gk -1 [T 1 ] = E Gk -1 ∥(I -ηA c (Z c k )){θ c k -θ ⋆ }∥ 2 -2η⟨(I -ηA c (Z c k )){θ c k -θ ⋆ } , ω c (Z c k )⟩ + η 2 ∥ω c (Z c k )∥ 2 = E Gk -1 ∥(I -ηA c (Z c k )){θ c k -θ ⋆ }∥ 2 + 2η 2 ⟨A c (Z c k ){θ c k -θ ⋆ } , ω c (Z c k )⟩ + η 2 ∥ω c (Z c k )∥ 2, where we used the fact that ⟨I , ω c (Z c k )⟩ = 0. Using Young's inequality for products, and Lemma D.4 with η ≤ 1 2L and u = θ c kθ ⋆ , we then obtainEQUATION)Plugging ( 54) in (53) and using the assumption η ≤ 1 2L , we obtainEQUATIONBounding the Lyapunov function. Taking the condtional expectation of (52) and using (55) for c = 1 to N , we obtain the following bound on the Lyapunov functionE Gk -1 [ψ k ] = 1 N N c=1 E Gk -1 ∥ θc k -θ ⋆ ∥ 2 -2η⟨ξ c k-1 -ξ c ⋆ , θc k -θ ⋆ ⟩ + η 2 p 2 1 N N c=1 ∥ξ c k-1 -ξ c ⋆ ∥ 2 ≤ 1 N N c=1 (1 -ηa)∥θ c k -θ ⋆ ∥ 2 -η 2 ∥ξ c k-1 -ξ c ⋆ ∥ 2 + 2η 2 Tr(Σ c ε ) + η 2 p 2 1 N N c=1 ∥ξ c k-1 -ξ c ⋆ ∥ 2 = (1 -ηa) 1 N N c=1 ∥θ c k -θ ⋆ ∥ 2 + (1 -p 2 ) η 2 p 2 1 N N c=1 ∥ξ c k-1 -ξ c ⋆ ∥ 2 + 2η 2 N N c=1 Tr(Σ c ε ) ,and the result of the Lemma follows from the Tower property.Theorem F.2 (Convergence rate). Assume A1 and A3(2). Then, for any η ≤ 1 2L and T > 0, it holdsE[ψ K ] ≤ 1 -ζ K ∥θ 0 -θ ⋆ ∥ 2 + η 2 p 2 ∆ heter + 2η 2 ζ 1 N N c=1 Tr(Σ c ε ) ,where ζ = min ηa, p 2 .Corollary F.3 (Iteration complexity). Let ϵ > 0. Set η = min 1 2L , ϵ 2 a 8σε and p = √ ηa (so that ζ = ηa). Then, E[ψ K ] ≤ ϵ 2 as long as the number of iterations isK ≥ max 2L a , 4σ ε ϵ 2 a 2 log ∥θ 0 -θ ⋆ ∥ 2 + min 1 2aL , ϵ 2 8σε ∆ heter 2ϵ 2 ,which corresponds to an expected number of communication roundsT ≥ max 2L a , 4σ ε ϵ 2 a 2 log ∥θ 0 -θ ⋆ ∥ 2 + min 1 2aL , ϵ 2 8σε ∆ heter 2ϵ 2 .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 to constants that are independent from the problem. Precisely, for every (p, η) there exists a FLSA problem such thatE[ψ K ] = 1 -ζ K ∥θ 0 -θ ⋆ ∥ 2 + η 2 p 2 ∆ heter + 2η 2 ζ σε ,where we have defined ζ = min 2ηa, p 2 .Proof. Define for all c ∈ [N ],Āc = aI , bc = b c u ,where u is a vector whom all coordinates are equal to 1. We also consider the sequence of i.i.d random variables (Z c k ) such that that for all c ∈ [N ]and 0 ≤ t ≤ T , Z c k follows a Rademacher distribution. Moreover, we defineA c (Z c k ) = Āc , b c (Z c k ) = bc + Z c k u .In particular this impliesω c (z) = Z c k u .We follow the same proof of Lemma F.1 until the chain of equalities breaks. Thereby, we start fromE[ψ k ] = E[ N c=1 ∥θ c k -θ ⋆ ∥ 2 + η 2 p 2 N c=1 ∥ξ c k -ξ c ⋆ ∥ 2 ] = E[ N c=1 ∥(I -ηA c (Z c k )){θ c k-1 -θ ⋆ } -ηω c (Z c k ))∥ 2 + (1 -p 2 ) η 2 p 2 N c=1 ∥ξ c k-1 -ξ c ⋆ ∥ 2 ] = E[ N c=1 ∥(I -η Āc ){θ c k-1 -θ ⋆ } -ηω c (Z c k ))∥ 2 + (1 -p 2 ) η 2 p 2 N c=1 ∥ξ c k-1 -ξ c ⋆ ∥ 2 ] = E[ N c=1 (1 -ηa) 2 ∥θ c k-1 -θ ⋆ ∥ 2 + η 2 ∥ω c (Z c k )∥ 2 + (1 -p 2 ) η 2 p 2 N c=1 ∥ξ c k-1 -ξ c ⋆ ∥ 2 ]where we used that A c (Z c k ) = Āc . Unrolling the recursion gives the desired result.Here, we give additional details regarding the numerical experiments. The environments used are instances of Garnet, where we use 30 states, embedded via a random projection in a d = 8dimensional space. We use two actions, and consider a 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 homogeneous setting, we sample one Garnet environment. Each client then receives a 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 ϵ ∼ U(0, 0.02).In the heterogeneous setting, we proceed similarly, except that we sample two different Garnet 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 ϵ ∼ U(0, 0.02).All the experiments presented in this paper can be run on a single laptop in just a few hours. 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 3 and Figure 4 , we give report the counterpart of Figure 1 with a wider ranger of number of local updates H ∈ {1, 10, 100, 1000, 10000}. The results obtained here match with observations from Section 6: in homogeneous settings, FedLSAand SCAFFLSAexhibit very similar behavior. In both methods, increasing the number of local steps speeds-up the training, until the stochastic 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- 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, we report in Figure 5 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. In this setting, all algorithms manage to find better estimators, since the amount of variance depends on the step size (as seen in Theorem 4.1 and Theorem 5.1). Additionally, FedLSA's bias is smaller than in Figure 7 , which is also in line with the upper bound E 1/2 [∥ θ(bi,bi) For each algorithm, we report the average MSE and variance over 5 runs. In Figure 7 and Figure 8 , we give the counterpart of Figure 1 , where we additionally plot the MSE of the estimator θ t + θ(bi,bi) ∞ , for different settings of all parameters. We recall that θ(bi,bi) ∞ = (I -Γ(η) H ) -1 ρH is the bias of FedLSA, as we proved in Theorem 4.1. Therefore, θ t + θ(bi,bi)∞ is a proper estimator of θ ⋆ , although, of course, it cannot be computed in practice since the bias θ(bi,bi) ∞ 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 an error similar to the one of SCAFFLSA, meaning that FedLSA, once its bias is removed, converges similarly to SCAFFLSA. The latter, however, does not require to remove an unknown bias, and directly estimates the right quantity.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, confidence intervals, or statistical significance tests, at 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. Justification: This paper is of purely theoretical nature, and the proposed methods do not deal with sensitive attributes that could induce unfairness or privacy issues. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: What are the functions $\boldsymbol{A}^c()$ and $\boldsymbol{b}^c()$ like in practice? Could you please provide some examples?
limitations: limitations: There was no discussion on the limitations of the proposed algorithm.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Also, there is a missing "c" superscript right above equation (1) in Algorithm 1.

The paper should be revised for clarity and typos.
questions: 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)? 

-Do the authors believe that their analysis could be extended to federated learning algorithms with vanishing step-size?

- It is possible that I missed this in the main text, but are any drawbacks to using SCAFFLSA instead of Federated LSA?
limitations: 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.
paper_summary: paper_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
Linear Stochastic Approximation and TD Learning.
strength_weakness: strength_weakness: The achieved speedup holds only for quadratic setup and the application of the quadratic loss function is quite limited. 
The experiments are a little simple.
questions: 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? 

Can the theoretical analysis be extended to a general case?

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.
limitations: limitations: The achieved speedup holds only for quadratic setup and the application of the quadratic loss function is quite limited.

Comments: comment: Thanks for your reply. Personally, I am positive about this work. However, we must recognize that there are some limitations in this paper, such as only applying to quadratic problems, the algorithm is directly the same as Scaffnew. Based on these, I will maintain my score!
I would like to thank the authors for their responses and for incorporating my suggestions in order to improve the readability of the paper. I have no further questions.