Resilience Beyond Stationary Client Unavailability: Unlocking Efficient and Unbiased Federated Learning

Background

• Federated learning supports global-model training without disclosing raw local data and is used in autonomous vehicles, the Internet of Things, and natural language processing.These applications are cited as examples of federated learning’s adoption.Source: §1 · p. 1

Related work

• Prior approaches commonly assume exact availability knowledge or benign stationarity, while gradient memorization methods require memory proportional to the number of clients times the model dimension.Asynchronous methods also assume all or uniformly sampled clients, limiting their applicability to dynamic availability.Source: §1 · p. 2

Availability model

• The paper models client i as available in round t with heterogeneous probability p_i^t governed by unknown, non-stationary dynamics, including occasional zero availability.This generalized model covers constant, client-specific, regularized, and cyclic participation as special cases.Source: §1 · pp. 2–3

Problem

• Heterogeneous and non-stationary client unavailability biases FedAvg and can substantially degrade performance, with uncertainty worsening the degradation.Internal schedules and hardware/software constraints, together with external network and mobility factors, produce complex availability dynamics.Source: §1 · pp. 2–3

Contributions

• FedSWE combines adaptive innovation echoing, global moving averages, and implicit gossiping to recover missed computation, diffuse updates, and correct residual bias without exposing availability dynamics or exchanging direct neighbor information.The paper also establishes convergence with linear speedup in certain special cases and evaluates FedSWE under diversified dynamics on real-world datasets.Source: §1 · p. 3

2.1 Dynamical client availability

• Related work classifies client-availability methods into controllable settings, where the parameter server selects participants, and uncontrollable settings, where availability is arbitrary or client-driven.The literature includes uniform, data-proportional, adaptive, cyclic, importance-based, and arbitrary-availability schemes.Source: §2.1 · pp. 3–4
• Unlike prior availability methods, the paper assumes neither side information or prior knowledge of clients’ availability probabilities nor parameter-server influence over them.Several alternatives instead assume known, globally shared, server-determined, stationary, or periodically balanced availability probabilities.Source: §2.1 · p. 4
• Existing uncontrollable-availability methods impose restrictions including homogeneous Markov dynamics, equal availability over windows, bounded inactive periods or gradients, substantial memory, and non-zero residual errors.These limitations appear across Ribero et al. (2022), Wang and Ji (2022), Crawshaw and Liu (2024), Yang et al. (2022), Gu et al. (2021), Yan et al. (2023), and Wang and Ji (2024).Source: §2.1 · p. 4

2.2 Asynchronous federated learning

• Asynchronous federated-learning guarantees commonly require bounded staleness or bounded stochastic gradients, while this paper claims convergence without bounded gradients or staleness and without non-zero residual terms.Arbitrary-delay distributed SGD can still incur a residual term O(ζ2) under bounded gradients and bounded inter-client heterogeneity.Source: §2.2 · pp. 4–5

Problem setup

• The system comprises a parameter server and m clients minimizing a non-convex objective defined by local data distributions and loss functions.Each local objective is an expectation over client i’s stochastic samples, and d denotes the model dimension.Source: §3 · p. 5

Availability assumption

• Assumption 1 permits individual clients’ availability probabilities to occasionally drop to zero while requiring their averages over suitable P-round windows to remain bounded away from zero.Pδ is defined as the minimum window length satisfying the availability condition for a given δ.Source: §3 · p. 5

Generality

• Under independent availability events across clients and rounds, the assumption encompasses uniform, stationary, and non-stationary lower-bounded availability cases, including Li et al. (2020a), Yang et al. (2022), Wang and Ji (2024), and Xiang et al. (2024, 2025).When Pδ = 1, the window condition reduces to a per-round lower bound on each client’s availability.Source: §3 · p. 6
• For Pδ > 1, the assumption also covers regularized and cyclic participation patterns while not requiring the equal-frequency balance imposed by regularized participation.Cyclic participation can model ordered group availability, such as time-zone-driven patterns; cited works include Wang and Ji (2022), Crawshaw and Liu (2024), and Cho et al. (2023a).Source: §3 · p. 6

Scope and limitation

• The theoretical analysis focuses on independent client unavailability because correlated availability entangles stochastic gradients with availability statistics, although experiments later report improvements under correlated participation.The authors conjecture independence may be mainly a technical convenience and leave correlated unavailability for future analysis.Source: §3 · p. 6

