Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis

• Prior work had not established reduced communication, linear speedup, and resilience to data heterogeneity together for general non-convex optimization with non-i.i.d. participation.Practical client devices may not be available around the clock, and availability can follow cyclic patterns.Source: §1 · pp. 1–2
• The target setting requires equal expected client participation frequency over a window of rounds, and includes cyclic availability.The participation distribution may be unknown, and client participation need not be independent across rounds.Source: §1 · p. 2
• For cyclic participation, Amplified SCAFFOLD reduces communication complexity from O(κ^2 ε^-4) to O(ε^-2).The paper also claims reduced communication, linear speedup, and resilience to data heterogeneity under periodic participation.Source: §1 · p. 2
• Amplified SCAFFOLD combines amplified updates across participation periods with control variates computed across those periods.The paper says this design eliminates the effect of data heterogeneity even under non-i.i.d. participation.Source: §1 · p. 2
• The analysis takes expectations over both client participation and stochastic gradients, and recursively bounds control-variate errors using mild participation regularity conditions.This addresses the nested dependence between participation and control-variate errors.Source: §1 · p. 2
• Experiments report faster convergence than baselines on synthetic and real-world problems under non-i.i.d. participation, with robustness to several setting changes.The ablation varies data heterogeneity, clients participating per round, and the number of client groups in cyclic participation.Source: §1 · p. 3

Federated Optimization

• Federated optimization analyses commonly assume full participation or uniformly random partial participation, and none of the cited works cover general patterns such as periodic participation.Prior work also studies communication efficiency and data heterogeneity, among other objectives.Source: §2 · p. 3

Client Participation

• Existing work had not jointly established linear speedup, reduced communication, and resilience to data heterogeneity for general non-convex objectives with periodic participation.Related work covers varied participation settings, including cyclic and arbitrary participation.Source: §2 · p. 3
• Related work spans client selection, biased, independent, unbiased, bounded-unavailability, asynchronous, cyclic, and arbitrary participation patterns.Cyclic data sampling was also studied for stochastic convex optimization in.Source: §2 · p. 3

3 Problem Setup

• The objective is to find an ε-stationary point, defined by a gradient norm at most ε, for the potentially non-convex global objective.Each client has a local objective, and the setup assumes smoothness and bounded stochastic-gradient variance.Source: §3 · p. 3

3.1 Participation Framework

• The participation framework partitions rounds into windows in which clients have equal expected participation frequency, while requiring nonzero sampling probability within each window.Participation may depend across rounds, so the window-level expectations and probabilities can themselves be random.Source: §3.1 · p. 4

3.2 Specific Participation Patterns

• Regularized participation requires every client to participate within each window, though participation within the window is otherwise flexible.The paper notes this constraint may be impractical.Source: §3.2 · p. 4
• In cyclic participation, clients are divided into equal-sized groups and only one group is eligible each round; this can model groups available at different times of day.Cyclic participation is less restrictive than regularized participation because not every client must participate within each window.Source: §3.2 · p. 4

4.1 Algorithm Overview

• Window-wide amplified updates and control variates give clients equal representation in expectation under periodic participation.Updates and control variates use information accumulated over P rounds, addressing unequal participation frequencies.Source: §4.1 · p. 5

4.2 Main Results

• The analysis establishes reduced communication, linear speedup, and heterogeneity-independent iteration and communication complexity.For reduced communication, the stated communication complexity is O(LP p_sample^-1 epsilon^-2), improving on parallel SGD's epsilon^-4 complexity.Source: §4.2 · p. 6

4.3 Application to Participation Patterns

• Under regularized participation, the algorithm achieves reduced communication and heterogeneity resilience; under cyclic participation, it also achieves linear speedup.For cyclic participation, the comparison says Amplified FedAvg does not reduce communication or achieve heterogeneity resilience except with full participation; the paper also says Amplified SCAFFOLD recovers SCAFFOLD's results under i.i.d. participation with a slightly worse dependence on N/S.Source: §4.3 · pp. 6–7

4.4 Proof Sketch

• The proof analyzes client-participation and stochastic-gradient randomness jointly, then bounds control-variate error across windows rather than consecutive rounds.Regularity conditions bound the nested non-uniform averages that arise in the window-level error recursion.Source: §4.4 · pp. 7–8

5.1 Setup

• With N = 250 clients, image-classification experiments use logistic regression on Fashion-MNIST and a two-layer CNN on CIFAR-10, with S = 10 sampled clients per round.The experiments use five client groups; the availability pattern keeps each group available for g rounds at a time.Source: §5.1 · p. 8, §5 · p. 8

5.2 Main Results

