PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong, Lili Su

arXiv:2609.04763v1cs.LGcs.DCmath.OC

TL;DR

Intermittent, heterogeneous, and non-stationary client availability can bias federated learning, while prior methods often require restrictive assumptions or substantial overhead. The paper proposes FedSWE, which uses adaptive echoing, global averaging, and implicit gossiping; it proves stationary-point convergence and linear speedup in special cases, with experiments supporting its performance under diversified dynamics.

  • Problem

    Heterogeneous and non-stationary client unavailability can introduce significant bias, while prior methods often assume benign stationarity or require substantial memory and computation.

  • Method

    FedSWE adaptively echoes missed local improvements, stabilizes updates with a global moving average, and mixes local updates through implicit gossiping.

  • Results

    FedSWE converges to a stationary point of the global objective, achieves linear speedup in certain special cases, and outperforms state-of-the-art algorithms under diversified non-stationary dynamics.

  • Takeaways & Limitations

    FedSWE provides a computationally and memory-efficient approach to federated learning with heterogeneous and non-stationary client availability.

  • Takeaways & Limitations

    The analysis focuses on independent client unavailability, while extending it to correlated availability remains future work.

Abstract

from arXiv · show

Due to resource constraints or external and internal uncertainties, clients in real-world federated learning systems are often intermittently available edge devices. In highly dynamic environments, the parameter server lacks prior real-time knowledge of clients' availability, making it challenging to adapt traditional federated learning algorithms to be resilient to uncertainties in client availability. If not carefully addressed, complex client availability can introduce significant bias, potentially harming the performance of the trained model. Most prior work either fails to account for non-stationary client availability dynamics or demands significant memory and computational overhead. This paper aims to develop efficient federated learning algorithms that are provably resilient to heterogeneous and non-stationary stochastic client availability. We propose FedSWE, which admits novel algorithmic structures to (i) compensate for missed computations, (ii) stabilize and diffuse the global updates over rounds, and (iii) evenly mix the local updates through implicit gossiping, despite being agnostic to non-stationary dynamics. Compared with the standard FedAvg, FedSWE introduces light additional memory and computation overhead. We show that FedSWE converges to a stationary point of non-convex objectives while achieving the desired linear speedup property in certain special cases. We corroborate our analysis with numerical experiments over diversified client unavailability dynamics on real-world data sets.

1 Introduction

Federated learning trains global models without exposing raw local data, but heterogeneous and non-stationary client availability can bias FedAvg and degrade performance. FedSWE addresses this with lightweight mechanisms for missed computation, update stabilization, and implicit information mixing.

  • Federated learning trains global models without disclosing clients’ raw local data.
  • Heterogeneous availability can bias training toward active clients, while greater availability uncertainty increases performance degradation.
  • Prior work often assumes known availability or benign stationarity, while other approaches require substantial memory or restrictive continuous computation.
  • FedSWE uses adaptive innovation echoing, a global moving average, and implicit gossiping to compensate for missed computation and diffuse updates.
  • FedSWE requires no direct neighbor exchanges and keeps availability dynamics undisclosed to clients and the parameter server.
  • The paper proves convergence with linear speedup in certain cases and evaluates FedSWE under diversified client-unavailability dynamics.

2 Related Work

Related work studies controllable and uncontrollable client availability, asynchronous learning, and memorized updates, but commonly relies on restrictive assumptions or added resources. This paper instead targets availability with unknown dynamics and no server control or prior probability knowledge.

  • Prior client-availability research includes settings where the parameter server can unilaterally determine participating clients.
  • Several methods assume known availability probabilities, server influence, stationarity, balanced participation, or bounded delays and gradients.
  • The paper’s setup assumes neither prior knowledge of availability probabilities nor parameter-server influence over them.
  • Memorizing unavailable clients’ latest gradients can improve numerical performance but demands substantial additional memory.
  • Asynchronous federated learning commonly relies on bounded staleness or bounded gradients for convergence guarantees.

3 Problem Formulation

