Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailability

We are truly grateful for your appreciation for our paper flow and extensive numerical experiments. We believe that many of your concerns can be easily addressed, and we apologize for our lack of clarity on these points. We hope that our response can address your concerns, and the insights discussed here will be incorporated into the camera-ready version if the paper gets accepted.

W1: on gradient amplification. We note that solving the issue of client unavailability by amplifying local gradients is widely adopted in the prior literature [19,27,53,52,40]. As pointed out by [13], when the exact availability distribution is known, the most intuitive way to amplify these gradients is to collect only the fastest responses and re-weight according to the response probabilities. Thus, like our method, these weights can be very large when the participation rate is very low. Although somewhat counterintuitive, as suggested by the numerical results in our manuscript and in [13,53], these types of algorithms perform just fine.

W1: on intuitive algorithm (novelty). We emphasize that our contribution is highly non-trivial. For example, the counterexample below shows that simply modifying weights accordingly to the participation interval but not postponing broadcast will not debias FedAvg under even stationary availability. The proof is skipped due to space. It highlights the need for both of the two algorithmic components in Section 5.

[Counterexample]. Suppose that we have two clients such that client #1 is always available, while client #2 is available only in odd rounds. Each client holds $F\_i(x)=1/2\|\|x-u\_i\|\|^2$ and computes 1 local step. The server boadcasts as in FedAvg [30] and aggregates local updates as $x^{t+1}\gets 1/\|{\mathcal{A}^t}\|\sum\_{i\in{\mathcal{A}^t}}x\_i^{t\dagger}$, where $x\_i^{t\dagger} \gets x^{t}-(t-\tau\_i(t))G\_i^t$. Choose $x^0=0$ and $\eta=1/T$. It holds that $\lim\_{T\rightarrow\infty}x^T=\frac{3u\_1+2u\_2}{5}.$

W2: on speedup in the last term. We achieve the desired speedup property for a sufficiently large training round $T$, consistent with the prior literature [52,53,60]. For ease of presentation, let $C\_1:=L(F(\bar{\mathbf{x}}^0)-F^\star)+\sigma^2$, $C\_2:=((\sigma^2+\zeta^2)/\delta)[(1+L^2)+\rho/(1-\sqrt{\rho})^2]$. In the special case where $k$ clients participate u.a.r., we have $\delta\_{\max}=\delta=k/m$. The convergence rate in (16) reduces to $\frac{1}{T}\sum\_{t=0}^{T-1}\mathbb{E}[\|\|\nabla F(\bar{\mathbf{x}}^t)\|\|^2] \lesssim\frac{C\_1}{\sqrt{s\delta mT}}+\frac{smC\_2}{T}.$ If we ignore the constants hidden behind the asymptotic bound, the first term dominates when $C\_1/\sqrt{s\delta mT}\ge C\_2(sm/T)$, i.e., when $T\ge C\_2^2/C\_1^2(s^3m^3\delta)$. Consequently, the convergence bound reduces further to $\frac{1}{T}\sum\_{t=0}^{T-1}\mathbb{E}[\|\|\nabla F(\bar{\mathbf{x}}^t)\|\|^2]\lesssim\frac{C\_1}{\sqrt{s\delta mT}}=\frac{C\_1}{\sqrt{s(k/m)mT}}=\frac{C\_1}{\sqrt{skT}}.$ Now, we can see that the R.H.S. of the bound indicates a clear speedup w.r.t. the number of local steps $s$ and the number of sampled clients $k$. We will make this clear in the camera-ready version if accepted.

W3: on the appearance of $(1+L^2)$ in Corollary 1. We note that the appearance of $L^2$ in Corollary 1 is not a glitch in our proof but a testament that we account for the key parameters in the assumptions. Although we agree with the reviewer that the term $(1 + \eta^2 L^2)$ would be at the constant level with the learning rate $1/L$, it is not uncommon to find the Lipschitz constant $L$ in the final bound in the prior literature; see, e.g., Theorems 1-3 in [27], Corollary 4 in [53], Theorem 3 in [R1].

Technically speaking, the appearance of $L^2$ results from Assumption 4. This assumption is more general than the popular ones in the prior literature on gradient divergence; see details in Table 2 on page 16. Then, together with Assumption 2, Proposition 3 on page 26 holds as follows: $\frac{1}{m}\sum\_{i=1}^m\|\|\nabla F_i(\mathbf{z}\_i^t)\|\|^2\le\frac{3 L^2}{m} \sum\_{i=1}^m \|\|\mathbf{z}\_i^t-\bar{\mathbf{z}}^t\|\|^2+3(\beta^2+1)\|\|\nabla F(\bar{\mathbf{z}}^t)\|\|^2+3\zeta^2.$ Notice that the coefficient of the first term on the R.H.S. is $L^2$ instead of a coupling of $\eta^2 L^2$. Consequently, we shall see a standalone $L^2$, for example, when we apply the above Proposition 3 to the first term in the second row in Lemma 3.