• FedAvg therefore incurs significant bias from both heterogeneous and non-stationary client availability.The section uses two examples to illustrate these effects under classic FedAvg.Source: §4 · p. 7, Figure 3 · p. 7
• FedAvg’s expected output can remain far from the optimum under most heterogeneous client-availability probabilities.With minimizer x⋆ = (u1 + u2)/2, setting u1 = 0 and u2 = 100 illustrates how heterogeneity in p_i affects the expected output.Source: §4 · p. 7
• Over 10% train- and test-accuracy drops occur when p = 0.1 and non-stationarity γ increases from 0.1 to 0.5.The experiment uses 100 clients performing SVHN image classification under FedAvg, with local data distributions following Dirichlet(0.1).Source: Figure 3 · p. 7, §4 · p. 7

5 Federated Stabilized Agile Weight Re-Equalization (FedSWE)

• FedSWE targets computation-light correction of missed client computations, requiring only O(1) additional computation per client and no additional stochastic samples relative to FedAvg.Naive catch-up consumes (t −τi(t) −1)·s additional local SGD updates and samples, whereas FedSWE avoids this overhead.Source: §5 · p. 8
• FedSWE combines adaptive innovation echoing, global moving averaging, and implicit gossiping to catch up missed computation, stabilize global updates, and correct residual bias.The three structures respectively equalize local improvements, diffuse updates across rounds, and balance information mixing.Source: §5 · p. 8

5.1 Adaptive innovation echoing

• Adaptive innovation echoing multiplies a client’s local innovation by (t −τi(t)) so that active clients contribute the same total number of echoed innovations in each round.This approximately equalizes local improvements without requiring clients to perform all missed computations immediately.Source: §5 · p. 7, §5.1 · p. 8

5.2 Global moving average

• Global moving averaging interpolates fresh local updates with the most recent global update using coefficients determined by active-client count and k, smoothing fluctuations caused by dynamic availability.Increasing k emphasizes the recent global update, but k →∞ prevents the global model from updating; k = Θ(m) is generally reasonable empirically.Source: §5.2 · pp. 8–9

5.3 Implicit gossiping

• Implicit gossiping postpones multicasting the global model so active clients exchange updated local models through the server, with bounded staleness and no significant slowdown versus vanilla FedAvg.Unlike standard gossip protocols, FedSWE uses no direct client-client communication.Source: §5.3 · p. 10

6.1 Assumptions

• The analysis assumes Lipschitz local gradients and bounded local-global gradient divergence, with the latter relaxing or matching common heterogeneous-data assumptions.For homogeneous local data, β = ζ = 0.Source: §6.1 · pp. 10–11

6.2 Augmented Learning Systems

• FedSWE is analyzed through k virtual clients with zero objectives and perpetual availability, yielding an auxiliary global objective whose convergence is equivalent to the original system up to rescaling.The auxiliary objectives facilitate analysis only and do not alter regular-client computation.Source: §6.2 · pp. 11–12

6.2.1 Information Mixing on the Augmented Learning System.

• A doubly stochastic mixing matrix models information diffusion, while its rolling-window spectral norm ρ_k quantifies consensus error.The analysis uses the second-largest eigenvalue of the expected squared mixing product over P_δ rounds.Source: §6.2.1 · p. 12

6.3 Imaginary Update Sequence Construction

• An imaginary sequence z_i^t approximates ideal per-round local optimization despite intermittent availability, enabling bounds relating actual and auxiliary client models.It is an analytical device rather than a sequence computed by clients and uses true gradients to avoid coupling availability and stochastic-sample randomness.Source: §6.3 · pp. 12–13
• The availability analysis bounds first and second moments of unavailable duration, recovering 1+1/δ and 2/δ^2 when P_δ = 1.For δ = 1, both bounds are loose by only a constant offset 1; the second-moment bound matches Xiang et al. (2024, Lemma 2).Source: §6.3 · pp. 13–14

6.4 Main Convergence Results

• FedSWE converges under Assumptions 1–4 and suitable learning rates, with approximation and consensus errors explicitly accounting for auxiliary-sequence deviations and implicit gossiping.The consensus analysis requires ρ_k < 1 when k > 0; in the special case k = Θ(m) and full availability, the bound becomes O(1/(smT)) and achieves linear speedup in local steps and clients.Source: §6.4 · pp. 14–17

