acceptodds
Under review as a conference paper at ICLR 2027

Cycwin-FL: Convergence for Federated Learning with Cyclic-Window Client Availability

Abstract

In resource-constrained federated learning (FL), client availability may be restricted by computing power, connectivity or privacy requirements, thus entailing *controlled* client participation. This prohibits direct application of existing convergence-analysis frameworks under the simplified assumption of full or uniform client sampling. Recent studies on convergence for FL with cyclic client participation schemes often considered restricted types of training objectives or specific cyclic patterns. In this paper, we investigate FL with a *general deterministic cyclic pattern*, i.e., *Cycwin-FL*, which applies FedAvg with uniform client sampling from within a window of among clients that cyclically advances by clients per communication round. We provide convergence analysis for Cycwin-FL with Polyak-Łojasiewicz (PL)-conditioned and general smooth non-convex objectives, respectively. Specifically, if is satisfied, for PL-conditioned objectives, we reveal an upper bound on the optimality gap leveraging window-induced bias cancellation, where is the total number of communication rounds; and for general smooth non-convex objectives, we derive the same convergence rate as the vanilla FedAvg. In addition, we also quantify the impact of failure in meeting the condition on convergence. Finally, experiments validate our theoretical insights into the effect of the cyclic patterns.

Primary area:
learning theory
Keywords:
Federated learning, cyclic-window client availability, convergence analysis

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_4cBsOpenReview ↗
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 O(1/T2)O(1/T^2) 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 O(1/T)O(1/\sqrt{T}) 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 γ\gamma and window-to-global heterogeneity α\alpha, 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
AuthorsOpenReview ↗

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.

W1/Q1: The theoretical novelty beyond CyCP is unclear. What new theoretical insights and nontrivial analytical challenges arise beyond CyCP?

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)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)(k,p)‘s. However, the window-induced gradient bias in (33) cancels as ∑pϵ(k,p)(w)=0\sum_p\epsilon^{(k,p)}(w)=0 in (34) at a common model ww, resulting in the gradient contributions across inner rounds pp being missing (p=1,…,Pp=1,\ldots,P). The challenge is therefore to exploit this cancellation to ensure convergence while retaining 1T∑k=0K−1∑p=1PE∥∇F(w(k,p−1))∥2\frac1T\sum_{k=0}^{K-1}\sum_{p=1}^P\mathbb E\|\nabla 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.
AuthorsOpenReview ↗

Response to Reviewer 4cBs (2/2)

W2: α\alpha and γ\gamma 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 α\alpha and γ\gamma.

We use quadratic local objectives with F(w)=∥w∥2/2F(w)=\|w\|^2/2 and L=μ=1L=\mu=1. We choose the client objectives so that, for every available set A\mathcal A, client m∈Am \in \mathcal A and model ww,

∥∇Fm(w)−∇F‾A(w)∥=γ,\|\nabla F_m(w)-\overline{\nabla F}_{\mathcal A}(w)\|=\gamma,

∥∇F‾A(w)−∇F(w)∥=α.\|\overline{\nabla F}_{\mathcal A}(w)-\nabla F(w)\|=\alpha.

These are exactly the gradient differences in Assumption 3.

We fix M=50M=50, B=Nw=5B=N_w=5, S=2S=2, τ=15\tau=15, η=10−4\eta=10^{-4}, T=20000T=20000 and w(0,0)=(3,0,3,0)⊤w^{(0,0)}=(3,0,3,0)^\top. Gradients are exact; only client sampling is random. The table averages F(w(t))−F∗F(w^{(t)})-F^* over rounds 19,000–19,999 and 5,000 Monte Carlo replicates paired across settings.

α\alphaγ\gammaMean optimality gap (×10−6\times10^{-6})
0.50.12.137
10.14.346
20.113.183
10.28.548
10.425.354

Larger α\alpha increases model drift, while larger γ\gamma increases client-sampling variance because S<BS<B. 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 ζ≥0\zeta\ge0 satisfies

∥∇Fm(w)−∇F(w)∥≤ζ,∀m,w.\|\nabla F_m(w)-\nabla F(w)\|\le\zeta,\qquad\forall m,w.

Averaging over m∈Am\in\mathcal A gives

