Conceptio › Archive › arXiv CS

arXiv CSopen access

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

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

Journal of Machine Learning Research 27 (2026) 1-73

Submitted 5/25; Published 8/26

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

arXiv:2609.04763v1 [cs.LG] 4 Sep 2026

Ming Xiang1 Stratis Ioannidis1 Edmund Yeh1 Carlee Joe-Wong2 Lili Su1 1 2

[email protected] [email protected] [email protected] [email protected] [email protected]

Northeastern University, Boston, MA USA; Carnegie Mellon University, Pittsburgh, PA USA.

Editor: Zhaoran Wang

Abstract 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. Keywords: federated learning, non-convex optimization, heterogeneous data, client unavailability, fault-tolerance

1 Introduction Federated learning is a distributed machine learning framework that enables training global models without disclosing raw local data (McMahan et al., 2017; Kairouz et al., 2021). It has been adopted in commercial applications such as autonomous vehicles (Chen et al., 2021; Zeng et al., 2022; Peng et al., 2023), internet of things (Nguyen et al., 2019), and natural language processing (Yang et al., 2018; Ramaswamy et al., 2019). ∗. A preliminary version of this work (Xiang et al., 2024) was presented at the 38th Annual Conference on Neural Information Processing Systems, Vancouver, Canada. ©2026 Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong and Lili Su. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v27/25-1020.html.

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Heterogeneous data and massive client populations are two of the defining characteristics of cross-device federated learning systems (McMahan et al., 2017; Kairouz et al., 2021; McLaughlin and Su, 2024). Despite intensive efforts (McMahan et al., 2017; Li et al., 2020b; Yuan and Li, 2022; Ruan et al., 2021; Kairouz et al., 2021), several key challenges that arise from the involvement of large-scale client populations are often overlooked in the existing literature (Perazzone et al., 2022). One of the primary hurdles is the issue of intermittent client unavailability. Intuitively, more active clients drive the global model to their local optima, biasing the training. In addition, the higher the uncertainty in client unavailability, the larger the performance degradation. Concrete examples that confirm these intuitions can be found in Section 4. Client unavailability issues can arise from internal factors such as different working schedules and heterogeneous hardware/software constraints. External factors, such as poor network coverage and frequent handovers of base stations due to fast movements, only exacerbate these problems (Tse and Viswanath, 2005; Wen et al., 2024; Ye et al., 2022; Bonawitz et al., 2019; Kairouz et al., 2021). The intricate interplay of internal and external factors results in non-stationary and heterogeneous client unavailability. There is a recent surge in the study of client unavailability (Li et al., 2020a; Yang et al., 2022; Wang and Ji, 2022, 2024; Cho et al., 2023a; Gu et al., 2021; Yan et al., 2023; Crawshaw and Liu, 2024). Despite their solid foundation in this direction, most prior work either assumes exact knowledge of the clients’ availability or requires their dynamics to be benignly stationary (McMahan et al., 2017; Li et al., 2020a; Perazzone et al., 2022; Wang and Ji, 2022, 2024; Crawshaw and Liu, 2024). The non-stationarity in client unavailability remains largely underexplored. A related line of work studies asynchronous federated learning wherein clients are vulnerable to delays in message transmission, and the reported model updates may be stale (Xie et al., 2019; Nguyen et al., 2022; Toghani and Uribe, 2022; Koloskova et al., 2022). However, the proposed methods assume the availability of all clients or uniformly sampled clients, making them infeasible for dynamic and complex client availability in practice. A handful of other works (Gu et al., 2021; Jhunjhunwala et al., 2022; Yan et al., 2023) memorize the old gradients of unavailable clients. However, the added memory burdens the federated learning system with substantial memory proportional to the product of the number of clients and the model dimension. We adopt the commonly-used stochastic client unavailability model (McMahan et al., 2017; Wang and Ji, 2022; Jhunjhunwala et al., 2022; Perazzone et al., 2022; Wang and Ji, 2024), p1t Parameter p2t Server where each client i is available for federated learnp3t ing training with probability pti in round t. The p4t p5t t pi ’s are heterogeneous across clients and are subject to unknown and non-stationary dynamics. An example can be found in Fig. 1. (Xiang et al., 2025) marks our first move towards understand- Figure 1: An illustration of heterogeneous and non-stationary availability. ing heterogeneity and non-stationarity in pti ’s but t focuses on a significantly simpler problem where pi ’s are used to describe the uplink communication failures—it requires that clients be capable of continuous local optimization regardless of failures. In addition, it imposes the assumption that pti ≥ δ, where δ > 0 is an absolute constant. 2

Efficient and Unbiased Federated Learning

Relaxing the requirement of continuous local computation, a preliminary version of this work (Xiang et al., 2024) studies client unavailability yet still imposes the technical assumption that pti ≥ δ. In this extended version, we generalize the dynamics of pti by allowing it to take zero values occasionally. Our generalized setup is motivated by the real-world scenario in which clients located in different geographical regions may experience availability issues due to time zone differences, naturally causing pti ’s to drop to zero from time to time (Zhu et al., 2022). When clients participate independently, our generalized model of pti covers some popular existing models as special cases such as pti = p (Li et al., 2020a; Yang et al., 2022), pti = pi (Wang and Ji, 2024), regularized participation (Wang and Ji, 2022; Crawshaw and Liu, 2024) and cyclic participation (Cho et al., 2023a). Details can be found in Section 3. Contributions. Our contributions are four-fold: • We demonstrate in Section 4, using concrete examples in the context of FedAvg - the most widely adopted federated learning algorithm, that both heterogeneity and non-stationarity of pti can result in bias and thus significant performance degradation of FedAvg. • We propose a computational and memory-efficient algorithm FedSWE in Section 5. At a high level, the design of FedSWE introduces three novel algorithmic components: (i) adaptive innovation echoing, which helps clients catch up on missed computation; (ii) global moving average, which stabilizes and diffuses the global updates over rounds; (iii) implicit gossiping, which facilitates a balanced information mixture through implicit client-client gossip, ultimately correcting residual bias. Notably, no direct neighbor information exchanges are involved, and the client unavailability dynamics remain undisclosed to all clients and the parameter server. • In Section 6, we show the convergence of FedSWE, which exhibits the desired linear speedup property in certain special cases. • In Section 7, we validate our analysis with numerical experiments over diversified client unavailability dynamics on real-world data sets.

2 Related Work 2.1 Dynamical client availability There is a recent surge of efforts to study client availability (Ruan et al., 2021; Ribero et al., 2022; Chen et al., 2022; Jhunjhunwala et al., 2022; Wang and Ji, 2022, 2024; Perazzone et al., 2022; Xiang et al., 2023; Crawshaw and Liu, 2024), which can be roughly classified into two categories depending on whether the parameter server can unilaterally determine the participating clients. (i) Controllable availability. Earlier research (McMahan et al., 2017; Li et al., 2020b; Jhunjhunwala et al., 2022) presumes that, in each round, the parameter server could recruit a small set of clients either uniformly at random or in proportion to the volume of local data held by clients. More recently, Cho et al. (2022) design adaptive and non-uniform client sampling to accelerate learning convergence, albeit at the cost of introducing a non-zero residual error. In another work, Cho et al. (2023a) study the convergence of FedAvg with cyclic client participation. Yet, the set of available clients is sampled uniformly at random per cyclic round and is chosen unilaterally and deliberately by the parameter server. Perazzone 3

Xiang, Ioannidis, Yeh, Joe-Wong and Su

et al. (2022) consider heterogeneous and time-varying response rates pti under the assumptions that pti is known a priori and that the stochastic gradients are bounded in expectation. Furthermore, the values of pti are determined by the parameter server by solving a stochastic optimization problem. Chen et al. (2022) propose a client sampling scheme wherein only the clients with the most “important” updates communicate back to the parameter server. This sampling method can achieve performance comparable to that of full client participation, provided that pti is globally known to both the parameter server and the clients. Departing from this line of literature, our setup neither assumes any side information or prior knowledge of the probability pti nor assumes that the parameter server has any influence on pti ’s. (ii) Uncontrollable availability. There is a handful of work on building resilience against arbitrary client availability (Ribero et al., 2022; Wang and Ji, 2022; Yan et al., 2023; Gu et al., 2021; Yang et al., 2022; Wang and Ji, 2024; Crawshaw and Liu, 2024). Ribero et al. (2022) consider random client availability whose underlying probabilities are also heterogeneous and time-varying with unknown dynamics. However, the underlying dynamics of pti ’s in (Ribero et al., 2022) are assumed to follow a homogeneous Markov chain. Wang and Ji (2022) propose a generalized FedAvg that amplifies parameter updates every P rounds for some carefully tuned P . Despite its elegant unified analysis and potential to accommodate non-independent unavailability dynamics, to reach a stationary point, pti needs to satisfy some assumptions to ensure roughly equal availability of all clients over every P rounds. Sharing a similar spirit, Crawshaw and Liu (2024) propose a SCAFFOLD variant that amplifies global parameter and local gradient updates every P round. In spite of its communication efficiency, ability for correlated participation, and resilience to data heterogeneity, the rolling average of pti over every P round is assumed to be the same constant for all clients. Yang et al. (2022) analyze a setting where clients participate in the training at their will. Yet, their convergence is shown to be up to a non-zero residual error. The algorithms proposed in (Gu et al., 2021; Yan et al., 2023) share the same idea of using the memorized latest gradient updates from unavailable clients for global aggregation. Despite superior numerical performance, both algorithms demand a substantial amount of additional memory (Wang and Ji, 2024). For non-convex objectives, both (Yan et al., 2023) and (Gu et al., 2021) require an absolute bounded inactive period, and share similar technical assumptions such as almost surely bounded stochastic gradients (Yan et al., 2023) or almost surely bounded gradient noise (Gu et al., 2021). Though bounded inactive periods are relevant for applications wherein the sensors wake up on a periodic schedule, this assumption is not satisfied even for the simple stochastic setting when clients are selected uniformly at random. A recent work (Wang and Ji, 2024) considers unknown heterogeneous pi ’s yet assumes pi ’s are fixed over time. Another concurrent work (Sun et al., 2025) characterizes periodic client participation through the lens of the Markov chain. In spite of its resilience to non-uniform and correlated availability, pti ’s are also assumed to be stationary over the window of participation. 2.2 Asynchronous federated learning Another related line of work is asynchronous federated learning. To the best of our knowledge, Xie et al. (2019) initialize the study of asynchronous federated learning, wherein the parameter server adjusts the global model every time it receives an update from a client. Convergence is shown under some technical assumptions such as weakly-convex global objectives, bounded 4

Efficient and Unbiased Federated Learning

delay, and bounded stochastic gradients. Nguyen et al. (2022) propose FedBuff, which uses additional memory to buffer asynchronous aggregation to achieve scalability and privacy. Convergence is shown under bounded gradients and bounded staleness assumptions. In fact, most convergence guarantees in the asynchronous federated learning literature rely on bounded staleness (Xie et al., 2019; Nguyen et al., 2022; Toghani and Uribe, 2022; Koloskova et al., 2022), or bounded gradients (Xie et al., 2019; Nguyen et al., 2022; Koloskova et al., 2022). Recently, arbitrary delay is considered in the context of distributed SGD with bounded stochastic gradients and (0, ζ)-bounded inter-client heterogeneity (Mishchenko et al., 2022) (see Assumption 4 therein for the definition). The convergence suffers from a non-zero residual term O(ζ 2 ). In contrast, our convergence guarantee is free from non-zero residual terms and does not require gradients or staleness to be bounded. Notations. Let ∥v∥2 , ∥A∥F and λ2 (B) define the l2 norm of a vector v, the Frobenius norm of a matrix A, and the second largest eigenvalue of a squared matrix B, respectively. Denote F t the sigma algebra generated by randomness up to round t, Rd a d-dimensional vector space, and [m] a set {k : k ∈ N, 1 ≤ k ≤ m]}. 1{E} is an indicator function of an event E, i.e., 1{E} = 1 when event E occurs, but 1{E} = 0 otherwise. For two functions f (n) and g(n), we have f (n) ≲ g(n), if there exists a constant co > 0 and an integer no ∈ N such that f (n) ≤ co g(n) for all n ≥ no , while f (n) ≍ g(n), if there exists a constant cθ > 0 and an integer nθ ∈ N such that f (n) = cθ g(n) for all n ≥ nθ .

3 Problem Formulation A federated learning system consists of a parameter server and m clients to collaboratively minimize m

1 X min F (x) = Fi (x), m x∈Rd

(1)

i=1

where Fi (x) ≜ Eξi ∼Di [ℓi (x; ξi )] is the non-convex local objective, Di is the local distribution, ξi is a stochastic sample that client i has access to, ℓi is the local loss function, and d is the model dimension. We use Assumption 1 to formally describe the non-stationary and heterogeneous client availability that we consider in this paper. Let At denote the set of available clients, and T be the number of total training rounds. Assumption 1. Define pti ≜ E[1{i∈At } ]. For any given δ ∈ (0, 1], there exists a window of P rounds such that 1 P

(n+1)P −1

pti ≥ δ, ∀n ∈ N,

(2)

t=nP

where the events {i ∈ At } are independent across clients i and across rounds t. Let Pδ be the collection of all P ’s that satisfy (2), and Pδ ≜ min Pδ . Assumption 1 requires that the averaged pti ’s over P consecutive rounds are non-trivially lower bounded away from zero while allowing pti ’s occasionally drop to zeros. Note that if (2) 5

Xiang, Ioannidis, Yeh, Joe-Wong and Su

holds for some P0 , then it must also hold for c · P0 , where c ∈ N. Hence, we will focus on Pδ to eliminate ambiguity. Next, we elaborate on the generality of Assumption 1 in Remark 1. Remark 1. Within the context that {i ∈ At } are independent across agents i and across rounds t, Assumption 1 generalizes many existing client availability assumptions. • When Pδ = 1, (2) reduces to pti ≥ δ, which encompasses the cases of uniform availability pti = p (Li et al., 2020a; Yang et al., 2022), stationary availability pti = pi ≥ mini∈[m] pi (Wang and Ji, 2024) and non-stationary availability pti ≥ δ (Xiang et al., 2024, 2025). • When Pδ > 1, Assumption 1 encompasses the following dynamics: (i) Regularized participation (Wang and Ji, 2022; Crawshaw and Liu, 2024): There exists µt0 ≥ 1/Pδ such that 1 Pδ

(n+1)Pδ −1

P i ∈ At = µn , for i ∈ [m] and ∀n ∈ N,

(3)

t=nPδ

