On the Convergence of Federated Averaging with Cyclic Client Participation

1 Introduction

• Practical client availability is cyclic because participation depends on local criteria, observed diurnal patterns, and limits on how frequently clients may participate.These criteria include device idleness, charging, and unmetered network access.Source: §1 · p. 2
• Under a global PL objective, cyclic client participation can achieve eO(1/T^2) error convergence under suitable conditions, faster than FedAvg’s standard O(1/T) rate.Here T is the number of communication rounds.Source: §1 · p. 2
• The framework covers client subsampling within available groups, group count and data heterogeneity effects, and local GD, SGD, and shuffled SGD.It includes several FedAvg variants as special cases and matches prior bounds in those cases.Source: §1 · p. 2
• Preliminary experiments show better test accuracy and training-loss convergence for cyclic participation than standard FedAvg.The passage reports this as preliminary experimental evidence.Source: §1 · p. 2

2.1 Client Participation in FL.

• Earlier FedAvg work focused on unbiased partial participation with O(1/T) convergence; cyclic participation had not been considered in that line of work.Related work also considered flexible or loss-dependent biased participation.Source: §2.1 · p. 2
• An analysis under the regularized participation class does not capture how client ordering or the number of client groups within a cycle affects convergence; asynchronous client-specific cycles also fail to simulate groups sequentially becoming available to the server.Source: §2.1 · pp. 2–3
• Prior cyclic-participation work examined privacy or communication efficiency, but one speedup bound had an unclear rate because its heterogeneity-dependent variance constant lacked bounds.The paper states that it gives a clear eO(1/T^2) speedup rate and identifies conditions for it.Source: §2.1 · p. 3

2.2 Shuffling-based methods.

• Shuffling-based methods use each component once per epoch, making within-epoch progress approximate full-batch gradient descent; CyCP resembles incremental gradient at the server level.In this analogy, each client is interpreted as a sample.Source: §2.2 · p. 3
• Shuffling analyses distinguish random reshuffling, shuffle once, and incremental gradient, with improved dependence on epoch count requiring a sufficiently large epoch regime.The cited bounds state that the improved dependence requires K larger than O(κ^a), where a is in [1, 2].Source: §2.2 · p. 3

3 Problem Formulation

• The global objective is the average of clients’ empirical losses, and the server seeks a model minimizing that objective.The system has M clients, each with a local training dataset and loss function.Source: §3 · p. 3
• In CyCP, M clients are split into K fixed, non-overlapping groups, traversed in a predetermined order, and N clients are sampled uniformly without replacement from each available group.Once selected, a client cannot participate for at least the next K−1 rounds.Source: §3 · pp. 4–5
• CyCP captures participation limits and patterns associated with privacy requirements, time zones, and device-charging preferences.A timer can enforce that clients participate again only after a period corresponding to K.Source: §3 · p. 4
• A cycle-epoch is the interval in which the server visits all client groups once, comprising K communication rounds.At each round, the server sends the current global model to the selected clients in the currently available group.Source: §3 · p. 4
• The framework considers local GD, SGD, and shuffled SGD; selected clients compute updates that the server aggregates into the global update.Local SGD samples from a client’s dataset, while local SSGD processes disjoint components in a randomly permuted order.Source: §3 · pp. 4–5
• With K = 1, CyCP becomes standard FedAvg with partial participation; with K = 1 and N = M, it also includes minibatch RR or local RR for the stated local-update settings.The paper states that its theoretical results match the bounds for these special cases.Source: §3 · p. 5

4.1 Assumptions

• The assumptions distinguish within-group heterogeneity γ from across-group heterogeneity α, yielding tighter bounds that separate their effects.The analysis assumes a global PL objective and notes that its treatment is restricted to PL functions for brevity and comparison with prior work.Source: §4.1 · p. 6

4.2 Convergence for CyCP with Local GD