6.5.1 On the Scaling of Convergence Results

• Increasing k is hypothesized and numerically shown to reduce ρ_k, while the convergence bound may have a sweet spot; empirically, k = Θ(m) best balances speed and test accuracy.As k →∞, ρ_k ≈ 0; larger P_δ produces worse information fusion, and the exact optimal k is analytically unclear.Source: §6.5.1 · pp. 17, 19, Figure 4 · p. 18

6.5.2 Necessity of Interpolation (k > 0) when Pδ > 1

• Interpolation with k > 0 is necessary under Assumption 1, as shown by a counterexample with alternating availability between two client groups.The construction uses quadratic local objectives and clients available only on alternating even or odd rounds.Source: §6.5.2 · p. 19
• The scalar example in Fig. 5 empirically verifies that k > 0 may correct the bias caused by isolated availability cohorts.The analysis also states that Assumption 1 holds under Pδ = 2 and δ = 0.5 for the specified output.Source: §6.5.2 · pp. 19–20
• When Pδ > 1, k > 0 mixes global models across rounds and corrects bias by enabling information exchange among otherwise isolated client cohorts.Clients exchange information in expectation over every sliding window of Pδ rounds when k > 0.Source: §6.5.2 · pp. 19–20
• Without interpolation, non-overlapping client groups cannot exchange models, causing the global objective to alternate between their respective average objectives.The parameter server cannot carry aggregated global updates across rounds under postponed multicasting without interpolation.Source: §6.5.2 · pp. 19–20

6.5.3 Special case when Pδ = 1

• When Pδ = 1, interpolation is optional because clients are not isolated and the information-mixing matrix has strictly positive expected entries in every round.Nevertheless, k > 0 still helps reduce fluctuations in the trajectory of x_t.Source: §6.5.3 · p. 20

7.1 Non-stationary and Heterogeneous Unavailability with Pδ > 1

• The experiments use 100 clients split into two heterogeneous groups with disjoint classes, Dirichlet local-data allocations, and alternating static or staircase availability trajectories.SVHN and CIFAR-10 models are trained for 10,000 and 20,000 rounds, respectively, with 10 local steps per availability and three random seeds.Source: §7.1 · pp. 21–22
• Without interpolation, clients fail to reach consensus and consensus errors can blow up, whereas interpolation diffuses global updates and corrects bias across rounds.Two-client visualizations show that k = 0 fails to reach consensus, while k = 1 enables consensus and drives scalar gradient outputs to 0, recovering the global optimum.Source: §7 · p. 21, §7.1 · p. 25
• FedSWE with k = 100 outperforms all baselines on SVHN and CIFAR-10 under periodic non-stationary unavailability, while using only O(d) memory.It matches FedKnown’s peak SVHN accuracy with more consistent performance and exceeds FedKnown on CIFAR-10.Source: Figure 7 · p. 23, Figure 10 · p. 25, §7.1 · pp. 26–27
• Increasing k initially improves FedSWE’s accuracy and convergence speed but causes slowdown and lower final accuracy when k becomes too large, motivating k = Θ(m).Accuracy peaks around k = m = 100, while the rounds needed to reach 40% accuracy increase substantially after k = m.Source: Figure 8 · p. 24, Figure 9 · p. 24, Figure 11 · p. 26

7.2 Non-stationary and Heterogeneous Unavailability with Pδ = 1

• For Pδ = 1, evaluations cover stationary, staircase, and sine availability trajectories on SVHN, CIFAR-10, and CINIC-10, including correlated client data and availability probabilities.FedSWE retains its outperformance even though the resulting client probabilities are non-independent and outside the theoretical analysis.Source: §7.1 · p. 24, §7.2 · p. 27
• FedSWE consistently outperforms methods without heavy memory or known statistics across the Pδ = 1 tasks, while interpolation improves accuracy on almost all tasks.The only near-exception is stationary SVHN, where interpolation and non-interpolation differ by less than 1%; FedSWE also occasionally beats memory-heavy MIFA and remains competitive with FedAvg using known probabilities.Source: §7.2 · pp. 27–28, Table 2 · p. 28

Conclusion