where Pδ is some carefully chosen integer. (3) says that every client becomes available equally often within each window. By contrast, our Assumption 1 does not require such “balance” in µn . On the other hand, outside the restriction that {i ∈ At } are independent across i and t, the regularized participation assumption (Wang and Ji, 2022; Crawshaw and Liu, 2024) allows clients’ participation to be correlated within Pδ consecutive rounds. (ii) Cyclic participation (Cho et al., 2023a; Crawshaw and Liu, 2024): Suppose that the m clients can be equally partitioned into K̄ groups. Denote the group index of client i as G(i) ∈ {1, · · · , K̄}. In each round t, pti is determined as ( p, if (t mod K̄) = G(i); pti = (4) 0, otherwise. Cyclic participation characterizes the scenario where client groups become available in order. For example, if clients are populated in different time zones around the globe, their availability naturally exhibits cyclic patterns due to time differences. On the other hand, outside the restriction that {i ∈ At } are independent across i and t, cyclic participation also admits correlated participation. Sun et al. (2025) generalize (4) by allowing clients to have different pi ’s rather than a homogeneous p. Independent client unavailability is a widely adopted assumption in federated learning research (Li et al., 2020a,b; Karimireddy et al., 2020; Yang et al., 2021, 2022; Wang and Ji, 2024), and it is also the focus of this paper. We aim to extend our approach to address correlated client unavailability in future work. Analyzing non-independent availability with uncertain probabilistic trajectories in Assumption 1 is in general challenging. For example, the involved entanglement of stochastic gradient and availability statistics fundamentally complicates the theoretical analysis. We conjecture that independent participation may be only for the technical convenience of our analysis. Our experiments in Section 7 suggest that the proposed algorithms offer notable improvements even when the clients’ participation is correlated. 6

Efficient and Unbiased Federated Learning

4 Heterogeneity and Non-stationarity May Lead to Significant Bias 50

0.8

0.6

0.4

0.2

||xoutput x ||

1.0

In this section, we illustrate the impacts of heterogeneity and non-stationarity of client availability under the classic FedAvg. We use two examples to showcase the significant bias incurred. Example 1 (Heterogeneity). Suppose that m = 2 and pti = pi for i ∈ [2]. Let Fi (x) ≜ ∥x − ui ∥22 /2, where x, ui ∈ R. The global objective (1) is 1 F (x) = (∥x − u1 ∥22 + ∥x − u2 ∥22 ), 2

0.00.0

(5)

0.2

0.4

0.6

0.8

1.0

Figure 2: Let xoutput ≜ limt→∞ E xt .

Under most of the choices of p1 , p2 , xoutput is far from x∗ .

with unique minimizer x⋆ = (u1 + u2 )/2. Let u1 = 0 and u2 = 100. Fig. 2 illustrates how the heterogeneity in pi affects the expected output of FedAvg.

82% 80% 78% 75% 73% 70% 68%

Test Acc

Train Acc

Example 2 (Non-stationarity). In Fig. 3, a total of m = 100 clients perform an image classification task on the SVHN data set (Netzer et al., 2011) under the FedAvg algorithm, whose local data set distribution follows Dirichlet(0.1) (Hsu et al., 2019). Clients become available with probability pti = p · [γ · sin(0.1π · t) + (1 − γ)], ∀i ∈ [m]. The hyperparameter details are deferred to Appendix H. Observations can be found in the caption.

p = 0.1 p = 0.3 p = 0.5 p = 1.0 = 0.1

= 0.2 = 0.3 Non-stationary Degree

= 0.5

(a) Train accuracy.

82% 80% 78% 75% 73% 70% 68%

p = 0.1 p = 0.3 p = 0.5 p = 1.0 = 0.1

= 0.2 = 0.3 Non-stationary Degree

= 0.5

(b) Test accuracy

Figure 3: Train and test accuracy results in percentage (%). In particular, the parameter γ signifies the degree of non-stationary. Notice that, as the client availability becomes more non-stationary (a larger γ), FedAvg experiences a significant drop in accuracy. For example, both the train and test accuracies drop by over 10% when p = 0.1, and γ increases from 0.1 to 0.5.

5 Federated Stabilized Agile Weight Re-Equalization (FedSWE) In order to minimize (1), it is natural to have the entire client population perform the same number of local updates and mix these updates carefully to ensure that they are weighted equally. However, due to intermittent availability, clients may miss computations in certain rounds and, as a result of the heterogeneity in pti , are unable to contribute an equal number of local updates. An alternative approach to equalizing the number of local updates is to have clients catch up by performing their missed local computations immediately when they 7

Xiang, Ioannidis, Yeh, Joe-Wong and Su

become available. However, this approach requires a daunting amount of resources and may not be feasible due to hardware or software constraints. Formally, recall that At is the set of ′ available clients at time t. Let τi (t) := {t′ : t′ < t and i ∈ At } denote the most recent (with respect to time t) round that client i is available. Compared with standard FedAvg, the naive “catch-up” procedure will consume (t − τi (t) − 1) · s local stochastic gradient descent updates and (t − τi (t) − 1) additional stochastic samples, where s is the number of local updates per global round when a client is available in standard FedAvg. In this work, we target computation-light algorithms that, compared with FedAvg, adjust local updates by O(1) additional computation per client without additional stochastic samples. We propose Federated Stabilized Agile Weight Re-Equalization (FedSWE), which is formally described in Algorithm 1. It involves three novel algorithmic structures: adaptive innovation echoing, global moving average and implicit gossiping. At a high level, these novel algorithmic structures (i) help clients catch up on the missed computation, (ii) stabilize and diffuse the global updates over rounds by interpolating between the fresh local updates and the most recent global update, and (iii) enable a balanced information mixture through implicit client-client gossip, ultimately correcting the remaining bias. In Algorithm 1, each client keeps two local variables xi and τi , along with a few auxiliary variables used in updating xi and τi . The server keeps tracking the most recent global update xt . The algorithm’s inputs are rather standard: total training rounds T , local and global learning rates ηl and ηg , the number of local updates per round s, the interpolation coefficient k, and the initial model x0 . In each round t, in lines 6-10, similar to FedAvg, an available client i ∈ At performs s steps of stochastic gradient descent on its local model xti , (t,k) (t,k) where ∇ℓi (·; ξi ) is the stochastic gradient of sample ξi . Next, we describe the novel algorithmic structures used in FedSWE. 5.1 Adaptive innovation echoing (t,0)

Departing from FedAvg, wherein the local estimate xti is updated as xt† − ηg Gti . i ← xi FedSWE “echos” the local innovation Gti by multiplying it by (t − τi (t)) (lines 12-13). Intuitively, this simple echoing helps approximately equalize the number of local improvements, as formally stated in Proposition 2. It says that the total number of innovations echoed is the same for all active clients for any given round. Proposition 2. For any R ∈ N, if i ∈ AR−1 , then

PR−1 t=0

1{i∈At } (t − τi (t)) = R.

5.2 Global moving average When client availability is highly dynamic, the set of active clients At can vary greatly from round to round, leading to unsteady global updates. Our extensive experiments in Section 7.1 confirm that most of the state-of-the-art methods experience significant fluctuations during training. The early version of our algorithm (i.e., Algorithm 1 with k = 0) presented in the conference paper (Xiang et al., 2024) is no exception and has a similar level of variability. k > 0, Algorithm 1 adaptively interpolates between the fresh local updates P When t† t i∈At xi and the most recent global update x in line 17, where the interpolation coefficients are jointly decided by the number of active clients At and the parameter k. For ease of 8

Efficient and Unbiased Federated Learning

Algorithm 1: Federated Stabilized Agile Weight Re-Equalization (FedSWE) 1 Inputs: T , s, k, ηl , ηg , x0 . 2 ⋆ Initializations. 3 for i ∈ [m] do x0i ← x0 and τi (0) ← −1 ; 4 for t = 0, · · · , T − 1 do 5 ⋆ On the available clients. 6 for i ∈ At do (t,0) 7 xi ← xti ; 8 for k = 0, · · · , s − 1 do (t,k+1) (t,k) (t,k) (t,k) 9 xi ← xi − ηl ∇ℓi (xi ; ξi ) ; 10 end (t,0)

(t,s)

▷ Client local SGD

Gti ← xi

12 13 14 15 16

(t,0) xt† − ηg (t − τi (t))Gti ; ▷ Client adaptive innovation echoing (Section 5.1) i ← xi τi (t + 1) ← t ; ▷ Client round index counter update (Section 5.1) t† Report xi to the parameter server

− xi

;

end ⋆ On the parameter server. P t† t ; xt+1 ← |At1|+k x + kx t i∈A i

▷ Global moving average (Section 5.2)

18 Multicast xt+1 to clients i ∈ At ; 19 ⋆ On all clients. 20 for i ∈ [m] do 21 if i ∈ At then 22 xt+1 ← xt+1 ; i 23 else 24 xt+1 ← xti ; i 25 τi (t + 1) ← τi (t); 26 end 27 end

▷ Postponed multicast (Section 5.3)

exposition, we restate the interpolation as follows: x

t+1

X t† 1 1 = t xi + 1 − t xt . |A | + k |A | + k t

(6)

i∈A

Intuitively, as k increases, the interpolation produces a smoother curve by emphasizing more on the most recent global update. However, the budget for increasing k is not unlimited. In particular, when k → ∞, the global update xt duplicates the global model from the last round, preventing effective learning from occurring. Specifically, unrolling the recursion, we have xt+1 = x0 for all t ≥ 0, i.e., the global model xt is not updated at all. In Section 7, we will show that k = Θ(m) is generally a reasonable empirical choice. We conjecture that discrete k’s are only necessary for the technical convenience of our analysis, and leave it as a future work on how to analyze continuous k theoretically. 9

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Furthermore, we want to note that (6) is closely related to global momentum and model exponential moving average, yet the interpolation coefficient is neither static nor decaying over rounds. Therefore, the existing theoretical analysis for momentum with static coefficient (Reddi et al., 2019; Li et al., 2023; Cheng et al., 2024) and model exponential moving average with decaying coefficient (Ahn and Cutkosky, 2024) is inapplicable to our problem. Beyond stabilizing training, we will show in Section 6 that interpolation is also necessary to strengthen global information diffusion across rounds. Details can be found therein. 5.3 Implicit gossiping In FedSWE, the parameter server does not send the most recent global model to the active clients at the beginning of a global round. Instead, the parameter server aggregates the t+1 to all active locally updated models xt† i through (6) and sends the new global model x clients At (lines 20-26). By postponing multicasting the shared global model, the active clients in At implicitly gossip their updated local models with each other through the parameter server (Xiang et al., 2023, 2024). Though the postponed multicasting brings in staleness, we will show that the staleness is bounded in Lemma 5. In addition, our empirical results (Table 7 in Appendix H) suggest that there is no significant slowdown when compared to vanilla FedAvg. Gossip-type algorithms were originally proposed for peer-to-peer networks and are wellknown for their agility to communication failures and asynchronous information exchange in achieving average consensus (DeGroot, 1974; Boyd et al., 2006; Kempe et al., 2003; Hajnal and Bartlett, 1958; Lynch, 1996; Nedic and Ozdaglar, 2009). Intuitively, the clients’ local estimates are eventually equally weighted in the final algorithm output. Note that, departing from the standard gossiping protocols therein (Kempe et al., 2003; Shah et al., 2009), information exchange in FedSWE does not involve direct client-client communication.

6 Convergence Analysis 6.1 Assumptions In this section, we analyze the convergence of FedSWE. We start by stating regulatory assumptions that are common in federated learning analysis (Li et al., 2020a; Wang et al., 2020; Karimireddy et al., 2020). Assumption 2. Each local objective function ∇Fi (x) is L-Lipschitz, i.e., ∥∇Fi (x1 ) − ∇Fi (x2 )∥2 ≤ L ∥x1 − x2 ∥2 , ∀x1 , x2 , and ∀ i ∈ [m]. Assumption 3. Stochastic gradients ∇ℓi (x; ξ) are unbiased with bounded variance, i.e., h i E [∇ℓi (x; ξ) | x] = ∇Fi (x) and E ∥∇ℓi (x; ξ) − ∇Fi (x)∥22 | x ≤ σ 2 , ∀ i ∈ [m]. Assumption 4. The divergence between local and global gradients is bounded for β, ζ ≥ 0 such that m 1 X ∥∇Fi (x) − ∇F (x)∥22 ≤ β 2 ∥∇F (x)∥22 + ζ 2 . (7) m i=1

Efficient and Unbiased Federated Learning

Table 1: Popular variant assumptions on gradient dissimilarity. Bounded Gradient Dissimilarity References maxx ∥∇Fi (x)∥22 ≤ ζ 2 , ∀ i ∈ [m]

(Li et al., 2020b; Yu et al., 2019b; Cho et al., 2022, 2023b; Yan et al., 2023).

2 2 1 Pm 2 i=1 ∥∇Fi (x)∥2 ≤ β ∥∇F (x)∥2 m

(Li et al., 2019, 2020a) (Yu et al., 2019a; Wang et al., 2019; Huang et al., 2022; Karimireddy et al., 2022; Wang and Ji, 2022, 2024; Yang et al., 2022; Wang et al., 2022; Allouah et al., 2023).

2 2 i=1 ∥∇Fi (x) − ∇F (x)∥2 ≤ ζ

1 Pm

2 2 1 Pm 2 2 i=1 ∥∇Fi (x)∥2 ≤ β ∥∇F (x)∥2 + ζ m

(Karimireddy et al., 2020; Wang et al., 2020; Wang and Joshi, 2021; Gu et al., 2021; Yuan and Li, 2022).

When the local data sets are homogeneous, ∇Fi (x) = ∇F (x) holds for any client i ∈ R, resulting in β = ζ = 0. Assumption 4 and its variants in Table 1 are often referred to as bounded gradient divergence to characterize data heterogeneity across clients. It can be easily checked that our Assumption 4 is more relaxed or equivalent to the variants therein. 6.2 Augmented Learning Systems For ease of analysis, it is technically convenient to consider an augmented learning system with k virtual clients, and to show convergence of x through this system. Observing that the update in (6) can be rewritten as xt+1 =

m+k X X t† 1 1 x + xt . i t t |A | + k |A | + k t i=m+1

i∈A

More specifically, we construct the augmented learning system as follows: let V = {m + t 1, · · · , m + k} with each element representing a virtual client; it holds that xt† i = x for each i ∈ V. Let Fi (x) ≜ 0 for i ∈ V and ∀x ∈ Rd . It is easy to see that, with this local objective function, we have X t† 1 xt+1 = t xi , |A | + k t i∈A ∪V

In addition, unlike regular clients in [m], each virtual client is always available, i.e., τi (t) = t−1 for i ∈ V. To distinguish, let R = [m] denote the regular clients and M = m + k. We define an auxiliary global objective function Fe as in (8): m 1 X m 1 X 1 X Fe(x) ≜ Fi (x) = Fi (x) = Fi (x) = F (x). (8) M M M m M i∈R∪V

i∈R

Note that the auxiliary local and global objectives are only used to facilitate our analysis of Algorithm 1; they do not affect the computation at the regular clients. Hence, to show 11

Xiang, Ioannidis, Yeh, Joe-Wong and Su

that x converges to a stationary point of F (·) with k > 0 on the regular client population R is equivalent to showing that x converges to Fe(x) with k = 0 on the augmented client population R ∪ V up to rescaling. The latter case can be analyzed by adapting our road map from the conference version (Xiang et al., 2024), but with non-trivial characterizations to account for the generalized Assumption 1. 6.2.1 Information Mixing on the Augmented Learning System. We construct a doubly stochastic information mixing matrix W (t) in (9) that characterizes the information diffusion in FedSWE.  1   |At |+k , (t) Wij ≜ 1,   0,

if {i, j ∈ At ∪ V}; if {i = j} and {i ∈ R \ At }; otherwise.

(9)

Q(n+1)P −1 Let W (n,Pδ ) ≜ t=nPδ δ W (t) and ρ(n, k) ≜ λ2 (E[(W (n,Pδ ) )2 ]), where λ2 (·) denotes the second largest eigenvalue, n ∈ Z+ , J = 11⊤ /M , and ρk ≜ maxn ρ(n, k). The information mixing errors, i.e., consensus errors, are quantified through Lemma 3. d×M , it Lemma 3. (Boyd et al., 2005; 2Koloskova et al., 22020) For any matrix B ∈ R (n,P ) δ − J ∥ ] ≤ ρ ∥B(I − J)∥ , where the expectation is taken w.r.t. holds that EW [∥B W k F F randomness in W matrices.

6.3 Imaginary Update Sequence Construction Directly analyzing the evolution of xt and xti is challenging due to the fact that different clients update at different rounds, and that different active clients echo their local innovation Gti (line 12 in Algorithm 1) with different strength (t − τi ). As such, we construct an imaginary update sequence zit for client i ∈ [m], whose evolution is closely coupled with xt and xti yet is easier to analyze. Note that the imaginary update sequence is never actually computed by clients but acts as a necessary tool in building up the analysis. Definition 4. The auxiliary sequence {zit } of client i ∈ R ∪ V is defined as zit

≜

( xti ,

∀ i ∈ V;

τ (t)+1 xti − ηl ηg s(t − τi (t) − 1)∇Fi (xi i ),

∀ i ∈ R.

(10)

We know that the virtual clients in V are (i) always available and (ii) with zero-valued local gradient updates since their local models are duplicates of the global model from the immediate previous round. Therefore, (10) can be simplified as (11) by using the convention τ (t)+1 that ∇Fi (xi i ) = 0 for any virtual client i ∈ V in any round t ∈ [T ]: τ (t)+1

zit ≜ xti − ηl ηg s(t − τi (t) − 1)∇Fi (xi i 12

), ∀ i ∈ R ∪ V.

(11)

Efficient and Unbiased Federated Learning

When i ∈ At−1 , the iterate of zi is a bit more involved:   P (12.a) (12.b) j∈At−1  t−1 t−1  t−1 t−1 zit = xti = zj + (xj − zj ) −ηg (t − 1 − τj (t − 1))Gj  t−1 |A | {z } |

(12)

(12.c)

1 |At−1 |

zjt−1 − ηl ηg

s−1 X

! (t−1,r) (t,r) ∇ℓj (xj ; ξi )

r=0

j∈At−1

s−1 X ηl ηg X τ (t−1)+1 (t−1,r) (t,r) + t−1 (t − 2 − τj (t − 1)) ∇Fj (xj j ) − ∇ℓj (xj ; ξi ) , (13) |A | t−1 r=0

j∈A

where (12.a) holds because of Definition 4 and i ∈ At−1 , (12.b) because of line 12 in Algorithm 1, addition and subtraction, and we can get (13) by replacing (12.c) with (10). Recall that, for client j ∈ V, we have (i) xtj = zjt and (ii) Gtj = 0. When i ∈ R \ At−1 , zit has a simple iterative relation: τ (t−1)+1

zit = zit−1 − ηl ηg s∇Fi (xi i

(14)

At a high level, the sequence zit approximately mimics the ideal descent evolution at a client as if the client performs local optimizations on its local model xi per round regardless of its availability. Mathematically, the idea is that, if the progress per iteration of the auxiliary sequence zit is bounded, we can show the convergence of xti when xti and zit are close to each other. It is worth noting that imaginary sequences are used in peer-to-peer distributed learning literature (Spiridonoff et al., 2020; Avdiukhin and Kasiviswanathan, 2021; Lian et al., 2017; Yuan et al., 2016; Stich, 2018; Nedić et al., 2018). Yet, existing constructions are not applicable to our problem due to the (i) non-convexity of the global objectives, (ii) multiple local updates per round, (iii) possibly unbounded gradients, and the (iv) general form of bounded gradient dissimilarity. Departing from the use of staled stochastic gradients for auxiliary updates therein, we adopt the true gradient ∇Fi (·) to avoid the complications from the involved interplay between randomness in stochastic samples and randomness in τi (t). On the technical front, it follows from Definition 4 that ∥xti − zit ∥22 ≤ τ (t)+1 2 ηl2 ηg2 s2 (t − τi (t) − 1)2 ∥∇Fi (xi i )∥2 , whose bound appears to be quite challenging to derive due to the coupling of different realizations of τi (t) and gradients. As such, we bound the average of ∥xti − zit ∥2 across clients and rounds in Proposition 8. Lemma 5 (Unavailability statistics). Under Assumption 1 and δ defined therein. It holds for t ≥ 0 that 1 E [t − τi (t)] ≤ Pδ + ; δ

(15)

h i ((P − 1)δ + 1)2 + (P − 1)δ 2 + 1 δ δ 2 E (t − τi (t)) ≤ . δ2

(16)

Remark 6. Lemma 5 yields an upper bound on the first and second moments of a client i’s unavailable duration. Its proof can be found in Appendix D.3, where we leverage the tools from probability theory (Gut, 2006). Here, we remark on some special cases: 13

Xiang, Ioannidis, Yeh, Joe-Wong and Su

• When δ = 1, all clients are available during all training rounds, suggesting a static unavailable duration t − τi (t) of length 1 and thus a static second moment of value 1. Recall that we require Pδ to be the minimum window size when given a budget δ in Assumption 1, so it implies Pδ = 1. In this case, both of our bounds are loose by only a constant offset 1. • When Pδ = 1, the dynamics (2) becomes pti ≥ δ, which follows a heterogeneous geometric distribution. Our bounds (15) and (16) reduce to 1+1/δ and 2/δ 2 , respectively. Compared with (Xiang et al., 2024, Lemma 2), the first moment is loose by only a constant offset 1, while the second moment matches the result therein. When we further relax the condition and consider the special case where clients are available with the same probability δ, the unavailable duration t − τi (t) simply follows a homogeneous geometric distribution. It can be checked that our bound trivially holds. 6.4 Main Convergence Results 1 PM t e⋆ t e Let z̄t ≜ M i=1 zi , F ≜ minx F (x), and δmax ≜ maxi∈R,t∈[T ] pi . Recall that M = m + k. Lemma 7 (Descent Lemma). Let F t define the sigma algebra generated by randomness up to round t. Suppose that Assumptions 2, 3 hold and ηl ηg ≤ 1/(8sL). It holds that h i 2 ηl ηg s E Fe(z̄ t+1 ) − Fe(z̄ t ) | F t ≤ − ∇Fe(z̄ t ) 3 2 m 2 2ηl ηg sLσ ηl ηg δmax + 9mηl2 sL X + (t − τi (t))2 M2 i=1

m 65ηg ηl3 s3 L2 X

τ (t)+1

(t − τi (t))2 ∇Fei (xi i

i=1 m

2 m

4ηl ηg sL2 X M i=1

)

xti − zit | {z }2

Approximation Error

ηl ηg sL2 X 2 zit − z̄ t 2 . 2M | {z } i=1

Consensus Error

The proof of Lemma 7 follows from the standard analysis for non-convex smooth objectives but with non-trivial adaptation to account for adaptive innovation echoing and implicit gossiping. In particular, it highlights two terms unique in our derivation: the approximation error from the auxiliary sequence and the consensus error from the implicit gossiping procedure. Proposition 8 (Approximation error). Suppose that Assumptions 2 and 4 holds, we have T −1 M T −1 m i h i 1 XX h t 2 (17.a) 1 X X 2 E xi − zit 2 = E xti − zit 2 M T t=0 i=1 M T t=0 i=1 T −1 2 2 2 X 2 2 2 2 [(Pδ − 1)δ + 1] + (Pδ − 1)δ + 1 M β + 1 1 e(z̄ t ) ≤ 3ηl ηg s E ∇ F δ2 m T t=0 2 ! m T −1 h 2 i 2 2 2 X X + (P − 1)δ + 1 [(P − 1)δ + 1] mζ 1 L 2 δ δ + E zit − z̄ t 2 , + 3ηl2 ηg2 s2 δ2 M M i=1 T t=0

where (17.a) holds because of (10). 14

(17)

Efficient and Unbiased Federated Learning

The proof of Proposition 8 starts from Definition 4. Although in general it is difficult to bound the error, Assumptions 2 and 4 allow us to break down the problem into bounding the averaged gradient norm of z̄ t and the consensus error over all randomness instead. Next, we analyze the consensus error. Note that although implicit gossiping takes place in Algorithm 1 for xti , its analysis is technically challenging as discussed before. So, we adopt the auxiliary zit as an intermediary and apply Young’s inequality to bound the actual consensus error. Formally, the auxiliary models can be expressed in a compact matrix form t ]. Their local parameter innovation matrix G ft (18) is formulated by as Z (t) ≜ [z1t , . . . , zm combing (12) and (14). e t = 1{i∈At } (t − τi (t)) G i

s−1 X

(t,r)

∇ℓi (xi

) − ∇Fi (xti ) + s∇Fi (xti ).

(18)

r=0

Unrolling the recursion, it holds for the consensus error

t t 2 i=1 ∥zi − z̄ ∥2 /M that

  2 t−1 t−1 2η2 X Y 2 η 1 g e (q)  W (q) − J , (19) e (t−1) W (t−1) (I − J) (19.a) Z (t−1) − ηl ηg G G = l M M F q=0

l=q

where equality (19.a) holds because all clients are initiated at the same weight. Recall that ρk is the spectral norm of the information mixing matrix square over a rolling window of Pδ rounds in Lemma 3. To ensure an exponential decay of the consensus error, it is crucial to have ρk < 1, which is confirmed by Lemma 9. Lemma 9. Suppose that Assumption 1 and k > 0. When Pδ = 1, it holds that 2 2 m δ + (k 2 + 2mk) δ 2 ρk ≤ 1 − . 8(m + k)2

(20)

When Pδ > 1, it holds that 2 2 m δ + (k 2 + 2mk) δ 2 ρk ≤ 1 − . 8(m + k)4Pδ +2

(21)

Proof Sketch. The full proof is deferred to Appendix D.5. Coarsely, we study the conductance of a hypothetical Markov chain, whose transition matrix is a matrix square (W (n,Pδ ) )2 , as we are interested in a sliding window of Pδ rounds. The unique challenge of our analysis arises from the involved information mixing between volatile regular clients in R and always-on virtual clients in V. Instead, we represent the federated learning systems as a graph, where the nodes are clients, and the edges are defined by the mixing matrix W weights, capturing the interactions between clients. As such, we can bound the conductance of the hypothetical Markov chain by studying the product of the edge weights and use Cheeger’s inequality to close the gap between the spectral norm and the conductance.

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Remark 10. Lemma 9 is divided into two parts: Pδ = 1 and Pδ > 1, where (20) is tighter than (21) when Pδ = 1. A similar dependence on the number of clients in the spectral norm bound has been noted in the prior fully decentralized learning literature, e.g., in (Nedić and Olshevsky, 2014), the clients therein are assumed to form a Pδ -strongly-connected graph. Mapping to our setup, it means that all clients are available at least once over Pδ consecutive rounds. In contrast, we only need the average available probability of each client to be non-zero across every Pδ rounds, which is more general and makes direct applications of their results inapplicable. It remains an open question whether the worst-case bound can be improved, and we would like to leave this as future work. We now proceed to present the convergence rates. In the sequel, we assume it holds for ηg and ηl that ηl ηg ≤

√ δ(1 − ρk ) m 96sL

Pδ M ((Pδ

− 1)2 δ 2 + 1) (β 2 + 1)

; ηl ≤

δ 216sL

((Pδ − 1)2 δ 2 + 1) (β 2 + 1)

(22)

The proof of the consensus error borrows insights from the analysis of the gossip algorithm (Nedic et al., 2017; Wang et al., 2022) but with substantial adaptation to accommodate the novel auxiliary formulation and multi-step local updates. Under the learning rate conidtions in (22) and Assumptions 1, 2, 3 and 4, we can show that T −1 M T −1 M T −1 i i i 1 X 1 X h t 1 X h 1 X 1 X h t 2 2 2 E xi − zit 2 ≍ E zi − z̄ t 2 ≍ E ∇F (z̄ t ) 2 . T t=0 M i=1 T t=0 M i=1 T t=0

(23)

It remains to bound the full convergence error of zit , which is presented in Theorem 11. Theorem 11 (Convergence error of zit ). Suppose that Assumptions 1, 2, 3 and 4 hold. Choose learning rates ηl and ηg such that the conditions in (22) are met for T ≥ 1 and k > 0. It holds that T −1 i m + k F (z̄ 0 ) − F ⋆ m + k δ η η Lσ 2 1 X h 1 max l g t 2 E ∇F (z̄ ) 2 ≲ + (Pδ − 1)2 + 2 T m ηl ηg sT m m+k δ t=0 m+k 1 1 + ηl2 ηg2 s2 L2 Pδ σ 2 + ζ 2 (Pδ − 1)2 + 2 1 + . (24) m δ (1 − ρk )2 By addition, subtraction, and Young’s inequality, (25) and (26) hold under Assumption 2. T −1 M T −1 M −1 M i i 1 TX i 1 X 1 X h t 1 X 1 X h t 1 X h t 2 2 2 E xi − x̄t 2 ≍ E xi − zit 2 + E zi − z̄ t 2 ; (25) T t=0 M i=1 T t=0 M i=1 T t=0 M i=1 T −1 T −1 M −1 h i i 1 TX i 1 X 1 X h t 1 X h 2 2 2 E ∇F (x̄t ) 2 ≍ E xi − zit 2 + E ∇F (z̄ t ) 2 . T t=0 T t=0 M i=1 T t=0

(26)

Moreover, from (23), (25) and (26), it can be seen that (27) holds. T −1 M T −1 T −1 i i i 1 X 1 X h t 1 X h 1 X h 2 2 2 E xi − x̄t 2 ≍ E ∇F (z̄ t ) 2 ≍ E ∇F (x̄t ) 2 . T t=0 M i=1 T t=0 T t=0

Combining (23), (24), (25) and (26), we are ready for Corollary 12. 16

(27)

Efficient and Unbiased Federated Learning

Corollary 12 (Convergence rate of xti ).√Suppose that Assumptions 1, 2, 3 and 4 hold. Choose learning rates as ηl = √T1sL , ηg = sδm. Let T ≥ 1 be sufficiently large so that the conditions of ηl and ηg in (22) are satisfied. For k > 0, it holds that T −1 i m + k L F (x̄0 ) − F ⋆ i 1 X h δmax h t 2 √ + 3√ E ∇F (x̄ ) 2 ≲ (Pδ − 1)2 δ 2 + 1 σ 2 T m sδmT δ 2 smT t=0 h i 1 m + k smPδ 2 2 2 2 σ +ζ (Pδ − 1) δ + 1 1 + . (28) + m T (1 − ρk )2

Remark 13 (Linear speedup). Corollary 12 establishes the full convergence rate for FedSWE algorithm. It can be seen that the second term dominates when T is sufficiently large, which relates to stochastic gradient noise σ 2 . The non-stationary client unavailability results in the third term, which relates to gradient divergence ζ 2 and also to σ 2 . The proof of Corollary 12 follows from (26) by plugging in Proposition 8 and Theorem 11. In the special case where k = Θ(m) and At =√[m], we simply have δmax = δ = 1 and Pδ = 1. Our convergence bound reduces to O(1/ smT ). In other words, we achieve the desired linear speedup property with respect to the number of local steps s and the number of clients m, matching rates in the established literature (Yu et al., 2019a,b; Yang et al., 2021; Wang and Ji, 2022, 2024). The linear speedup property enables a large cross-device federated learning system to take advantage of the massive scale of parallelism. Notice that the consensus error (27) and the convergence rate (28) have the same asymptotic order with respect to the parameters mentioned above. Hence, the consensus error also enjoys the desired linear speedup property when T is sufficiently large in this special case. 6.5 Impacts of k In this section, we elaborate on the scaling of spectral norm ρk and convergence upper bound in (28) w.r.t. k. Next, we explore the necessity of interpolation (k > 0) under Assumption 1. 6.5.1 On the Scaling of Convergence Results On spectral norm ρk . It is easy to show that the upper bound in (20) decreases monotonically in k by taking partial derivatives; yet, the monotonicity is not that straightforward in (21). On the other hand, the upper bounds characterize only the worst-case scenario, so they cannot directly inform the monotonicity analysis of ρk w.r.t. k. Intuitively, a greater k implies a more connected client population because virtual clients are always available. When k → ∞, we have ρk ≈ 0 since the W matrix will be dominated by the virtual clients, approaching a scaled all-one matrix. We hypothesize that the spectral norm ρk would decrease w.r.t. k, which is numerically demonstrated in Example 3 by explicit realizations of Assumption 1. Example 3. In Fig. 4, a total of m = 10 clients are available under the dynamics shown in Fig. 4a with Pδ = 1 and Fig. 4b with Pδ > 1. We expect to see a smaller spectral norm when clients are more frequently available. The results match our hypothesis that the spectral norm ρk would decrease w.r.t. k. It is expected that a larger Pδ leads to worse information fusion, i.e., a smaller spectral norm ρk . Details can be found in the captions. 17

Xiang, Ioannidis, Yeh, Joe-Wong and Su

0.915 0.910 0.905 0.74 0.73

0.1

0.53 0.52 0.51 0.315 0.310 0.305 0.115

0.5

0.000 0.001

0.46 0.2

0.3

0.110 0.001

0.1

0.48

0.3

0.1 0.2

0.5

0.7

0.0 0.2

0.7

0.9

0.0 0.2

0.9

1.0

0.0 0.2

1.0

0.0

100 200 300 400 Number of Virtual Clients k

100 200 300 400 Number of Virtual Clients k Group 2

Group 1

200 400 Global Rounds

(a) Regular clients (i.e., clients in R) are available with probability p in any global round. That is, the period is P = 1. The values of p can be found in the legends. y-axis is the calculated spectral norm of (W (0,1) )2 over 1000 repetitions. We can see that the spectral norm decreases in k except when p = 1. In that case, clients are always available, leading to a zero-valued spectral norm.

25 50 75 Global Rounds

100

(b) Regular clients (i.e., clients in R) are divided into two groups. Each group i is available with probability pi for 10 rounds. That is, the period is P = 20. y-axis is the calculated spectral norm of (W (0,20) )2 over 1000 repetitions. We can see that the spectral norm decreases in k.

Figure 4: Calculated spectral norm results with varying numbers of k. We consider m = 10 clients with availability dynamics described in the plots. Note that the y-axis of each subplot is of a different range.

On convergence upper bound in (28). We have shown in Lemma 9 that ρk < 1, which holds independently of k as long as k > 0. Intuitively, as we have discussed in Section 5.2, 18

Efficient and Unbiased Federated Learning

there exists a sweet spot k ∗ for k that balances training stability and convergence speed. Yet, analytically obtaining the exact k ∗ is fundamentally challenging, if not impossible at all. Specifically, the value of k affects the convergence upper bound in (28) by (i) explicitly showing up in the numerator and by (ii) implicitly influencing the spectral norm ρk . Recall that we hypothesize in 3 that the spectral norm ρk monotonically decreases w.r.t. k. However, which term will ultimately dominate the monotonicity of (28) as k increases remains unclear. In Section 7, we empirically find that k = Θ(m) strikes the best balance between convergence speed and test accuracy. 6.5.2 Necessity of Interpolation (k > 0) when Pδ > 1 Observe that we require the coefficient k > 0 in Lemma 9, which appears to be an artifact in our proofs to improve training stability. However, we show next in Proposition 14 that for our algorithm to hold under Assumption 1, it is necessary to have k > 0. To see this, we construct a counterexample via a similar quadratic function as in Example 1. Let client i’s local objective Fi (x) ≜ ∥x − ui ∥22 /2, where x, ui ∈ R and i ∈ [m]. The global objective is m

1 X F (x) = ∥x − ui ∥22 , 2m

(29)

i=1

P with unique global minimizer x∗ = ( m i=1 ui )/m. Proposition 14. For a global objective as per (29), let M1 the first half client population, M2 the remaining client population, and M ≜ [m] = M1 ∪ M2 . When all clients in M1 are available in even rounds only, while those in M2 are available in odd rounds only. We have (i) Assumption 1 holds under Pδ = 2 and δ = 0.5; (ii) It holds for the output xtout of Algorithm 1 without interpolation (k = 0) that 2

lim E

t→∞

∇F (xtout ) − ∇F (x∗ ) 2

1 = 2 m

ui −

i∈M1

X j∈M2

(30)

Proof of Proposition 14. At a high level, our proof suggests an interesting client participation dynamics that prevents two groups of clients from properly mixing global updates. Construction of pti ’s. We assume that clients in M1 are available in even rounds only with 2r+1 = 1, p2r i = 1, while the rest clients in M2 are exclusively available in odd rounds with pi + t where r ∈ Z . It is easy to extend the proof to the case where pi < 1 for the same group of clients. Global and local gradients. The global gradient ∇F (x) and local gradient ∇Fi (x) are m

∇F (x) = x −

1 X ui , ∇Fi (x) = x − ui . m i=1

Combining them together. Due to the postponed multi-cast procedure and the lack of interpolation, the parameter server cannot carry the aggregated global updates from one round to another. Hence, the available clients depend on their cohorts’ updates in that round 19

Xiang, Ioannidis, Yeh, Joe-Wong and Su

to prepare their local models for the next availability. Since M1 ∩ M2 = ∅ and non-overlap availability between two groups, the clients in M1 cannot exchange models with the clients in M2 . Therefore, the global objective alternates between an average objective of clients in M1 and of clients in M2 , i.e., ( 2 1 P Feven = m i∈M1 ∥x − ui ∥2 ; P 2 1 Fodd = m i∈M2 ∥x − ui ∥2 . The expected output xtout follows that ( P t 2( i∈M1 ui )/m E xout = P 2( i∈M2 ui )/m

if t = 2r; if t = 2r + 1.

Consequently, 2

h E

∇F (xtout ) − ∇F (x∗ ) 2

1 = 2 m

X i∈M1

ui −

X j∈M2

. 2

As is empirically verified by the scalar example in Fig. 5, k > 0 may correct the bias. Intuitively, interpolation mixes the global models over rounds and enables clients to share information through the parameter server with cohorts in the current round and those from previous rounds. Mathematically, we guarantee clients to exchange information with each other in expectation over every sliding window of Pδ rounds, provided k > 0. See the proof of Lemma 9 for details. 6.5.3 Special case when Pδ = 1 Our conference version (Xiang et al., 2024) studies a special case where Pδ = 1 and interpolation becomes optional. Our discussions in Section 6.5.2 are consistent with our results therein. Informally, this is because clients in (Xiang et al., 2024) are never isolated into distinct groups when Pδ = 1. On the technical front, all elements in the information mixing matrix W (t) are strictly positive in expectation in any round t under the unavailability dynamics therein. Hence, clients can evenly diffuse information with each other in expectation. Nevertheless, k > 0 still helps to reduce fluctuations of the trajectory of xt .

7 Numerical Experiments In this section, we evaluate FedSWE on real-world data sets to corroborate our analysis and compare the performance of FedSWE with the state-of-the-art algorithms. The missing specifications and additional numerical results can be found in Appendix H. Specifically, we consider a federated learning system of one parameter server and m = 100 clients. We focus on image classification tasks, and consider multiple real-world data sets (Netzer et al., 2011; Krizhevsky et al., 2009; Darlow et al., 2018). Each data set contains 10 image classes, but the categories differ. 20

Efficient and Unbiased Federated Learning

Client # 1 Client # 2

Global Optimum

100

Bias

10 0

200 400 600 800 1000 Global Rounds

rithm 1 with interpolation (k = 1). It can be seen that the gradient outputs converge to 0 under interpolation, recovering the global optimum.

||xi x||2

1.0

Bias

1 2

i=1

1 2

||xi x||2

rithm 1 without interpolation (k = 0). It can be seen that the biases are significant.

10000 8000 6000 4000 2000 0

200 400 600 800 1000 Global Rounds

(b) A visualization of the scalar gradient of Algo-

(a) A visualization of the scalar gradient of Algo-

i=1

100

Bias

Client # 2

5 F(x)

F(x)

Client # 1

0.5 0.0 0.5 1.0 0

200 400 600 800 1000 Global Rounds

(d) A visualization of the consensus of Algorithm 1

without interpolation (k = 0). It can be seen that two clients fail to reach a consensus.

with interpolation (k = 1). It can be seen that two clients can reach a consensus under interpolation.

Figure 5: Visualizations of Algorithm 1 with two clients and a global objective (29), whose u1 = 100, u2 = −100. The first client is available exclusively in even rounds, while the second client is available in odd rounds only. x-axis is the global round index, the details of y-axis can be found in the subplots. Figs. 5a and 5c plot the results of Algorithm 1 without interpolation. It can be seen that the outputs alternate between two clients’ local optimums and can deviate far away from the true global minimizer u1 + u2 = 0. Moreover, the clients fail to reach a consensus. In sharp contrast, Figs. 5b and 5d indicate that Algorithm 1 recovers the global minimizer with interpolation (k = 1) and allows clients to reach a consensus.

7.1 Non-stationary and Heterogeneous Unavailability with Pδ > 1 We start from a general case where the length of the sliding window Pδ > 1 in Assumption 1. Data sets and data heterogeneity. We perform the experiments on SVHN (Netzer et al., 2011) and CIFAR-10 (Krizhevsky et al., 2009) data sets. Similar to Proposition 14, we divide clients into two groups M1 and M2 , each with 50 clients. Each group of clients collectively hold 5 classes of images from the original data set, non-overlapping with the other group. To emulate highly heterogeneous local data distributions within each group, the images are 21

Xiang, Ioannidis, Yeh, Joe-Wong and Su

100

500

xi x 2 m

1 m

i = 11

10 33 10 10 10 55

i=1

xxii xx 22

1011 10 10 11 10

1000

0 0 2000 4000 10000 20006000 80004000 6000 Global rounds Global rounds

2000

101 10 1 10 3 10 5 80000

10000

200010000 4000 6000 8000 10000 Global rounds

(b) SVHN data set. Heterogeneous and nonsta-

intra-period probability, detailed in Fig. 6e.

tionary intra-period pti , detailed in Fig. 6f.

i=1

xi x 2

102 100 10 2 10 4

1 m

i=1

xi x 2

(a) SVHN data set. Heterogeneous but stationary

5000

10000 15000 20000 Global rounds

102 100 10 2 10 4 0

5000

Heterogeneous but stationary intra-period probability, detailed in Fig. 6e. A Client in Group 1

(d) CIFAR-10 data set. Heterogeneous and nonstationary intra-period pti , detailed in Fig. 6f.

A Client in Group 2

A Client in Group 1

A Client in Group 2

pit

10000 15000 20000 Global rounds

75 100 125 Global Rounds

150

175

200

75 100 125 Global Rounds

150

175

200

(e) An illustration of the client unavailability dy-

(f) An illustration of the client unavailability dy-

namics in Figs. 6a and 6c. The two client groups M1 and M2 are available alternately, where pi ’s remain static within each available period.

namics in Figs. 6b and 6d. The two client groups are available alternately, where pti ’s have a staircase pattern within each available window.

Figure 6: Plots of the consensus errors on a logarithmic scale with m = 100 clients. The 100 clients are evenly divided into two non-overlapping groups M1 and M2 . The global rounds can be partitioned into periods, each with length 50 rounds. In all odd periods, the available probability pti > 0 if i ∈ M1 while pti = 0 otherwise. In all even periods, the available probability pti > 0 if i ∈ M2 while pti = 0 otherwise. We train CNN networks on the SVHN data set and CIFAR-10 data set for T = 10000 and T = 20000 rounds, respectively. When a client becomes available, it performs s = 10 steps of local computation. The results are obtained under 3 random seeds and sampled every Pδ round. The solid curves differ from each other by the values of k, and the shaded areas plot the standard deviation. It can be observed from the plots that clients fail to reach a consensus when k = 0.

assigned to individual clients i according to νi ∼ Dirichlet(α = 0.1) (Hsu et al., 2019; Wang and Ji, 2022, 2024). Non-stationary client unavailability with Pδ > 1. We evaluate two non-stationary unavailable dynamics—static and staircase probabilistic trajectories—both with Pδ = 100. Illustrative plots can be found in Figs. 6e and 6f. The non-stationary dynamics are motivated by real-world federated learning participation statistics and by generalizing the existing 22

Efficient and Unbiased Federated Learning

gFedAvg

FedAvg

80% 60% 40% 20% 0%

FedKnown

MIFA

FedAU

FedVARP

FedSWE

80% 80% 60% 60% 40% 40% 20% 20% 0% 0 2000 4000 6000 8000 10000 0% Rounds 0 2000 04000 6000 2000 8000 100004000 6000 8000 Global10000 Global Rounds Global Rounds

(b) No interpolation (k = 0). Heterogeneous and non-stationary intra-period probability pti (Fig. 7f).

(a) No interpolation (k = 0). Heterogeneous but stationary intra-period probability pi (Fig. 7e).

80% 60% 40% 20% 0%

2000 4000 6000 8000 10000 Global Rounds

(d) With interpolation (k = 100). Heterogeneous

neous but stationary intra-period probability pi (Fig. 7e).

and non-stationary intra-period probability pti (Fig. 7f).

A Client in Group 1

A Client in Group 2

A Client in Group 1

A Client in Group 2

pit

1 0

75 100 125 Global Rounds

150

175

200

75 100 125 Global Rounds

150

175

200

(e) The two client groups are available alternately;

(f) The two client groups are available alternately;

however, the clients’ pi ’s remain static within each available window.

however, the clients’ pti ’s show a staircase pattern within each available window.

Figure 7: Test accuracy results with m = 100 clients, who are divided into two non-overlapping but evenly sized groups. We train CNN networks on the SVHN data set for T = 10000 rounds. When a client becomes available, it performs s = 10 steps of local computation. The results are obtained under 3 random seeds and sampled every Pδ round. The curves plot the averaged results, while the shaded areas plot the standard deviation.

participation patterns, such as cyclic participation (Cho et al., 2023a; Wang and Ji, 2024). Formally, let fi (t) be a time-dependent function under the specific non-stationary dynamics, and pi = ⟨νi , ϕ⟩, where νi ∼ Dirichlet(α = 0.1), and ϕ characterizes the unbalanced contribution of different image classes to the generated probabilities. The unavailability dynamics of client group M1 and M2 are illustrated in (31) and in (32), respectively. For i ∈ M1 , we have ( pi · fi (t), if (t mod Pδ ) ≤ P2δ ; t pi = (31) 0, otherwise.

For j ∈ M2 , we have ( pj · fj (t), if (t mod Pδ ) > P2δ ; t pj = (32) 0, otherwise.

Xiang, Ioannidis, Yeh, Joe-Wong and Su

80%

60%

40% 100

101

102 k

103

40% 100

104

101

102 k

103

104

(a) Heterogeneous but stationary intra-period

(b) Heterogeneous and non-stationary intra-

probability pi (Fig. 7e).

period probability pti (Fig. 7f).

Figure 8: Test accuracy of FedSWE with different k’s on SVHN data set under different unavailability dynamics. The reported results are averaged over the last 500 rounds. Consistent with Remark 13, we observe an initial increase in test accuracy, followed by a decline, peaking around k = m = 100.

104 Rounds

Rounds

104 103 102 100

101

102 k

103

103 102 100

104

101

102 k

103

104

(a) Heterogeneous yet stationary intra-period

(b) Heterogeneous and non-stationary intra-

probability pi (Fig. 7e).

period probability pti (Fig. 7f).

Figure 9: The number of rounds needed to achieve 40% test accuracy of FedSWE with various k values on the SVHN data set under different unavailability dynamics. We can observe a similar trend as in Fig. 8 that a slight speedup in the beginning but a significant slowdown after k = m.

Each element of [ϕ]c is drawn from Uniform(0, Φc ), where a smaller Φc leads to a less significant contribution of that image class. It is immediately clear that the coupling of local data distribution νi ∼ Dirichlet(α = 0.1) and class contribution ϕ leads to non-independent pi ’s. Although the non-independence setup violates our theoretical analysis, we observe that FedSWE retains its outperformance. Correlating the local data distribution and the probability of client availability is a common practice in the prior literature. For example, Gu et al. (2021) experiment with a formula for pi so that clients that hold images of smaller digits participate less frequently. Wang and Ji (2024) construct pi as an inner product of the clients’ local data distribution νi and an external distribution Φ′ . We highlight that the periodic unavailability dynamics evaluated in our work are more challenging, e.g., than (Wang and Ji, 2022), where they select a fixed number of S clients out of the available client group to participate in each round t uniformly at random. In our work, we may have fewer than S available clients in any round t due to the heterogeneity in the base probability pi and randomness in the Bernoulli sampling process; therefore, a fixed size of sampling clients in each round is not guaranteed. Benchmark algorithms. We compare FedSWE with six baseline algorithms, including FedAvg over active clients (McMahan et al., 2017), gFedAvg (Wang and Ji, 2022), FedAvg with known probability (FedKnown) (Perazzone et al., 2022), FedAU (Wang and Ji, 24

Efficient and Unbiased Federated Learning

FedAvg FedAvg

gFedAvg FedKnown

FedAU gFedAvg

FedVARP FedKnown FedAWE-M

MIFA

80% 60% 40% 40% 20% 20% 0% 0 5000 10000 15000 20000 0% Global 0 Rounds 2000

FedAvg gFedAvg MIFA FedKnown

FedAU

40% 20% 0%

5000 10000 15000 20000 Global Rounds

4000 6000 8000 10000 Global Rounds(b) No interpolation (k = 0).

Heterogeneous and non-stationary intra-period probability pti (Fig. 10f).

(a) No interpolation (k = 0). Heterogeneous but stationary intra-period probability pi (Fig. 10e).

FedVARP FedAWE-M FedSWE

60%

80% 60% 40% 20% 0%

FedAU

MIFA FedVARP

80% 60% 40% 20% 0%

5000 10000 15000 20000 Global Rounds

(d) With interpolation (k = 100). Heterogeneous

neous but stationary intra-period probability pi (Fig. 10e).

and non-stationary intra-period probability pti (Fig. 10f).

A Client in Group 1

A Client in Group 2

A Client in Group 1

A Client in Group 2

pit

1 0

75 100 125 Global Rounds

150

175

200

75 100 125 Global Rounds

150

175

200

(e) The two client groups are available alternately;

(f) The two client groups are available alternately;

however, the clients’ pi ’s remain static within each available window.

however, the clients’ pti ’s show a staircase pattern within each available window.

Figure 10: Test accuracy results with m = 100 clients, who are divided into two non-overlapping but evenly sized groups. Only a single client group is available in each training round. Inside an available window of P rounds, a client i in each group is available with probability pti . We train CNN networks on the CIFAR-10 data set for T = 20000 rounds. When a client becomes available, it performs s = 10 steps of local computation. The results are obtained under 3 random seeds and sampled every P round. The curves plot the averaged results, while the shaded areas plot the standard deviation.

2024), MIFA (Gu et al., 2021) and FedVARP (Jhunjhunwala et al., 2022). The details of the algorithms are deferred to Appendix H. Necessity of interpolation (k > 0). Recall that we show in Proposition 14 that interpolation is necessary for information diffusion over rounds under periodic unavailability. To validate such a claim, we show in Fig. 6 that clients fail to reach a consensus when k = 0. Specifically, instead of decaying, we observe that the consensus errors blow up in the plots. In contrast, the interpolation carries global updates from round to round and eventually allows clients to correct bias. Furthermore, as k increases, we observe a smaller consensus error, 25

Xiang, Ioannidis, Yeh, Joe-Wong and Su

60%

40%

50% 40%

20% 100

101

102 k

103

104

100

101

102 k

103

104

(a) Heterogeneous but stationary intra-period

(b) Heterogeneous and non-stationary intra-

probability pi (Fig. 10e).

period probability pti (Fig. 10f).

Figure 11: Test accuracy of FedSWE with different k’s on CIFAR-10 data set under different unavailability dynamics. The reported results are averaged over the last 500 rounds. Consistent with Remark 13, we observe an initial increase in test accuracy, followed by a decline, peaking around k = m = 100.

104 Rounds

Rounds

104 103 102 100

101

102 k

103

103 102 100

104

101

102 k

103

104

(a) Heterogeneous yet stationary intra-period

(b) Heterogeneous and non-stationary intra-

probability pi (Fig. 10e).

period probability pti (Fig. 10f).

Figure 12: The number of rounds needed to achieve 40% test accuracy of FedSWE with various k values on CIFAR-10 data set under different unavailability dynamics. We can observe a similar trend as in Fig. 11 that a slight speedup in the beginning but a significant slowdown after k = m.

which implies better client connectivity. Yet, as we will show next, excessively increasing k will inevitably lead to an unnecessary slowdown in convergence. Performance discussions. We can observe from Figs. 7b, 7a, 10a and 10b that most of the algorithms, including our conference version: FedSWE without interpolation (k = 0), suffer from the challenging periodic non-stationary dynamics and experience high fluctuations. As we have illustrated in Proposition 14, FedSWE without interpolation fails to diffuse information across rounds. For baseline algorithms on the SVHN data set, FedKnown attains the best peak accuracy, while FedVARP and gFedAvg yield the smoothest curves yet with less accurate predictions. In sharp contrast, FedSWE with k = 100 generates relatively smooth trajectories and outperforms all the baseline algorithms on both SVHN (Figs. 7c and 7d) and CIFAR-10 data sets (Figs. 10c and 10d). For the SVHN data set, FedSWE with k = 100 attains comparable accuracy as the peak accuracy of FedKnown yet with more consistent performance. For the CIFAR-10 data set, FedSWE with k = 100 obtains even better accuracy than FedKnown. It is worth noting that, despite the impressive empirical performance of FedKnown, its analysis requires strictly positive probabilities (Perazzone et al., 2022), and its implementation adopts pti ’s as a known priori. FedAU is provably robust to stationary dynamics; yet, we consider non-stationary availability here. It is a bit surprising 26

Efficient and Unbiased Federated Learning

that FedSWE surpasses MIFA and FedVARP, which both require heavy memory of size O(md); however, the interpolation in FedSWE only requires light memory of size O(d). Under the periodic unavailability dynamics, the clients in the inactive client group can be unavailable for quite a long period of global rounds; therefore, their gradients from the most recent availability may not be a good approximation of their latest fresh gradients if they are available. Effects of interpolation coefficient k. Figs. 8 and 11 compare the test accuracies of FedSWE under different choices of k. The results show that increasing k is not always beneficial. On the one hand, FedSWE converges faster as k approaches m, but it undergoes a substantial slowdown when k continues to rise, as shown by the number of rounds required to reach 40% test accuracy in Figs. 9 and 12. On the other hand, the final test accuracy increases and then drops in Figs. 8 and 11. This aligns with our discussions in Remark 13, where we show that the convergence upper bound minimizes at a unique point. However, the exact analytical form depends on parameters that are difficult, if not impossible, to obtain in practice. Based on the results, we empirically recommend k = Θ(m) to strike a balance between performance and convergence speed. 7.2 Non-stationary and Heterogeneous Unavailability with Pδ = 1 In this section, we investigate the special case of Assumption 1, where Pδ = 1 as in (Xiang et al., 2024), with interpolation providing an added benefit. Our numerical results are presented in Table 2, where we study additional availability dynamics and data sets. The results are partitioned into two parts, where the latter part includes algorithms aided by heavy memory or known statistics, such as MIFA, FedVARP and FedKnown. Non-stationary client unavailability with Pδ = 1. We study a total of three client unavailability dynamics in Table 2, including stationary, staircase, and sine probabilistic trajectories. Their visualizations are also available in the same table. Our choices of non-stationary dynamics are motivated by real-world federated learning participation statistics (Bonawitz et al., 2019; Ribero et al., 2022). The learning tasks become more challenging as the list progresses due to the growing complexity of the non-stationary dynamics. Mathematically, similar to the construction—(31) and (32)—in Section 7.1 but without alternate client group availability, client i’s dynamics is defined as pti = pi · fi (t). The definitions of pti and fi (t) can be found therein. Note that the pi ’s remain to be nonindependent across different clients, but we observe that FedSWE retains its outperformance. Performance discussions. In addition to the baselines in Section 7.1, we include the evaluation results on FedAvg over all clients, F3AST algorithm (Ribero et al., 2022) and on CINIC-10 data set (Darlow et al., 2018). To understand the nuances in the performance of our conference version (Xiang et al., 2024) and this journal extension, we also compare the performance of FedSWE without (k = 0) and with interpolation (k = 100). It is observed that FedSWE consistently outperforms the algorithms not aided by heavy memory or known statistics. In particular, FedSWE with interpolation attains better accuracies than its non-interpolation variant (Xiang et al., 2024) on almost all tasks, providing added benefits. In the only exception (stationary on SVHN data set), their performances are close, with accuracy differences of less than 1%. We also surprisingly observe that FedSWE occasionally beats MIFA, which is memory heavy. We attribute it to its reuse of stored gradients 27

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Table 2: Results and comparisons on real-world data sets in the form of mean accuracy ± standard deviation and are obtained over 3 repetitions in different random seeds. Results are averaged over the last 50 rounds. The total number of global rounds is 2000 for SVHN, CIFAR-10 and CINIC-10. Algorithms are categorized into two groups: (1) ones not aided by memory or known statistics; (2) ones assisted by memory. For a fair competition, we boldface the best accuracy in the first group, while the second best is underlined. Unavailable Dynamics

Stationary pi 0

Non-stationary (Staircase) pti

Non-stationary (Sine) pti

Data sets Algorithms

Train

SVHN Test

CIFAR-10 Train Test

CINIC-10 Train Test

FedSWE (ours, k = 0) FedSWE (ours, k = 100) FedAvg over active FedAvg over all gFedAvg FedAU F3AST

86.5 ± 0.7 % 86.3 ± 1.1% 82.6 ± 1.0 % 76.1 ± 2.1 % 83.5 ± 1.5 % 83.4 ± 1.0 % 83.2 ± 0.7 %

86.1 ± 0.7 % 85.4 ± 1.0% 82.4 ± 1.1 % 76.1 ± 2.4 % 83.0 ± 1.2% 83.2 ± 1.0 % 83.2 ± 0.7 %

68.1 ± 1.4 % 68.7 ± 1.0 % 64.1 ± 1.9 % 55.8 ± 2.1 % 64.5 ± 1.7% 65.4 ± 1.4 % 64.4 ± 1.1 %

66.3 ± 1.1 % 66.9 ± 0.9 % 62.9 ± 1.4 % 55.4 ± 1.8 % 63.8 ± 1.7% 64.1 ± 1.0 % 63.5 ± 0.9 %

47.9 ± 2.1 % 48.3 ± 1.7 % 43.6 ± 2.4 % 38.4 ± 2.1 % 45.3 ± 1.4% 45.6 ± 1.5 % 45.3 ± 1.2 %

47.3 ± 2.0 % 47.9 ± 1.6 % 43.1 ± 2.4 % 38.0 ± 2.1 % 44.9 ± 1.2% 45.2 ± 1.5 % 44.8 ± 1.2 %

FedAvg with known pi ’s MIFA (memory aided) FedVARP (memory aided)

86.1 ± 0.5 % 84.2 ± 0.5 % 84.6 ± 0.2 %

85.6 ± 0.5 % 84.1 ± 0.6 % 84.3 ± 0.1 %

65.4 ± 1.0 % 66.6 ± 0.8 % 67.5 ± 0.2 %

63.1 ± 0.9 % 65.3 ± 0.6 % 66.3 ± 0.3 %

45.0 ± 1.2 % 47.5 ± 0.5 % 47.8 ± 0.2 %

44.6 ± 1.1 % 46.9 ± 0.5 % 47.2 ± 0.2 %

FedSWE (ours, k = 0) FedSWE (ours, k = 100) FedAvg over active FedAvg over all gFedAvg FedAU F3AST

85.9 ± 0.8 % 86.0 ± 1.2 % 82.5 ± 1.0 % 75.9 ± 2.1 % 83.1 ± 1.3 % 83.6 ± 0.8 % 83.1 ± 0.6 %

85.6 ± 1.0 % 85.9 ± 0.7 % 82.4 ± 0.9 % 75.9 ± 2.3 % 83.0 ± 1.1 % 83.4 ± 0.8 % 83.1 ± 0.6 %

67.7 ± 1.3 % 67.8 ± 1.0 % 64.2 ± 1.8 % 55.7 ± 2.1 % 65.0 ± 1.6 % 65.2 ± 1.7 % 64.3 ± 1.1%

66.0 ± 1.2 % 66.1 ± 1.2 % 63.0 ± 1.4 % 55.4 ± 1.8 % 64.9 ± 1.5 % 63.9 ± 1.5 % 63.3 ± 0.9 %

47.5 ± 2.0 % 47.7 ± 1.5 % 43.7 ± 2.0 % 38.4 ± 2.0 % 45.3 ± 1.4 % 45.7 ± 1.5 % 45.2 ± 1.2 %

46.9 ± 2.0 % 47.1 ± 1.4 % 42.3 ± 2.2 % 37.9 ± 2.0 % 44.9 ± 1.3 % 45.1 ± 1.5 % 44.8 ± 1.2 %

FedAvg with known pti ’s MIFA (memory aided) FedVARP (memory aided)

85.8 ± 0.8 % 84.2 ± 0.5 % 84.6 ± 0.2 %

85.2 ± 0.9 % 84.0 ± 0.5 % 84.3 ± 0.3 %

68.0 ± 1.6 % 66.7 ± 0.7 % 67.3 ± 0.3 %

66.1 ± 1.8 % 65.3 ± 0.5 % 66.1 ± 0.3 %

45.0 ± 1.1 % 47.5 ± 0.5 % 47.7 ± 0.2 %

44.7 ± 1.0 % 46.9 ± 0.5 % 47.2 ± 0.1 %

FedSWE (ours, k = 0) FedSWE (ours, k = 100) FedAvg over active FedAvg over all gFedAvg FedAU F3AST

85.7 ± 0.9 % 85.9 ± 1.2 % 82.1 ± 1.1 % 71.3 ± 2.5 % 83.6 ± 1.3% 82.5 ± 1.4 % 82.3 ± 1.0 %

85.6 ± 0.9 % 85.8 ± 0.8 % 82.0 ± 1.3 % 71.3 ± 2.8 % 83.5 ± 1.1 % 82.5 ± 1.3 % 82.3 ± 1.0 %

64.9 ± 1.9 % 65.8 ± 1.8 % 63.3 ± 1.9 % 52.2 ± 2.4 % 62.4 ± 1.2 % 64.2 ± 2.3 % 63.1 ± 1.7 %

63.5 ± 2.0 % 64.2 ± 1.9 % 62.1 ± 1.8 % 52.1 ± 2.2 % 62.2 ± 1.2 % 63.0 ± 1.9 % 62.3 ± 1.5 %

46.4 ± 2.4 % 47.2 ± 2.0 % 43.1 ± 2.5 % 36.4 ± 2.0 % 43.3 ± 1.1 % 44.4 ± 2.1 % 44.1 ± 1.6 %

45.8 ± 2.4 % 46.7 ± 1.8 % 42.6 ± 2.5 % 36.0 ± 1.9 % 42.9 ± 1.0 % 43.9 ± 2.1 % 43.7 ± 1.6 %

FedAvg with known pti ’s MIFA (memory aided) FedVARP (memory aided)

86.3 ± 1.0 % 84.2 ± 0.4 % 84.5 ± 0.2 %

86.0 ± 1.0 % 84.1 ± 0.4 % 84.3 ± 0.1 %

69.1 ± 1.2 % 66.6 ± 0.8 % 67.4 ± 0.2 %

67.3 ± 1.3 % 65.5 ± 0.6 % 66.0 ± 0.3 %

47.9 ± 1.5 % 47.4 ± 0.5 % 47.7 ± 0.1 %

47.4 ± 1.1 % 46.9 ± 0.4 % 47.1 ± 0.2 %

from the unavailable clients. Although FedSWE brings in staleness due to implicit gossiping, our results in Section 7.1 for k ≥ 0 and Table 7 in Appendix H for k = 0 indicate that there is no significant slowdown for FedSWE when compared to the baseline algorithms. Furthermore, FedSWE attains competitive or even better performance than FedAvg with known probability, yet completely unknown to the underlying dynamics in client unavailability.

8 Conclusion In this paper, we have shown that the significant impacts of heterogeneous and non-stationary client unavailability on learning performance through FedAvg. To address this, we have proposed an algorithm FedSWE, which provably converges to a stationary point of the global objective by adaptively echoing clients’ local improvements, by interpolating updates across rounds via a global moving average, and by evenly diffusing local updates through implicit gossiping. Notably, it achieves the desired linear speedup property in certain special cases. Experiments have validated the superiority of FedSWE over state-of-the-art algorithms under diversified non-stationary dynamics. Future work will investigate how to relax the assumption of independence in client availability.

Efficient and Unbiased Federated Learning

Acknowledgments and Disclosure of Funding We gratefully acknowledge the support from the National Science Foundation under grants 2106891, 2107062, and the National Science Foundation CAREER award under grant 2340482. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the National Science Foundation or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.

References Kwangjun Ahn and Ashok Cutkosky. Adam with model exponential moving average is effective for nonconvex optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum? id=v416YLOQuU. Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. arXiv preprint arXiv:2302.01772, 2023. Dmitrii Avdiukhin and Shiva Kasiviswanathan. Federated learning under arbitrary communication patterns. In International Conference on Machine Learning, pages 425–435. PMLR, 2021. Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečnỳ, Stefano Mazzocchi, Brendan McMahan, et al. Towards federated learning at scale: System design. Proceedings of machine learning and systems, 1:374–388, 2019. Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Gossip algorithms: Design, analysis and applications. In Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., volume 3, pages 1653–1664. IEEE, 2005. Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, 52(6):2508–2530, 2006. Jin-Hua Chen, Min-Rong Chen, Guo-Qiang Zeng, and Jia-Si Weng. Bdfl: a byzantinefault-tolerance decentralized federated learning method for autonomous vehicle. IEEE Transactions on Vehicular Technology, 70(9):8639–8652, 2021. Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for federated learning. Transactions on Machine Learning Research, 2022. ISSN 2835-8856. URL https://openreview.net/forum?id=8GvRCWKHIL. Ziheng Cheng, Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=TdhkAcXkRi. 29

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Towards understanding biased client selection in federated learning. In International Conference on Artificial Intelligence and Statistics, pages 10351–10375. PMLR, 2022. Yae Jee Cho, Pranay Sharma, Gauri Joshi, Zheng Xu, Satyen Kale, and Tong Zhang. On the convergence of federated averaging with cyclic client participation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 5677–5721. PMLR, 23–29 Jul 2023a. Yae Jee Cho, Jianyu Wang, Tarun Chirvolu, and Gauri Joshi. Communication-efficient and model-heterogeneous personalized federated learning via clustered knowledge transfer. IEEE Journal of Selected Topics in Signal Processing, 2023b. Michael Crawshaw and Mingrui Liu. Federated learning under periodic client participation and heterogeneous data: A new communication-efficient algorithm and analysis. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. Luke N Darlow, Elliot J Crowley, Antreas Antoniou, and Amos J Storkey. Cinic-10 is not imagenet or cifar-10. arXiv preprint arXiv:1810.03505, 2018. Morris H DeGroot. Reaching a consensus. Journal of the American Statistical association, 69(345):118–121, 1974. Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang. Fast federated learning in the presence of arbitrary device unavailability. Advances in Neural Information Processing Systems, 34:12052–12064, 2021. Allan Gut. Probability: a graduate course, volume 200. Springer, 2006. John Hajnal and MS Bartlett. Weak ergodicity in non-homogeneous markov chains. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 54, pages 233– 246. Cambridge Univ Press, 1958. Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification, 2019. Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=Xm9iN3UsdpH. Divyansh Jhunjhunwala, Pranay Sharma, Aushim Nagarkatti, and Gauri Joshi. Fedvarp: Tackling the variance due to partial client participation in federated learning. In Uncertainty in Artificial Intelligence, pages 906–916. PMLR, 2022. Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel 30

Efficient and Unbiased Federated Learning

Cummings, Rafael G. L. D’Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends® in Machine Learning, 14 (1–2):1–210, 2021. Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132–5143. PMLR, 2020. Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. In International Conference on Learning Representations. PMLR, 2022. David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 482–491. IEEE, 2003. Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381–5393. PMLR, 2020. Anastasiia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous sgd for distributed and federated learning. Advances in Neural Information Processing Systems, 35:17202–17215, 2022. Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assumptions. Advances in Neural Information Processing Systems, 36:52166–52196, 2023. Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy. Feddane: A federated newton-type method. In 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pages 1227–1231. IEEE, 2019. Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429–450, 2020a. Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2020b. URL https://openreview.net/forum?id=HJxNAnVtDS. 31

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996. ISBN 9780080504704. Connor J. McLaughlin and Lili Su. Personalized federated learning via feature distribution adaptation. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 77038–77059. Curran Associates, Inc., 2024. URL https://proceedings.neurips.cc/paper_files/paper/2024/file/ 8ce6c5450ccddbe6adee4b3749893587-Paper-Conference.pdf. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017. Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake E Woodworth. Asynchronous sgd beats minibatch sgd under arbitrary delays. Advances in Neural Information Processing Systems, 35:420–433, 2022. Angelia Nedić and Alex Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60(3):601–615, 2014. Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61, 2009. Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597–2633, 2017. Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communicationcomputation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5): 953–976, 2018. Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011. URL http: //ufldl.stanford.edu/housenumbers/nips2011_housenumbers.pdf. John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. In International Conference on Artificial Intelligence and Statistics, pages 3581–3607. PMLR, 2022. Thien Duc Nguyen, Samuel Marchal, Markus Miettinen, Hossein Fereidooni, N Asokan, and Ahmad-Reza Sadeghi. Dı̈ot: A federated self-learning anomaly detection system for iot. 32

Efficient and Unbiased Federated Learning

In 2019 IEEE 39th International conference on distributed computing systems (ICDCS), pages 756–767. IEEE, 2019. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019. Muzi Peng, Jiangwei Wang, Dongjin Song, Fei Miao, and Lili Su. Privacy-preserving and uncertainty-aware federated trajectory prediction for connected autonomous vehicles. In The 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2023). IEEE/RSJ, 2023. Jake Perazzone, Shiqiang Wang, Mingyue Ji, and Kevin S Chan. Communication-efficient device scheduling for federated learning using stochastic optimization. In IEEE INFOCOM 2022-IEEE Conference on Computer Communications, pages 1449–1458. IEEE, 2022. Swaroop Ramaswamy, Rajiv Mathews, Kanishka Rao, and Françoise Beaufays. Federated learning for emoji prediction in a mobile keyboard. arXiv preprint arXiv:1906.04329, 2019. Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv:1904.09237, 2019. Mónica Ribero, Haris Vikalo, and Gustavo De Veciana. Federated learning under intermittent client availability and time-varying communication constraints. IEEE Journal of Selected Topics in Signal Processing, 17(1):98–111, 2022. Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, and Carlee Joe-Wong. Towards flexible device participation in federated learning. In International Conference on Artificial Intelligence and Statistics, pages 3403–3411. PMLR, 2021. Devavrat Shah et al. Gossip algorithms. Foundations and Trends® in Networking, 3(1): 1–125, 2009. Artin Spiridonoff, Alex Olshevsky, and Ioannis Ch Paschalidis. Robust asynchronous stochastic gradient-push: Asymptotically optimal and network-independent performance for strongly convex functions. Journal of Machine Learning Research, 21(58), 2020. Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.09767, 2018. Zhenyu Sun, ziyang zhang, Zheng Xu, Gauri Joshi, Pranay Sharma, and Ermin Wei. Debiasing federated learning with correlated client participation. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview. net/forum?id=9h45qxXEx0. Mohammad Taha Toghani and César A Uribe. Unbounded gradients in federated learning with buffered asynchronous aggregation. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1–8. IEEE, 2022. 33

Xiang, Ioannidis, Yeh, Joe-Wong and Su

David Tse and Pramod Viswanath. Fundamentals of wireless communication. Cambridge university press, 2005. Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of local-update sgd algorithms. The Journal of Machine Learning Research, 22 (1):9709–9758, 2021. Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:7611–7623, 2020. Jianyu Wang, Anit Kumar Sahu, Gauri Joshi, and Soummya Kar. Matcha: A matchingbased link scheduling strategy to speed up distributed optimization. IEEE Transactions on Signal Processing, 70:5208–5221, 2022. Shiqiang Wang and Mingyue Ji. A unified analysis of federated learning with arbitrary client participation. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https: //openreview.net/forum?id=qSs7C7c4G8D. Shiqiang Wang and Mingyue Ji. A lightweight method for tackling unknown participation statistics in federated averaging. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=ZKEuFKfCKA. Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. IEEE journal on selected areas in communications, 37(6):1205–1221, 2019. Ming Wen, Chengchang Liu, and Yuedong Xu. Communication efficient distributed newton method over unreliable networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 15832–15840, 2024. Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong, and Lili Su. Towards bias correction of fedavg over nonuniform and time-varying communications. In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 6719–6724, 2023. doi: 10.1109/CDC49753.2023.10383258. Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong, and Lili Su. Efficient federated learning against heterogeneous and non-stationary client unavailability. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong, and Lili Su. Empowering federated learning with implicit gossiping: Mitigating connection unreliability amidst unknown and arbitrary dynamics. IEEE Transactions on Signal Processing, 73:766–780, 2025. doi: 10.1109/TSP.2025.3526782. Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint arXiv:1903.03934, 2019. 34

Efficient and Unbiased Federated Learning

Yikai Yan, Chaoyue Niu, Yucheng Ding, Zhenzhe Zheng, Shaojie Tang, Qinya Li, Fan Wu, Chengfei Lyu, Yanghe Feng, and Guihai Chen. Federated optimization under intermittent client availability. INFORMS Journal on Computing, 2023. Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprint arXiv:2101.11203, 2021. Haibo Yang, Xin Zhang, Prashant Khanduri, and Jia Liu. Anarchic federated learning. In International Conference on Machine Learning, pages 25331–25363. PMLR, 2022. Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions. arXiv preprint arXiv:1812.02903, 2018. Hao Ye, Le Liang, and Geoffrey Ye Li. Decentralized federated learning with unreliable communications. IEEE Journal of Selected Topics in Signal Processing, 16(3):487–500, 2022. doi: 10.1109/JSTSP.2022.3152445. Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pages 7184–7193. PMLR, 2019a. Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5693–5700, 2019b. Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835–1854, 2016. Xiaotong Yuan and Ping Li. On convergence of fedprox: Local dissimilarity invariant bounds, non-smoothness and beyond. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=_33ynl9VgCX. Tengchan Zeng, Omid Semiari, Mingzhe Chen, Walid Saad, and Mehdi Bennis. Federated learning on the road autonomous controller design for connected and autonomous vehicles. IEEE Transactions on Wireless Communications, 21(12):10407–10423, 2022. Chen Zhu, Zheng Xu, Mingqing Chen, Jakub Konečnỳ, Andrew Hard, and Tom Goldstein. Diurnal or nocturnal? federated learning of multi-branch networks from periodically shifting distributions. In International Conference on Learning Representations, 2022.

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Appendices Here, we provide an overview of the Appendices. In particular, the proofs of the main results are presented and backed by supporting lemmas and propositions. A Nomenclature

B Useful Inequalities

C Descent Lemma (Lemma 7) C.1 Multi-step perturbation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 Descent lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39 39 41

D Intermediate Results D.1 Bounding local and global dissimilarity . . . . . . . . . . . . . . . . . . . . . D.2 Weight re-equalization (Proposition 2) . . . . . . . . . . . . . . . . . . . . . D.3 Unavailable statistics (Lemma 5) . . . . . . . . . . . . . . . . . . . . . . . . D.4 Auxiliary sequence construction and properties (Proposition 8) . . . . . . . D.5 Consensus error of the auxiliary sequence . . . . . . . . . . . . . . . . . . . D.6 Spectral norm upper bound (Lemma 9) . . . . . . . . . . . . . . . . . . . .

46 46 47 48 49 51 57

E Convergence Error of z̄ t (Theorem 11)

F Convergence Rate of x̄t (Corollary 12) F.1 Convergence error of Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . . F.2 Convergence rate of Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . .

67 67 68

G Additional Results and Interpretations G.1 Consensus error of Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . . . G.2 Orders of the asymptotic rates . . . . . . . . . . . . . . . . . . . . . . . . .

68 68 69

H Numerical Experiments H.1 Experimental setups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.2 Non-stationary client unavailability dynamics . . . . . . . . . . . . . . . . . H.3 Additional results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69 69 71 72

Efficient and Unbiased Federated Learning

Appendix A. Nomenclature In this section, we provide the notations and nomenclatures used throughout our proofs for a comprehensive presentation.

Table 3: Nomenclature table Notation(s)

Definition

The set of active clients in round t.

A doubly stochastic matrix to capture the information mixing error. Its definition can be found in (9).

pti

The probability that a client i becomes available in round t.

τi (t)

τi (t) ≜ sup{t′ | t′ < t, i ∈ At } defines client i’s most recent active round. In particular, τi (0) = −1 for all i ∈ [m].

xti

The real model at client i at the beginning of round t in Algorithm 1.

zit

The auxiliary model at client i at the beginning of round t. Refer to Definition 4 for more details. The sequence is for analysis only and is not computed by any clients.

The aggregated real model at the end of round t−1 in Algorithm 1.

The auxiliary model at the end of round t − 1.

t† xt† i , zi

The real model of an active client i, and auxiliary model of an active client i after s-step local computation in round t, respectively. Refer to Algorithm 1 for more details.

(t,r)

′

The real model at client i after r-step local computation.

x̄t , z̄ t

The real and auxiliary model mean over all clients in a distributed system and in round t, respectively.

Fi (x)

The local objective function at client i, which is assumed to be non-convex.

F (x)

The Pm global objective function defined in (1): i=1 Fi (x)/m.

∇ℓi (x)

The local stochastic gradient function at client i taken with respect to x.

∇Fi (x)

The local true gradient function at client i taken with respect to x.

Client i’s local data distribution.

ξi

An independent stochastic sample drawn from client i’s local distribution Di .

F (x)

≜

Xiang, Ioannidis, Yeh, Joe-Wong and Su

δ Pδ , P

Table 4: Variable table An absolute constant that is the lower bound on the client unavailability. The period in Assumption 1.

Lipschitz constant in Assumption 2.

σ2

The upper bound of the stochastic gradient variance.

(β, ζ)

Parameters that capture the averaged gradient dissimilarity between global and local objectives.

The spectral norm of a stochastic matrix in expectation.

The number of local computation steps.

The interpolation coefficient in the global moving average procedure.

The number of clients in the federated learning system.

M = m + k.

Appendix B. Useful Inequalities For completeness and for ease of exposition, we present some common inequalities that will be frequently used in our proofs. The followings hold for any ai ∈ Rd and any i ∈ [m]. 1. Jensen’s inequality. m

1 X ai m i=1

1 X ∥ai ∥22 ≤ m

and

i=1

m X i=1

≤m

ai 2

m X

∥ai ∥22 .

(33)

i=1

2. Young’s inequality (a.k.a. Peter-Paul inequality).

⟨a1 , a2 ⟩ ≤

∥a1 ∥22 ϵ ∥a2 ∥22 + , 2ϵ 2

for any ϵ > 0.

(34)

Equivalently, we have ∥a1 + a2 ∥22 = ∥a1 ∥22 + ∥a2 ∥22 + 2 ⟨a1 , a2 ⟩ 1 ≤ 1+ ∥a1 ∥22 + (1 + ϵ) ∥a2 ∥22 , ϵ 38

for any ϵ > 0.

(35)

Efficient and Unbiased Federated Learning

3. Smoothness corollary. Given Assumption 2, it holds that Z 1

∇F (a2 + τ (a1 − a2 ))dτ Z 1 ⟨a1 − a2 , ∇F (a2 + τ (a1 − a2 )) − ∇F (a2 )⟩ dτ = ⟨∇F (a2 ), a1 − a2 ⟩ + 0 Z 1 (a) τ ∥a1 − a2 ∥2 ∥(a1 − a2 )∥2 dτ ≤ ⟨∇F (a2 ), a1 − a2 ⟩ + L

F (a1 ) − F (a2 ) =

a1 − a2 ,

L ≤ ⟨∇F (a2 ), a1 − a2 ⟩ + ∥a1 − a2 ∥22 , 2

(36)

where (a) follows from Cauchy-Schwartz inequality and Assumption 2.

Appendix C. Descent Lemma (Lemma 7) In this section, we first present a bound on multi-step local computation. Then, we apply the bound to the analysis of descent lemma. C.1 Multi-step perturbation Lemma 15. Suppose that Assumption 2 and Assumption 3 hold. For each regular client i ∈ R, we have  E

s−1 X



2 (t,r)

∇Fi (xi

) − ∇Fi (xti )

r=0

F t  ≤ 5ηl2 s3 L2 σ 2 + 20ηl2 s4 L2 ∇Fi (xti ) 2 2

Proof of Lemma 15 The proof shares a similar road map to (Yang et al., 2021, Lemma 2 2), but the objective is instead to show an upper bound with respect to ∇Fi (xti ) 2 . It holds that  E

s−1 X r=0

2 (t,r) ∇Fi (xi ) − ∇Fi (xti )



(a)

≤s

s−1 X 2 (t,r) t t E ∇Fi (xi ) − ∇Fi (xi ) F 2

r=0

2 (b)

≤ sL

s−1 X r=0

2 (t,r) xi − xti 2

(37)

where inequality (a) holds because of Jensen’s inequality, inequality (b) holds because (t,r) (t,k) of Assumption 2. It remains to bound E[∥xi − xti ∥2 | F t ]. In what follows, we use ∇ℓi 39

Xiang, Ioannidis, Yeh, Joe-Wong and Su

(t,k)

to denote ∇ℓi (xi E

2 (t,r) xi − xti 2

(t,k)

) and ∇Fi

(t,k)

as ∇Fi (xi

), respectively, for ease of presentation.

(t,r−1) (t,r−1) 2 xi − xti − ηl ∇ℓi 2

(t,r−1) (t,r−1) ∇ℓi − ∇Fi

(t,r−1) + xi − xti − ηl

(t,r−1) ∇Fi − ∇Fit + ∇Fit

−ηl F 2 2 (c) 2 (t,r−1) (t,r−1) 2 (t,r−1) (t,r−1) t t t t t = ηl E ∇ℓi − ∇Fi F + E xi − xi − ηl ∇Fi − ∇Fi + ∇Fi F 2 2 (d) (t,r−1) (t,r−1) 2 2 t ≤ ηl E ∇ℓi − ∇Fi F 2 2 2 1 (t,r−1) (t,r−1) 2 t t t t t E xi − xi F + 2sηl E ∇Fi − ∇Fi + ∇Fi F + 1+ 2s − 1 2 2 (t,r−1) (t,r−1) 2 − ∇Fi Ft ≤ ηl2 E ∇ℓi 2 2 2 1 2 (t,r−1) (t,r−1) t t t t 2 + 1+ − ∇Fi F + 4sηl2 ∇Fit 2 E xi − xi F + 4sηl E ∇Fi 2s − 1 2 2 =E

(e)

≤ ηl2 σ 2 + 4sηl2 ∇Fit 2 2 2 1 (t,r−1) (t,r−1) t t 2 2 t t + 1+ E xi − xi F + 4sL ηl E xi − xi F 2s − 1 2 2 2 1 2 (t,r−1) + 4sL2 ηl2 E xi − xti Ft , = ηl2 σ 2 + 4sηl2 ∇Fit 2 + 1 + 2s − 1 2 (t,k)

(t,r)

where equality (c) holds because ∇ℓi is an unbiased estimator of ∇Fi , inequality (d) holds because of Young’s inequality, inequality (e) holds because of Assumption 2. 1 , it holds that By ηl ≤ 4sL 1 1 1 2 + 4sL2 ηl2 ≤ + ≤ . 2s − 1 2s − 1 4s 2s − 1 Unroll the recursion, we have E

(t,r)

− xti

2 2

X r−1 Ft ≤ 1+ k=0

2 2s − 1

ηl2 σ 2 + 4sηl2 ∇Fit 2

s−1 X ≤ 1+

k 2 2 ηl2 σ 2 + 4sηl2 ∇Fit 2 2s − 1 k=0 " # s− 1 1 2 2 2s − 1 2 2 2 = 1+ − 1 ηl2 σ 2 + 4sηl2 ∇Fit 2 1+ 2 2s − 1 2s − 1 i (f ) 1 h√ 2 ≤ s− 3e − 1 ηl2 σ 2 + 4sηl2 ∇Fit 2 2 (g)

≤ 5sηl2 σ 2 + 20s2 ηl2 ∇Fit 2 , 40

Efficient and Unbiased Federated Learning

where inequality (f ) holds because of (1 + 1/x)x < exp(1), inequality (g) holds because of √ 3 exp(1) − 1 < 5. Plug it back into (37), we have the desired result  E

s−1 X



2 (t,r)

∇Fi (xi

) − ∇Fi (xti )

r=0

F t  ≤ 5ηl2 s3 L2 σ 2 + 20ηl2 s4 L2 ∇Fi (xti ) 2 . 2

C.2 Descent lemma 1 P Recall that we have defined an auxiliary global objective Fe(x) = M i∈R∪V Fi (x). Proof of Lemma 7 By Assumption 2 and inequality (36), we have

E L D 2 Fe(z̄ t+1 ) − Fe(z̄ t ) ≤ ∇Fe(z̄ t ), z̄ t+1 − z̄ t + z̄ t+1 − z̄ t 2 . 2 | {z } | {z } (A)

(B)

Recall that M ≜ m + k = |R ∪ V|. The one-round innovation of z̄ can be rewritten as 1 X 1 X t† 1 X t+1 zi − zit + zi − zit zit+1 − zit + M M M i∈V i∈At i∈R\At X X 1 1 = zit† − zit + zit+1 − zit M M i∈At i∈R\At   m t−1 s−1 X X 1 X (t,r) (t,r) = 1{i∈At } ηl ηg s ∇Fi (xki ) − ηl ηg (t − τi (t)) ∇ℓi (xi ; ξi ) M

z̄ t+1 − z̄ t =

i=1

r=0

k=τi (t)+1

−

ηl ηg s X 1{i∈R\At } ∇Fi (xti ) M i=1

m X

1 = M

(a)

−

i=1

m ηl ηg s X

(b) ηl ηg

1{i∈At } (t − τi (t))

−

i=1 m ηl ηg X

ηl ηg s M

s−1 X

(t,r)

∇Fi (xi

r=0 s−1 X

1{i∈At } (t − τi (t))

i=1 m X

s−1

i=1

r=0

X 1 X (t,r) (t,r) 1{i∈At } ηl ηg (t − τi (t)) ∇ℓi (xi ; ξi ) M

1{i∈R\At } ∇Fi (xti )

i=1 m X

M +

1{i∈At } ηl ηg s(t − 1 − τi (t))∇Fi (xti ) −

(t,r)

; ξi

(t,r)

) − ∇ℓi (xi

∇Fi (xti ) − ∇Fi (xi

r=0

∇Fi (xti ),

i=1

)

(t,r)

)

Xiang, Ioannidis, Yeh, Joe-Wong and Su

where equality (a) using the fact that xki = xti for all k such that τi (t) + 1 ≤ k ≤ t, (t,r) and equality (b) is obtained by adding and subtracting ∇ℓi (xti ; ξi ) and by the fact that 1{i∈At } + 1{i∈R\At } = 1 since a client i ∈ V does not update gradients. Bounding (A). D E (A) = ∇Fe(z̄ t ), z̄ t+1 − z̄ t * + m t−1 s−1 X X X 1 (t,r) (t,r) (t,r) t = ηl ηg ∇Fe(z̄ ), 1{i∈At } 1{τi (t)=p} (t − p) ∇Fi (xi ) − ∇ℓi (xi ; ξi ) M p=−1 r=0 i=1 {z } | (A.I)

m X

t−1 X

ηl ηg + 1{i∈At } 1{τi (t)=p} M p=−1 i=1 |

* t

∇Fe(z̄ ), (t − p)

s−1 X

(t,r) ∇Fi (xti ) − ∇Fi (xi )

r=0

}

(A.II)

* + m m E X ηl ηg s X D e t 1 + ∇F (z̄ ), ∇Fi (zit ) − ∇Fi (xti ) − ηl ηg s ∇Fe(z̄ t ), ∇Fi (zit ) . M M i=1 i=1 {z } | {z } | (A.III)

(A.IV)

Bounding (A.I) h i E (A.I) F t " "* (a)

= η l ηg E E

s−1 t−1 m X X 1 X (t,r) (t,r) (t,r) 1{τi (t)=p} (t − p) ∇Fi (xi ) − ∇ℓi (xi ; ξi ) 1{i∈At } ∇Fe(z̄ ), M i=1 r=0 p=−1

# (t,r) xi , F t

# F

D = ηl ηg ∇Fe(z̄ t ),

(b)

t−1 s−1 h h m i i i X X 1 X h (t,r) (t,r) (t,r) (t,r) 1{τi (t)=p} (t − p) E E ∇Fi (xi ) − ∇ℓi (xi ; ξi ) xi , F t F t E 1{i∈At } F t M i=1 p=−1 r=0

= 0,

where equality (a) holds because of the law of total expectation, equality (b) holds because 1{i∈At } is by definition independent of others and Assumption 3. Bounding (A.II) m (c) η η X l g

(A.II) ≤

M ηl ηg s 12M

1{i∈At }

 s ∇Fe(z̄ t ) + 12 2 2

1{τi (t)=p} 

p=−1

i=1 m X

t−1 X

1{i∈At } ∇Fe(z̄ t )

i=1

3(t − p)2 s

s−1 X

r=0

p=−1

r=0

)  2

m t−1 s−1 X ηl ηg X 3(t − p)2 X (t,r) + 1{i∈At } 1{τi (t)=p} ∇Fi (xti ) − ∇Fi (xi ) M s i=1

(t,r)

∇Fi (xti ) − ∇Fi (xi

, 2



Efficient and Unbiased Federated Learning

where inequality (c) holds because of Young’s inequality. We further have: m t−1 i (d) η η s 2 15ηg ηl3 s2 L2 σ 2 X X l g t e E (A.II) F ≤ ∇F (z̄ ) + 1{τi (t)=p} (t − p)2 12 M 2

i=1 p=−1

m t−1 60ηg ηl3 s3 L2 X X

1{τi (t)=p} (t − p)2 ∇Fi (xti ) 2

i=1 p=−1 m

t−1

2 15ηg ηl3 s2 L2 σ 2 X X ηl ηg s ∇Fe(z̄ t ) + 1{τi (t)=p} (t − p)2 = 12 M 2 i=1 p=−1

m t−1 60ηg ηl3 s3 L2 X X

1{τi (t)=p} (t − p)2 ∇Fi (xp+1 ) i

i=1 p=−1

2 2

where inequality (d) holds because of Lemma 15, the last equality using the fact that xki = xti for all k such that τi (t) + 1 ≤ k ≤ t. Bounding (A.III). (A.III) =

i=1

E (e) η η s 2 ηl ηg s X D e t 3ηl ηg sL2 X t 2 l g ∇F (z̄ ), ∇Fi (zit ) − ∇Fi (xti ) ≤ zi − xti 2 , ∇Fe(z̄ t ) + M 12 M 2

where inequality (e) follows from Young’s inequality and Assumption 2. It holds that, m i ηη s h 2 3ηl ηg sL2 X t 2 l g E (A.III) F t ≤ zi − xti 2 . ∇Fe(z̄ t ) + 12 M 2 i=1

Bounding (A.IV)   2 2 m m X X 2 ηl ηg s  1 1 (A.IV) = ∇Fe(z̄ t ) + ∇Fi (zit ) − ∇Fe(z̄ t ) − ∇Fi (zit )  , 2 M M 2 i=1

i=1

where the equality follows from the identity in Appendix B (3). It holds that   2 2 m m m h i ηη s X X X 2 1 1 1 l g  E (A.IV) F t = ∇Fe(z̄ t ) + ∇Fi (zit ) − ∇Fi (z̄ t ) − ∇Fi (zit )  2 M M M 2 i=1 i=1 i=1 2 2   2 m m 2 ηl ηg s  1 X L2 X t 2 ≥ ∇Fe(z̄ t ) + ∇Fi (zit ) − z̄ − zit 2  , 2 M M 2 i=1

i=1

where the first equality holds because a client i ∈ V does not update gradients, and it holds that m 1 X 1 X 1 X t t t e ∇F (z̄ ) ≜ ∇Fi (z̄ ) + ∇Fi (z̄ ) = ∇Fi (z̄ t ), M M M i∈R

i∈V

i=1

Xiang, Ioannidis, Yeh, Joe-Wong and Su

where we use the convention that ∇Fi (z̄ t ) = 0 for i ∈ V. Putting (A) together, m t−1 h i 2 15ηg ηl3 s2 L2 σ 2 X X ηl ηg s E (A) F t ≤ − ∇Fe(z̄ t ) + 1{τi (t)=p} (t − p)2 3 M 2 i=1 p=−1

m 3ηl ηg sL2 X

ηl ηg s 1 − 2 M

xti − zit 2 +

i=1 m X i=1

∇Fi (zit ) 2

m ηl ηg sL2 X

z̄ t − zit 2

i=1 m

t−1

2 60ηg ηl3 s3 L2 X X + 1{τi (t)=p} (t − p)2 ∇Fi (xp+1 ) . i M 2 i=1 p=−1

Bounding (B). m s−1 2 X ηl2 ηg2 X (t,r) (t,r) (t,r) (B) ≤ 2L 2 ∇Fi (xi ) − ∇ℓi (xi ; ξi ) 1{i∈At } (t − τi (t)) M r=0 i=1 | {z }2 (B.I)

m s−1 X η 2 ηg2 X (t,r) + 2L l 2 m 1{i∈At } (t − τi (t))2 ∇Fi (xti ) − ∇Fi (xi ) M r=0 i=1 {z }2 | (B.II)

m m η 2 ηg2 s2 X 1 X 2 + 2L l 2 m ∇Fi (xti ) − ∇Fi (zit ) 2 + 2Lηl2 ηg2 s2 ∇Fi (zit ) M M i=1 i=1 | {z } | {z }2 (B.III)

Bounding (B.I)

(B.IV)

Recall that δmax ≜ supi∈[m],t∈[T ] pti . It holds that,

h i E (B.I) F t m s−1 h i X ηl2 ηg2 X (t,r) (t,r) (t,r) (t,r) 2 t 2 t t = 2L 2 E 1{i∈At } F (t − τi (t)) E E ∇Fi (xi ) − ∇ℓi (xi ; ξi ) xi , F F M 2

(f )

r=0 i=1 m t−1 2 2 2 (g) 2η η sLδmax σ X X g ≤ l 1{τi (t)=p} (t − p)2 , M2 i=1 p=−1

where equality (f ) holds by the law of total expectation and by the independence of event {i ∈ At }, inequality (g) holds because of Assumption 3 and by definition pti ≤ δmax . 44

Efficient and Unbiased Federated Learning

Bounding (B.II)

We have,

m X t−1 h i η 2 ηg2 X E (B.II) F t ≤ 2L l 1{τi (t)=p} (t − p)2 5ηl2 s3 L2 σ 2 M i=1 p=−1

m t−1 X η 2 ηg2 X 2 + 2L l 1{τi (t)=p} (t − p)2 20ηl2 s4 L2 ∇Fi (xti ) 2 M p=−1

i=1

m X t−1 10ηg2 ηl4 s3 L3 σ 2 X

1{τi (t)=p} (t − p)2

i=1 p=−1

m X t−1 2 40ηg2 ηl4 s4 L3 X + ) , 1{τi (t)=p} (t − p)2 ∇Fi (xp+1 i M 2 i=1 p=−1

where the last equality using the fact that xki = xti for all k such that τi (t) + 1 ≤ k ≤ t.

Bounding (B.III).

E (B.III) F

m 2ηl2 ηg2 s2 L3 X 2 ≤ xti − zit 2 . M i=1

Putting (B) together, we get

E (B) F

t−1 m X t−1 2ηl2 ηg2 sLσ 2 X 10ηg2 ηl4 s3 L3 σ 2 X 2 1{τi (t)=p} (t − p) + 1{τi (t)=p} (t − p)2 ≤ M2 M p=−1

m X t−1 40ηg2 ηl4 s4 L3 X

i=1 p=−1

1{τi (t)=p} (t − p)2 ∇Fi (xp+1 ) i

i=1 p=−1

2 2

m m 2ηl2 ηg2 s2 L3 X 1 X t t 2 2 2 2 + xi − zi 2 + 2Lηl ηg s ∇Fi (zit ) M M i=1

i=1

. 2

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Now, everything: h i 2 ηl ηg s ∇Fe(z̄ t ) E Fe(z̄ t+1 ) − Fe(z̄ t ) F t ≤ − 3 2 2

ηl ηg s 1 X − (1 − 4Lηl ηg s) ∇Fi (zit ) 2 M

i=1 2 m t−1 2 2 2 2ηl ηg sLδmax σ X X + 1{τi (t)=p} (t − p)2 M2 i=1 p=−1 m

t−1

5ηg ηl3 s2 L2 (3 + 2ηg ηl sL) σ 2 X X 1{τi (t)=p} (t − p)2 M i=1 p=−1

m 1 X

+ ηl ηg sL (3 + 2ηl ηg sL)

+ 20ηg ηl3 s3 L2 (3 + 2ηg ηl sL)

i=1

1 M

ηl ηg sL 2 xti − zit 2 + 2M m X t−1 X

zit − z̄ t 2

i=1

1{τi (t)=p} (t − p)2 ∇Fi (xp+1 ) i

i=1 p=−1 m

≤−

m 2 X

t−1

2 2η 2 ηg2 sLδmax σ 2 X X ηl ηg s ∇Fe(z̄ t ) + l 1{τi (t)=p} (t − p)2 3 M2 2 i=1 p=−1

t−1

17ηg ηl3 s2 L2 σ 2 X X 1{τi (t)=p} (t − p)2 M i=1 p=−1

+ 4ηl ηg sL2

ηl ηg sL2 X t 1 X t 2 2 xi − zit 2 + zi − z̄ t 2 M 2M i=1

+ 65ηg ηl3 s3 L2

1 M

i=1

m X t−1 X

1{τi (t)=p} (t − p)2 ∇Fi (xp+1 ) i

i=1 p=−1

1 and that where the last inequality holds because ηl ηg ≤ 8sL

2 2

1 Pm t 2 i=1 ∇Fi (zi ) 2 ≥ 0. M

Appendix D. Intermediate Results In this section, we present the intermediate results that serve as handy tools in building up our proofs afterwards. D.1 Bounding local and global dissimilarity Proposition 16. For any t, it holds that m

i=1

2 1 X 3L2 X t 3M 2 3mζ 2 2 2 ∇Fi (zit ) 2 ≤ zi − z̄ t 2 + β + 1 ∇Fe(z̄ t ) + . M M m M 2

2 2

Efficient and Unbiased Federated Learning

Proof of Proposition 16 m

1 X 1 X 2 2 ∇Fi (zit ) 2 = ∇Fi (zit ) − ∇Fi (z̄ t ) + ∇Fi (z̄ t ) − ∇F (z̄ t ) + ∇F (z̄ t ) 2 m m i=1

i=1

≤

m 3 X

3 2 ∇Fi (zit ) − ∇Fi (z̄ t ) 2 + m

zit − z̄ t 2 + 3 β 2 + 1

i=1 m (a) 3L2 X

≤

m X

∇Fi (z̄ t ) − ∇F (z̄ t ) 2 + 3 ∇F (z̄ t ) 2

i=1 2

∇F (z̄ t ) 2 + 3ζ 2 ,

i=1

where inequality (a) follows from Assumptions 2 and 4. It follows that m

i=1

2 3L2 X t 3M 2 1 X 3m 2 2 2 ∇Fi (zit ) 2 ≤ zi − z̄ t 2 + β + 1 ∇Fe(z̄ t ) + ζ , M M m M 2

e where the equality holds because ∇F (x) = M m ∇F (x).

D.2 Weight re-equalization (Proposition 2) Proof of Proposition 2 We show Proposition 2 by induction. P When T = 1 and i ∈ A0 , we have 0t=0 1{i∈At } (t − τi (t)) = 1{i∈A0 } (0 − τi (0)) = 1. Therefore, the base case holds. P K−1 . Next, The induction hypothesis is that K−1 t=0 1{i∈At } (t − τi (t)) = K holds for i ∈ A we focus on K + 1: K X

1{i∈At } (t − τi (t)) =

t=0

K−1 X

1{i∈At } (t − τi (t)) + 1{i∈AK } (K − τi (K)) .

(38)

t=0

Now, we have two cases: (a)

• Suppose i ∈ AK−1 , then we simply have τi (K) = K − 1. It follows that (38) = K + 1, where (a) follows from induction hypothesis. • Suppose i ∈ / AK−1 , K X t=0

(b)

1{i∈At } (t − τi (t)) =

τi (K)

1{i∈At } (t − τi (t)) + 1{i∈AK } (K − τi (K))

t=0

= τi (K) + 1 + (K − τi (K)) = K + 1, where (b) follows because 1{i∈At } = 0 for τi (K) ≤ t ≤ K − 1 and induction hypothesis Pτi (K) that t=0 1{i∈At } (t − τi (t)) = τi (K) + 1 for i ∈ Aτi (K) .

Xiang, Ioannidis, Yeh, Joe-Wong and Su

D.3 Unavailable statistics (Lemma 5) Proof of Lemma 5 E [t − τi (t)] = =

t X r=0 t X

P {t − τi (t) > r} t−1 Y

(39)

(1 − pri 1 ) = 1 +

t t−1 X Y

r=0 r1 =t−r

= 1 + lim

r=1 r1 =t−r

ℓP X

ℓ→∞

(1 − pri 1 ) ≤ 1 +

t−1 Y

∞ t−1 X Y

(1 − pri 1 )

r=1 r1 =t−r

(1 − pri 1 )

r=1 r1 =t−r

Let t0 ∈ {0, Pδ , 2Pδ , . . .}, it holds that t0 +P Yδ −1

(a) (1 − pti ) ≤

Pδ −

Pt0 +Pδ −1 t=t0

pti

!Pδ ≤ (1 − δ)Pδ ,

Pδ

t=t0

where inequality (a) holds because of AM-GM inequality. Also, it trivially holds that ′

l Y

(1 − pti ) ≤ 1,

t=l

where t0 ≤ l ≤ l′ ≤ t0 + Pδ − 1. In general, we have • When r ≥ Pδ , it holds that tY 0 −1

(1 − pri 1 ) ≤

r1 =t0 −r

⌊t0 /Pδ ⌋−1

(r0 +1)Pδ −1

r0 =(t0 −r)/Pδ

r1 =r0 Pδ

(1 − pri 1 ) ≤ (1 − δ)Pδ (t0 /Pδ −⌈(t0 −r)/Pδ ⌉) ≤ (1 − δ)r−Pδ .

• When r < Pδ , it holds that tY 0 −1

(1 − pri 1 ) ≤ 1.

r1 =t0 −r

Hence, tY 0 −1

(r−Pδ )1{r≥P }

(1 − pri 1 ) ≤ (1 − δ)

r1 =t0 −r

It holds for (39) that E [t − τi (t)] ≤ 1 +

∞ X

(1 − δ)

r=1

(r−Pδ )1{r≥P } δ

1 = Pδ + . δ

From (Gut, 2006, Theorem 12.3 (1)), we know that Z ∞ E [g(X)] = g(0) + g ′ (x)P {X > x} dx, 0

(40)

Efficient and Unbiased Federated Learning

where X is a non-negative random variable, and g a non-negative, strictly increasing, differentiable function. Therefore, ∞ h i (a) X (r−Pδ )1{r≥P } δ E (t − τi (t))2 ≤ 2 r (1 − δ) r=1

1−δ Pδ (Pδ − 1) Pδ + + 2 2 δ δ 1 1 = 2 ((Pδ − 1)δ + 1)2 + 2 (Pδ − 1)δ 2 + 1 , δ δ

≤2

(41)

where inequality (a) holds because of (40), For a neat presentation, we use (var) as a shorthand notation in the following proofs for the constant in (41).

D.4 Auxiliary sequence construction and properties (Proposition 8) Proposition 17. For any t ≥ 0, when i ∈ / At , it holds that xt+1 − zit+1 = ηl ηg s(t − τi (t + i τi (t+1)+1 t+1 = xt+1 , and z t+1 = xt+1 . 1))∇Fi (xi ); when i ∈ At , it holds that zit† = xt† i , z i i Proof of Proposition 17 The proof is divided into two parts: i ∈ / At and i ∈ At , When i ∈ / At .

It holds that  τ (t+1)+1

xt+1 − zit+1 = xi i i

τ (t+1)+1

− zi i

t X

− η l ηg s

 ∇Fi (xki )

k=τi (t+1)+1

 (a)

τ (t+1)+1

= xi i

τ (t+1)+1

− xi i

t X

− η l ηg s

 τ (t+1)+1 

∇Fi (xi i

)

k=τi (t+1)+1 τ (t+1)+1 = ηl ηg s(t − τi (t + 1))∇Fi (xi i ),

where equality (a) follows from Definition 4 for inactive clients. t++ t , then by the aggregation rules, When i ∈ At . Note that = xt++ for each i Pif zi t++ P i ∈ At++ t+1 t t we know x = 1/ A = 1/ A = z t+1 . Then, we know that i∈At xi i∈At zi xt+1 = zit+1 , ∀ i ∈ At . Hence, to show the Proposition, it is sufficient to show zit++ = xt++ i i holds for i ∈ At , which can be shown by induction. When t = 0,

(0,0) (0,s) (0,0) (0,s) zi0++ = zi0 + 0 − xi − xi = x0i − xi − xi = x0++ . i 49

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Thus, the base case holds. The induction hypothesis is that zit++ = xt++ , ∀ i ∈ At is true i for all t ≥ 0. Now, we focus on t + 1.

(t+1)++

t X

= zit+1 + ηl ηg s

(t+1,0) (t+1,s) ∇Fi (xki ) − (t + 1 − τi (t + 1)) xi − xi

k=τi (t+1)+1 τ (t+1)+1

= zit+1 + ηl ηg s(t − τi (t + 1))∇Fi (xi i (a)

τ (t+1)+1

= zi i

(t+1,0) (t+1,s) ) − (t + 1 − τi (t + 1)) xi − xi τ (t+1)+1

− ηl ηg s(t − τi (t + 1) − 1 + 1)∇Fi (xi i

)

τ (t+1)+1 (t+1,0) (t+1,s) + ηl ηg s(t − τi (t + 1))∇Fi (xi i ) − (t + 1 − τi (t + 1)) xi − xi τ (t+1)+1 (t+1,0) (t+1,s) = zi i − (t + 1 − τi (t + 1)) xi − xi (b) τi (t+1)+1 (t+1,0) (t+1,s) = xi − (t + 1 − τi (t + 1)) xi − xi (t+1)++

= xi

where equality (a) follows from the auxiliary updates zi , and equality (b) holds because of the induction hypothesis and the fact that τi (t + 1) < t + 1 and i ∈ Aτi (t+1) . Proof of Proposition 8 From Propositions 17, we have 2

xti − zit 2 ≤ ηl ηg s (t − τi (t) − 1) ∇Fi (xti ) 2 = ηl2 ηg2 s2

t−1 X

1{τi (t)=p} (t − p − 1)2 ∇Fi (xp+1 ) i

p=−1

2 2

Take expectation over all the randomness

h E

t−1 i X 2 2 (a) xti − zit 2 ≤ ηl2 ηg2 s2 E 1{τi (t)=p} (t − p − 1)2 E ∇Fi (xp+1 ) i 2

p=−1 (b)

≤ ηl2 ηg2 s2

t−1 X

(t − p − 1) P {τi (t) = p} · E

p=−1

∇Fi (zip+1 )

2 2

where inequality (a) follows because by definition 1{τi (t)=p} is independent of ∇Fi (xp+1 ) , i inequality (b) follows because xp+1 = zip+1 from Proposition 17. i 50

Efficient and Unbiased Federated Learning

T −1

i i 1 X 1 X h t 1 X 1 X h t 2 2 E xi − zit 2 = E xi − zit 2 T M T M t=0 t=0 i=1 i=1 T −1 m t−1 2 1 X 1 X X P {τi (t) = p} (t − p − 1)2 E ∇Fi (zip+1 ) = ηl2 ηg2 s2 T M 2 (c)

≤ ηl2 ηg2 s2

1 M

t=0

i=1 p=−1

m X

T −1 X

i=1

1 T

h E

∇Fi (zit ) 2

i h i E (t − τi (t))2

t=0

m T −1 i 1 X1 X h 2 2 2 2 ≤ ηl ηg s (var) E ∇Fi (zit ) 2 M T t=0 i=1 T −1 2 2 2 X 2 2 2 2 [(Pδ − 1)δ + 1] + (Pδ − 1)δ + 1 M (β + 1) 1 e(z̄ t ) E ∇ F ≤ 3ηl ηg s δ2 m T 2 t=0 2 2 2 mζ 2 2 2 [(Pδ − 1)δ + 1] + (Pδ − 1)δ + 1 + 3ηl ηg s δ2 M ! M T −1 i L2 X 1 X h t 2 + 3ηl2 ηg2 s2 E zi − z̄ t 2 , M T

(d)

i=1

t=0

where inequality (c) follows from re-indexing, inequality (d) from Lemma 5.

D.5 Consensus error of the auxiliary sequence Lemma 18 (Consensus error of zit ). Assuming that ηl ≤ δ/(20sL), and ηl ηg ≤ δ(1 − √ √ ρ)/(10sL( ρ + 1)), under Assumptions 2, 3 and 4, it holds that T −1 M i 32η 2 η 2 sPδ ((P − 1)δ + 1)2 + (P − 1)δ 2 + 1 mσ 2 1 XX h t δ δ l g t 2 E zi − z̄ 2 ≤ 2 2 MT (1 − ρk ) δ M t=0 i=1 TX −1 2 24ηl2 ηg2 s2 Pδ (β 2 + 1) ((Pδ − 1)δ + 1)2 + (Pδ − 1)δ 2 + 1 M 1 e(z̄ t ) + E ∇ F (1 − ρk )2 δ2 m T 2 t=0 2 24ηl2 ηg2 s2 Pδ [(Pδ − 1)δ + 1]2 + (Pδ − 1)δ 2 + 1 mζ + . (1 − ρk )2 δ2 M

Proof of Lemma 18 When t = 0, Z 0 = [z 0 , · · · , z 0 ], which immediately leads to Z 0 (I − J) = [z 0 , · · · , z 0 ] − [z 0 , · · · , z 0 ] = 0. For t ≥ 1, recall that W (t) is a doubly stochastic matrix to characterize the information e t in (42) captures the local parameter changes in each round. Specifically, mixture, and that G 51

Xiang, Ioannidis, Yeh, Joe-Wong and Su

for a client i ∈ R, it holds that " e t ≜ 1{i∈At } (t − τi (t)) G i

s−1 X

# (t,r) τ (t)+1 ∇ℓi (xi ) − s (t − 1 − τi (t)) ∇Fi (xi i )

r=0 τi (t)+1 + 1{i∈A ) / t } s∇Fi (xi s−1 X

= 1{i∈At } (t − τi (t))

(t,r)

∇ℓi (xi

) − ∇Fi (xti ) + s∇Fi (xti ),

(42)

r=0 τ (t)+1

where the last equality holds because xti = xi i

and re-grouping. It can be seen that

e t−1 W (t−1) . Z (t) = Z (t−1) − ηl ηg G Define n(t) = ⌊ Ptδ ⌋ − 1. For ease of presentation, we drop the variable t. We have t − 2Pδ < nPδ ≤ t − Pδ ; therefore, (n + 1)Pδ ≤ t < (n + 2)Pδ . Further, Pδ ≤ t − nPδ < 2Pδ . Expanding Z, we get e t−1 )W (t−1) (I − J) Z (t) (I − J) = (Z (t−1) − ηl ηg G = Z nPδ

t−1 Y

W ℓ (I − J) − ηl ηg

t−1 X q=nPδ

ℓ=nPδ

eq G

t−1 Y

W (ℓ) (I − J) .

ℓ=q

e t , ∆t and ∇F t define as follows: Let matrix notations ∆ x Gqi = 1{i∈At } (t − τi (t))

s−1 X

(t,r)

∇ℓi (xi

(t,r)

; ξi

(t,r)

) − ∇Fi (xi

)

r=0

}

e t ]i [∆

+ 1{i∈At } (t − τi (t))

s−1 X

(t,r)

∇Fi (xi

r=0

[∆t ]i

) − ∇Fi (xti ) +s ∇Fi (xti ) . | {z } [∇Fxt ]i }

Assuming an absolute constant ρe ∈ (ρk , 1), it holds that   t−1 t−1 t−1 h i Y X Y eq W ℓ (I − J) − ηl ηg G W (ℓ) (I − J) ∥2F  EW ∥Z (t) (I − J) ∥2F = EW ∥Z nPδ q=nPδ

ℓ=nPδ

ℓ=q

  t−1 t−1 X Y (a) nP 1 eq ≤ 1+ ρk EW ∥Z δ − Z̄ nPδ ∥2F + (1 + γ)ηl2 ηg2 EW ∥ G W (ℓ) (I − J) ∥2F  γ q=nPδ ℓ=q   t−1 t−1 X Y (b) η 2 ηg2 eq EW ∥ G W (ℓ) (I − J) ∥2F  . ≤ ρe∥Z nPδ − Z̄ nPδ ∥2F + l ρe − ρk q=nPδ

ℓ=q

Efficient and Unbiased Federated Learning

where inequality (a) holds because Young’s inequality and Lemma 3, inequality (b) holds by ρk plugging in γ = ρe−ρ . Unrolling the recursion, it holds that k ∥Z

(t)

(I − J) ∥2F ≤ ρe∥Z nPδ − Z̄ nPδ ∥2F +

t−1 t−1 X Y ηl2 ηg2 q e ∥ G W (ℓ) (I − J) ∥2F ρe − ρk q=nPδ

ηl2 ηg2 ρe∥ ρe − ρk

≤ ρe2 ∥Z (n−1)Pδ − Z̄ (n−1)Pδ ∥2F +

nP δ −1 X

eq G

≤

ηl2 ηg2 ρe − ρk

∥

eq G

t−1 Y

W (ℓ) (I − J) ∥2F +

ℓ=q

e q Qb

ℓ=q W

q=a G

(A) = ∥

b X

=∥

e q + ∆q + ∇Fxq ∆

(j+1)Pδ −1

eq G

q=jPδ

 W (ℓ) (I − J) ∥2F  .

ℓ=q

b Y

W (ℓ) (I − J) ∥2F

ℓ=q

eq ∆

q=a

ρen−j ∥

(j+1)Pδ −1

(ℓ) (I − J) ∥2 . It remains to bound (A): F

q=a b X

ℓ=q

n−1 X j=0

q=nPδ

Define (A) = ∥

ℓ=q

q=(n−1)Pδ

q=nPδ

t−1 X

W (ℓ) (I − J) ∥2F

t−1 t−1 X Y ηl2 ηg2 eq ∥ G W (ℓ) (I − J) ∥2F ρe − ρk

+ 

ℓ=q

nP δ −1 Y

b Y

W (ℓ) (I − J) ∥2F + ∥

∆

q=a

(∆q + ∇Fxq )

q=a

ℓ=q

* b X

b X

b Y

(ℓ)

(I − J) ,

b X

W (ℓ) (I − J) ∥2F

ℓ=q q

(∆

+ ∇Fxq )

q=a

ℓ=q

b Y

+ W

(ℓ)

(I − J)

ℓ=q

. F

Take expectation with respect to randomness in stochastic gradients, denote by Eξ [·]:  Eξ [(A)] = Eξ ∥

b X

 eq  ∆

q=a

b Y







W (ℓ) − J ∥2F  + Eξ ∥

b X

 (∆q + ∇Fxq ) 

q=a

ℓ=q

b Y



W (ℓ) − J ∥2F 

ℓ=q

*    +  b b b b X Y X Y e q  W (ℓ) − J , + 2Eξ  ∆ (∆q + ∇Fxq )  W (ℓ) − J  q=a

 = Eξ ∥

b X

 eq  ∆

q=a

b Y

* b X q=a

≤ Eξ ∥

b X q=a







W (ℓ) − J ∥2F  + Eξ ∥

 eq  ∆

b Y

ℓ=q

b X

 (∆q + ∇Fxq ) 

q=a

ℓ=q

+2 

q=a

ℓ=q

 h

eq  Eξ ∆

b Y

 W (ℓ) − J , 



W (ℓ) − J ∥2F  + Eξ ∥

b X

b X q=a

F  W (ℓ) − J ∥2F 

ℓ=q

 (∆q + ∇Fxq ) 

q=a

ℓ=q



t−1 Y

b Y

+ W (ℓ) − J

ℓ=q

 (∆q + ∇Fxq ) 

b Y ℓ=q





F

W (ℓ) − J ∥2F  ,

Xiang, Ioannidis, Yeh, Joe-Wong and Su

h i e q = 0. Next, we take expectation over the where the last inequality holds because Eξ ∆ remaining randomness.  E [(A)] ≤ E ∥

b X

 eq  ∆

q=a

b Y







W (ℓ) − J ∥2F  + E ∥

b X

 (∆q + ∇Fxq ) 

q=a

ℓ=q





t−1 Y





W (ℓ) − J ∥2F 

ℓ=q









            b t−1 b b b b   X   X   X Y Y (ℓ) Y       q (ℓ) 2 2 q (ℓ) 2 q e  ≤ E ∥ ∆ W − J ∥F  + 2E ∥ W − J ∥2F  . ∆  W − J ∥F  + 2s E ∥ ∇Fx        ℓ=q ℓ=q ℓ=q   q=a   q=a   q=a | {z } {z } | {z } | (I)

(II)

(III)

Bounding E [(I)] b X

E [(I)] =





eq  E ∥∆

q=a

b Y



W (ℓ) − J ∥2F 

b X X

*



ep  E ∆

q=a p̸=q

≤

(43)

ℓ=q

+ b (c) X



t−1 Y





eq  W (ℓ) − J , ∆

ℓ=p

t−1 Y

+ W (ℓ) − J 

ℓ=q

h i e q ∥2 , E ∥∆ F

(44)

q=a

where inequality (c)hholds because of independent and unbiased stochastic gradients. It i q 2 e remains to bound E ∥∆ ∥F .

e q ∥2F = ∥∆

m X

1{i∈Aq }

q−1 X

1{τi (t)=p} (q − p)

p=−1

i=1

s−1 X

2 (q,r) (q,r) (q,r) ∇ℓi (xi ; ξi ) − ∇Fi (xi )

r=0

. 2

Further take expectation w.r.t. the randomness in stochastic gradients. q−1 m s−1 h i X X X (q,r) (p,r) (q,r) 2 q 2 2 e Eξ ∥∆ ∥F = 1{i∈Aq } 1{τi (t)=p} (q − p) Eξ ∇ℓi (xi ; ξi ) − ∇Fi (xi ) p=−1

i=1

≤ sσ

m X i=1

1{i∈Aq }

r=0

q−1 X

1{τi (t)=p} (q − p)2 .

p=−1

Take expectation over the remaining randomness: q−1 m h i h h ii X X e q ∥2 = E Eξ ∥∆ e q ∥2 ≤ sσ 2 q E ∥∆ E 1 E 1{τi (t)=p} (q − p)2 ≤ msσ 2 (var) . {i∈A } F F p=−1

i=1

Recall that (var) refers to (41). Therefore, we have E [(I)] ≤ 2Pδ msσ 2 (var) . 54

Efficient and Unbiased Federated Learning

Bounding E [(II)]         b b b b X Y X Y E [(II)] = E ∥ ∆q  W (ℓ) − J ∥2F  ≤ 2Pδ E ∥∆q  W (ℓ) − J ∥2F  q=a

≤ 2Pδ

b X

q=t−Pδ

ℓ=q

E ∥∆q ∥2F .

q=a

It remains to bound E ∥∆q ∥2F . Take expectation with respect to randomness in stochastic gradients: q−1 q−1 m X m X X X q 2 2 2 3 2 2 2 2 4 2 Eξ ∥∆ ∥F ≤ 4ηl s L 1{τi (q)=p} (q − p) σ + 16ηl s L 1{τi (q)=p} (q − p)2 ∥∇Fi (xqi )∥2 , i=1 p=−1

i=1 p=−1

Next, we take expectation over the remaining randomness and plug back in: E [(II)] ≤ 16ηl2 s3 L2 Pδ2

q−1 m X X

E 1{τi (q)=p} (q − p)2 σ 2

i=1 p=−1

+ 32ηl2 s4 L2 Pδ

b X m X

q−1 h i X q 2 E ∥∇Fi (xi )∥2 E 1{τi (q)=p} (q − p)2

q=a i=1

p=−1

≤ 16ηl2 s3 L2 Pδ2 mσ 2 (var) + 32ηl2 s4 L2 Pδ

b X m X

h i 2 E ∥∇Fi (xqi )∥2 (var) ,

q=a i=1

Bounding E [(III)]

Use a similar trick as in bounding E [(II)] , and we get     b b b X m h i X X Y 2 E [(III)] = E ∥ ∇Fxq  W (ℓ) − J ∥2F  ≤ 2Pδ E ∥∇Fi (xqi )∥2 . q=a

q=a i=1

ℓ=q

Hence, we have E [(A)] ≤ 2Pδ (var) msσ

1 + 16ηl2 s2 L2 Pδ (var)

+ 2s

1 + 16ηl2 s2 L2

! b X m h i X q 2 E ∥∇Fi (xi )∥2 q=a i=1

It follows that   (j+1)Pδ −1 (j+1)Pδ −1 t−1 t−1 n−1 2 2 X Y X X Y η η g  eq eq E ∥Z (t) (I − J) ∥2F ≤ l ∥ G W (ℓ) (I − J) ∥2F + ρen−j ∥ G W (ℓ) (I − J) ∥2F  ρe − ρk j=0 q=nPδ q=jPδ ℓ=q ℓ=q   t−1 X m h i X ηl2 ηg2 2 msσ 2 1 + 16ηl2 s2 L2 Pδ (var) + 2s2 1 + 16ηl2 s2 L2 ≤ 2Pδ (var) E ∥∇Fi (xqi )∥2  ρe − ρk q=nPδ i=1   (j+1)Pδ −1 m i X X X h ηl2 ηg2 n−1 2 + 2Pδ (var) ρen−j msσ 2 1 + 16ηl2 s2 L2 Pδ (var) + 2s2 1 + 16ηl2 s2 L2 E ∥∇Fi (xqi )∥2  . ρe − ρk j=0 i=1 h

q=jPδ

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Rearranging the terms, we have

n i h η 2 ηg2 X E ∥Z (t) (I − J) ∥2F ≤ 2Pδ (var) l ρen−j msσ 2 1 + 16ηl2 s2 L2 Pδ (var) ρe − ρk j=0   (j+1)Pδ −1 m t−1 X m n 2 2 i X h i h X X X η η 2 2 g  + 4s2 1 + 16ηl2 s2 L2 Pδ (var) l E ∥∇Fi (xqi )∥2 + ρen−j E ∥∇Fi (xqi )∥2  ρe − ρk i=1 j=0 i=1 q=nPδ

q=jPδ

ηl2 ηg2

msσ 2 1 + 16ηl2 s2 L2 Pδ (var)   (j+1)Pδ −1 m t−1 X m n 2 2 h i X h i X X X η η 2 2 g  + 4s2 1 + 16ηl2 s2 L2 Pδ (var) l E ∥∇Fi (xqi )∥2 + ρen−j E ∥∇Fi (xqi )∥2  . ρe − ρk i=1 j=0 i=1

≤ 2Pδ (var)

(e ρ − ρk )(1 − ρe)

q=nPδ

q=jPδ

It follows that

T −1 i ηl2 ηg2 msσ 2 1 X h (t) 2 2 2 2 E ∥Z (I − J) ∥F ≤ 2Pδ (var) 1 + 16ηl s L Pδ (var) M T t=0 (e ρ − ρk )(1 − ρe) M   (j+1)Pδ −1 m T −1 t−1 X m n 2 2 h i X h i X X X X η η 1 2 2 g  E ∥∇Fi (xqi )∥2 + ρen−j E ∥∇Fi (xqi )∥2  + 4s2 1 + 16ηl2 s2 L2 Pδ (var) l ρe − ρk M T t=0 j=0 i=1 q=nPδ i=1 q=jPδ ! ∞ m T −1 i X ηl2 ηg2 ηl2 ηg2 1 X X h msσ 2 t 2 q 2 2 ρe E ∇Fi (xi ) 2 ≤ 4Pδ (var) + 16s Pδ (var) (e ρ − ρk )(1 − ρe) M ρe − ρk M T t=0 i=1 q=0 ≤ 4Pδ (var)

T −1 m i ηl2 ηg2 ηl2 ηg2 msσ 2 1 XX h 2 + 16s2 Pδ2 (var) E ∇Fi (xti ) 2 . (e ρ − ρk )(1 − ρe) M (e ρ − ρk )(1 − ρe) M T t=0 i=1

Further, it holds that

T −1 m T −1 m i i 1 XX h 1 XX h 2 2 E ∇Fi (xti ) 2 ≤ ηl2 ηg2 s2 (var) E ∇Fi (zit ) 2 M T t=0 i=1 M T t=0 i=1 T −1 2 3M (β 2 + 1) 2 2 2 1 X t e ≤ ηl ηg s (var) E ∇F (z̄ ) m T t=0 2

3mηl2 ηg2 s2 (var) ζ 2 M

+ 3ηl2 ηg2 s2 L2 (var)

T −1 M i 1 XX h t 2 E zi − z̄ t 2 . M T t=0 i=1

Efficient and Unbiased Federated Learning

Plug it back in, we have T −1 M i ηl2 ηg2 1 XX h t smσ 2 2 E zi − z̄ t 2 ≤ 4Pδ (var) M T t=0 i=1 (e ρ − ρk )(1 − ρe) M

2 T −1 2 48M ηl4 ηg4 (β 2 + 1)s4 Pδ2 (var) 1 X t e E ∇F (z̄ ) + m (e ρ − ρk )(1 − ρe) T t=0 2 4 4 2 ηl ηg mζ 2 + 48s4 Pδ2 (var) (e ρ − ρk )(1 − ρe) M T −1 M i 1 1 X X h t 2 + 3ηl2 ηg2 s2 Pδ (var) E zi − z̄ t 2 . (e ρ − ρk )(1 − ρe) M T t=0 i=1

Under our choice of learning rate condition, it holds that T −1 M i 8ηl2 ηg2 sPδ (var) mσ 2 1 XX h t 2 E zi − z̄ t 2 ≤ MT (e ρ − ρk )(1 − ρe) M t=0 i=1

−1 2 6ηl2 ηg2 s2 Pδ (var) (β 2 + 1) M 1 TX t e + E ∇F (z̄ ) (e ρ − ρk )(1 − ρe) m T 2 t=0 6η 2 ηg2 s2 Pδ (var) mζ 2 . + l (e ρ − ρk )(1 − ρe) M k By taking ρe = 1+ρ 2 , we get

T −1 M

i 32η 2 η 2 sPδ (var) 1 XX h t 2 l g E zi − z̄ t 2 ≤ MT (1 − ρk )2 t=0 i=1

mσ 2 M

−1 2 24ηl2 ηg2 s2 Pδ (var) (β 2 + 1) M 1 TX e(z̄ t ) E ∇ F (1 − ρk )2 m T 2 t=0 24ηl2 ηg2 s2 Pδ (var) mζ 2 . + (1 − ρk )2 M

D.6 Spectral norm upper bound (Lemma 9) Proof of Lemma 9 Before we dive into the concrete proof, let us first go over some additional notations and agree on a fact about matrix products. Qk (t) ≜ W (1) W (2) · · · W (k) defines an ordered matrix product from W (1) Notations. t=1 W to W (k) , where k ∈ Z+ , and an undirected graph Gt ≜ VGt , Et , W (t) , where VGt ≜ R ∪ V defines the set of vertices for all t ∈ [T ], W (t) defines the weighted adjacency matrix, an (t) edge (i, j) ∈ Et if Wij > 0 for i, j ∈ [M ]. 57

Xiang, Ioannidis, Yeh, Joe-Wong and Su

A fact about matrix product. Pδ Y

(t)

Wij =

t=1

M X

(1)

Wik1 · · ·

k1 =1

By definition of matrix products, we have (P −2)

WkP δ−3 kP −2 δ

kPδ −2 =1

It is observed from (45) that

M X kPδ −1 =1

(P −1)

(P )

WkP δ−2 kP −1 WkP δ−1 j . δ

(45)

(t) t=1 Wij > 0 if there exists at least one

Q Pδ

(1)

(P −1)

(2)

(P )

Wik1 Wk1 k2 · · · WkP δ−2 kP −1 WkP δ−1 j > 0, δ

Q δ (t) where k1 , . . . , kPδ −1 ∈ R ∪ V. In the language of graph theory, Pt=1 Wij > 0 if there exists a directed path starting from node i of G1 and ends at node j of GPδ through G2 , G3 , . . ., Q δ GPδ −1 sequentially. Therefore, to lower bound elements in Pt=1 Wt , it suffices to find the paths of interest for the lower bound. Element-wise lower bound of W (t) matrix for all t ∈ [T ]. Recall the definition of a W matrix: 1 {i∈At } 1{j∈At }  , if i ̸= j and i, j ∈ R;  |At |+k   1  t i∈A }  {  if i ∈ R and j ∈ V;   |At |+k , 1{j∈At } (t) Wij = if i ∈ V and j ∈ R; |At |+k ,   1{i∈At }    if i = j and i ∈ R;  |At |+k + (1 − 1{i∈At } ),    1 if i = j and i ∈ V, |At |+k , Next, we focus on the diagonal element in W (t) , we have two cases: • When i ∈ R, we have (t)

Wii =

1{i∈At } (1 − 1{i∈At } ) 1{i∈At } 1 + (1 − 1{i∈At } ) ≥ t + = t ; t t |A | + k |A | + k |A | + k |A | + k

• When i ∈ V, we have (t)

Wii =

1 . |At | + k

For the edge weight of ij, where i ̸= j, it holds that 1{i∈[M ]} 1{j∈[M ]} . |At | + k Q 2 t0 +P −1 (t) . Fig. 13 presents a simple example of Element-wise lower bound of W t=t0 a path from node i to j, which visualizes the transition between different nodes. We will use it to assist our proof. By definition, we have  !2 !⊤ t +P −1 !  ! t0 +P t0 +P t0 +P t0 0 Y δ Yδ −1 Yδ −1 Y Yδ −1 (t) (t) (t) (t) (t) W = W W = W  W . (t)

Wij ≥

t=t0

t=t0 +Pδ −1

{z (I)

(II)

}

Efficient and Unbiased Federated Learning

1 M 1 M

1{i∈At } M

1 M

1{j∈At } M

(a) A directed path from node i to j through a virtual node. 1 M 1 M

1{i∈At }

1 M

1{j∈At } M

1 M

(b) A directed path from node i to a virtual node. (c) A directed path from a virtual node to node j.

Figure 13: An illustration of a directed path from node i to j through an intermediate virtual node. The dashed arcs are self-loops. The weights next to the dashed arcs and solid lines are the lower bounds of each edge weight, respectively.

Q 2 t0 +Pδ −1 (t) ] , where i = W To lower bound [ ̸ j. It suffices to let a node i take one path ij t=t0 to an intermediate node h in (I) and then take another path from the intermediate node h back to node j in (II). We will return to the case i = j later. Let h ∈ V. • In (I) (Fig. 13b), we start from node i in W (t0 +P −1) to node h in W (t0 ) via a directed path. One possible path is to stay in self-loops as long as one can, and jump only once from node i to node h. It holds that   [(I)]ih ≥

 t0 +P δ −1 X t=t0

 1 Q  ′ |At′ | + k ·  t ̸=t | {z } self-loop weights

1{i∈At } |At | + k | {z }

Pt0 +Pδ −1   1{i∈At }  = Q t=t0 .  t0 +Pδ −1 (|At′ | + k)  t′ =t0

(46)

one jump weight

• In (II) (Fig. 13c), we can show the results similarly in the following  [(II)]hj ≥



 t0 +P δ −1 X t=t0

 1{i∈At }   |At | + k  | {z }

one jump weight

Pt0 +Pδ −1   1{j∈At } 1 t=t0  = Qt0 +P · Q . ′  −1 t δ (|At′ | + k) ′ =t t′ ̸=t |A | + k  t 0 | {z } self-loop weights

Hence, when h ∈ V, we have P X h∈V

[(I)]ih · [(II)]hj ≥

t0 +Pδ −1 1{i∈At } t=t0

Q 59

t0 +Pδ −1 1{j∈At } t=t0

t0 +Pδ −1 (|At′ | + k) t′ =t0

(47)

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Q 2 t0 +Pδ −1 (t) . Recall that F t defines the Expected element-wise lower bound of W t=t0 sigma algebra generated by the randomness up to round t, and that we assume independent availability. Note that we are interested only in the off-diagonal elements. By the law of total expectation, it holds for i ̸= j that • i ∈ R, j ∈ R. P     P !2  t0 +Pδ −1 t0 +Pδ −1 t0 +P t t 1 1 Yδ −1 {i∈A } {j∈A } t=t t=t 0 0 F t0  E  W (t)  F t0  ≥ E  2Pδ M t=t 0

! # # ! t +P −1 0 X δ 1 1{j∈At } F t0 +Pδ −1 , F t0 F t0 = 2P E E 1{i∈At } M δ t=t0 t=t0 " " t +P −1 ! # " t +P −1 ! # # 0 X 0 X δ δ 1 (a) = E E 1{i∈At } F t0 +Pδ −1 E 1{j∈At } F t0 +Pδ −1 F t0 M 2Pδ t=t0 t=t0 " t +P −2 ! t +P −2 ! # 0 X 0 X δ δ 1 = 2P E 1{i∈At } + P i ∈ At0 +Pδ −1 1{j∈At } + P j ∈ At0 +Pδ −1 F t0 M δ t=t t=t " "

t0 +P δ −1 X

= ··· P P t0 +Pδ −1 t0 +Pδ −1 t t P i ∈ A P j ∈ A t=t0 t=t0 δ 2 Pδ 2 ≥ , = M 2Pδ M 2Pδ where equality (a) holds because of independence. • i ∈ V, j ∈ R. In this case, the node can move to an arbitrary virtual node (j included) in (I).   !2  " t +P −1 ! # t0 +P 0 X δ Yδ −1 P δ E  W (t)  F t0  ≥ 2P E 1{i∈At } F t0 δ M t=t t=t 0

" "

t0 +P δ −1 X

Pδ = 2P E E 1{i∈At } F t0 +Pδ −1 M δ t=t0 P t0 +Pδ −1 t Pδ P i ∈ A t=t0 δPδ 2 ≥ . = M 2Pδ M 2Pδ • i ∈ R, j ∈ V. Similar strategy as above.  !2  t0 +P Yδ −1 E  W (t)  t=t0

# F t0

 F t0  ≥

δPδ 2 . M 2Pδ

• i ∈ V, j ∈ V.  E 

t0 +P Yδ −1 t=t0

W (t)

!2 





F t0  ≥

Pδ 2 δPδ 2 ≥ . M 2Pδ M 2Pδ

Efficient and Unbiased Federated Learning

Cheeger’s inequality.

For ease of presentation, define W t0 ,Pδ ≜ E

2 t0 +Pδ −1 W (i) i=t0

and ρ = λ2 (W t0 ,Pδ ). Suppose we have |S ∩ V| = a. Accordingly, we have |S ∩ R| = |S| − a, |V ∩ S ′ | = k − a and |R ∩ S ′ | = |S ′ | − (k − a). Let t0 ,Pδ i∈S,j ∈S / πi Wij

f (a, S) ≜

i∈S πi

t0 ,Pδ i∈S,j ∈S / Wij

|S|

1 for all i ∈ R ∪ V. It follows that where the equality holds because πi = m+k

X i∈S,j ∈S /

Wijt0 ,Pδ ≥

Pδ 2 δ 2 Pδ 2 δ ′ (|S| − a) S − (k − a) + |S| S ′ − (|S| − a)( S ′ − (k − a)) . 2P 2P M δ M δ

Next, we decompose the two coefficients, respectively. |S| S ′ − (|S| − a)( S ′ − (k − a)) = |S| (m + k − |S|) − (|S| − a) (m + k − |S| − k + a) = m |S| + k |S| − |S|2 − m |S| + |S|2 − a |S| + am − a |S| + a2 = a2 + a (m − 2 |S|) + k |S| . (|S| − a) S ′ − (k − a) = (|S| − a) (m + k − |S| − (k − a)) = m |S| − am − |S|2 − a2 + 2a |S| = −a2 − a(m − 2 |S|) + m |S| − |S|2 . Therefore, f becomes: δ 2 (|S| − a) (|S ′ | − (k − a)) + δ (|S| |S ′ | − (|S| − a)(|S ′ | − (k − a))) M 2Pδ |S| a2 (δ − δ 2 ) + a(m − 2 |S|)(δ − δ 2 ) + k |S| δPδ + |S| (m − |S|)δ 2 = . M 2Pδ |S| It follows that, • m ≥ 2 |S|, i.e., |S| ≤ m 2 . Hence, we have ( m δ + k)δPδ f (a, S) f (0, S) ≥ ≥ 2 . k k M 2Pδ • m < 2 |S|, i.e., |S| > m 2 . In this case, the axis of symmetry is on the right-hand side. Hence, it holds that a2 δ − δ2 a m − 2 |S| kδPδ + (m − |S|)δ 2 Pδ f ≥ 2P + 2P (δ − δ 2 ) + M δ |S| M δ |S| M 2Pδ 2 2 p m √ kδ + (m − |S|)δ 2 − δ−δ 2 |S| − 4 |S| ≥ . (48) 2P M 61

Xiang, Ioannidis, Yeh, Joe-Wong and Su

It is easy to see that (48) is monotonic decreasing w.r.t. |S|. By definition, we know that |S| ≤ m+k and plug this in, we have 2 2 m−k 2 δ−δ m+k m2 kδ + ( 2 )δ − 4 2 + m+k − 4m 4 2 f≥ 2P δ M 2 2 m−k 2 δ−δ m kδ + ( 2 )δ − m+k − 2(m − k) 4 2 = 2Pδ M k2 k2 δ k − 2(m+k) + δ 2 m−k + 2 2(m+k) = 2P (m + k) δ 2 2 2 m δ + (k + 2mk)δ . = 2(m + k)2Pδ +1 By comparing the above two lower bounds, we conclude that Pδ ,t0 i∈S,j ∈S / πi Wij

P Φ(M ) = P min

1 i∈S πi ≤ 2

i∈S πi

≥

m2 δ 2 + (k 2 + 2mk)δ . 2(m + k)2Pδ +1

2 ≤ Φ(M ) ≤ From Cheeger’s inequality, we know that 1−λ 2

2 (1 − λ2 ). Thus,

2 2 m δ + (k 2 + 2mk) 2 Φ2 (M ) ρ(t) = λ2 ≤ 1 − ≤1− δ . 2 8(m + k)4P +2 Special case where P = 1. By using a similar argument as above and adapting the results in (Xiang et al., 2024), it holds that 2 2 m δ + (k 2 + 2mk) 2 Φ2 (M ) ≤1− δ , ρ(t) = λ2 ≤ 1 − 2 8(m + k)2 which is decreasing in k. The monotonicity can be seen by taking the partial derivative w.r.t. k. Let m2 δ + (2mk + k 2 ) h(k) ≜ . (m + k)2 It follows that ∂h(k) (2m + 2k)(m + k)2 − (2m + 2k)(m2 δ + 2mk + k 2 ) = ∂k (m + k)4 (m + k)2 − (m2 δ + 2mk + k 2 ) =2 (m + k)2 2 2m (1 − δ) = > 0. (m + k)2

Efficient and Unbiased Federated Learning

Appendix E. Convergence Error of z̄ t (Theorem 11) In the sequel, we recall and assume the following learning rate conditions in (22): ηl ηg ≤

√ δ(1 − ρk ) m

δ p p and ηl ≤ . 96sL Pδ M [(Pδ − 1)2 δ 2 + 1] (β 2 + 1) 216sL [(Pδ − 1)2 δ 2 + 1] (β 2 + 1)

Recall that δmax ≜ maxi∈[m],t∈[T ] pti and Fe⋆ ≜ minx Fe(x). Proof of Theorem 11 Take expectation over all the randomness, plug in Lemma 18 and Proposition 8. By telescoping sum, it holds that h i E Fe⋆ − Fe(z̄ 0 ) T +

T −1

ηl ηg s 1 X ≤− E 3 T

2ηl2 ηg2 sLδmax σ M 2T

t=0 −1 m t−1 2 T XX X

E 1{τi (t)=p} (t − p)2

xti − zit 2

zit − z̄ t 2

t=0 i=1 T −1 m t−1 65ηg ηl3 s3 L2 X X X

(49)

t=0 i=1

T −1 M ηl ηg sL2 X X

2M T

t=0 i=1 p=−1

T −1 M 4ηl ηg sL2 X X

∇Fe(z̄ t )

t=0 i=1 p=−1

T −1 m t−1 17ηg ηl3 s2 L2 σ 2 X X X

E 1{τi (t)=p} (t − p)2 E

(50)

∇Fi (xp+1 ) i

t=0 i=1 p=−1

2 2

(51)

Next, we bound (49), (50) and (51), respectively. First, we show that T −1 m −1 T −1 M i 3mζ 2 3M β 2 + 1 1 TX i 2 3L2 X X h t 1 XX h 2 t 2 E ∇Fi (zi ) 2 ≤ + E ∇Fe(z̄ t ) + E zi − z̄ t 2 MT M m T MT 2 t=0 i=1 t=0 t=0 i=1 " # 2 2 2 2 2 24ηl ηg s Pδ (var) L mζ ≤3 1+ 2 (1 − ρk ) M " # −1 2 24ηl2 ηg2 s2 Pδ (var) L2 1 TX 3M β 2 + 1 t e + 1+ E ∇F (z̄ ) m (1 − ρk )2 T 2 t=0 96ηl2 ηg2 sPδ (var) L2 mσ 2 + , (52) (1 − ρk )2 M where the last inequality follows from Lemma 18. 63

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Bounding (49). T −1 M −1 X m h i 4η 3 η 3 s3 L2 (var) TX i 4ηl ηg sL2 X X h t 2 2 g E xi − zit 2 ≤ l E ∇Fi (zit ) 2 MT MT t=0 i=1 t=0 i=1 # " 2 2 2 2 24ηl ηg s Pδ (var) L mζ 2 ≤ 12ηl3 ηg3 s3 L2 (var) 1 + (1 − ρk )2 M " # T −1 2 η 2 s2 P (var) L2 2 24η M 1 X δ g l t 3 3 3 2 2 e E ∇F (z̄ ) + 12ηl ηg s L (var) β + 1 1 + (1 − ρk )2 m T 2 t=0 384ηl5 ηg5 s4 Pδ (var)2 L4 mσ 2 + (1 − ρk )2 M 2 2 mζ 3 3 3 2 2 mσ 3 3 3 ≤ 16ηl ηg s L (var) + 4ηl ηg s Pδ (var) L M M TX −1 2 M 1 t 3 3 3 2 2 E ∇Fe(z̄ ) + 16ηl ηg s L (var) β + 1 , m T 2 t=0

√ where the last inequality holds due to ηl ηg ≤ (1 − ρk )/(10sL Pδ · var). Bounding (50). T −1 m i ηl ηg sL2 X X h t 2 E zi − z̄ t 2 2M T t=0 i=1 4ηl3 ηg3 s2 L2 Pδ (var) mσ 2 ≤ (e ρ − ρk )(1 − ρe) M

3η 3 ηg3 s3 L2 Pδ (var) (β 2 + 1) + l (e ρ − ρk )(1 − ρe)

M m

T −1

1 X E T

∇Fe(z̄ t )

t=0

2 2

3η 3 ηg3 s3 L2 Pδ (var) + l (e ρ − ρk )(1 − ρe)

mζ 2 M

Bounding (51).

65ηg ηl3 s3 L2

T −1 m t−1 1 XX X E 1{τi (t)=p} (t − p)2 E MT t=0 i=1 p=−1 T −1 m

∇Fi (xp+1 ) i

i 65ηl3 ηg s3 L2 (var) X X h 2 E ∇Fi (xti ) 2 MT t=0 i=1 2 mζ 3 3 2 ≤ 260ηl ηg s L (var) M T −1 2 2 M 260ηl3 ηg s3 L2 (var) β 2 + 1 X t 3 3 2 mσ e + E ∇F (z̄ ) + 65ηg ηl s L , m T M 2

≤

t=0

Efficient and Unbiased Federated Learning

√ where the last inequality holds due to ηl ηg ≤ (1 − ρk )/(10sL Pδ · var). Putting (49), (50) and (51) together and plugging them back into the telescoping sum, it holds that h i E Fe⋆ − Fe(z̄ 0 ) T ! T −1 2 2 12ηl3 ηg3 s3 L2 M ηl ηg s 1 X M m Pδ (var) (β + 1) 2 3 3 3 2 t ≤− β +1 − − 16ηl ηg s L (var) E ∇Fe(z̄ ) 3 m (1 − ρk )2 T 2 t=0 −1 2 1 TX M 2 3 3 2 t e β +1 − −260ηl ηg s L (var) E ∇F (z̄ ) m T 2 t=0 2η 2 ηg2 sLδmax (var) mσ 2 mσ 2 3 2 2 + 17η η s L (var) + l g l M2 M 2 2 3 3 2 2 16ηl ηg s L Pδ (var) mσ 2 mσ 3 3 2 mσ + 4ηl3 ηg3 s3 Pδ (var) L2 s L + + 65η η g l M (1 − ρk )2 M M 2 2 2 3 3 2 3 12ηl ηg s L Pδ (var) mζ mζ mζ 3 3 3 2 3 2 3 + 16ηl ηg s L (var) + + 260ηl ηg s L (var) 2 M (1 − ρk ) M M T −1 2 ηl ηg s 1 X E ∇Fe(z̄ t ) ≤− 4 T 2 t=0 2ηl2 ηg2 sLδmax (var) mσ 2 mσ 2 3 2 2 + 17ηg ηl s L (var) + M2 M 3 3 2 2 2 2 16ηl ηg s L Pδ (var) mσ 2 2 mσ 3 3 3 3 3 2 mσ + 4ηl ηg s Pδ (var) L + + 65ηg ηl s L M (1 − ρk )2 M M 2 2 2 3 2 3 3 12ηl ηg s L Pδ (var) mζ mζ mζ 3 3 3 2 3 3 2 + 16ηl ηg s L (var) + + 260ηl ηg s L (var) , 2 M (1 − ρk ) M M where the last inequality holds because √ 1 (1 − ρk ) m p p ηl ηg ≤ and ηl ≤ . 2 48sL Pδ M (var) (β + 1) 108sL (var) (β 2 + 1) Combining the above and rearranging the terms, it holds that 4 Fe(z̄ 0 ) − Fe⋆ T −1 X 2 1 ≤ E ∇Fe(z̄ t ) T ηl ηg sT 2 t=0 8ηl ηg Lδmax (var) mσ 2 mσ 2 2 2 + + 68ηl sL (var) M2 M 2 2 2 2 64ηl ηg sL Pδ (var) mσ 2 mσ 2 2 2 2 2 mσ 2 2 2 + 16ηl ηg s Pδ (var) L + + 260ηl s L (var) M (1 − ρk )2 M M 2 2 2 η 2 s2 L2 P (var) 2 48η mζ mζ mζ δ l g + 64ηl2 ηg2 s2 L2 (var) + + 1040ηl2 s2 L2 (var) . M (1 − ρk )2 M M 65

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Expanding the second moment of the unavailable duration, it holds that 1 T

T −1 X

∇Fe (z̄ t )

≤

4 Fe(z̄ 0 ) − Fe⋆

ηl ηg sT [(Pδ − 1)δ + 1] + (Pδ − 1)δ 2 + 1 8ηl ηg Lδmax mσ 2 2 2 + 68ηl sL + δ2 M M ! 2 2 2 2 2 64η η sL P [(Pδ − 1)δ + 1] + (Pδ − 1)δ + 1 mσ 2 δ l g 2 2 2 2 2 2 2 + 16ηl ηg s Pδ L + + 260ηl s L δ2 (1 − ρk )2 M ! 48ηl2 ηg2 s2 L2 Pδ [(Pδ − 1)δ + 1]2 + (Pδ − 1)δ 2 + 1 mζ 2 2 2 2 2 2 2 2 . + 64ηl ηg s L + + 1040ηl s L δ2 (1 − ρk )2 M t=0

It holds that [(Pδ − 1)δ + 1]2 + (Pδ − 1)δ 2 + 1 2 (Pδ − 1)2 δ 2 + 1 + (Pδ − 1)2 δ 2 + 1 ≤ δ2 δ2 1 = 3 (Pδ − 1)2 + 2 . δ

(53)

Grouping the terms of the same order in terms of asymptotic, we have 1 T

T −1 X t=0

∇Fe (z̄ t )

2 2

Fe(z̄ 0 ) − Fe⋆

δmax ηl ηg Lmσ 2 1 2 + (Pδ − 1) + 2 ηl ηg sT M2 δ m 1 1 2 2 2 2 2 2 2 + ηl ηg s L Pδ 1+ , σ +ζ (Pδ − 1) + 2 M δ (1 − ρk )2

≲

where we use the convention that ηg ≥ 1 for ease of presentation. Using the fact that m )∇F (x), it holds that ∇Fe(x) = ( M T −1

F (z̄ 0 ) − F ⋆ δmax ηl ηg Lσ 2 M 1 2 + (Pδ − 1) + 2 ηl ηg sT M m δ M 1 1 2 2 2 2 2 2 2 + η l η g s L Pδ σ +ζ (Pδ − 1) + 2 1+ m δ (1 − ρk )2 F (z̄ 0 ) − F ⋆ δmax ηl ηg Lσ 2 M 1 ≲ + (Pδ − 1)2 + 2 m ηl ηg sT m δ M 1 1 2 2 2 2 2 2 2 + η l η g s L Pδ σ +ζ (Pδ − 1) + 2 1 + , m δ (1 − ρk )2

i 1 X h 2 E ∇F (z̄ t ) 2 ≲ T t=0

M m

Efficient and Unbiased Federated Learning

Appendix F. Convergence Rate of x̄t (Corollary 12) F.1 Convergence error of Algorithm 1 Corollary 19 (Convergence error of xti ). Suppose learning rates conditions in (22) are met for ηl and ηg , and Assumptions 1, 2, 3 and 4 hold for T ≥ 1, it holds that T −1

i 1 X h 2 E ∇F (x̄t ) 2 ≲ T

t=0

M m

F (z̄ 0 ) − F ⋆ δmax ηl ηg Lσ 2 1 2 (P − 1) + 2 + ηl ηg sT m δ M 1 1 2 2 2 2 2 2 2 + ηl ηg s L Pδ σ +ζ (P − 1) + 2 1 + , m δ (1 − ρk )2

Proof of Corollary 19 T −1

T −1

i i i 1 X h 3 X h 3 X h 2 2 2 E ∇F (x̄t ) 2 ≤ E ∇F (x̄t ) − ∇F (z̄ t ) 2 + E ∇F (z̄ t ) 2 T T 2T t=0

t=0

−1 2 T X

(a) 3L

≤

t=0

−1 X (b) 3L2 T

≤

h E

t=0

≤ 3 (var)

1 M

i 3 2 x̄t − z̄ t 2 + 2T m X

h E

∇F (z̄ t ) 2

t=0

T −1

xti − zit 2 +

i 3 X h 2 E ∇F (z̄ t ) 2 2T t=0

i=1

−1 ηl2 ηg2 s2 L2 TX

t=0

T −1 X

t=0

1 M

m X

h E

2 ∇Fi (zit ) 2

T −1

i 3 X h 2 + E ∇F (z̄ t ) 2 , 2T t=0

i=1

where inequality (a) follows from Appendix B 2, inequality (b) follows from Assumption 2. Further plug in (52) and use the learning rate conditions, it holds that T −1

T −1

i i 1 X h 2 X h 2 2 E ∇F (x̄t ) 2 ≤ E ∇F (z̄ t ) 2 + 12 (var) ηl2 ηg2 s2 L2 T T t=0

t=0

M ζ2 m

+ 3 (var) ηl2 ηg2 s2 L2

Grouping the terms of the same order in terms of asymptotic, we have T −1

i 1 X h 2 E ∇F (x̄t ) 2 ≲ T t=0

M m

F (z̄ 0 ) − F ⋆ δmax ηl ηg Lσ 2 1 2 + (P − 1) + 2 ηl ηg sT m δ M 1 1 2 2 2 2 2 2 2 σ +ζ (P − 1) + 2 1 + + ηl ηg s L Pδ , m δ (1 − ρk )2

where we use the convention that ηg ≥ 1 for ease of presentation.

M σ2 m

Xiang, Ioannidis, Yeh, Joe-Wong and Su

F.2 Convergence rate of Algorithm 1

√ Proof of Corollary 12 Choose step-size as ηl = √T1sL , ηg = sδm such that learning rate conditions in (22) are met, it holds that T −1 i M L F (x̄0 ) − F ⋆ i δmax h 1 X h t 2 √ + 3√ E ∇F (x̄ ) 2 ≲ (Pδ − 1)2 δ 2 + 1 σ 2 T m sδmT δ 2 smT t=0 i h 1 M smPδ 2 2 2 2 σ +ζ (Pδ − 1) δ + 1 1 + . + m T (1 − ρk )2

Appendix G. Additional Results and Interpretations G.1 Consensus error of Algorithm 1 Corollary 20 (Consensus error of xti ). Suppose learning rates conditions are met in (22) for ηl and ηg , and Assumptions 1, 2, 3 and 4 hold for T ≥ 1, it holds that T −1 M i M F (z̄ 0 ) − F ⋆ δ η η Lσ 2 1 X 1 X h t 1 max l g 2 t 2 + (Pδ − 1) + 2 E xi − x̄ 2 ≲ T M m ηl ηg sT m δ t=0 i=1 1 1 M 2 2 2 2 2 2 2 (Pδ − 1) + 2 1 + ηl ηg s L Pδ σ + ζ , + m δ (1 − ρk )2 Proof of Corollary 20 T −1

T −1

1 X 1 X t 1 X 1 X t 2 2 xi − x̄t 2 = xi − zit + zit − z̄ t + z̄ t − x̄t 2 T M T M t=0

(a) 1

≤

(b) 1

≤

T 1 T

i=1

T −1 X t=0 T −1 X t=0 T −1 X t=0

3 M

M X i=1

M 3 X

M 6 M

xti − zit 2 +

i=1 M X i=1

xti − zit 2 + 2

xti − zit 2 +

t=0 i=1 T −1 M X X

1 T

1 T 1 T

t=0 T −1 X t=0 T −1 X t=0

3 M

i=1

M 3 X

M 3 M

T −1

zit − z̄ t 2 +

i=1 M X

zit − z̄ t 2 +

1 X 2 3 z̄ t − x̄t 2 T 1 T

t=0 T −1 X t=0

3 X t 2 zi − xti 2 M i=1

zit − z̄ t 2 ,

i=1

where inequalities (a) and (b) follow from Jensen’s inequality. It holds that T −1 M

T −1

i i 1 XX h t 4 X h 2 2 E xi − x̄t 2 ≤ E ∇F (z̄ t ) 2 MT T t=0 i=1 t=0 2 96ηl2 ηg2 sPδ (var) mσ 2 2 2 2 2 mσ + + 6 (var) ηl ηg s L (1 − ρk )2 M M 2 72ηl2 ηg2 s2 Pδ (var) mζ 2 mζ + + 72 (var) ηl2 ηg2 s2 L2 . (1 − ρk )2 M M 68

Efficient and Unbiased Federated Learning

where the last inequality holds because of learning rate condition in (22). Group the terms of the same order in terms of asymptotics, we have T −1 M i M F (z̄ 0 ) − F ⋆ δ η η Lσ 2 1 X 1 X h t 1 max l g 2 t 2 (Pδ − 1) + 2 E xi − x̄ 2 ≲ + T M m ηl ηg sT m δ t=0 i=1 M 1 1 2 2 2 2 2 2 2 + ηl ηg s L Pδ (Pδ − 1) + 2 1 + , σ +ζ m δ (1 − ρk )2 where we use the convention that ηg ≥ 1 for ease of presentation.

G.2 Orders of the asymptotic rates From Theorem 11, Corollary 19, Corollary 20, it is easy to see from the theorem statements that they are all of the same asymptotic order, i.e., T −1

T −1

t=0

i=1

t=0

1 X 1 X 1 X 1 X E[∥∇F (x̄t )∥22 ] ≍ E[∥∇F (z̄ t )∥22 ]. E[∥xti − x̄t ∥22 ] ≍ T T M T In addition, we can also see that T −1

T −1

t=0

i=1

t=0

i=1

t=0

1 X 1 X 1 X 1 X 1 X E[∥∇F (z̄ t )∥22 ]. E[∥xti − zit ∥22 ] ≍ E[∥zit − z̄ t ∥22 ] ≍ T M T M T Therefore, we conclude that (23), (25) and (26) hold.

Appendix H. Numerical Experiments H.1 Experimental setups Client Index

•Hardware Hardware. The simulations and are performed on a private cluster with 64 CPUs, 500 GB RAM and 8 NVIDIA A5000 GPU cards. • Software. We code the experiments based on PyTorch 1.13.1 (Paszke et al., 2019) and Python 3.7.16.

18 16 14 Software 12 10 8 6 4 2 0 0 1 2 3

Setups.

4 5 6 Data (label) class

Figure 14: An example of data heterogeneity using Neural Network and Hyperparameter Dirichlet(α = 0.1) distribution with 20 Specifications. Table 5 specifies details of clients. x-axis denotes the categories of images, while y-axis denotes the client the structures of the convolutional neural index. The size of a circle refers to the network and training. We initialize CNNs proportion of pictures in a given class. using the Kaiming initialization. The initial The color of a circle distinguishes images local learning rate η0 and the global learnwith different categories. ing rate ηg are searched, based on the best performance after 500 global rounds, over two grids {0.1, 0.05, 0.01, 0.005, 0.001, 0.0005} and {0.5, 1, 1.5, 5, 10, 50}, respectively. The results are presented in Table 6. 69

Xiang, Ioannidis, Yeh, Joe-Wong and Su

Table 5: Neural network architecture, loss function, learning rate scheduling, training steps and batch size specifications

Data sets

SVHN

CIFAR-10

CINIC-10

Neural network

CNN

Model architecture∗

C(3,32) – R – M – C(32,32) – R – M – L(128) – R – L(10)

C(3,32) – R – M – C(32,32) – R – M – L(256) – R – L(64) – R – L(10)

CNN C(3,32) – R – M – C(32,32) – R–M–D– L(512) – R – D – L(256) – R – D – L(10)

Loss function

Cross-entropy loss ηl = η0 in Section 7.1; ηl = √ η0

Local learning rate ηl scheduling

t/10+1

in Section 7.2,

where t denotes the global round.

Number of local steps s

Number of global rounds T in Section 7.1

10000

20000

–

Number of global rounds T in Section 7.2

2000

Batch size

128

∗ C(# in-channel, # out-channel): a 2D convolution layer (kernel size 3, stride 1, padding 1); R: ReLU

activation function; M: a 2D max-pool layer (kernel size 2, stride 2); L: (# outputs): a fully-connected linear layer; D: a dropout layer (probability 0.2).

Table 6: Initial learning rate η0 and global learning rate ηg FedAvg active

FedAvg known

FedAvg all

SVHN

η0 0.05

ηg 1.0

η0 0.1

ηg 1.0

η0 0.05

ηg 1.0

η0 0.05

ηg 1.0

η0 0.05

ηg 1.0

η0 0.1

ηg 1.0

η0 0.05

ηg 1.0

CIFAR-10

η0 0.05

ηg 1.0

η0 0.1

ηg 1.0

η0 0.05

ηg 1.0

η0 0.05

ηg 1.0

η0 0.05

ηg 1.0

η0 0.1

ηg 1.0

η0 0.05

ηg 1.0

CINIC-10

η0 0.05

ηg 1.0

η0 0.1

ηg 1.0

η0 0.05

ηg 1.0

η0 0.05

ηg 1.0

η0 0.05

ηg 1.0

η0 0.1

ηg 1.0

η0 0.05

ηg 1.0

Algorithms

FedAU

F3AST

FedSWE

MIFA

Baseline Algorithm Details. The difference between FedAvg over active clients and FedAvg over all clients is that the latter counts the contributions of unavailable clients as 0’s. We set β = 0.001 for F3AST (Ribero et al., 2022), which is tuned over a grid of {0.1, 0.05, 0.01, 0.005, 0.001, 0.0005}. The amplification factor of gFedAvg in (Wang and Ji, 2022) is set as 10, and the period is set as 100. In addition, as recommended by (Wang and Ji, 2024), we choose K = 50 in FedAU without further specification. Fig. 3 adopts the same hyperparameter setups as the ones in Section 7.2, yet with only 1000 training rounds. Data sets and Data Heterogeneity. 70

Efficient and Unbiased Federated Learning

Data sets. All the data sets we evaluate contain 10 classes of images. Some data enhancement tricks that are standard in training image classifiers are applied during training. Specifically, we apply random cropping and gradient clipping with a max norm of 0.5 to all data set trainings. Furthermore, random horizontal flipping is applied to CIFAR-10 and CINIC-10. One full set of experiments in Section 7.2 takes about 6 hours on SVHN and CIFAR-10 data sets, while about 10 hours on CINIC-10 data set. The training time for experiments in Section 7.1 almost doubles. • SVHN (Netzer et al., 2011). The data set contains 32×32 colored images of 10 different digits. In total, there are 73257 train images and 26032 test images. • CIFAR-10 (Krizhevsky et al., 2009). The data set contains 32×32 colored images of 10 different objects. In total, there are 50000 train images and 10000 test images. • CINIC-10 (Darlow et al., 2018). The data set contains 32×32 colored images of 10 different objects. In total, there are 90000 train images and 90000 test images. Data heterogeneity. Fig. 14 visualizes an example of 20 clients, the size of each circle corresponds to the relative proportion of images from a specific class. The larger the circle, the greater the share of images associated with that particular class. Moreover, α controls the heterogeneity of the data such that a greater α entails a more non-i.i.d. local data distribution and vice versa. H.2 Non-stationary client unavailability dynamics

Count

Client unavailability dynamics and visualiza16 tions. As specified in Section 7, we consider a total 14 of four client unavailable dynamics in the form of 12 pti = pi · fi (t), where pi = ⟨νi , ϕ⟩, νi ∼ Dirichlet(α) 10 8 and ϕ is the distribution to characterize the uneven 6 contributions of each image class. In detail, each 4 element [ϕ]c is drawn from a uniform distribution 2 Uniform(0, Φc ). We set Φc = 1 for the first half 0 image classes and Φc′ = 0.5 for the remaining half 0.2 0.4 0.6 0.8 1.0 Probability pi image classes. Fig. 15 plots one resulting pi ’s example, wherein pi ’s are heterogeneous across clients. Next, we formally introduce fi (t)’s under each Figure 15: A histogram of one generated pi ’s example with a total of dynamic in Section 7.2. m = 100 clients. It can be • Stationary: fi (t) ≜ 1; seen that the majority of pi ’s are below 0.5. • Non-stationary with staircase trajectory: fi (t) ≜ 1{t∈[t0 ,t0 +P/2)} + 0.4 · 1{t∈[t0 +P/2,t0 +P )} , where P defines a period, t0 ∈ {0, P, 2P, 3P, . . .}. • Non-stationary with sine trajectory: fi (t) ≜ γ sin(2π/P · t) + (1 − γ), where γ signifies the degree of non-stationary. We choose γ = 0.3 and P = 20 for all non-stationary dynamics in Section 7.2. Next, we visualize the probability trajectories and sampled client availability in Section 7.2 in Fig. 16. 71

Xiang, Ioannidis, Yeh, Joe-Wong and Su

0.1

0.9

0 0

0.9 0.5 0.1 0

0.1

0.5

0.9

pit

0.5

pit

1 10

30 40 50 Global round t

0 0

0.9 0.5 0.1 0

(a) Stationary

30 40 50 Global round t

(b) Non-stationary with staircase trajectory

0.1

0.5

0.9

pit

1 0 0

0.9 0.5 0.1 0

30 40 50 Global round t

Figure 16: Examples of client unavailability with probabilistic trajectories. The first row in each sub-figure plots the probabilistic trajectory of each dynamics. The second row visualizes the simulated client availability by using a colored box to denote that a client is available in that round. The y-axis is the base probability pi to construct pti . In other words, more blank space means that a client is more scarcely available. We simulate the cases where pi ∈ {0.1, 0.5, 0.9}. The detailed construction of pti can be found in Appendix H.2

Table 7: The first round to reach a targeted test accuracy under non-stationary of sine trajectory over 3 random seeds. We study the first round to reach 1/4, 1/2, 3/4 and 1 of the best test accuracy of each data set in Table 2, which is rounded up to the nearest 10% below for ease of presentation. In addition, we sample the mean of test accuracy every 20 global rounds to mitigate noisy progress. Some algorithms may never attain the targeted accuracy due to their inferior performance, where we use “—” as a placeholder. Data sets

SVHN

CIFAR-10

CINIC-10

Quarters

1/4

1/2

3/4

1/4

1/2

3/4

1/4

1/2

3/4

Test accuracy

20%

40%

60%

80%

15%

30%

45%

60%

10%

20%

30%

40%

FedSWE (ours, k = 0) FedAvg over active clients FedAvg over all clients FedAU F3AST

40 20 100 60 40

120 80 420 100 120

200 160 960 160 200

820 900 — 840 1080

20 10 20 10 20

60 20 60 20 40

200 120 520 100 160

1360 1060 — 960 1300

0 0 0 0 0

20 20 20 20 20

120 40 200 80 60

540 800 — 460 540

FedAvg with known pti ’s MIFA (memory aided)

20 20

40 80

100 140

320 600

10 10

20 20

140 80

620 700

0 0

20 20

40 40

400 240

H.3 Additional results In this section, we provide ablation results on FedSWE with k = 0.

Efficient and Unbiased Federated Learning

Table 8: Results after different parameter γ. pti = pi · (γ sin(2π/P · t) + (1 − γ)). Unavailable Dynamics Non-stationary (Sine) pti 0

Data sets Algorithms FedSWE (ours, k = 0) FedAvg over active FedAvg over all FedAU F3AST

γ = 0.3 Train Test 85.7 ± 0.9 % 85.6 ± 0.9 % 82.1 ± 1.1 % 82.0 ± 1.3 % 71.3 ± 2.5 % 71.3 ± 2.8 % 82.5 ± 1.4 % 82.5 ± 1.3 % 82.3 ± 1.0 % 82.3 ± 1.0 %

γ = 0.2 Train Test 85.7 ± 0.5 % 85.7 ± 0.5 % 82.0 ± 1.2 % 81.9 ± 1.2 % 73.2 ± 2.5 % 73.2 ± 2.8 % 83.5 ± 0.3 % 83.4 ± 0.4 % 82.3 ± 0.9 % 82.6 ± 0.8 %

γ = 0.1 Train Test 85.8 ± 0.6 % 85.7 ± 0.7 % 82.3 ± 0.9 % 82.2 ± 1.0 % 74.0 ± 2.1 % 74.9 ± 2.4 % 83.7 ± 0.3 % 83.6 ± 0.3 % 82.9 ± 0.7 % 82.9 ± 0.6 %

FedAvg with known pti ’s MIFA (memory aided)

86.3 ± 1.0 % 84.2 ± 0.4 %

86.2 ± 1.2 % 84.6 ± 0.1 %

86.4 ± 0.9 % 84.6 ± 0.1 %

86.0 ± 1.0 % 84.1 ± 0.4 %

86.0 ± 1.4 % 84.5 ± 0.1 %

86.0 ± 0.8 % 84.4 ± 0.1 %

Table 9: Results after different Dirichlet parameter α. pti = pi (γ sin(2π/P · t) + (1 − γ)). Unavailable Dynamics Non-stationary (Sine) pti 0

Data sets Algorithms FedSWE (ours, k = 0) FedAvg over active FedAvg over all FedAU F3AST

α = 0.05 Train Test 82.5 ± 2.1 % 82.5 ± 2.4 % 78.9 ± 1.6 % 78.5 ± 1.8 % 58.5 ± 3.0 % 58.5 ± 3.8 % 79.5 ± 1.6 % 79.5 ± 1.7 % 78.9 ± 1.3 % 78.9 ± 1.3 %

α = 0.1 Train Test 85.7 ± 0.9 % 85.6 ± 0.9 % 82.1 ± 1.1 % 82.0 ± 1.3 % 71.3 ± 2.5 % 71.3 ± 2.8 % 82.5 ± 1.4 % 82.5 ± 1.3 % 82.3 ± 1.0 % 82.3 ± 1.0 %

α = 1.0 Train Test 90.6 ± 0.2 % 89.7 ± 0.3 % 88.3 ± 0.1 % 87.5 ± 0.1 % 82.0 ± 0.7 % 81.9 ± 0.6 % 88.4 ± 0.1 % 87.6 ± 0.2 % 87.6 ± 0.1 % 87.0 ± 0.1 %

FedAvg with known pti ’s MIFA (memory aided)

84.2 ± 1.0 % 82.6 ± 0.1 %

86.3 ± 1.0 % 84.2 ± 0.4 %

91.5 ± 0.3 % 88.4 ± 0.1 %

83.5 ± 1.0 % 82.6 ± 0.0 %

86.0 ± 1.0 % 84.1 ± 0.4 %

90.5 ± 0.1 % 87.5 ± 0.1 %

Staleness studies. Table 7 illustrates the first round to reach a targeted test accuracy under non-stationary client availability with sine trajectory. Specifications can be found in the caption. It can be easily checked that, during the initial stage (the first three quarters), FedSWE slightly lags behind FedAvg over active clients. However, when reaching the final stage (the last quarter), FedSWE attains the target accuracy in a comparable or lower number of rounds to FedAvg over active clients in the evaluations on SVHN and CINIC-10 data sets. The slowdown of FedSWE on CIFAR-10 data set is worth further investigation. In general, we arrive numerically at the conclusion that the staleness incurred by implicit gossiping in FedSWE is mild. Impact of system-design parameters. In this part, we study the impact of system-design parameter including the degree of non-stationarity γ and data heterogeneity α under nonstationary with sine trajectory. The results are in Table 8 and Table 9. Overall, FedSWE keeps outperforming the algorithms not assisted by memories or known statistics. In Table 9, clients’ local data becomes more heterogeneous when α increases. We can see a clear increasing trend in accuracy. However, FedSWE remains to attain the best accuracies both train and test when compared to the algorithms not aided by heavy memory or known statistics. Moreover, it outperforms MIFA, which consumes a lot of storage space, when α = 0.1 and 1.0. The observations confirm the practicality of FedSWE.

Record · ID 660782 · SHA-256 6d25a6b6fc820050
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.