∥∇F‾A(w)−∇F(w)∥≤ζ.\|\overline{\nabla F}_{\mathcal A}(w)-\nabla F(w)\|\le\zeta.

The triangle inequality then gives ∥∇Fm(w)−∇F‾A(w)∥≤2ζ\|\nabla F_m(w)-\overline{\nabla F}_{\mathcal A}(w)\|\le2\zeta. Thus α=ζ\alpha=\zeta and γ=2ζ\gamma=2\zeta are valid bounds in (10)–(11). Conversely, Assumption 3 implies the standard bound with ζ=α+γ\zeta=\alpha+\gamma. 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.

AuthorsOpenReview ↗

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.

Reviewer_WuahOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the convergence of federated learning under cyclic-window client availability, providing theoretical guarantees for both PL and non-convex objectives under balanced scheduling and characterizing the impact of scheduling unbalance on convergence.

Critical strengths
  1. The theoretical analysis is relatively comprehensive, covering both the Polyak–Łojasiewicz (PL) condition and the non-convex setting. Under balanced scheduling, the convergence rates are consistent with those of standard FedAvg. Under unbalanced scheduling, the effect of the imbalance is explicitly incorporated into the convergence guarantees.

  2. The experiments also show that unbalanced scheduling can lead to worse performance than balanced scheduling, providing empirical support for the theoretical results.

Critical weaknesses
  1. The practical applications of cyclic-window client availability are not sufficiently clear. The authors only mention low Earth orbit (LEO) satellite networks as an example.

  2. Under unbalanced scheduling, the theoretical results indicate that convergence to a stationary point cannot be guaranteed under either the PL condition or the non-convex setting, and the experimental results are consistent with this observation. However, whether the scheduling pattern is balanced appears to be determined by the system configuration (i.e., whether Assumption 4 holds). Is there a way to transform an unbalanced scheduling pattern into a balanced one?

  3. The heterogeneity assumption (Assumption 3) may be relatively strong. Refer to EF21: https://arxiv.org/pdf/2106.05203.

Questions for authors
  1. Could the authors further clarify the practical scenarios in which cyclic-window client availability arises and explain where the proposed framework would be most applicable?

  2. Can an unbalanced scheduling pattern be transformed into a balanced one? Alternatively, under unbalanced scheduling, are there any approaches that could ensure convergence of the model parameters to a first-order stationary point?

  3. Is it possible to relax or eliminate Assumption 3?

5 comments
AuthorsOpenReview ↗

Response to Reviewer Wuah (1/3)

Thank you for your valuable comments and constructive suggestions. All the equation numbering follows that in the original submission.

W1/Q1: The practical applications are unclear beyond the LEO satellite example. Which practical scenarios produce cyclic-window availability, and where is the framework most applicable?

We appreciate the opportunity to clarify how recurring, overlapping availability in satellite and smartphone FL motivates our model, and hope the explanations below can address your concerns:

  1. Periodic availability in satellite FL. Satellite FL is our main example because orbital motion creates recurring ground-station windows. Razmi et al. (2022) [R1] describe a polar ground-station configuration with recurring contact order. This motivates a cyclic client order and a sliding availability window of size BB and advance NwN_w.

  2. Overlapping availability in smartphone FL. Such overlapping availability also arises in smartphone FL. Bonawitz et al. [R2] describe phones training when idle, charging, and connected to unmetered networks. Across time zones, overlapping nighttime eligibility allows neighboring populations to remain available simultaneously while the active population shifts. Moreover, Zhu et al. [R3] find that gradual periodic shifts better match practical observations than abrupt block switches. In this case, our sliding window models this staggered availability: when Nw<BN_w<B, some clients remain eligible across consecutive rounds.

We hope that these clarifications sufficiently highlight the practical applications of our work.

[R1] Razmi N et al. Ground-Assisted Federated Learning in LEO Satellite Constellations. IEEE Wireless Communications Letters, 11(4):717–721, 2022.

[R2] Bonawitz K et al. Towards Federated Learning at Scale: System Design. MLSys, 2019.

[R3] Zhu C et al. Diurnal or Nocturnal? Federated Learning of Multi-branch Networks from Periodically Shifting Distributions. ICLR, 2022.

AuthorsOpenReview ↗

Response to Reviewer Wuah (2/3)