The paper models each client as independently available with a heterogeneous, unknown, non-stationary probability, allowing occasional absences while requiring nontrivial availability over finite windows. This framework includes several existing participation patterns, but the analysis focuses on independence.

  • A federated learning system uses a parameter server and m clients to minimize an aggregate objective built from local objectives.
  • The availability events are independent across clients and training rounds.
  • The model permits p_i^t to occasionally equal zero while requiring averaged availability over a window of P rounds to remain bounded away from zero.
  • The assumption encompasses uniform, stationary, non-stationary, regularized, and cyclic participation as special cases.
  • The paper leaves correlated availability for future work because its interaction with stochastic gradients complicates theoretical analysis.

4 Heterogeneity and Non-stationarity May Lead to Significant Bias

FedAvg can be substantially biased by heterogeneous client availability, while increasingly non-stationary availability causes marked accuracy degradation. The examples show that availability dynamics affect both expected outputs and train/test performance.

  • Heterogeneous availability probabilities can place FedAvg's expected output far from the unique minimizer x⋆.In the example, x⋆ = (u1 + u2)/2 with u1 = 0 and u2 = 100.
  • Over 10%: both train and test accuracy drop when p = 0.1 and γ increases from 0.1 to 0.5.Here, γ represents the degree of non-stationarity.
  • FedAvg experiences a significant accuracy drop as client availability becomes more non-stationary.The reported degradation applies to both train and test accuracy.

5 Federated Stabilized Agile Weight Re-Equalization (FedSWE)

FedSWE is designed to handle intermittent availability by compensating for missed computation, stabilizing global updates, and balancing local information without requiring availability dynamics to be disclosed. Its design targets lightweight operation while using adaptive echoing, moving-average interpolation, and implicit gossiping.

  • 5 Federated Stabilized Agile Weight Re-Equalization (FedSWE): FedSWE targets O(1) additional computation per client without additional stochastic samples compared with FedAvg.A naive catch-up procedure instead requires computation and samples proportional to missed rounds.
  • 5 Federated Stabilized Agile Weight Re-Equalization (FedSWE): FedSWE combines adaptive innovation echoing, global moving average, and implicit gossiping to address missed computation and residual bias.These structures respectively help clients catch up, stabilize and diffuse updates, and balance information mixing.
  • 5.1 Adaptive innovation echoing: Adaptive innovation echoing multiplies a local innovation by t − τ_i(t), approximately equalizing innovations across active clients.The total number of echoed innovations is the same for all active clients in a given round.
  • 5.2 Global moving average: Global moving average interpolates fresh local updates with the most recent global update, with coefficients determined by active-client count and k.Increasing k produces smoother updates but gives greater weight to the recent global model.
  • 5.2 Global moving average: As k →∞, the global model remains unchanged, preventing effective learning; the paper reports k = Θ(m) as a generally reasonable empirical choice.The interpolation coefficient is neither static nor decaying over rounds, so existing analyses for those settings do not directly apply.
  • 5.3 Implicit gossiping: Implicit gossiping arises when the server postpones multicasting the shared global model, allowing active clients' updates to mix through the server.This introduces staleness, which the paper states is bounded, and avoids direct neighbor exchanges.

6 Convergence Analysis

The convergence analysis uses virtual clients, information mixing, and auxiliary update sequences to control approximation and consensus errors under heterogeneous, non-stationary availability. Under the stated assumptions and learning-rate conditions, FedSWE converges, with linear speedup in a special fully available case and interpolation helping correct availability-induced bias.

  • Augmented system: The analysis introduces k virtual clients that are always available and have zero local objectives, converting the system into an augmented one for convergence analysis.These auxiliary clients do not affect regular-client computation; convergence on the regular population is related to convergence on the augmented population up to rescaling.
  • Information mixing: FedSWE models information diffusion with a doubly stochastic mixing matrix and quantifies consensus through the spectral norm ρ_k over rolling availability windows.When ρ_k < 1, the consensus error decays exponentially; Lemma 9 establishes this condition for k > 0.
  • Auxiliary sequences: The analysis constructs an imaginary update sequence that tracks the actual iterates while making the effects of unequal update strengths easier to analyze.The sequence is analytical only and is never computed by clients.
  • Convergence bounds: Under Assumptions 1–4 and the required learning-rate conditions, the descent, approximation, and convergence results bound FedSWE’s full convergence error.The bound separates approximation and consensus contributions and accounts for gradient divergence and stochastic effects.
  • Linear speedup: In the special case k = Θ(m) with all clients available, the convergence bound becomes O(1/√(smT)), providing the desired linear speedup in local steps and client count.This rate matches established results in the corresponding fully available setting.
  • Bias correction and scaling: A positive interpolation size k can correct availability-induced bias by mixing global models across rounds and enabling information exchange over every Pδ-round window.The analysis also identifies a trade-off: k affects the convergence bound directly and through the spectral norm, with experiments finding k = Θ(m) as a favorable balance.