• For CyCP+GD, intra-group heterogeneity γ governs the dominant convergence term; when γ is close to zero, the rate can reach ˜O(1/T²).The section states that intra-group heterogeneity has a more significant contribution to error than inter-group heterogeneity α.Source: §4.2 · p. 7
• For CyCP+GD, K = M/N is necessary for lower cost than Standard FedAvg; middle-range 1 < K < M/N costs more.The analysis also says the choice of N can be adjusted when K is naturally fixed.Source: §4.2 · p. 7

4.3 Convergence for CyCP with Local SGD

• For both local SGD and SSGD, increasing K has no adverse impact on convergence because T = KK in the analysis.The SSGD analysis also finds the same dependency on K as CyCP+GD.Source: §4.2 · p. 7, §4.3 · p. 8, §4.4 · p. 9
• For CyCP+SGD, the best convergence rate remains ˜O(1/T) when stochastic gradient variance is positive, even with K = M/N or γ close to zero.A lower cost than Standard FedAvg is possible when N = M/K and γ² ≥ Mσ²/Nτ.Source: §4.3 · p. 8

4.4 Convergence for CyCP with Local SSGD

• For CyCP+SSGD, sufficiently large M and K = M/N make its total cost to reach ε error lower than local RR.The comparison favors smaller inter-group data heterogeneity and larger intra-group data heterogeneity.Source: §4.4 · pp. 10–11

Setup

• The experiments use MLP image classifiers on FMNIST and 62-label EMNIST, with 100 or 500 clients and three partition seeds.They select 5 or 10 clients per round and partition data using Dirichlet distributions with α controlling heterogeneity.Source: §5 · p. 11

Effect of K and Data Heterogeneity

• 5–10% higher test accuracy for FMNIST at α = 0.5 with CyCP (K > 1) than K = 1 (Standard FedAvg) across local procedures.The reported advantage also appears for K values between 1 and M/N.Source: Figure 2 · p. 11, §5 · pp. 11–12
• 2–8% higher test accuracy for FMNIST at α = 2.0 with CyCP (K > 1) than Standard FedAvg, with a smaller gap than at α = 0.5.The text relates the smaller gap to lower data heterogeneity.Source: Figure 3 · p. 11, §5 · p. 12
• CyCP has a larger test-accuracy improvement over Standard FedAvg on EMNIST at α = 0.05 than on FMNIST.The text attributes the larger gap to EMNIST's more heterogeneous partition.Source: Figure 4 · p. 12, §5 · p. 12

Difference Across Client Local Procedures

• At the highest K, local SGD and SSGD test-accuracy curves oscillate as the server visits groups with increasing inter-group heterogeneity.The text reports similar oscillations in training-loss curves.Source: §5 · p. 12

6 Concluding Remarks

• The framework identifies conditions under which cyclic participation converges faster than Standard FedAvg and compares local procedures and special-case algorithms by cost to reach ε error.Future work includes non-PL objectives, general optimizers such as momentum, and client groups that are overlapping or not fixed during training.Source: §6 · p. 12

A Additional Experimental Details and Results

• For each benchmark, experiments grid-searched learning rates 0.05, 0.01, 0.005, 0.001, batch sizes 32, 64, 128, and local iterations 5, 10, 30, 50 for highest test accuracy, then fixed hyperparameters while changing only K.Source: A Additional Experimental Details and… · p. 17
• Higher K > 1 leads to faster training-loss convergence, with a larger improvement gap under high than low data heterogeneity.For high heterogeneity, SGD and SSGD oscillate at K = 20; oscillations are not observed at lower heterogeneity and lower K values.Source: A Additional Experimental Details and… · p. 17, Figure 5 · p. 17, Figure 6 · p. 17

B Useful Inequalities

• The appendix lists standard inequalities, including Young’s, Jensen’s, sum-of-squares, and without-replacement sampling results, for use in the proofs.The supplied passages name these results but do not show their full statements.Source: B Useful Inequalities · p. 18

C Proofs for the CyCP+Local GD Case

• For the local-GD case, the model update is interpreted as noisy gradient descent, and the proof bounds its noise term.The effective learning rate is ηKN.Source: §C.1 · pp. 19–20

C.2 Intermediate Results