W4: on the performance of (FedAvg all). In numerical experiments, the phenomenon that (FedAvg all) lags behind (FedAvg active) has been observed under stationary availability in [53] and more significantly in [13, Fig. 2] (FedAvg with device sampling). Non-stationary dynamics brings in more uncertainty, so it is expected that things can become even worse. We recall that (FedAvg all) differs from (FedAvg active) by the gradient aggregation rules. Specifically, $\text{FedAvg all}:\\ G^t\_{all}:=\frac{1}{m} \sum\_{i=1}^m\mathbf{1}\_{\\{i\in{\mathcal{A}}^t\\}}G\_i^t;\\ \text{FedAvg active}:\\ G^t\_{active}:=\frac{1}{\|{\mathcal{A}}^t\|}\sum\_{i=1}^m\mathbf{1}\_{\\{i\in{\mathcal{A}}^t\\}}G\_i^t.$

Question: provide an in-depth analysis on the algorithm's complexity. We have briefly discussed the memory and computational complexity in lines 160-165 on page 4, but we are happy to address them in more detail here. A detailed complexity comparison for the baseline algorithms, including ours, can be found in Table 1 in the pdf. Since our algorithm does not draw new stochastic samples for training, there is no increase in sample complexity. It takes $O(1)$ extra memory unit to store the last active round $\tau\_i(t)$. The weight echoing step incurs $O(1)$ additional computation to adjust the weight of gradient accumulation.

References:

[R1] Fatkhullin, I. et al. (2023). Momentum provably improves error feedback!. Advances in Neural Information Processing Systems, 36.

Thank you for your appreciation for the motivation, principled algorithm and good results of the paper. We hope that our response can address your concerns.

W1: on pointers to the supplementary material. We apologize for not being clear enough in the main text. If the paper gets accepted, we will have one additional page to accommodate those pointers in the main text, including but not limited to line 131, line 224 and line 241 per your suggestions.

W2: on implications of the technical lemmas. In the manuscript, each technical lemma is accompanied by brief illustrations either before or after it, but they may not be clear enough. We are happy to elaborate the implications here in detail.

• Proposition 1 indicates that, when a client becomes available, the weight echoing procedure equalizes the number of local improvements with that of the other available peers. It captures the algorithmic intuition to allow the unavailable clients to catch up to missed computations.
• Proposition 2 builds the connection between the sequence $\mathbf{x}\_i^t$ and the auxiliary sequence $\mathbf{z}\_i^t$. At a high level, it says that we shall see a bounded approximation error as long as the gradient norm and consensus error of the auxiliary sequence $\mathbf{z}\_i^t$ are bounded. Therefore, the problem boils down to bounding those two terms.
• Lemma 1 is well known in the fully decentralized learning literature to characterize information mixing [33,32,49]. The spectral norm $\rho$ is expected to be strictly smaller than 1 to ensure exponential decay, which we have shown in Lemma 4.
• Lemma 2 is an intermediate result to characterize the statistical properties of the unavailable duration. It indicates that despite the lack of structure in the non-stationary dynamics, the expected echoing weight remains finite.
• Lemma 3 quantifies the progress of the global objective per global round. Similarly to Proposition 2, it points out the need for the other technical lemmas, for example, Lemma 2 for the second term, Proposition 2 for the approximation error.

Again, we will make sure to improve the presentation if the paper gets accepted.

Q1: why $p_i$ is defined from the image class distribution. We note that correlating the local data distribution and the probability of client availability is a common practice in the prior literature. For example, MIFA [13] experiments with a formula for $p\_i$ so that clients that hold images of smaller digits participate less frequently. Similarly to our construction, FedAU [53] considers $p\_i$ as an inner product of the clients' local data distribution $\nu\_i$ and an external distribution $\Phi^\prime$.

Moreover, we recall that the issue of client unavailability fundamentally arises from heterogeneous local data distributions (a.k.a. non-i.i.d. local data). As we have demonstrated in Fig. 2, Section 4, the expected output of FedAvg can be far away from the global optimum under non-i.i.d. local data. Intuitively, when clients hold homogeneous local data, the bias will be much milder even under heterogeneous availability. This is because every client becomes interchangeable when their local data distributions are homogeneous.