• 800 rounds reach objective value 0.2 for Amplified SCAFFOLD, versus 1900 for SCAFFOLD and 4800 for both FedAvg and Amplified FedAvg; it requires the fewest rounds overall.Across the synthetic, Fashion-MNIST, and CIFAR-10 settings, it reaches the best overall solution among the algorithms by all reported metrics.Source: §5.2 · p. 9, Figure 1 · p. 9, Figure 2 · p. 10
• Amplified FedAvg is comparable to FedAvg, with only slight gains on synthetic data and Fashion-MNIST; on CIFAR-10 it is faster but less stable.The authors suggest its gains may be limited when training from scratch, unlike the prior evaluation that used FedAvg pretraining.Source: §5.2 · p. 9
• SCAFFOLD outperforms Amplified FedAvg in all three settings, although it remains significantly slower than Amplified SCAFFOLD on the synthetic objective and CIFAR-10.The authors note that SCAFFOLD has no theoretical guarantees under non-i.i.d. participation.Source: §5.2 · p. 9

5.3 Ablation Study

• Across the ablation settings, Amplified SCAFFOLD consistently reaches the best training loss and testing accuracy, with experiments indicating superior generalization.The study varies data similarity, participating clients, and the number of client groups.Source: §5.3 · p. 9
• Test accuracy decreases only from 84.6% to 84.45% as data similarity changes from 100% to 2.5%; all baselines have larger decreases.These endpoints compare completely homogeneous with extremely heterogeneous data.Source: §5.3 · pp. 9–10
• Reducing participating clients to S = 5 causes some performance degradation; SCAFFOLD is competitive for S ≥ 15 but drops significantly against Amplified SCAFFOLD at S = 5.The number of participating clients affects performance less than data heterogeneity in this ablation.Source: §5.3 · p. 10
• As the number of client groups increases, FedAvg and Amplified FedAvg worsen, while SCAFFOLD and Amplified SCAFFOLD maintain performance.This empirical stability holds even though Amplified SCAFFOLD's worst-case communication complexity increases with the number of groups.Source: §5.3 · p. 10

6 Conclusion

• Amplified SCAFFOLD is proved to reduce communication, achieve linear speedup, and remain unaffected by data heterogeneity under periodic participation.Experiments also show it outperforming baselines on standard non-i.i.d. benchmarks and robustness to changes in heterogeneity and participating-client count.Source: §6 · p. 10
• The framework requires equal client participation chances over well-defined time windows known to the implementer, so freely joining or leaving clients may fall outside its scope.Extending the guarantees to that setting may require reformulating the optimization problem and adding assumptions about participation.Source: §6 · p. 10

A.1 Preliminary Definitions

• The analysis conditions are satisfied by i.i.d., regularized, and cyclic participation; the conditions enforce bounded control-variate error and sufficient participation uniformity for variance bounds.The first condition limits a term in the nested non-uniform error average, while the second ensures clients participate sufficiently uniformly.Source: §A.1 · p. 17

A.2 Proofs

• Induction unrolls mutually recursive bounds on update-error quantities, yielding the bounds used to prove Equations 3 and 4.The recurrence arguments assume η ≤ 1/(60LIP).Source: §A.2 · pp. 24, 27, 29, 31
• Lemma 2’s proof bounds its terms using martingale differences and stochastic-gradient noise independent across clients.It then applies Lemma 1’s Equation 4 bound under conditions on η and γη.Source: §A.2 · pp. 31, 32, 36
• Lemma 3’s proof splits into participation cases, combines the resulting bounds, and applies Lemma 2.The argument uses conditional and total expectations and chooses λ based on the sampling probability.Source: §A.2 · pp. 36, 38, 39
• Theorem 2 restates Theorem 1 and establishes Algorithm 1’s stated guarantee under Assumptions 1 and 2.The proof derives the guarantee by combining the preceding bounds and averaging over the specified starting rounds.Source: §A.2 · pp. 40, 43, 44
• Corollary 2 restates Corollary 1 for ε > 0 and I ≥ 1, with its conditions ensuring Theorem 2 applies.The proof explicitly invokes Theorem 2 after verifying its conditions.Source: §A.2 · p. 45
• The final proof step uses the chosen γη and R parameters.Source: §A.2 · p. 45

B Proofs for Specific Participation Patterns

• The specific-pattern proofs derive their results by verifying the general conditions and substituting pattern-specific values into Corollary 1.The text identifies ρ², P, and p_sample as the quantities to plug in.Source: B Proofs for Specific Participation… · pp. 45, 47

Regularized Participation

• For regularized participation, the proof verifies Equations 1 and 2 and applies Corollary 1, using p_sample = 1 for the complexity result.The proof states that both conditions are satisfied before invoking the corollary.Source: B Proofs for Specific Participation… · p. 46

Cyclic Participation

• For cyclic participation with K̄ groups and S participating clients per round, Corollary 4 states that choices of η, γ, P, I, and R achieve the stated stationarity bound.The proof checks Equations 1 and 2 by using each client's group and availability round within the P-round window.Source: B Proofs for Specific Participation… · pp. 46–47

C Complexity of Amplified FedAvg