• FedSWE provably converges to a stationary point of the global objective despite heterogeneous and non-stationary client unavailability.It adaptively echoes clients’ local improvements, interpolates updates across rounds with a global moving average, and evenly diffuses local updates through implicit gossiping.Source: §8 · p. 28
• FedSWE achieves the desired linear speedup property in certain special cases.Source: §8 · p. 28
• Experiments validate FedSWE’s superiority over state-of-the-art algorithms under diversified non-stationary client-availability dynamics.Source: §8 · p. 28
• Future work will investigate relaxing the assumption of independence in client availability.Source: §8 · p. 28

Appendices

• The appendices present proofs of the main results together with supporting lemmas and propositions.Source: Appendices · p. 36

Appendix A. Nomenclature

• Appendix A defines the notation and nomenclature used throughout the proofs, including the lower bound δ on client unavailability.Source: Appendix A · p. 37, Table 3 · p. 37, Table 4 · p. 38

Appendix B. Useful Inequalities

• Appendix B collects common inequalities used in the proofs, including Young’s inequality and a smoothness corollary under Assumption 2.Source: Appendix B · pp. 38–39

Appendix C. Descent Lemma (Lemma 7)

• Appendix C first bounds multi-step local computation and then applies that bound to derive the descent lemma.Source: Appendix C · p. 39

C.1 Multi-step perturbation

• Lemma 15 bounds the multi-step perturbation for each regular client under Assumptions 2 and 3, using Jensen’s inequality, smoothness, and recursive unrolling.Source: §C.1 · pp. 39–41

C.2 Descent lemma

• The descent proof analyzes the auxiliary global objective eF(x) and rewrites the one-round innovation of ¯z using client updates, availability events, and gradient identities.Source: §C.2 · pp. 41–42
• The descent bound combines Lemma 15 with Young’s inequality, Assumption 2, the Appendix B identity, total expectation, and the step-size condition η_lη_g ≤ 1/(8sL).Source: §C.2 · pp. 43, 44, 46

D.1 Bounding local and global dissimilarity

• Proposition 16 bounds local and global dissimilarity under Assumptions 2 and 4.Source: §D.1 · p. 46, Proof of Proposition 16 · p. 47

Proof of Proposition 16

• The proof of Proposition 16 derives its inequality using Assumptions 2 and 4.Source: Proof of Proposition 16 · p. 47

D.2 Weight re-equalization (Proposition 2)

• Proposition 2 is proved by induction, maintaining the re-equalization identity across rounds and separating cases according to prior client availability.Source: §D.2 · p. 47

D.3 Unavailable statistics (Lemma 5)

• The unavailable-statistics analysis bounds the relevant probability terms using AM-GM, tail-integral arguments, and a shorthand constant introduced for subsequent proofs.Source: Proof of Lemma 5 · pp. 48–49

D.4 Auxiliary sequence construction and properties (Proposition 8)

• Proposition 17 constructs auxiliary updates separately for inactive and active clients and establishes their stated relations by induction.Source: §D.4 · pp. 49–50

D.5 Consensus error of the auxiliary sequence

• Lemma 18 analyzes the auxiliary sequence’s consensus error under explicit conditions on η_l and η_lη_g, using doubly stochastic mixing matrices and local parameter changes.Source: §D.5 · pp. 51, 57

D.6 Spectral norm upper bound (Lemma 9)

• The spectral-norm proof represents ordered matrix products through directed paths across successive weighted graphs, including transitions through virtual nodes and self-loops.Source: §D.6 · pp. 57–59
• The argument compares two preceding lower bounds and notes that the resulting expression is decreasing in k, as shown by taking its partial derivative with respect to k.Source: §D.6 · p. 62

Appendix E. Convergence Error of ¯zt (Theorem 11)

