SCAFFLSA: Quantifying and Eliminating Heterogeneity Bias in Federated
  Linear Stochastic Approximation and Temporal Difference Learning
Paul Mangold Sergey Samsonov Safwan Labbi Ilya Levin Reda Alami Alexey Naumov Eric Moulines
In this paper, we perform a non-asymptotic analysis of the federated linear
stochastic approximation (FedLSA) algorithm. We explicitly quantify the bias
introduced by local training with heterogeneous agents, and investigate the
sample complexity of the algorithm. We show that the communication complexity
of FedLSA scales polynomially with the desired precision $\epsilon$, which
limits the benefits of federation. To overcome this, we propose SCAFFLSA, a
novel variant of FedLSA, that uses control variates to correct the bias of
local training, and prove its convergence without assumptions on statistical
heterogeneity. We apply the proposed methodology to federated temporal
difference learning with linear function approximation, and analyze the
corresponding complexity improvements.