• The prior Amplified FedAvg analysis assumes a sampling-dependent weighted heterogeneity bound, rather than only the conventional heterogeneity constant κ.The section restates its prior corollary and explains how to interpret that bound using κ.Source: C Complexity of Amplified FedAvg · p. 48
• The analysis converts the sampling-dependent heterogeneity bound into terms involving conventional heterogeneity κ and participation-pattern quantity v, enabling complexity comparisons across participation patterns.For cyclic participation, the analysis expresses v using the number of client groups and clients participating per round; P may be chosen as m times the number of groups.Source: C Complexity of Amplified FedAvg · p. 48
• For cyclic participation, the section gives parameter choices for Amplified FedAvg to find an ε-stationary point.The supplied passage does not include the choices or resulting complexity bound.Source: C Complexity of Amplified FedAvg · p. 49

D Experiment Details

• The appendix details the sampling, heterogeneity, tuning, synthetic-objective, and CNN settings used in the experiments.It identifies these as details deferred from the main body.Source: D Experiment Details · p. 49

D.1 Client Sampling Parameters

• The synthetic experiment uses two client groups, availability time g = 240, communication interval I = 10, and R = 5000 training rounds.Fashion-MNIST uses logistic regression with I = 30, R = 2000, and g = 4; CIFAR-10 uses a two-layer CNN with I = 5, R = 12000, and g = 10.Source: §D.1 · p. 49

D.2 Heterogeneity Protocol

• The heterogeneity protocol mixes an i.i.d. pool and a label-sorted non-i.i.d. pool, with the similarity parameter s controlling their proportions in each client’s data.s = 0% gives maximal heterogeneity, while s = 100% allocates data uniformly at random.Source: §D.2 · p. 50

D.3 Hyperparameter Tuning

• The four baselines are individually grid-searched over learning-rate and amplification-rate ranges, with FedProx’s µ also tuned.The search ranges and final parameter values are reported in Table 2.Source: §D.3 · p. 50, Table 2 · p. 50

D.4 Synthetic Objective

• The synthetic experiment uses a difficult lower-bound objective parameterized by H, κ, σ, c, µ, and L, with stochastic gradients perturbed by Gaussian noise.The objective maps R^4 to R and has two clients; its parameter settings are H = 16, κ = 16, σ = 1, c = 1, µ = 2, and L = 2.Source: §D.4 · pp. 50–51
• Figure 3 reports that Amplified SCAFFOLD maintains the best performance in the FashionMNIST comparison with additional baselines.Source: Figure 3 · p. 51

D.5 CNN Architecture

• The CIFAR-10 CNN has a 64-channel convolutional layer with a 5 × 5 kernel, stride 2, padding 2, and ReLU, followed by a fully connected layer.Source: §D.5 · p. 51

E Additional Experimental Results

• The additional experiments compare four added baselines on Fashion-MNIST and CIFAR-10, and test all nine algorithms on CIFAR-10 under Stochastic Client Availability.The added baselines are FedAdam, FedYogi, FedAvg-M, and Amplified FedAvg with FedProx regularization.Source: E Additional Experimental Results · p. 51

E.1 Additional Baselines

• Amplified SCAFFOLD outperforms the added baselines on Fashion-MNIST and CIFAR-10; FedAdam is competitive on CIFAR-10, while FedYogi and FedAvg-M lag.On Fashion-MNIST, FedAdam and FedYogi are overtaken by Amplified SCAFFOLD and later SCAFFOLD; Amplified FedProx is nearly identical to Amplified FedAvg on both datasets.Source: §E.1 · pp. 51–52, Figure 4 · p. 52
• The additional comparisons place the empirical results alongside convergence guarantees for periodic participation, a setting FedAdam and FedYogi were not designed to address.Source: §E.1 · p. 52

E.2 CIFAR-10 with Stochastic Client Availability

• Under Stochastic Cyclic Availability, Amplified SCAFFOLD outperforms all baselines on CIFAR-10, with FedAdam competitive and FedYogi and FedAvg-M next.The other baselines perform significantly worse, and adding FedProx regularization does not benefit Amplified FedAvg.Source: §E.2 · p. 52

F Extended Comparison with Baselines

• On CIFAR-10 with stochastic cyclic availability, Amplified SCAFFOLD converges fastest.Source: Figure 5 · p. 53
• FedAvg under cyclic participation [8] cannot benefit from local steps in its convergence rate unless participation is regularized.The comparison concerns objectives satisfying L-smoothness and the µ-PL condition.Source: F Extended Comparison with Baselines · pp. 52–53
• The authors identify an apparent error in SCAFFOLD’s analysis: its proof omits a conditioning step, while their analysis uses Jensen’s inequality to handle the conditional expectation.They note this yields a potentially worse dependence on N, while focusing on complexity in ε, κ, σ, and other parameters.Source: F Extended Comparison with Baselines · pp. 53–54

NeurIPS Paper Checklist

• The authors state that experimental details are specified in Sections 5.1 and D, and that supplemental code includes reproduction instructions.Source: NeurIPS Paper Checklist · pp. 56–57
• The authors mark societal-impact discussion as not applicable, describing the work as theoretical optimization research with no direct path to harms beyond those of distributed learning or machine learning generally.Source: NeurIPS Paper Checklist · p. 58
• The paper marks participant-instruction, compensation, and human-subjects review questions as not applicable because it involves no crowdsourcing or human-subjects research.Source: NeurIPS Paper Checklist · p. 60