• Theorem 11 assumes the learning-rate conditions specified in (22) for analyzing ¯z_t’s convergence error.Source: Appendix E · p. 63
• The proof takes expectation over all randomness, applies Lemma 18 and Proposition 8, and uses a telescoping sum.Source: Appendix E · p. 63
• The analysis separately bounds terms (49), (50), and (51) before combining them in the convergence-error argument.Source: Appendix E · pp. 63, 65
• The step-size argument requires η_lη_g ≤ (1 −ρ^k)/(10sL√Pδ · var).Source: Appendix E · p. 65
• The proof expands the second moment of the unavailable duration to refine the convergence-error bound.Source: Appendix E · p. 66
• Finally, the resulting terms are grouped by asymptotic order, using the convention η_g ≥ 1 and the identity ∇eF(x) = ( m.Source: Appendix E · p. 66

F.1 Convergence error of Algorithm 1

• Corollary 19 states a convergence-error result for x_t under the appendix’s analyzed setting.Source: §F.1 · p. 67
• The convergence-error guarantee requires learning-rate conditions (22) for η_l and η_g, Assumptions 1–4, and T ≥ 1.Source: §F.1 · p. 67

Proof of Corollary 19

• The proof derives an intermediate inequality using Appendix B 2 and Assumption 2.Source: Proof of Corollary 19 · p. 67
• After substituting (52) and applying the learning-rate conditions, the proof obtains the stated bound.Source: Proof of Corollary 19 · p. 67
• The resulting terms are grouped according to their asymptotic order.Source: Proof of Corollary 19 · p. 67

F.2 Convergence rate of Algorithm 1

• Under learning-rate conditions (22), the appendix also states a convergence-rate result involving sδm.Source: §F.2 · p. 68

G.1 Consensus error of Algorithm 1

• Under the learning-rate conditions and Assumptions 1–4, Corollary 20 gives a consensus-error guarantee for Algorithm 1.The result applies for T ≥ 1.Source: §G.1 · p. 68

Proof of Corollary 20

• The proof derives Corollary 20 using Jensen’s inequality and the learning-rate condition, then groups terms by asymptotic order.Source: Proof of Corollary 20 · pp. 68–69

G.2 Orders of the asymptotic rates

• Theorem 11 and Corollaries 19–20 share the same asymptotic order, yielding the stated rate relations in (23), (25), and (26).Source: §G.2 · p. 69

H.1 Experimental setups

• The experiments specify CNN architecture and training in Table 5, use Kaiming initialization, apply augmentation and gradient clipping, and search local and global learning rates after 500 global rounds.Random cropping and gradient clipping with maximum norm 0.5 are applied to all dataset trainings; random horizontal flipping is applied to CIFAR-10 and CINIC-10. Learning rates are searched over the specified grids, with results in Table 6.Source: §H.1 · pp. 69, 71, Table 5 · p. 70, Table 6 · p. 70
• Baseline experiments distinguish FedAvg over active clients from FedAvg over all clients and specify tuned settings for F3AST, gFedAvg, and FedAU.The appendix sets β = 0.001 for F3AST, gFedAvg’s amplification factor to 10 with period 100, and FedAU’s K to 50.Source: §H.1 · p. 70

H.2 Non-stationary client unavailability dynamics

• Client unavailability is modeled as p_ti = p_i · f_i(t), with heterogeneous base probabilities generated from Dirichlet client vectors and class-dependent uniform contributions.The resulting p_i values are heterogeneous across clients, and most are below 0.5 for m = 100 clients.Source: §H.2 · p. 71
• The study compares stationary, staircase, and sine client-unavailability trajectories, using γ = 0.3 and P = 20 for all non-stationary dynamics.Simulations cover base probabilities p_i ∈ {0.1, 0.5, 0.9}, with trajectories and sampled availability visualized in Figure 16.Source: §H.2 · pp. 71–72, Figure 16 · p. 72
• Table 7 measures the first round reaching 1/4, 1/2, 3/4, and 1 of each dataset’s best test accuracy under sine-trajectory unavailability across three random seeds.Mean test accuracy is sampled every 20 global rounds, and “—” denotes targets that an algorithm never reaches.Source: Table 7 · p. 72, §H.2 · p. 72

Additional ablations

• The additional experiments include FedSWE ablations with k = 0 and studies varying the non-stationarity parameter γ and Dirichlet parameter α.Results for γ and α are reported in Tables 8 and 9.Source: §H.3 · pp. 72–73, Table 8 · p. 73, Table 9 · p. 73

Staleness studies

• FedSWE reaches target accuracy in a comparable or lower number of final-stage rounds than FedAvg on SVHN and CINIC-10, although it slows on CIFAR-10.During the first three quarters, FedSWE slightly lags behind FedAvg over active clients; overall, the staleness from implicit gossiping is numerically mild.Source: §H.3 · p. 73

Impact of system-design parameters

• As data heterogeneity increases, FedSWE attains the best training and test accuracies versus methods without heavy memory or known statistics, and outperforms MIFA at α = 0.1 and 1.0.These results support FedSWE’s practicality; the experiments vary non-stationarity γ and Dirichlet data-heterogeneity parameter α under a sine trajectory.Source: §H.3 · p. 73