7 Numerical Experiments

FedSWE is evaluated on SVHN and CIFAR-10 under heterogeneous, non-stationary client unavailability, with experiments examining interpolation, consensus, accuracy, and convergence speed. Across these settings, interpolation improves information diffusion and FedSWE achieves strong performance with light memory.

  • Experimental setup: The experiments use 100 clients on SVHN and CIFAR-10, with clients divided into two groups holding non-overlapping classes and trained under multiple unavailability dynamics.The evaluation includes static and staircase probabilistic trajectories with Pδ > 1, alongside heterogeneous local data distributions.
  • Consensus and interpolation: With interpolation, two clients reach consensus and gradient outputs converge to 0, recovering the global optimum in the scalar visualization.The corresponding no-interpolation visualizations show significant bias and failure to reach consensus.
  • Consensus and interpolation: Without interpolation, clients fail to reach consensus and consensus errors can increase rather than decay under periodic non-stationary availability.Interpolation carries global updates across rounds, allowing clients to correct bias.
  • Performance comparisons: FedSWE with k = 100 produces relatively smooth trajectories and outperforms the baseline algorithms on SVHN and CIFAR-10 under challenging periodic dynamics.On SVHN it matches FedKnown’s peak accuracy with more consistent performance, while on CIFAR-10 it obtains higher accuracy than FedKnown.
  • Effect of interpolation coefficient: Increasing k initially improves convergence and final accuracy, but excessive k causes substantial slowdown and eventually lowers final test accuracy.The number of rounds to reach 40% accuracy shows a significant slowdown after k = m, while accuracy peaks around k = m = 100 on SVHN.
  • Performance comparisons: FedSWE consistently outperforms methods without heavy memory or known statistics, while its interpolation uses O(d) memory compared with O(md) for MIFA and FedVARP.Its performance is competitive with or better than FedAvg with known probability despite unknown availability dynamics.

8 Conclusion

The paper concludes that heterogeneous and non-stationary client unavailability can significantly affect FedAvg, and introduces FedSWE to address this challenge. FedSWE is shown to converge under the proposed setting and performs strongly across diversified dynamics.

  • Conclusion: FedSWE addresses client-unavailability bias through adaptive innovation echoing, global moving-average interpolation, and implicit gossiping of local updates.These mechanisms compensate for missed computation, diffuse updates across rounds, and evenly mix local information.
  • Conclusion: FedSWE provably converges to a stationary point of the global objective and achieves the desired linear speedup property in certain special cases.The conclusion also reports validation against state-of-the-art algorithms under diversified non-stationary dynamics.
  • Conclusion: The experiments validate FedSWE’s superiority over state-of-the-art algorithms under diversified non-stationary client-unavailability dynamics.

Appendices

The appendices provide notation, standard inequalities, intermediate lemmas, and proof steps supporting the paper’s convergence analysis. They also formalize the auxiliary objective, update recursions, and matrix-product arguments.

  • Proof preliminaries: The appendices introduce nomenclature and variable tables, then record common inequalities used throughout the proofs.These include Young’s inequality and a smoothness corollary.
  • Proof preliminaries: The proof development bounds multi-step local computation and applies that bound to descent analysis under the stated assumptions.The appendix derives supporting lemmas using Jensen’s, Cauchy-Schwarz, Young’s, and related inequalities.
  • Auxiliary dynamics: The analysis rewrites one-round innovations and auxiliary updates to characterize the effects of active, inactive, regular, and virtual clients.Virtual clients do not update gradients, enabling the auxiliary global objective and subsequent expectation calculations.

