- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies the Federated Learning (FL) algorithm under deterministic cyclic-window client participation, termed Cycwin-FL. The proposed framework generalizes the existing CyCP by allowing overlapping client availability windows, where clients are uniformly sampled within a window that shifts cyclically across communication rounds. The main contribution is the derivation of convergence bounds for both PL objectives and general smooth non-convex objectives. For PL objectives, the authors extend the improved convergence rate of established by CyCP to more general balanced cyclic-window patterns under full-window participation and noiseless gradients. For unbalanced participation, they characterize the resulting client-weighting bias and derive additional error terms that may not vanish as the number of communication rounds increases. Furthermore, they establish an convergence rate for the average expected squared gradient norm under general smooth non-convex objectives, and present experiments on image classification and quadratic optimization problems to validate the theoretical findings.
Critical strengths
S1. Rigorous theoretical analysis. This paper provides a rigorous convergence analysis of FedAvg under generalized cyclic-window client participation, covering both PL and general smooth non-convex objectives.
S2. Generalization of existing convergence theory. This paper extends the convergence analysis of CyCP to more general cyclic participation patterns, including overlapping windows and unbalanced client availability. In particular, it characterizes the additional optimization errors arising from unbalanced participation.
S3. Empirical validation of theoretical findings. Experimental results on image classification and quadratic optimization problems are consistent with the theoretical analysis, supporting the derived convergence bounds and the effects of balanced and unbalanced client participation.
Critical weaknesses
W1. Limited theoretical novelty.
Although this paper generalizes CyCP to overlapping and unbalanced cyclic-window participation, the main theoretical findings appear largely predictable from the existing convergence analysis of CyCP. I recognize that generalizing client sampling schemes and their convergence analyses is a meaningful contribution to the FL research community. However, the paper appears to provide limited fundamentally new theoretical insights, and it remains unclear whether the proposed generalization involves substantial analytical challenges beyond those addressed in prior work.
W2. Limited empirical validation of heterogeneity assumptions (Assumption 3).
Assumption 3 introduces two heterogeneity parameters, within-window heterogeneity and window-to-global heterogeneity , but their values are not quantified in the experiments. It would be valuable to empirically estimate these parameters under different levels of data heterogeneity and investigate how their magnitudes relate to the observed convergence behavior and the theoretical bounds.
Questions for authors
Q1. Regarding W1, could the authors clarify whether the proposed generalization provides any fundamentally new theoretical insights or introduces nontrivial analytical challenges beyond those addressed in prior work, particularly CyCP?
Q2. Could the authors clarify how Assumption 3 relates to standard gradient heterogeneity assumptions commonly used in FL convergence analyses?
4 comments
Response to Reviewer 4cBs (2/2)
W2: and are not quantified empirically. How do they vary with data heterogeneity and relate to convergence and the theoretical bounds?
Thank you for your comments. We try to address this concern by experimentally analyzing the direct effects of and .
We use quadratic local objectives with and . We choose the client objectives so that, for every available set , client and model ,
These are exactly the gradient differences in Assumption 3.
We fix , , , , , and . Gradients are exact; only client sampling is random. The table averages over rounds 19,000–19,999 and 5,000 Monte Carlo replicates paired across settings.
| Mean optimality gap () | ||
|---|---|---|
| 0.5 | 0.1 | 2.137 |
| 1 | 0.1 | 4.346 |
| 2 | 0.1 | 13.183 |
| 1 | 0.2 | 8.548 |
| 1 | 0.4 | 25.354 |
Larger increases model drift, while larger increases client-sampling variance because . Each raises the optimality gap, consistent with the bound. We also study neural-network training on CIFAR-10, providing results for general non-convex objectives and direct measurements of the gradient differences in (10)–(11). Details are provided in Appendix J. We hope these enhancements sufficiently resolve your concerns.
Q2: How does Assumption 3 relate to standard gradient heterogeneity assumptions in FL?
Thank you for your valuable feedback. We appreciate the opportunity to clarify how Assumption 3 refines a standard gradient-heterogeneity bound.
A standard assumption, as in Woodworth et al. [R2, Eq. (12)], is that some finite satisfies
Averaging over gives
The triangle inequality then gives . Thus and are valid bounds in (10)–(11). Conversely, Assumption 3 implies the standard bound with . This separates inter-window and intra-window heterogeneity in the bounds. In this sense, Assumption 3 and the standard condition are equivalent up to their bounding constants.
[R2] Woodworth B, Patel K K, Srebro N. Minibatch vs Local SGD for Heterogeneous Distributed Learning. In Advances in Neural Information Processing Systems, 2020.
Thank you for your detailed responses and additional analyses/experiments.
Regarding W1, my concern has been partially mitigated. In particular, the sharper convergence bound compared with CyCP is a meaningful theoretical contribution that I better appreciated through this rebuttal. The additional proof in Appendix L and the numerical comparisons also helped address my concern about theoretical novelty.
Regarding W2 and Q2, the additional experiments and the clarification of how Assumption 3 relates to the standard heterogeneity assumption in Woodworth et al. (2020) have alleviated my concerns. I believe these additions and clarifications would also be valuable to general readers, and I encourage the authors to incorporate them into the revised version.
Given that my concerns have been mitigated, I have improved my rating.
Response to Reviewer 4cBs
Thank you for your careful reassessment and constructive feedback. We appreciate your recognition of our theoretical contribution and your updated assessment.
Following your suggestion, we will add these analyses, experiments, and clarifications to the revised paper.
Thank you again for your valuable suggestions, which have helped us improve the paper.
Response to Reviewer 4cBs (1/2)
Thank you for your valuable comments and constructive suggestions. All the equation numbering follows that in the original submission.
We explain non-trivial technical challenges in dealing with general smooth and non-convex objectives and failure to meet balanced conditions, all beyond CyCP [R1], and our solutions with insights.
Firstly, compared to CyCP that only considered PL conditions, we establish an O(T−1/2) bound for general smooth non-convex objectives with deterministic cyclic patterns for the first time, which is quite non-trivial. This is because we must bound the average expected squared gradient norm over all (k,p)‘s. However, the window-induced gradient bias in (33) cancels as ∑pϵ(k,p)(w)=0 in (34) at a common model w, resulting in the gradient contributions across inner rounds p being missing (p=1,…,P). The challenge is therefore to exploit this cancellation to ensure convergence while retaining T1∑k=0K−1∑p=1PE∥∇F(w(k,p−1))∥2. We resolve it by revisiting the gradient comparison used in the PL proof:
\qquad\text{(cf. (99)).}$$ We then reformulate the gradient-descent recursion as (102), which completes the proof for Theorem 3.2 (Appendix E). Moreover, we aim to address very challenging general *unbalanced* availability, which includes the cyclic pattern of CyCP as a special example. Let $c_m$ count client $m$’s available rounds per cycle. These counts provide *balanced* availability when $d\mid B$, $d=\gcd(M,N_w)$ (Lemma 3.1). CyCP has $N_w=B$, $c_m=1$ for all clients, so it is balanced. However, when the balanced condition is broken due to different $c_m$’s among clients, we model these general patterns in Section 4.1. Next, we quantify the effect of unbalanced cyclic patterns and correct their cyclic gradient bias. Unequal $c_m$’s result in an objective $F_\pi(w)=\sum_m[c_m/(PB)]F_m(w)$, which may differ from $F(w)$ in (1). However, simply reducing the step size cannot remove this bias $(\alpha+\gamma)^2\Delta_{\rm cyc}^2/\mu$. We introduce $a_m=PB/(Mc_m)$ such that $a_mc_m/(PB)=1/M$, which recovers the original objective $F(w)$ in (1) under unbalanced conditions. [Appendix K](https://anonymous.4open.science/r/Cycwin-FL_Rebuttal-384E/appendix_K_inverse_coverage.pdf) gives more details. Last but not least, we reveal a sharper PL-conditioned bound than CyCP by reducing the influence of the period $P$ in the accumulated stochastic-variance estimate from $P^2V_\nu$ to $PV_\nu$. In the same $N_w=B$, $M=PB$ setting, these terms are $$\text{CyCP: }\widetilde O\left(\frac{LP\Sigma_{\rm eff}^2}{\mu^2T}\right),\qquad \text{ours: }\widetilde O\left(\frac{L\Sigma_{\rm eff}^2}{\mu^2T}\right).$$ For fixed parameters with $\Sigma_{\rm eff}^2>0$ and $P\ge3$, we therefore characterize more refined insights on $P$ via the model drift (cf. (13)). Refer to [Appendix L](https://anonymous.4open.science/r/Cycwin-FL_Rebuttal-384E/appendix_L_sharper_bounds.pdf) for numerical comparison with CyCP. [R1] Cho Y J, Sharma P, Joshi G, Xu Z, Kale S, Zhang T. [On the Convergence of Federated Averaging with Cyclic Client Participation](https://proceedings.mlr.press/v202/cho23b.html). In *Proceedings of the 40th International Conference on Machine Learning*, 2023.