Thanks for the response
Dear Reviewer i6Qf:
Thanks for your response. We apologize for any lack of clarity in the previous response due to insufficient space and hope that our further elaborations can address your concerns.
**On gradient amplification.**
- First, we are happy to elaborate the details of the cited references to corroborate our claim on gradient amplification.
- [53] tackles stationary client unavailability, where the accumulated local gradients of each client are amplified by a factor obtained from a separate online estimation scheme.
- [40] generalizes FedAvg in Algorithm 1 by amplifying the accumulation of local gradients by their corresponding responsive probabilities.
- [19], as a classic survey in the federated learning community, points out open challenges in mitigating bias. For example, Section 7.2.3 on page 84 in [arXiv:1912.04977] mentions in the second bullet point that ''If the expected rate of contribution depends on factors outside our control, ..., one can correct for bias by scaling up or down contributions from devices depending on their stratum.''
- [52] studies non-stochastic client unavailability and proposes a generalized FedAvg algorithm, which is different from the vanilla FedAvg. In line 12 of its pseudocode, the accumulation of local gradients is amplified by a factor of $(\eta-1)$ every $P$ rounds.
- [27], although studies partial device participation with known probability in Section 3.3, does not touch gradient amplifications. We are willing to take this off from the response.
- Second, we are running the additional experiments under extremely small probabilities per your requests. We will update the experimental results in a separate response or, in the worst case, in the camera-ready version if accepted, as we are only less than one day away from the end of the author-reviewer discussion period.
- In our submission, the contributing weight of each client's local gradient accumulation is not just $(t-\tau\_i(t))$ but a coupling of $\eta\_g(t-\tau\_i(t))$ due to a global learning rate $\eta\_g$ in line 10 of Algorithm 1.
- For empirical success, the negative impacts of extremely long unavailable duration can be potentially mitigated through the carefully tuned global learning rate $\eta\_g$. Alternatively, we conjecture that clipping the unavailable duration up to a threshold like in FedAU [53] might help. It is also interesting to explore this direction theoretically in the future.
**On the appearance of $(1+L^2)$.** After an additional careful review of our proofs, we did not identify the issues that will affect our presentations in Theorem 1 and Corollary 1.
However, we discover an interesting fact that allows us to remove $L^2$ by following the same proof outline and learning rate conditions in $(10)$ but slightly different simplification techniques during lines 789 and 792 on page 34 and line 807 on page 37. The results hold in parallel to those in our initial submission, and we will incorporate the complete results, together with their proofs, into the camera-ready version if accepted.
For ease of presentation, we discuss only the asymptotics w.r.t. $\eta\_l$ and $L$. The term $1/(mT)\sum\_{t=0}^{T-1}\sum\_{i=1}^m\mathbb{E}[\|\|\nabla F\_i(z\_i^t)\|\|^2]$ in lines 789, 792 and 806 can be expanded to three terms relating to $\zeta^2$, $\mathbb{E}[\|\|\nabla F(\bar{z}^t)\|\|^2]$ and $\mathbb{E}[\|\|z\_i^t-\bar{z}^t\|\|^2]$ by Proposition 3. Since $\eta\_l$ and $L$ share the same order in the first two, we are interested only in the last consensus error term, whose coefficient is proportional to $\eta\_l^3L^4$ ($\eta\_l^2L^4$ for line 807 since no rearrangement is needed).
- *Sketch of the new derivation.* Directly plugging Lemma 6 on page 29 into lines 789, 792 to bound the consensus error term will yield the coefficients of the resulting terms in the scale of $\eta\_l^5L^4$. During the rearrangement in line 799, the order of $\eta\_l$ reduces by 1 and thus becomes $\eta\_l^4L^4$. Line 807 can be shown analogously. By choosing $\eta\_l=1/(sL\sqrt{T})$ for sufficiently large $T$, we will remove $L^2$.
- *Sketch of the original derivation.* First, we apply the learning rate condition in (10) to simplify the coefficients of the respective terms in the consensus error bound (Lemma 6) on page 29. Then, the simplified consensus error bound is plugged into lines 789, 792 and 806. The resulting coefficients remain proportional to $\eta\_l^3L^4$ ($\eta\_l^2L^4$ for line 807). Therefore, $L^2$ remains after the rearrangement (one-order reduction) and the choice of learning rate.
We appreciate the reviewer's efforts to check the provided literature in detail. We believe that this was only due to miscommunications, as we try to justify the appearance of $L$ instead of a union of $(1+L^2)$.
Best regards,
Authors of Submission 449