W2/Q2: Under unbalanced scheduling, convergence is not guaranteed. Can an unbalanced cyclic pattern be made balanced, or can first-order stationarity be ensured under unbalanced participation?

We agree with the reviewer that this is an important issue and deserves explicit clarification. In this work, we correct the unequal client weights and establish convergence guarantees without modifying the underlying availability pattern.

Let cmc_m count client mm's available rounds per cycle (Section 4.1), giving πm=cm/(PB)\pi_m=c_m/(PB). We multiply its local update in (5) by am=PB/(Mcm)a_m=PB/(Mc_m), retaining the divisor SS. Then

=\sum_m\frac{c_ma_m}{PB}\nabla F_m(w)=\nabla F(w).$$ Thus the cycle average restores the global objective (1) even when $c_m$ differ. Under Assumptions 1 and 3, with $F$ bounded below, full-window participation and exact gradients, the bound has no objective-mismatch term. For fixed system parameters, let the horizon-dependent step size tend to zero while its product with the horizon diverges. Then the average squared gradient norm vanishes; under the PL condition, the optimality gap also vanishes. [Appendix K](https://anonymous.4open.science/r/Cycwin-FL_Rebuttal-384E/appendix_K_inverse_coverage.pdf) gives the theorem, proof and setups. Both CIFAR-10 tasks use $M=50$, 400 distinct images per client, and alternating 90:10/10:90 splits of classes 0–4/5–9. Unbalanced runs use $B=S=3,N_w=2,P=25$; the balanced reference uses $N_w=1$. Paired runs share data and a 10-epoch pooled-data ResNet-18 warm-up. 1. First, ridge regression on fixed features with regularization 0.1 is PL. From zero weights, we use exact gradients, $\tau=2$, $T=50000$ and three paired replicates. Entries average $F(w^{(t)})-F*$ over rounds $49,000-49,999$ and replicates; $F^*$ is computed numerically. Here $L$ is the largest client-Hessian eigenvalue. | $\eta L$ | Unbalanced | Inverse weighting | Balanced | | -------- | ------------------- | ------------------- | ------------------- | | 0.1 | $6.74\times10^{-3}$ | $1.88\times10^{-5}$ | $5.79\times10^{-5}$ | | 0.05 | $6.68\times10^{-3}$ | $5.00\times10^{-6}$ | $1.73\times10^{-5}$ | Halving the step size lowers the weighted gap but barely changes the unweighted gap, consistent with correcting cyclic gradient bias. 2. Second, we train the width-16 GroupNorm ResNet-18 end to end with cross-entropy, head regularization 0.01, $\tau=2$, batch size 64, $\eta=0.005$ and $T=500$. Over ten paired replicates, mean final test accuracy rises from 60.20% to 61.06%; mean loss on 20 images/client over rounds 400–499 falls from 0.9136 to 0.8923. Both improve in all ten replicates; the paired accuracy gain is 0.87 percentage points, with a 95% CI [0.54, 1.20]. In summary, inverse-coverage weighting restores $F(w)$ in the cycle average without changing client availability. The theorem establishes convergence under the stated assumptions, while the two CIFAR-10 experiments show a smaller PL optimality gap and improved neural-network test accuracy in the evaluated settings.
AuthorsOpenReview ↗

Response to Reviewer Wuah (3/3)

W3/Q3: Assumption 3 may be too strong. Can it be relaxed or eliminated? Please consider EF21.

We appreciate the reviewer’s insightful question. We try to address this concern by discussing gradient-estimation updates as a possible way to relax Assumption 3, as follows.

EF21 [R4] avoids bounded gradient dissimilarity using a contractive compressor and error feedback to maintain gradient estimates and control their error. MARINA [R5] also avoids this assumption by using compressed gradient differences and occasional full-gradient refreshes.

In this case, a promising extension to Cycwin-FL is to maintain each client's gradient estimate and refresh it when available. Analyzing this error between visits and after refreshes could relax the assumption.

However, our analysis focuses on isolating how participation affects FedAvg. Assumption 3 follows CyCP's separation of within-group and group-to-global heterogeneity [R6], extended to windows. It also relates to the uniform client-to-global bound ζ\zeta used by Woodworth et al. [R7, Eq. (12)], which permits α=ζ\alpha=\zeta and γ=2ζ\gamma=2\zeta as upper bounds. Moreover, to understand their effects, we measure gradients on CIFAR-10 and vary α\alpha and γ\gamma independently in PL experiments; Appendix J provides the results.

[R4] Richtárik P et al. EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback. NeurIPS, 2021.

[R5] Gorbunov E et al. MARINA: Faster Non-Convex Distributed Learning with Compression. ICML, 2021.

[R6] Cho Y J et al. On the Convergence of Federated Averaging with Cyclic Client Participation. ICML, 2023.

[R7] Woodworth B et al. Minibatch vs Local SGD for Heterogeneous Distributed Learning. NeurIPS, 2020.

Reviewer_kY7DOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies FedAvg under deterministic cyclic-window client availability, where clients are sampled from a periodically shifting window. It establishes a necessary and sufficient condition for balanced participation and derives O~(1/T)\tilde{\mathcal{O}}(1/T) convergence for PL objectives and O(1/T)\mathcal{O}(1/\sqrt{T}) convergence for general smooth non-convex objectives. For unbalanced participation, the authors characterize the resulting client-weighting bias and its impact on convergence. Experiments support the theoretical findings.

Critical strengths
  1. The paper addresses a practically relevant problem in federated learning with structured client availability.
  2. The theoretical analysis covers both PL and general non-convex objectives, with explicit characterization of sampling noise, local drift, and cyclic imbalance.
  3. The experiments across multiple datasets support the theoretical insights and include ablation studies investigating key system parameters.
Critical weaknesses
  1. The algorithmic novelty is limited, as Cycwin-FL essentially applies standard FedAvg under a generalized cyclic participation schedule.
  2. The analysis relies on restrictive assumptions, including deterministic periodic availability and uniformly bounded gradient heterogeneity, which may limit practical applicability.
  3. The theoretical step-size and horizon requirements are conservative. For example, Theorem 3.2 requires T≥4096P2T\geq4096P^2, which is far beyond the experimental training horizons.
  4. The experiments primarily demonstrate comparable performance to FedAvg rather than clear improvements. Moreover, the dependence on cycle length is not directly validated.
  5. There are no participation-aware baselines (e.g., Crawshaw & Liu, 2024; amplified FedAvg from Wang & Ji, 2022).
Questions for authors
  1. How does the theoretical contribution compare with existing analyses of cyclic client participation, particularly Cho et al. (2023), beyond extending the participation patterns?
  2. Can the convergence analysis be extended to irregular or stochastic client availability, which may better reflect practical satellite communication scenarios?
  3. How sensitive are the theoretical guarantees to the bounded heterogeneity assumption, and could this assumption be relaxed?
5 comments
AuthorsOpenReview ↗

Response to Reviewer kY7D (1/3)

Thank you for your valuable comments and constructive suggestions. All the equation numbering follows that in the original submission.

W1/Q1: The algorithmic novelty is limited because Cycwin-FL applies FedAvg under a generalized cyclic schedule. What theoretical contributions go beyond extending CyCP's participation patterns?

We explain in the sequel our non-trivial contributions to dealing with general smooth and non-convex objectives and failure to meet the balanced condition (Lemma 3.1), all beyond CyCP [R1], and their insights.

Firstly, compared to CyCP that only considered PL conditions, we establish an O(T−1/2)O(T^{-1/2}) bound for FedAvg with general smooth non-convex objectives under our deterministic cyclic-window patterns, which is quite non-trivial. This is because we must bound the average expected squared gradient norm over all (k,p)(k,p)‘s. However, the window-induced gradient bias in (33) cancels as ∑pϵ(k,p)(w)=0\sum_p\epsilon^{(k,p)}(w)=0 in (34) at a common model ww, resulting in the gradient contributions across inner rounds pp being missing (p=1,…,Pp=1,\ldots,P). The challenge is therefore to exploit this cancellation to ensure convergence while retaining 1T∑k=0K−1∑p=1PE∥∇F(w(k,p−1))∥2\frac1T\sum_{k=0}^{K-1}\sum_{p=1}^P\mathbb E\|\nabla 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 periodic availability, including both *balanced* and *unbalanced* cyclic patterns, with 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 mismatch term $(\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) in the cycle average 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. We hope that this clarification clearly illustrates the differences between our work and that of Cho et al. in terms of technical contributions. [R1] Cho Y J *et al.* [On the Convergence of Federated Averaging with Cyclic Client Participation](https://proceedings.mlr.press/v202/cho23b.html). ICML, 2023.
AuthorsOpenReview ↗

Response to Reviewer kY7D (2/3)

W2/Q2: Deterministic periodic availability may limit practical applicability. Can the analysis cover irregular or stochastic availability that may better reflect satellite communication?

We appreciate the opportunity to clarify cyclic availability and irregular participation, and we hope the explanations below can address your concerns.

  1. Clarification of the cyclic pattern. The "cyclic pattern" considered herein refers to a structured availability process involving uniform sampling with a deterministic total number of participants. Admittedly, more general irregular participation, as mentioned by the reviewer, may include, for example, random sampling of available clients with replacement in each round, causing a random total number of participants in each round. Satellite channels can cause such irregular participation because communication conditions vary across clients and over time.

  2. Strong practical relevance. Our cyclic pattern, motivated by applications involving satellite movements, covers many cases of strong practical relevance. Specifically, Razmi et al. (2022) [R2] described a polar setting with the same contact order in each orbit, motivating a cyclic client order. FedLEO (2023) [R3] scheduled sink uploads using predicted visibility and forwarded local models within an orbital plane, allowing clients to contribute without direct ground contact, which validates our assumption of a "deterministic" number of participants in model aggregation even if a client "randomly" loses contact with the server. In fact, we addressed very challenging general periodic availability, including both balanced and unbalanced cyclic patterns, with the cyclic pattern considered in the most closely related work, CyCP, as a special case. The balanced condition is satisfied when d∣Bd\mid B, where d=gcd⁡(M,Nw)d=\gcd(M,N_w) (Lemma 3.1). CyCP has Nw=BN_w=B for all clients, so it is balanced. However, when the balanced condition is broken, we characterize these general patterns in Section 4.1.

  3. Related analysis and open challenges. For the most general form of "irregular participation," including uniform sampling with replacement, related work [R4, R5] exists, but its results typically rely on specific assumptions. For example, Wang & Ji [R4, Prop. 4.7] assumed independence across rounds in one finite-time result. Crawshaw & Liu [R5] required the same expected weights for each client over a window. Thus, establishing theoretical guarantees for more general irregular participation under weaker restrictions remains an open problem in the FL community and is left for future work.

We hope these enhancements sufficiently resolve your concerns.

[R2] Razmi N et al. Ground-Assisted Federated Learning in LEO Satellite Constellations. IEEE Wireless Communications Letters, 11(4):717–721, 2022.

[R3] Elmahallawy M, Luo T. Optimizing Federated Learning in LEO Satellite Constellations via Intra-Plane Model Propagation and Sink Satellite Scheduling. ICC, 2023.

[R4] Wang S, Ji M. A Unified Analysis of Federated Learning with Arbitrary Client Participation. NeurIPS, 2022.

[R5] Crawshaw M, Liu M. Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis. NeurIPS, 2024.

AuthorsOpenReview ↗

Response to Reviewer kY7D (3/3)

W2/Q3: Uniformly bounded gradient heterogeneity may limit practical applicability. How sensitive are the guarantees to this assumption, and can it be relaxed?

Thank you for your valuable feedback. We appreciate the opportunity to clarify Assumption 3, possible relaxations, and sensitivity.

Our Assumption 3 is closely related to a commonly used heterogeneity condition. For example, Woodworth et al. [R6, Eq. (12)] used a uniform client-to-global gradient bound, which is equivalent to Assumption 3 up to the choice of bounding constants. Please refer to our reply to Reviewer 4cBs’s Q2 for more detail.

To understand how heterogeneity affects convergence, we conduct experiments that isolate the individual effects of γ\gamma and α\alpha. Please refer to Appendix J for the full experiments.

Finally, relaxation is possible: EF21 [R7] avoided this condition using a contractive compressor and error feedback. However, this method requires revising the training strategy. Adapting it to Cycwin-FL can be a valuable direction for future work, as discussed in our reply to Reviewer Wuah’s W3/Q3.

[R6] Woodworth B et al. Minibatch vs Local SGD for Heterogeneous Distributed Learning. NeurIPS, 2020.

[R7] Richtárik P et al. EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback. NeurIPS, 2021.

W3: The step-size and horizon requirements are conservative; in particular, T≥4096P2T\ge4096P^2 exceeds the experimental horizons.

We explain how a capped step removes the explicit horizon restriction, i.e., T≥4096P2T\ge4096P^2, below.

T≥4096P2T\ge4096P^2 supports Theorem 3.2’s explicit bound by ensuring η=1/(LτT)≤1/(64LPτ)\eta=1/(L\tau\sqrt T)\le1/(64LP\tau). However, the capped step (107) in Appendix E gives the simplified O(T−1/2)O(T^{-1/2}) rate without this threshold. Note that such horizon conditions are common in explicit FL bounds, e.g., CyCP’s Theorem 2 [R1].

W4: Experiments show comparable performance to FedAvg rather than improvements, and do not directly validate the effect of cycle length.

We explicitly validate the effects of the cycle length PP and discuss future acceleration below to clarify these points.

For example, Appendix I studies a CIFAR-10 ridge PL objective with M=50M=50, B=S=10B=S=10, τ=2\tau=2 and P=10,25,50P=10,25,50, using three paired seeds. At ηLmax⁡=0.05\eta L_{\max}=0.05, the mean cycle-averaged optimality gap first falls below 5×10−35\times10^{-3} at recorded rounds 610, 825 and 2,250, respectively. At ηLmax⁡=0.1\eta L_{\max}=0.1, the corresponding recorded rounds are 410 and 1,225 for P=10P=10 and 2525, while P=50P=50 has no recorded cycle-averaged optimality gap below this level during 50,000 rounds. In the end-to-end CIFAR-10 experiment, the mean within-cycle objective range also rises from 0.123 to 0.286 as PP increases from 10 to 50. Thus, longer cycles delay the target gap and increase oscillation in these patterns.

Our goal is not to propose a new optimizer that outperforms FedAvg. Instead, we analyze in detail how our cyclic participation pattern affects FedAvg convergence via its system parameters. To accelerate training, we could adapt methods such as SCAFFOLD [R8], which used control variates to correct heterogeneity-induced client drift. However, this would require revising the training strategy and establishing the corresponding guarantees, which is left as valuable future work.

[R8] Karimireddy S P et al. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. ICML, 2020.

W5: Participation-aware baselines are missing, including Crawshaw & Liu (2024) and amplified FedAvg from Wang & Ji (2022).

We would like to clarify baseline relevance and our choice of CyCP.

We agree that Amplified FedAvg [R4] and Amplified SCAFFOLD [R5] are relevant. With gcd⁡(M,Nw)∣B\gcd(M,N_w)\mid B and S=BS=B, cycle-average weights are 1/M1/M, meeting the regularized participation condition in [R4, R5]. However, their guarantees require additional training techniques that are fundamentally different from ours: amplified updates in [R4] and amplified updates with control variates in [R5]. Beyond equal mean client weights, Theorem 1 of [R5] also requires a positive lower bound on each client’s participation probability within a window and the participation-moment conditions in Eqs. (1)–(2).

CyCP [R1] and our work track accumulated gradients along deterministic schedules to quantify how cyclic participation affects FedAvg convergence. This key contribution makes CyCP our closest theoretical baseline.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary Response to the Area Chair and All Reviewers

Dear Area Chair and Reviewers,

We thank all reviewers for their valuable comments and constructive suggestions, which have helped us improve the paper. Based on our discussions with the reviewers, we have revised the manuscript and uploaded the updated version, with changes from the original submission highlighted in blue. The main revisions are:

  1. We expanded the practical motivation and clarified our contributions relative to existing work in Sections 1–2.

  2. We added the complete PL bound comparison with CyCP, including the proof and numerical comparisons, in Section 3.1 and Appendix L.

  3. We clarified the relationship between Assumption 3 and the standard heterogeneity condition in Section 3 and Appendix J, and added experiments examining α\alpha and γ\gamma in Appendix J.

  4. We added inverse-coverage correction, its convergence guarantees and complete proofs, and supporting experiments in Sections 4.2 and 5.2 and Appendix K.

  5. We added experiments examining the influence of cycle length PP on convergence in Appendix I.

Thank you again for your time and valuable feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.