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

The achieved speedup holds only for quadratic setup and the application of the quadratic loss function is quite limited. We emphasize that our analysis holds for the general setting of linear stochastic approximation, which encompasses minimization of quadratic functions, but also works for other settings where the system matrix is not symmetric. This is crucial, as the matrices involved in TD learning are not symmetric. We stress that our analysis is the first of its kind for federated LSA.

The experiments are a little simple. The Garnet problems used in our experiments are common for federated TD, and the only problem that we are aware of in the federated TD literature. We stress that our paper is a theoretical paper, and the purpose of our experiment is thus only to illustrate our theory numerically. Nonetheless, we are happy to add more experiments on other problems if the reviewer has some specific problems to suggest.

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? This is indeed the case, thank you for pointing it out. We will make sure to add a sentence about this in the discussion after Corollaries 5.2 and 5.3.

Can the theoretical analysis be extended to a general case? Extending our analysis to other settings, e.g. for strongly-convex and smooth problems is much more technical, and is a very interesting direction for future research.

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. Thank you for pointing this issue, we will update the plots in the camera ready version, making sure that the y-axis is the same each time. We will also provide addditional plots for $H \in \\{1, 10, 100, 1000, 10000\\}$ and $N \in \\{10, 100\\}$ in the appendix; we add these additional plots to the pdf attached to the global rebuttal. If you have any additional suggestions to improve the experiments in the camera ready, we will be happy to integrate them.

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)? Thank you for the suggestion, which will greatly help to improve the readability of our paper. We will add the following table, instantiating our results for TD learning, in the camera ready version. In this table, we highlight the dependence on the discount factor $\gamma$ and on the smallest eigenvalue of the $\Sigma_\varphi^c$ (see Assumption TD3). Regarding Markovian sampling, complexity is the same as i.i.d. setting up to a multiplicative factor $\max_c \tau_{mix}(c)$ (as defined in Assumption A2) in the number of local samples $H$. We will add a sentence in both tables' captions mentioning this.

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. We will make the separation between results on general federated LSA and federated TD more clear, by stating first the general results in i.i.d. and markovian settings (in two different paragraph), then moving to federated TD. We will also use the additional page in the camera ready to give more details regarding equations and mathematical symbols. If you have any additional suggestion regarding presentation, we are happy to hear it to try to make the paper as clear as possible.

Do the authors believe that their analysis could be extended to federated learning algorithms with vanishing step-size? The analysis could indeed easily be extended to federated linear stochastic approximation with vanishing step sizes, using the same technique. We refrained from doing so due to space limitation.

Regarding extension to more general "federated learning", we want to emphasize that our analysis already works for the special case of quadratic problems $\min_\theta \| X \theta - y \|^2$, that can be cast as $X^\top X \theta = X^\top y$, and fit our assumptions as long as $X^\top X$ is invertible. Still, we stress that our analysis is more general since we do not assume $\bar{A}^c$ to be symmetric. Extending our analysis to other settings, e.g. for strongly-convex and smooth problems is much more technical, and is a very interesting direction for future research.

It is possible that I missed this in the main text, but are any drawbacks to using SCAFFLSA instead of Federated LSA? This is the main claim of our paper: in terms of sample and communication complexity, SCAFFLSA is guaranteed to perform as good as FedLSA in all settings, and can significantly reduce communication cost in heterogeneous settings. We show this theoretically, and illustrate it numerically; we refer the reviewer to the pdf attached to the general rebuttal for additional numerical evidence of this.

The only drawback of SCAFFLSA lies in the fact that each agent is required to store an additional vector (the local control variate), which increases the cost in terms of memory for each agent. This drawback is shared with all control variates methods (such as Scaffold, Scaffnew...), and is generally not a problem provided agents have access to sufficiently large memory.

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. The Garnet problems used in our experiments are common in the TD literature and serve the purpose of illustrating numerically our theoretical findings. Nonetheless, we are happy to add more experiments on other problems if the reviewer has some specific problems to suggest.

What are the functions $A^c()$ and $b^c()$ like in practice? Could you please provide some examples? In TD learning, the system is given by $\bar{A}^c = \mathbb{E} [\phi(s)\{\phi(s)-\gamma \phi(s')\}^{\top}]$ and $\bar{b}^c = \mathbb{E}[\phi(s) r^c(s,a)]$, where $s \sim \mu^c, s' \sim P^{\pi,c}(\cdot|s)$. Thus, taking the sampling set $\mathsf{Z} = \mathcal{S} \times \mathcal{A} \times \mathcal{S}$, we can define $A^c(s, a, s') = \phi(s)\{\phi(s)-\gamma \phi(s')\}^{\top}$ and $b^c(s, a, s') = \phi(s) r^c(s,a)$. The points $s, a, s'$ are then either i.i.d. samples (following Assumption TD1) or a Markov chain (following Assumption TD2).