• The cyclic-participation error bound adds dependence on intra-group heterogeneity γ when clients are subsampled within each group.The result is stated alongside bounds on summed client-group gradients under Assumption 3.Source: §C.2 · p. 20

C.3 Proof of Theorem 1

• With the stated assumptions and step-size choice, the local-GD theorem gives a convergence-error bound when K ≥ 7κ log(MK2).The step size is η = log(MK2)/µNKK, and the bound suppresses logarithmic terms and numerical constants.Source: §C.3 · p. 21

C.4 Proofs on Intermediate Lemmas

• The proof bounds update error terms using intermediate lemmas and the assumptions, then unrolls the resulting inequality to obtain the theorem’s convergence bound.The derivation invokes smoothness and the step-size restriction η ≤ 1/(7LNK).Source: §C.3 · pp. 21–22, §C.4 · p. 24

C.3 Proof of Theorem 1

• For any N > 1, the stated cost comparison favors K > 1 over K = 1 only when K = M/N, corresponding to full client participation in every group.The communication-round formulation sets T = KK and notes that increasing K requires increasing T accordingly.Source: §C.3 · pp. 21, 23

D Proofs for the CyCP+Local SGD Case

• For local SGD, the update analysis conditions on the randomness through cycle epoch k and samples N clients uniformly without replacement from each available group.The proof uses a stochastic-gradient update over K inner communication rounds.Source: D Proofs for the CyCP+Local SGD Case · p. 27, §D.1 · pp. 27–28

D.2 Intermediate Results

• The local-SGD error bounds depend mainly on the number of local steps τ and intra- and inter-group heterogeneity γ and α.The cyclic-participation error bounds additionally include a variance term σ2 from stochastic gradients.Source: §D.2 · p. 28

D.3 Proof of Theorem 2

• Under Assumptions 1–4 and the stated step size, the local-SGD theorem bounds convergence error for K ≥ 10κ log(MK2) communication rounds.The bound is expressed in terms of T = KK with logarithmic terms and constants suppressed.Source: §D.3 · p. 29

D.4 Proof for Corollary 2

• Except when K = M/N, the passage states that for γ ≥ A1σ2/τ, CSGD|K>1 > CSGD|K=1 requires an additional condition.The passage does not provide that condition’s full right-hand side.Source: §D.4 · p. 32

D.5 Proofs on Intermediate Lemmas

• The intermediate-lemma proofs use smoothness, stochastic-gradient independence across clients, and unbiasedness to derive the error bounds.They also apply the previously established client-group gradient and trajectory bounds.Source: §D.5 · pp. 33, 39, 40, 42

E Proofs for the CyCP+Shuffled SGD Case

• In shuffled SGD, each selected client initializes from the global model and processes its local loss components sequentially in shuffled-SGD steps.The component losses sum to the client’s local loss.Source: E Proofs for the CyCP+Shuffled SGD Case · p. 45

• Lemma E.1 bounds the norm of the error term arising from CyCP.Source: §E.1 · p. 46
• Lemma E.2 bounds the squared norm of the error term arising from CyCP.Source: §E.1 · p. 47
• The bounds depend on ν = γ + α and use η = log(MK2)/τµNKK with K ≥10κ log (MK2).The passage identifies ν as intra-component heterogeneity and γ and α as intra-group and inter-group heterogeneity.Source: §E.1 · p. 47

E.2 Proof for Theorem 3

• Under Assumptions 1–3 and 5, the theorem bounds convergence error for η = log(MBK2)/µKBK and K ≥10κ log (MBK2).Here κ = L/µ.Source: §E.2 · p. 47
• The corollary expresses the bound in terms of total communication rounds T = KK, while the lower bound on K means increasing K requires increasing T.Source: §E.2 · p. 47

E.3 Proof for Corollary 3

• For CyCP+Shuffled SGD to cost less than LocalRR, the proof states a required condition and its equivalent form.Source: §E.3 · p. 50

E.4 Proofs on Intermediate Lemmas

• The proof separately bounds all three components of r(k,0), uses the same techniques for additional terms, and bounds squared noise-term norms, ultimately obtaining a final bound.Source: §E.4 · pp. 50, 53, 54