Appendix D. Intermediate Results

Appendix D develops intermediate results for the convergence proof, including induction-based update identities, probability bounds, consensus analysis, and graph-connectivity arguments. These results establish how information propagates through the augmented system over sliding windows.

  • Update identities: Induction arguments establish identities for inactive-client updates and auxiliary variables across successive global rounds.The proof separates active and inactive clients and uses their last-availability times.
  • Probabilistic bounds: The appendix bounds availability-related quantities and derives conditions controlling learning-rate-dependent terms in the intermediate results.The bounds use the assumed availability structure and stated learning-rate restrictions.
  • Consensus analysis: Consensus analysis starts from identical initial virtual-client states and tracks deviations through doubly stochastic mixing matrices and local parameter changes.The matrix representation isolates consensus error from per-round innovations.
  • Graph connectivity: Matrix-product positivity is characterized through directed paths across sequential graph layers, supporting lower bounds on information transfer.The construction uses self-loops and intermediate virtual nodes to connect client states over a sliding window.
  • Graph connectivity: The appendix derives element-wise and expected lower bounds for mixing matrices by considering regular and virtual client subsets.These bounds support the claimed connectivity and diffusion properties of the augmented system.

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

The proof bounds the convergence error by decomposing the update analysis into several auxiliary terms and controlling their asymptotic orders under the stated learning-rate conditions.

  • The convergence proof begins by imposing the learning-rate conditions in (22).
  • The analysis bounds terms (49), (50), and (51) separately before combining them through a telescoping sum.
  • The resulting inequalities rely on the auxiliary lemmas and on a learning-rate constraint involving η_l, η_g, ρ_k, s, L, √P, δ, and var.
  • The proof controls unavailable-duration contributions by expanding their second moment and grouping terms by asymptotic order.

F.1 Convergence error of Algorithm 1

This section derives a convergence-error bound for Algorithm 1 under the prescribed learning-rate conditions and assumptions.

  • Corollary 19 gives a convergence-error result for Algorithm 1 when the learning-rate conditions and Assumptions 1–4 hold.
  • The derivation combines earlier bounds with inequalities justified by Appendix B 2 and Assumption 2.
  • The final expression is obtained by grouping terms according to their asymptotic order.

G.1 Consensus error of Algorithm 1

The section states the consensus-error result for Algorithm 1 and documents the experimental setup used to evaluate client unavailability under heterogeneous data and multiple dynamics.

  • G.1 Consensus error of Algorithm 1: Corollary 20 provides a consensus-error bound for Algorithm 1 under the learning-rate conditions and Assumptions 1–4.
  • G.1 Consensus error of Algorithm 1: The theorem and corollaries are stated to share the same asymptotic order, and the preceding conditions establish the claimed bounds.
  • Experimental setup: The experiments use image data sets with 10 classes, standard augmentation, and gradient clipping with maximum norm 0.5.
  • Client unavailability dynamics: Client unavailability is modeled through heterogeneous base probabilities and stationary, staircase, and sine trajectories.
  • Evaluation protocol: The evaluation measures the first round reaching fractions of each data set’s best test accuracy, with accuracy sampled every 20 global rounds.

H.3 Additional results

Additional experiments examine ablations, staleness, and system-design parameters, finding that FedSWE remains competitive or superior across the reported settings.

  • Ablation: The ablation study evaluates FedSWE with k = 0.
  • Staleness studies: Under sine-trajectory unavailability, FedSWE slightly lags early but reaches final-stage targets in comparable or fewer rounds than FedAvg over active clients on SVHN and CINIC-10.
  • Staleness studies: The CIFAR-10 slowdown in the final-stage comparison remains identified for further investigation.
  • System-design parameters: Across non-stationarity and data-heterogeneity settings, FedSWE outperforms methods without memories or known statistics and surpasses MIFA at α = 0.1 and 1.0.
Loading 2609.04763v1…