Q2: why not, for example, sample $p\sim\mathsf{Dirichlet}(\gamma)$. The issue of directly applying the Dirichlet distribution to construct $p\_i$'s is that the generated $p\_i$'s are likely to be more concentrated in the presence of a larger client population. Suppose that we have $\mathbf{p}:=[p\_1,\ldots,p\_m]\sim\mathsf{Dirichlet}(\gamma)$, it holds that $\mathbb{E}[p\_i]=\frac{1}{m},\\ \mathsf{Var}(p\_i)=\frac{m-1}{m^2(m\gamma+1)}<\frac{m}{m^2(m\gamma)}=\frac{1}{m^2 \gamma},\\ \forall i\in[m].$ In the cross-device federated learning, $m$ could be quite large, leading to small $\mathbb{E}[p\_i]$ and $\mathsf{Var}(p\_i)$. In other words, the generated $p\_i$'s are more likely to center around the mean with a larger client population. For example, Fig. 1 and Fig. 2 in the pdf are histograms of $\mathbf{p}$ realizations with $m=100$ clients, where $\gamma=0.1$ in the former and $\gamma=1$ in the latter. It can be seen that all the $p\_i$'s concentrate around their mean $0.01$, and the range of the generated $p\_i$'s is around $0.16$ in the former while around $0.06$ in the latter. In contrast, our construction of $p\_i$'s results in less concentration. We copy Fig. 5 from our manuscript on page 42 and attach it as Fig. 3 in the pdf, which is a histogram of the generated $p\_i$'s under our construction. Clearly, our $p\_i$'s are more spread out with a significantly heavier tail over the entire $[0,1]$ interval.

Limitations: the limitations are not sufficiently discussed in Section 8. Thank you for bringing this to our attention. Per NeurIPS guideline, we have Section A in the Appendix to elaborate the potential limitations of our work. We briefly reiterate them here for completeness.

• Availability probabilities in the manuscript are theoretically assumed to be independent and strictly positive. It is interesting to theoretically characterize the setting, where we have correlated probabilities under arbitrary probabilistic trajectories.
• Client unavailability can vary greatly in the presence of heterogeneous and non-stationary dynamics. It is also worth exploring variance-reduction techniques for a more robust update.

Thanks to the authors for the elucidating response. I have also read and considered all the other reviews and relative authors' rebuttals. Since the provided information allowed me to better understand the work, I can more confidently confirm that the work provides interesting insights, and so I raised my confidence score accordingly. The authors promised to enhance the presentation, and based on the clear rebuttal I believe this will enhance the paper quality.

Thank you for your appreciation for the novelty and generality of our problem setup. Please find our responses to your questions below.

W1/Q1: reference Theorems 1-2 in the FedAU paper [53] for a theoretical analysis of Section 4. Yes, we are happy to reference Theorem 1 and Theorem 2 in the FedAU paper in the camera-ready version if the paper gets accepted. Thank you for pointing out our oversight. Those two theorems share a similar spirit with us and will complement our numerical results in Section 4, where we use numerical experiments to illustrate the significant bias incurred under stationary dynamics. However, it is worth noting that our paper focuses on a much harder problem, where the non-stationary dynamics is unstructured. Thus, we generalize their results to the problem of non-stationary dynamics.

Q1: insights beyond Theorem 1 in the FedAU paper [53]. Theorem 1 in the FedAU paper theoretically characterizes the biased global objective under heterogeneous but stationary client unavailability. However, as we focus on the general case where clients are allowed to have unstructured non-stationary dynamics subject to Assumption 1, we believe it is in general hard to obtain a nice analytical form as that in the FedAU paper. This is because the complex interplay between $p\_i^t$'s across rounds and clients will inevitably complicate and thus hinder the theoretical analysis. Fortunately, the numerical experiments help us to confirm that non-stationary dynamics will further degrade the performance of FedAvg algorithm.

Q2: conduct related experiments to compare with FedVARP. Thank you for the great suggestion. Yes, we are happy to add new experiments on FedVARP for a more in-depth understanding of our work.

Specifically, we test the FedVARP algorithm under the client unavailability dynamics in Table 1 on page 9 in our manuscript. Please refer to Table 2 in the pdf for complete results. Due to space limit, Table Q2 only lists the comparisons between our algorithm, FedVARP and MIFA under the staircase non-stationary dynamics.

We can see from Table Q2 that the performance of FedVARP is in general slightly better than MIFA, consistent with the observations in [53] and [R1]. We want to emphasize that it is a bit unfair to compare the proposed algorithm with those variance-reduced algorithms, where they take advantage of significantly more extra memory space proportional to the size of $O(md)$ and thus violate our design principle of this work: efficiency. In fact, most of the clients in cross-device federated learning are mobile or IoT devices with limited storage and memory capacity [19]. The added memory will burden their hardware, eventually impacting regular operations. However, our algorithm can sometimes even outperform them. Similarly to the statements in the manuscript (lines 340-341 on page 9), we attribute this phenomenon to our usage of gradients from always fresh stochastic samples. This is in contrast to their reuse of stored gradients from unavailable clients.

Table Q2: Additional performance comparisons with FedVARP under the staircase non-stationary dynamics.

References:

[R1] Jhunjhunwala, D., et al. (2022). Fedvarp: Tackling the variance due to partial client participation in federated learning. In Uncertainty in Artificial Intelligence (pp. 906-916). PMLR.