Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailability
Authors: Ming Xiang
Stratis Ioannidis
Edmund Yeh
Carlee Joe-Wong
Lili Su
Venue: NeurIPS 2024 poster (2024)
Keywords: distributed learning
non-convex optimization
federated learning
fault-tolerance
Primary area: optimization
TL;DR: We propose FedAWE, an efficient algorithm for handling heterogeneous and non-stationary client unavailability in federated learning, achieving linear speedup and outperforming state-of-the-art methods in experiments over diversified dynamics.

Abstract: Addressing intermittent client availability is critical for the real-world deployment of federated learning algorithms. Most prior work either overlooks the potential non-stationarity in the dynamics of client unavailability or requires substantial memory/computation overhead. We study federated learning in the presence of heterogeneous and non-stationary client availability, which may occur when the deployment environments are uncertain, or the clients are mobile. The impacts of heterogeneity and non-stationarity on client unavailability can be significant, as we illustrate using FedAvg, the most widely adopted federated learning algorithm. We propose FedAWE, which includes novel algorithmic structures that (i) compensate for missed computations due to unavailability with only $O(1)$ additional memory and computation with respect to standard FedAvg, and (ii) evenly diffuse local updates within the federated learning system through implicit gossiping, despite being agnostic to non-stationary dynamics. We show that FedAWE converges to a stationary point of even non-convex objectives while achieving the desired linear speedup property. We corroborate our analysis with numerical experiments over diversified client unavailability dynamics on real-world data sets.

Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailability
Ming Xiang'
Stratis Ioannidis'
Edmund Yeh
Carlee Joe-Wong" Lili Su
Northeesteer University, Boston, MA *Carnegie Mellon University, Pittsburgh, PA
(xiang. mi, 1.,1.ssl. sul.suueoortto snortheetseeer edu
{ioannidis eyeh Pece neu. edu cjoewong@andrer cmu. edu
Abstract
Addressing intermittent client availability is critical for the real-world deployment federated learning algorithms. Most prior work either overlooks the potential non-stationarity in the dynamics of client unavailability memory/compputaion overhead. We study federated learning the presence heterogeneous and non-stationary client availability, which may occur when the deployment environments are uncertain, or the clients are mobile. The impacts heterogeneity and non-stationarity client unavailability can be significant, as we illustrate using FedAvg, the most widely adopted federated learning algorithm. We propose FedAWE, which includes novel algorithmic structures that (i) compensate for missed computations due to unavailability with only O(1) additional memory and computation with respect standard FedAvg, and (ii) evenly diffuse local updates within the federated learning system through implicit gossiping, despite being agnostic to non-stationary dynamics. We show that FedAWE converges a stationary point of even non-convex objectives while achieving the desired linear speedup property. We corroborate our analysis with numerical experiments over diversified client unavailability dynamics on worldworld data sets.
requires substantial
Introduction
Federated learning is distributed machine learning approach that enables training global models without disclosing raw local data [32, 21]. has been adopted in commercial applications such as autonomous vehicles [6, 70, 41], the Internet of things [39], and natural language processing [63, 43].
Heterogeneous data and massive client populations two of the defining characteristics of cross- device federated learning systems [32, 21 Despite intensive efforts [32, 29, 68, 45, 21], several key often overlooked in the existing literature [42]. One of the primary hurdles is the issue of client unavailability. Intuitively, more active clients drive the global model their local optima by overfitting their local data, which biases the training. In addition, the higher the uncertainty in client unavailability. the larger the performance degradation. Concrete examples that confirm these intuitions in the context of FedAvg the most widely adopted federated learning algorithm can be found in Section 4. Client unavailability issues can arise from internal factors such different working schedules and heterogencous bardware/software constraints. External factors, such as poor network coverage and frequent handovers of base stations due fast movements, only exacerbate these problems [50, 57, 64, 3, 21]. The intricate interplay of internal and external factors results in the non-stationarity and heterogeneity of client unavailability.
challenges that arise from the involvement of large-scale client populations
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Most prior work either assumes exact knowledge of the clients' available dynamics or requires their dynamics to be benignly stationary [32, 27, 42, 54, 55, 11]. A related line of work studies asynchronous federated learning wherein clients are vulnera- ble to delays in message transmission and the reported model updates may be stale [59, 38, 49, 25J. The proposed methods therein assume the availability of all clients or uniformly sam- pled clients, making them inapplicable to our settings. A few recent works [44, 58] study non-stationary dynamics. Ribero et al. [44] consider the settings where the available probabilities follow a homogeneous Markov chain. Xiang al. [58] require that clients be capable of continuous local optimization regardless of communication failures. A handful of other works [14, 60] memorize the old gradients of the unavailable clients compensate for their unavailability. However, the added memory burdens the federated learning system with substantial memory proportional the product of the number of clients and the model dimension.
Porumeter
Pi
PP
p4
Figure 1:
Client i's available proba- bilities p 's are hetcrogencous and are subject to non non-stationary dynamics.
Contributions. In this work, we focus on stochastic client unavailability, where client is available for federated learning model training with probability v at any time t. An illustration can be found in Fig. 1. Our contributions are four-fold:
In Section 4, via constructing concrete examples, we demonstrate that both heterogeneity and non-stationarity of pl will result in bias and thus significant performance degradation of FedAvg. In Section 5, we propose an algorithm named FedAWE, which features computational and memory efficiency: only ((1) additional computation and memory per client will be used when compared with FedAvg. The design of FedAWE introduces two novel algorithmic structures: adaptive inno- vation echoing and implicit gossiping. At a high level, these novel algorithmic structures (i) help clients catch up the missed computation, and (ii) simultaneously enable a balanced information mixture through implicit client-client gossip, which ultimately corrects the remaining bias. Notably, no direct neighbor information exchanges are used, and the client unavailability dynamics remains unknown to all clients and the parameter server.
In Section 6, we show that FedAWE converges stationary point of even non-convex global objective and achieves the linear speedup property without conditions on second-order partial derivatives of the loss function in analysis.
In Section 7, we validate our analysis with numerical experiments over diversified client unavail- ability dynamics on real-world data sets.
2 Related Work
Dynamical client availability. There is recent surge of efforts to study time-varying client availability [45, 44, 7, 54, 44, 42, 58, 11], which can be roughly classified into two categories depending whether the parameter server can unilaterally determine the participating clients.
(i) Controllable participation. Earlier research [32, 29] presumes that, in each round, the parameter server could select a small set of clients either uniformly at random or in proportion to the volume of local data held by clients. More recently, Cho al. [10] design adaptive and con-uniform client sampling to accelerate learning convergence, albeit at the cost of introducing a non-zero residual error. In another work, Cho al. [8] 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 decided unilaterally by the parameter server. Perazzone et al. [42] consider heterogeneous and time-varying response rates of under the assumptions that pł is known a priori and that the stochastic gradients are bounded in expectation. Furthermore, the dynamics of P are determined by the parameter server by solving a stochastic optimization problem. Chen et al. [7] propose 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 pf 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 response rates P nor assumes that the parameter server has any influence on pÝ.
(ii) Uncontrollable participation. There is a handful of work on building resilience against arbitrary client availability [44, 54, 60, 14, 62, 55]. Ribero et al. [44] consider random client availability whose underlying response rates are also heterogeneous and time- varyingrying with unknown dynamics.

---

However, the underlying dynamics of P in [44] are assumed to follow a homogeneous Markov chain. Wang and [54] propose generalized FedAvg that amplifies parameter updates every rounds for some carefully tuned P. Despite its elegant and unified analysis and potential to accommodate non-independent unavailability dynamics, to reach a stationary point, p needs to satisfy some assumptions to ensure roughly equal availability of all clients over every P round. Sharing a similar spirit, Crawshaw and Liu [11] propose a SCAFFOLD variant that amplifies global parameter and local gradient updates every P round. In spite of its communication efficiency and resilience to data heterogeneity, the rolling average of p over every P round is assumed to be the same constant for all clients. Yang et al. [62] analyze 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 [14, 60] share the same idea of using the memorized latest updates from unavailable clients for global aggregation. Despite superior numerical performance, both algorithms demand a substantial amount of additional memory [55]. For non-convex objectives, both [60] and [14] require absolute bounded inactive period, and share similar technical assumptions such as almost surely bounded stochastic gradients [60] Lipschitz Hessian [14]. 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. Wang and Ji consider unknown heterogeneous p;" in a concurrent work [55]; however, p, 's are assumed to be fixed over time.
Asynchronous federated learning. Another related line of work is asynchronous federated learning. To the best of our knowledge, Xie et al. [59] initialize the study of asynchronous federated learning, wherein the parameter server revises the glohal model every time it receives an update from a client. Convergence is shown under some technical assumptions such weakly-convex global objectives, bounded delay, and bounded stochastic gradients. Zakerinia et al. [69] propose QuAFL which is shown to be resilient to computation asynchronicity and quantized communication yet under the bounded and stationary delay assumption. Nguyen et al. [38] propose FedBuff, which uses additional memory to buffer asynchronous aggregation to achieve scalability and privacy. Convergence shown under bounded gradients and bounded staleness assumptions. In fact, most convergence guarantees in the asynchronous federated learning literature rely on bounded staleness [59, 38, 49, 25]. or bounded gradients [59. 38, 25]. Recently, arbitrary delay is considered in the context of distributed SGD with bounded stochastic gradients and (0, ç)-bounded inter-client heterogeneity [33] (see Assumption for the definition). The convergence suffers from non-zero residual term O(²²). In contrast, our convergence guarantee free from non-zero residual terms and does not require gradients to be bounded.
3 Problem Formulation
A federated learning system consists of a parameter server and m clients that collaboratively minimize
m
min F(x) #ERd
F((x))
where (x) A EE,-D, (2; E:)] is the local objective and can be non-convex, Dj is the local distribution, & is stochastic sample that client has access to, L, is the local loss function, and d is the model dimension.
We use Assumption 1 to capture the uncertain non-stationary dynamics and heterogeneity. Let A' denote the set of active clients, 1 (-) an indicator function, T the number of total training rounds.
Assumption 1. There exists 8 (o, 1] such that pt A [811 (ie 2 8, where the events (i E At} are independent across clients and across rounds / E [T]]
Assumption subsumes uniform availability [27, 62] and stationary availability considered in [55]. Independent client unavailability is widely adopted by federated learning research [27, 29, 23, 61, 62, 55]. Analyzing indeependddnt unavailability, together with uncertain and non-stationary dynamics in Assumption 1, is in general challenging. Specifically, the involved entanglement of stochastic gradient and availability statistics fundamentally complicates the theoretical analysis. However, we conjecture that independence and strictly positive probabilities are only necessary for the technical convenience of our analysis. Our experiments in Section suggest that our algorithm offers notable improvement even in the presence of non- non-independent and occasionally zero-valued probabilities.
3

---

Future work will investigate how to provably accommodate correlated or zero-valued probabilities of arbitrary probabilistic trajectories.
Heterogeneity and Non-stationarity May Lead to Significant Bias
In this section, we illustrate the impacts of heterogeneity and non-stationarity of client availability under clas- sic FedAvg. We use two examples showcase the signifi- cant bias incurred.
1.0
0.6
Example 1 (Heterogeneity). Suppose that m and pl p: for E [2]. Let F; (a) _ || - us /2, where æ, u4 E The global objective (1) is
0.4
20
0.2
F (z) 2 (11==11-))) un 11 + u2ll2).
0.0
0.2
0.4
0.6
0.8
1.0
P1.
with unique minimizer x (u1 + u2)/2. Let un and
Figure 2: Let Touppt lim; [xx*]
U2 100. Fig. 2 illustrates how the heterogeneity in pt affects the expected output of FedAvg.
Under most of the choices pt, P2. Toumput is far from x²".
Example matches [55, Theorem 1], which shows that FedAvg leads to biased global objective (3) under heterogeneous p; s, and that (3) may be significantly away from (1) depending on p.'s.
F(x)
Pr Pj Fx(2).
When the probabilistic dynamics of p is non-stationary, obtaining exact biased objective similar (3) near analytical form becomes challenging. if not impossible, due to the unstructured non- stationary dynamics. Fortunately, Example 2 helps us confirm that the complex interplay between pf's across rounds and clients will inevitably further degrade the performance of FedAvg algorithm.
Example 2 (Non-stationarity). In Fig. 3, total of m = 100 clients perform an image classification task on the SVHN dataset [37] under the FedAvg algorithm, whose local dataset distribution follows Dirichlet(0.1) [17]. Clients become available with probability Pp = p sin.iinO..1 (0.11-t)) +f -7)], vi E [m]. The hyperparameter details are deferred to Appendix J. Observations can be found in the caption.
82%
80%
0=0.3
0.3
p=0.5
70%
0.5.5
p-100
68%
p 1.0
y-
y- Non-stationary Degree
0-
0-5.5
0.1.1
y- Non-stationary Degree y-
(a) Train accuracy.
(b) Test accuracy
Figure 3: Train and test accuracy results in percentage (%). In particular, the parameter y signifies the degree of non-stationary. Notice that, the client availability becomes more non-stationary (a larger 7), FedAvg experiences significant drop accuracy. For example, both the train and accuracies drop by over 10% when p = 0.1, and y increases from 0.1 to 0.5.
5 Federated Agile Weight Re-Equalization (FedAWE)
To minimize (1), one natural idea is to have the entire client population performs the same number of local updates and mixes these updates carefully to ensure they are weighted equally. Unfortunately, when clients are available only intermittently, they will miss some rounds. A naive approach to equalizing the number of local updates to have clients catch up by performing their missed local computations immediately when they become available. However, this approach requires daunting

---

Algorithm 1: FedAWE
1 Inputs: T. 8, M,s 7g x
2 for i E [m]] do x. f- x and (0) f -1;
3 for 1. = 0,.., do
4 for i E A' do
x² t+ t Di Eie,i 26!1; 15
(1,0)
(- a
for bori E [m] do if' E A' then
6
for
k = 0. ... do
17
2
(1,++1)
18
x t x²t!1
(t,k)
1) (2 (1.k), 51 e((ik));
else
8
2
xtt1 ++1 < x/: ni( + +
9
end
10
G f x (1,0)
I [,,s)
21
end
2
7g
(t))
12
(t + 1) t t;
Report x² to the parameter server;
14
end
23
end
amount of resources and may not be possible due to hardware/software constraints. Formally, recall that A' is the set of available clients time Let (t) - {t' t' and A²), denote the most recent (with respect to time t) round that client is available. Compared with standard FedAvg, the naive "catch-up" procedure will consume (t (1) - 1) local stochastic gradient descent updates and (t - (t) 1) additional stochastic samples, where s is the number of local updates per round when a client available in standard FedAvg.
In this work, we target computation-light algorithms that, compared with FedAvg, only take ((1) additional computation without additional stochastic samples. We propose Federated Agile Weight Re- De-FEqulizztion (FedAWE), which is formally described Algorithm 1. involves two novel algo- rithmic structures: adaptive innovation echoing and implicit gossiping. At a high level, these novel algorithmic structures (i) help clients catch up on the missed computation, and (ii) simultancously enable a balanced information mixture through implicit client-client gossip, which ultimately corrects the remaining bias.
In Algorithm 1, each client keeps two local variables x; and Ti, along with few auxiliary variables used in updating æ, and TR. The algorithm inputs are rather standard: total training rounds T, local and global learning rates yy and 7/.. the number of local updates per round 8, and the initial model 2 In each round f, similar to FedAvg, an available client E A'' performs steps of stochastic gradient descent on its local model x (lines 5-8), where (=: (f.K)) is the stochastic gradient of sample <) e(t,)) Next, we describe the two novel algorithmic structures used in FedAWE.
Adaptive innovation echoing. Departing from FedAvg wherein the local estimate a is updated as at! +- x (t,0) n, G.. In FedAWE (lines 10-11), we "echo" the local innovation G by multiplying it by (t- (()). Intuitively, this simple echoing helps us approximately equalize the number of local improvements, as formally stated in Proposition It says that the total numbers of innovations echoing are the same for all active clients for any given round and allows the unavailable clients to catch up to the missed computations when they become available.
Proposition 1. If (iE 1) = 1, it holds that ER=1 ((EEA)) (t- (c))((t) = RR21
Implicit gossiping. In FedAWE, the parameter server does not send the most recent global model to the active clients at the beginning of round. Instead, the parame- ter server aggregates the locally updated models z!! and sends the new global model r++ to all active clients A² (lines 15-1 By postponing multicasting the shared global model, the active clients in A' implicilly gossip their updated local models with each other through the parameter server [58]. Though the postponed multi-cast brings staleness, a simple coupling argument shows that the staleness is bounded (Lemma 2). In addition, empirical results (Table 8 in Appendix J) suggest that there is
if 4'; 1. if and of A':
(4)
0. otherwise.
5

---

no significant slowdown when compared to vanilla FedAvg. Gossip-type algorithms were originally proposed for peer-to-ppee networks and are well-known for their agility communication failures and asynchronous information exchange in achieving average consensus [13, 4, 24, (6,31,66) Intuitively, the clients' local estimates are eventually equally weighted in the final algorithm output. Note that, de- parting from the standard gossiping protocols therein [24, 46), information exchange in FedAWE does not involve client-client communication. The information mixing matrix under FedAWE is defined
in (4), which doubly stochastic. Let M(O) - ()))( p(() _ >2
11 /m,
and p & max; p(t), where (2(-) denotes the second largest cigenvalue. We next characterize the information mixing error, i.e., consensus enror in Lemma 1.
Lemma 1 ([35, 34, 51]). For any matrix B E Raxm, it holds that Ew [| - - 1B
p'l B ppp where the expectation is taken with respect to randomness in W matrices.
6 Convergence Analysis
In this section, we analyze the convergence of FedAWE. All missing proof's and intermediate results are deferred to the Appendix. Details can be found in Table of Contents.
6.1 Assumptions
We start by stating regulatory assumptions that common in federated learning analysis (27, 23]. Assumption 2. Each local objective function (z) is L-Lipschitz, i.c.,
[[VF((z)) - (F((22) I L || - æ2112 Væ æ2, and V E [m]. Assumption 3. Stochastic gradients Ve, {) are unbiased with bounded variance, i.e., E (V((((;) æ] (x)) and ([;; {) - VF(())) m| S o², V E [m].
Assumption 4. The divergence between local and global gradients is bounded for B, C 2 such that
1 [VF(x) - VF 8 [V
(5)
When the local data sets are homogeneous, (Z) F holds for any client i E [m]. resulting in B O. Assumption 4 and its variants in Table 1 often referred to as bounded gradient dissimilarity assumption to account for data heterogeneity across clients. It can be easily checked that our Assumption 4 is more relaxed or equivalent to the variants therein.
Table 1: Popular variant assumptions on gradient dissimilarity.
Bounded Gradient Dissimilarity
References
max (F 112 = <², V E [m]
[29, 66, 9, 10, 60)
1
-= VF < 1
[27,20 28]
Σ i=l [F( [Z) - VF S c²
[53, 65, 18, 56, 1, 22, 54, 62)
E (F B (VF()) 2 c2²
[23, 68, 52, 51, 14]
m
6.2 Auxiliary/mmaginrry update sequence construction.
Directly analyzing the evolution of x' and of is challenging due to the fact that different clients update different rounds, and that different active clients echo their local innovation G (line in Algorithm 1) with different strength (t - r;). As such, we construct an auxiliary/imaginry update sequence 2 for client i [m]. whose evolution is closely coupled with x' and x but is easier to analyze. Note that the auxiliary/imagiarry update sequence is never actually computed by clients but acts necessary tool in building up the analysis.
Definition 1. The auxiliary sequence { of client E [m] is defined as
2 P x mmgg(( ri(t)= (x T (0+1), Vie [m].
(6)

---

Recall that (0) -1. Thus. by definition, x = x according to (6). For general t. when client E AA we simply have (t) auxiliary model zf and the real model a are identical whenever the client i becomes available in the previous round.
and thus - (t) - (t 1) That is, the
When E A the iterate of z; is a bit more involved:
EjEAt t-1 A
(x) 25
nnn 11 (t- (1)t-11);-111
(7)
(7.c)
where (7.a) holds because of Definition and i E A' (7.b) because of line 10 in Algorithm 1, addition and subtraction. (7.c) can be expanded by (6). We defer the simplified form of (7) to (18) in Appendix C for a tidy presentation.
When i $ A 2 has simple iterative relation:
x = 2
(8)
At a high level, the sequence 2 approximately mimics the ideal descent evolution at client as the client performs local optimizations its local model z; per round regardless of its availability. Mathematically, the idea is that, if the progress per iteration of the auxiliary sequence 2 is bounded, we can show the convergence of æ when æ; and 2 are close to each other.
worth noting that auxiliary sequences are used in peer-to-pes distributed learning literature [47, 2, 30, 67, 48, 34]. Yet, existing constructions are not applicable to our problem due to (1) the non-convexity of the global objectives, (2) multiple local updates per round, (3) possibly unbounded gradients, and (4) the general form of bounded gradient dissimilarity. Departing from the use of staled stochastic gradients for auxiliary updates therein, we adopt the true gradient (.). to avoid the complications from the involved interplay between randomness in stochastic samples and randomness in (t). On the technical front, it follows from Definition 1 that || =z11 I vi s (t) 1) (z;
whose bound appears to be quite challenging to derive due to the coupling of different realizations of T, (t) and gradients. As such, we bound the average of ||m| 2 1| across clients and rounds in Proposition 2.
Lemma 2 (Unavailability statistics). Under Assumption I and defined therein. It holds for t 2 0 that E [t - T; (t) S 1/6 and ((==T(()) s 2/82.
Lemma 2 yields an upper bound on the first and second moments of a client i's unavailable duration despite the unstructured nature of clients' non-stationary and heterogeneous unavailability. In the special case where we have clients available with the same probability ó, the duration simply follows a homogeneous geometric distribution. It can be casily checked that our bounds trivially hold. However. the duration becomes a more challenging non-homogeneous geometric random variable under our non-stationary unavailability dynamics. Lemma 2 can be derived by using simple coupling argument and by using tools from probability theory [15].
6.3 Main results.
Let 2, A E. 2/, F ming F(x), and 6max A max vi.
Lemma 3 (Descent Lemma). Let Ft define the sigma algebra generated by randomness up to round Suppose Assumptions 2, 3 hold and miy S (/00ss)). holds that
E [F()(+1)- -F(=F))))))))) 15
2 (mmg + 4.5mmn7 sL)
Σ (t (t))²
m²
35 L2 m
(1 - -1-T((1))² (F.1) ((000)
m
i=1
2. 2.2n sT?
m
mg m
| 2
2 2 21
m
2m
Approximation Error
Consensus Error

---

The proof of Lemma 3 follows from the standard analysis for non- non-convex smooth objectives but with non-trivial adaptation 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 2 (Approximation error). Given Assumptions 2 and 4, it holds that
m
2 2 6tfi Bl
2 2
|
<|1b]]
(
R
82
T
62
6L
2
2 11
E
||
=11]]
(9)
8
The proof of Proposition 2 starts from Definition 1. Although in general it is difficult to bound the error, Assumptions and 4 allow us break down the problem into bounding the averaged gradient norm of zz and the consensus error over all randomness instead. Next, we analyze the consensus error. Note that although implicit gossiping takes place in Algorithm for ær, its analysis is technically challenging as discussed before. So, we adopt the auxiliary 2 as an intermediary and apply Young's 's inequality to bound the actual consensus error. Details will be specified next. Formally, the auxiliary models can be expressed in a compact matrix form as (t) _ [zi...., = Their local parameter innovation matrix Go is formulated by combing (7) and (8). We refer the interested readers to (19) in Appendix C for the exact formula. Unrolling the recursion, the consensus error can be expanded as
- 2 (z(t-)) - nm, G1--1) w(t-t) (I- 1) (10.a) niing E ((o)
II l=q
[ww--
-
(10)
where equality (10.a) holds because all clients are initiated at the same weight.
Lemma ([58)). Under Assumption 1, it holds that p S 1 5 5'01-(1-8)")
Recall that p bounds the expected spectral norm of the information mixing matrix W(O, It is important to have p < 1 for an exponential decay of the consensus error (see Lemma 1). We now proceed to present the convergence rates. In the sequel, we assume it holds for 77 and ? that
(1 - vp) 5
5
Tjrlg [ 1) 1) +1)(+++)++))) (F TI S 200ssL (I++)
(1I)
The proof of the consensus error borrows insights from the analysis of the gossip algorithm [35. 53] but with substantial adaptation to accommodate the novel auxilíary formulation and multi-step local updates. Under the learning rate conidtions in (1 I) and Assumptions 1, 2, and 4, we can show that
mf EE =11
mT -Σ=[
1 ME
(12)
It remains to bound the full convergence error of z/, which is presented in Theorem 1. Theorem 1 (Convergence error of 2)). Suppose that Assumptions 1, 2, 3 and hold. Choose learning rates nn and ng such that the conditions in (11) are met for T > 1, it holds that
Σ [[VE(>>>) <
(F(*") - F+)
Log 5max
0² 5² 82 - (2(1-pp)) (13)
ST
m
82
By addition, subtraction, and Young's inequality, (14) and (15) hold under Assumption 2.
Σ
=1 (14)
Σ E [IV
(15)
8

---

Moreover, from (12), (14) and (15), it can be seen that (16) holds.
T-1 ΣΣ x11 =
E
V VVF
(16)
mT t=0
C
Combining (12), (13), (14) and (15), we are ready for Corollary 1. Corollary 1 (Convergence rate of æ²). Suppose that Assumptions 1, 2, 3 and hold. Choose learning rates as = VTst. "l = v ssm such that the conditions in (11) are met for T 2 1, is holds that
E
[12]
L (F(*")-F) -
mmax
Sm
o )
(17)
VodmT
8 V sm
8(1 611-2)2 T
Corollary establishes the full convergence rate for FedAWE algorithm. It can be seen that the first and second terms dominate when T is sufficiently large, which relate to initial suboptimality gap and stochastic gradient noise o², respectively. The non-stationary client unavailability results in the third term, which relates to gradient divergence ç² and also to o². The proof of Corollary I follows from (15) by plugging in Proposition 2 and Theorem 1. In the special case where clients participate uniformly at random, we simply have 8max = 8 = k//m. Our convergence bound attains the rate of (kT) In other words, we achieve the desired linear speedup property with respect to the number of local steps s and the number of active clients kt matching the established literature [61, 54, 65, 66]. The linear speedup property enables a large cross-device federated learning system to take advantage of a massive scale of parallelism. Notice that the consensus error (16) and the convergence rate (17) have the same asymptotic order with respect to the parameters therein. Hence, the consensus error also enjoys the desired linear speedup property when T is sufficiently large.
7 Numerical Experiments
Overview, In this section, we evaluate FedAWE on real-world data sets to corroborate our analysis and compare it with the other state-of-the-an algorithms. The missing specifications and additional results can be found in Appendix J. Specifically, we consider a federated learning system of one parameter server and m 100 clients, wherein clients become available intermittently. The image classification tasks use CNNs and are based on SVHN [37], CIFAR-10 10 [26] and CINIC-10 [12] data sets. All of them include 10 classes of images of different categories. To emulate a highly heterogeneous local data distribution, the image class distribution V4 ~ Dirichlet(a = 0.1) at client i [17, 54, 55].
Non-stationary client unavailability. A total of four unavailable dynamics are evaluated in Table including stationary and non-stationary with staircase, sine and interleaved sine trajectories, with their visualizations available in the same table. The classification tasks become more challenging as the list progresses due to the growing complexity in the non non-stationary dynamics. Furthermore, our choices of the non-stationary dynamics are motivated by real-world federated learning participation statistics, for example, sine trajectory [3], and by generalizing the existing participation patterns such as cyclic participation [8. 55). In particular, the interleaved sine dynamics is more challenging than the vanilla cyclic availability dynamics since clients become available during each active period with probability that less than 1 and non-stationary simultaneously. Formally. client i's dynamics is defined as of ps ft((), where fi(() is a time-dependent function under non-stationary dynamics but fa(() = 1 when stationary, and p: (vi, Φ). e characterizes the unbalanced contribution of different image classes to the generated probabilities. Each element of (d), is drawn from Uniform(0, 4c), where smaller &. leads to a less significant contribution of that image class.
Correlating the local data distribution and the probability of client availability is a common practice in the prior literature. For example, Gu al. in [14] experiment with formula for p: so that clients that hold images of smaller digits participate less frequently. Wang and Ji in [55] construct Pa as an inner product of the clients' local data distribution V4 and an external distribution &'. is immediately clear that the coupling of local data distribution (N; ~ Dirichlet(a = 0.1)) and class contribution leads to non-independent p,'s. s.. addition, Assumption will not hold in the case of interleaved sine non-stationary dynamics since p occasionally reach O. Although being agnostic to the challenging client unavailability dynamics not covered by our analysis, we observe that FedAWE retains its outperformance. Comparisons will be specified next.

---

Table 2: Results and comparisons on real- world datasets form mean accuracy 1 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) not aided by memory known statisties; (2) ones assisted by memory or known statistics. For a fair competition, we boldface the best accuracy the first group, while the second best underlined.
Unavailable
Datasets
SWHN
CIFAR-10
CINIC-10
Dynamics
Algoršthiss
Train
Test
Train
Train
FeciAE (ours)
86.5
0.7%
86.1
0.7
68.1
1.4%
66.3 1 1.1
47,9 = 2.1
47.3 1: 2.0%
Stationayy
FedAvg over active Fedkvg all
82.6
1.0%
82.4
1.1%
64.1 + 1.%
62.9 + 1 %
43.6 + 24 %
43.1
+ 2.4
76.1 2.1% %
76.1
2.4%
55.8
2.1
5544 + 18%
38.4
%
38.0
2.1 %
FadAlI
81.4 1.0%
812- 1.0%
65.4
64.1
45.6
45.2
F3AST
83.2 0.7 %
0.7% 83.2
64.4
%
63.5 0.99
45.3 = 1.2
44.8 +
Fadkvg, with known pt's
86.1 0.5
85.6
0.5
65.4
1.0%
63.1 +.9
45.0
1.2%
44.6
1.1
NIFA (memory alded)
84.2
0.5 %
0.6 84.1
66.6 +: 0.8%
65.3 + 0.6 %
47.5 = 0.5 %
46.9 + 0.5
(memory
Non-stutionary
Fodivg over active
FeCANE (ours)
82.5
1.0
82.4
0.9
64.2 1.8%
66.0
63.0 1:
43.7
47.5
2.0%
42.3
(Staircaase
Fadkyg over all
75.9 = 2.1
75.9 2.3
55.7 2.1 %
55.4
%
38.4
2.0
37.9 + 2.0
FedAU F3AST
83.6 = 0.8
83.4 0.8
65.2
63.9 +:
45.7
45.1
%
Junu
1.15
63.3
45.2 1.2
Fadkig with known pt's
85.8
85.2 0.9
1.6%
66.1 +
45.0
44.7
NIFA (memory aided)
81.2
0.5%
81.0 = 0,5 %
66.7 2 0.7 %
65.3 + 0.5 %
17.5 = 0.5 %
16.9 + 0.5
FedVARF (momory aided)
0.2% 84.6
84.3
0.3%
67.3 0.3
66.1 +:
47.7 0.2
47.2
0.1
FocANE (ours)
85.7 0.9
85.6
0.9
64.9
1.9
63.5 +: 2.0
46.4
2.4%
45.8 +: 2.4
Non-stationary (Sine)
FedAug over active
N2.1 1.1%
82.0
63.3
62.1 +
43,1
42.6
Feddug over all
71.3
2.5%
71.3
2.8 %
$2.2 2 2.4%
$2.1 1 2.2 %
36.1 = 2
36.0
1.9
FedAU F3AST
62,5 = 14% %
K2.5
1,3
64.2 14222233
63.0 +
44.4 =
43.9 4: 2.1
Fodking with known pt's
1.0%
47.9
47.4
NTFA (memory aldec)
84.2
0.4
0.4 84.3 0.1
84.1
(6.6 0.8 %
65.5 +
47.4 + 0.1
46.9 + 0.4
FedVARP (memory alded)
84.5
0.2
67.4 2: 0.2 %
66.0 + 0.3 %
47.7 = 0.1 %
47.1 + 0.2 %
FedAMB (ours)
85.2
1.6 %
84.6
1.6
64.8 2
63.3 +:
47.1 : %
46.6
2.7
Non-stationary (Interleaved Sine)
Fodivg over active
60.7
41.9
41.5
Feddog over all FadAU F3AST
69.5
3.4%
69.5
51.3 2.7 %
51.3 1:
35.9
2.0%
35.6
2.0
82.6
1.3%
$2.4
1.1
63.9 + 2.2%
62.8 +
%
44.2 = 2.2
43.8
2.1
MCAA
81.3
1.2%
$1.3
1.2%
62.2 2.1
61.3
43.1 2.2
42.7
2.2
Feddvg with known pl's
2.1
2.2
(ovemory oideaf)
83.8
1.9
64.6
46.1
45.9
PedVARP (memory aided))
84,5
0.3 %
81.1 0.5
%
67.3 2
%
65.7 1:
0.2
%
47.7 =
0.5
47.2 1:
0.3 %
Benchmark algorithms and discussions. We compare FedAWE with six baseline algorithms, includ- ing FedAvg over active clients [32], FedAvg over all clients, FedAU [55], F3AST [44], FedAvg with known p [42], MIFA [14] and FedVARP [20]. The details of the algorithm and the additional results deferred to Appendix J. It is observed that FedAWE consistently outperforms the algorithms not aided by memory or known statistics. Surprisingly, FedAWE occasionally beats MIFA and FedVARP, which are memory-heavy We attribute it to reuse of stored gradients from the unavailable clients. Although FedAWE brings in stalenss due to implicit gossiping, our results (Table 8 in Appendix J) indicate that there is no significant slowdown for FedAWE when compared to vanilla FedAvg, where we study the first round to achieve a targeted accuracy by different algorithms. In addition, FedAWE at- tains competitive even better performance than FedAvg with known probability, yet unknown to the underlying dynamics in client unavailability.
8 Conclusion
In this paper, we have shown that the impacts of heterogeneous and non-stationary client unavailability can be significant through concrete examples on FedAvg. To address this, we have proposed an algorithm FedAWE, which provably converges by adaptively echoing clients' local improvement and by evenly diffusing local updates through implicit gossiping. Theoretically. it achieves the desired linear speedup property. Experiments have validated the superiority of FedAWE over ofte-of-theean algorithms under diversified non-stationary dynamics. Future work will investigate how to extend our analysis to broader unavailability dynamics such as non-independent and non-stationary unavailability and how to incorporate our findings into federated learning algorithms of different local optimization methods.
10

---

Acknowledgments and Disclosure of Funding
We gratefully acknowledge the support from the National Science Foundation under grants 2106891, 2107062, the National Science Foundation CAREER award under grant 2340482,, and the Sony Faculty Innovation Award. The research was sponsored by the Army Research Laboratory under Cooperative Agreement Number 1991NNF-2322-000 document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory, 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. We also thank Connor J. McLaughlin for valuable discussions and feedback on this work.
The views and conclusions contained in this
References
[1] Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In International Conference on Artificial Intelligence and Statistics, pages 1232-1300. PMLR, 2023.
[2] Dmitrii Avdiukhin and Shiva Kasiviswanathan. Federated learning under arbitrary communi- cation patterns. In International Conference on Machine Learning, pages 425-435. PMLR, 2021.
[3] Keith Bonawitz. Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, et al. Towards federated learning scale: System design. Proceedings of Machine Learning and Systems, 1:374-388, 2019.
[4] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508-2555 2006.
[5] Dan Busbridge, Jason Ramapuram, Pierre Ablin, Tatiana Likhomanenko, Eeshan Gunesh Dhekane, Xavier Suau Cuadros, and Russell Webb. How to scale your ema. Advances in Neural Information Processing Systems, 36, 2024.
[6] Lin-Hua Chen, Min-Rong Chen, Guo- AiooQQiag Zeng, and Jia-Si Weng. Bdfl: byzantine-faute fault- tolerance decentralized federated learning method for autonomous vehicle, IEEE Transactions on Vehicular Technology, (019):8639-865, 2021.
[7] Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for federated learning. Transactions on Machine Learning Research, 2022.
[8] 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, pages 5677-5721. PMLR, 23-29 Jul 2023.
[9] Yae Jee Cho, Jianyu Wang, Tarun Chirvolu, and Gauri Joshi. Communication-effcientt and model-hheterogeneous personalized federated learning via clustered knowledge transfer. JEEE Journal of Selected Topics in Signal Processing, 2023.
[10] 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.
[11] Michael Crawshaw and Mingrui Liu. Federated learning under periodic client participation and heterogeneous data: A new cummunication-cfficcee algorithm and analysis. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[12] Luke Darlow, Elliot J Crowley, Antreas Antoniou, and Amos Storkey. Cinic- is not imagenet cifar-10 10. arXiv preprint arXiv:1810.03300 2018.

---

[13] Morris H DeGroot. Reaching consensus. Journal of the American Statistical association. 69(345):118112) 1974.
[14] Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang. Fast federated learning the presence of arbitrary device unavailability. Advances in Neural Information Processing Systems, 34:12052- 12064, 2021.
[15] Allan Gut. Probability: graduate course, volume 200. Springer, 2006.
[16] 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.
[17] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.0633 2019.
[18] 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.
[19] Mark Jerrum and Alistair Sinclair. Conductance and the rapid mixing property for markov chains: the approximation permanent resolved. In Proceedings of the Twentieth Annual ACM Symposium Theory of Computing, pages 235-244, 1988.
[20] Divyansh Jhunjhunwala, Pranay Sharma, Aushim Nagarkatti, and Gauri Joshi. Fedvarp: Tack- ling the variance due to partial client participation federated learning. In Uncertainty in Artificial Intelligence, pages 906-916. PMLR, 2022.
[21] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Har- chaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi. Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems federated learning. Foundations and Trends@ in Machine Learning, 4(1-2))1-210 2021.
[22] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heteroge- neous datasets via bucketing. In International Conference on Learning Representations. PMLR, 2022.
[23] 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.
[24] David Kempe, Alin Dobra, and Johannes Gehrke Gossip- based computation of aggregate information. In 44th Anmual IEEE Symposium Foundations of Computer Science, 2003. Proceedings., pages 491. IEEE, 2003.
[25] Anastasiaa Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous sgd for distributed and federated learning. Advances in Neural Information Processing Systems, 25:17202-172155 2022.
[26] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers features from tiny images. 2009.
[27] 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 4500 2020.
12

---

[28] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy, Feddane: federated newton-typa type method. In 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pages 1227-1231. IEEE, 2019.
[29] 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, 2020.
[30] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, 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.
[31] Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996.
[32] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication -efficiient learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282 PMLR, 2017.
[33] 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.
[34] Angelia Nedié, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-976, 2018.
[35] 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.
[36] Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent opti- mization. IEEE Transactions on Automatic Control, (4(1):48-65) 61, 2009.
[37] 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.
[38] 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.
[39] Thien Due Nguyen, Samuel Marchal, Markus Miettinen, Hossein Fereidooni, N Asokan, and Ahmad- Rezaa Sadeghi. Diot: A federated self-learning anomaly detection system for iot. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pages 756-767. IEEE, 2019,
[40] 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.
[41] Muzi Peng, Jiangwei Wang, Dongjin Song. Fei Miao, and Lili Su. uncertainty-awan aware federated trajectory prediction for connected autonomous vehicles. In The 2023 IEEE/RS. International Conference on Intelligent Robots and Systems (IROS 2023). IEEE/RSJ, 2023.
and
[42] Jake Perazzone, Shiqiang Wang, Mingyue Ji, and Kevin S Chan. Communictioon-ffficeenn device scheduling for federated learning using stochastic optimization. In IEEE INFOCOM 2022-IEEE Conference on Computer Communications, pages 1449-1458. IEEE, 2022.
[43] Swaroop Ramaswamy, Rajiv Mathews, Kanishka Rao, and Françoise Beaufays. Federated learning for emoji prediction in mobile keyboard. arXiv preprint arXiv:1906 04329, 2019.
[44] Mónica Ribero, Haris Vikalo, and Gustavo De Veciana. Federated learning under intermittent client availability and time-varying communication constraints. IEFE Journal of Selected Topics in Signal Processing. 111)
13

---

[45] 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.
[46] Devavrat Shah et al. Gossip algorithms. Foundations and Trends@ in Networking, 3(1):1-125, 2009.
[47] Artin Spiridonoff, Alex Olshevsky, and Ioannis Ch Paschalidis. Robust asynchronous stochastic gradient-push: Asymptotically optimal and network-inndpeendet performance for strongly convex functions. Journal of Machine Learning Research, 21(58), 2020.
[48] Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
[49] Mohammad Taha Toghani and César A Uribe. Unbounded gradients in federated learning with buffered asynchronous aggregation. In 2022 58th Annual Allerton Conference on Communica- rion, Control, and Computing (Allerton), pages 1-8. IEEE, 2022.
[50] David Tse and Pramod Viswanath. Fundamentals of wireless communication. Cambridge university press, 2005.
[51] 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);900--9758 2021.
[52] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems, 33:761 1-7623, 2020.
[53] Jianyu Wang, Anit Kumar Sahu, Gauri Joshi, and Soummya Kar. Matcha: A matching- based link scheduling strategy to speed up distributed optimization. IEEE Transactions on Signal Processing. 70:5208-522 5221, 2022.
[54] 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.
[55] Shiqiang Wang and Mingyue Ji. A lightweight method for tackling unknown participation statistics in federated averaging. In The Twelfth International Conference on Learning Repre- sentations, 2024.
[56] Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning resource constrained edge computing systems. IEEE journal on selected areas in communications, 3206) 1221, 2019.
[57] Ming Wen, Chengchang Liu, and Yuedong Xu. Communication efficient distributed new- ton method over unreliable networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 15832-15840, 2024.
[58] Ming Xiang, Stratis loannidis, Edmund Yeh, Carlee Joe- Noe-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.
[59] Cong Xie, Sammi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint arXiv: 033344, 2019.
[60] 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.
[61] Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker partici- pation in non-lll) federated learning. International Conference on Learning Representations, 2021.
14

---

[62] Haibo Yang. Xin Zhang, Prashant Khanduri, and Jia Liu. Anarchic federated learning. In International Conference on Machine Learning, pages 25331-25363, PMLR, 2022.
[63] Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions. arXiv preprint arXiv: 2018.
[64] 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.
[65] 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, 2019.
[66] 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, 2019.
[67] Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-18542 2016.
[68] 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 Neural Information Processing Systems, 2022.
[69] Hossein Zakerinia, Shayan Talaei, Giorgi Nadiradze, and Dan Alistarh. coaamuunicatioo-fffiiie federated learning with data and client heterogeneity. In International Conference on Artificial Intelligence and Statistics, pages 3448 -456. PMLR, 2024.
[70] 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): 14407-1333, 2022.
15

---

Appendices
Here, we provide an overview of the Appendix. In particular, the proofs of the main results presented and backed by supporting lemmas and propositions.
Limitations
17
Broader Impacts
17
Nomenclatures
17
D Useful Inequalities
19
Descent Lemma (Lemma 3)
20
E.1 Multi-step perturbation
20
E.2 Descent lemma
21
Intermediate Results
26
Fl1
Bounding local and global dissimilarity
26
F.2
Weight re-equalization (Proposition 1)
26
F3
Unavailable statisties (Lemma 2)
26
F4
Auxiliary sequence construction and properties (Proposition 2)
27
F.5
Consensus error of the auxiliary sequence
29
F.6
Spectral norm upper bound (Lemma
34
G Convergence Error of æ (Theorem 1)
35
H Convergence Rate of al (Corollary 1)
38
H.1 Convergence error of Algorithm
38
H.2
Convergence rate of Algorithm
39
Additional Results and Interpretations
40
I.1
Consensus error of Algorithm
40
I.2 Orders of the asymptotic rates
41
J
Numerical Experiments
42
J.1
Code
42
J.2 Experimental setups
42
J.3 Non-stationary client unavailability dynamics
J.4 Additional results
44
16

---

A Limitations
The limitations of our work are two-fold:
The client unavailability dynamics are assumed independent and strictly positive across clients and rounds. While deriving guarantees is generally challenging without assuming indepen- dence and positivity (see Section 3), is interesting to explore how to relax the client unavailability dynamics, where the probabilities can potentially have arbitrary trajectories.
2. Our study focuses on heterogencous and non-stationary client unavailability in federated learn- ing, which may vary gready due its inherent uncontrollable nature. Although we have shown FedAWE provably converges to stationary point of even non-convex objectives, an inter- esting yet challenging future direction is incorporate variance reduction techniques for more robust update.
B Broader Impacts
Federated learning has become the main trend for distributed learning in recent years and has empowered commercial industries such autonomous vehicles, the Internet of Things, and natural language processing. Our paper focuses on the practical implementation of federated learning systems in the real world and has significantly advanced the theory and algorithms for federated learning by bringing together insights from statistics, optimization, distributed computing and engineering practices. In addition, our research is important for federated learning systems expand their outreach to more undesirable deployment environments. We are unaware of any potential negative social impacts of our work.
C Nomenclatures
In this section, we provide notations and nomenclatures used throughout our proofs for comprehensive presentation. However, it is worth noting that all notations have been properly introduced before their first use. We next articulate the missing definitions and equation formulas.
Table 3: Notation table
[e]] lull2
The norm given vector v.
|
The Frobenius norm of a given matrix A.
The sigma algebra generated by randomness up to round f.
(A)
The second largest eigenvalue of square matrix A.
Rd
d-dimensional vector space, where d denotes the dimension.
[m]
set
{k: k E N, [I,
1l (8)
An indicator function of event E, i.e. 1 (g) when event E occurs, but 1 [(E) = otherwise.
f(n) S g(n). if there exists a constant c, > 0 and an integer no N, f()) < cog(n)
for all n 2 Rg.
f(n) = g(n), if there exists constant ce > O and an integer no E N, f(m) = cog(n)
for all n 2 no-
Missing definitions and equation formulas.
17

---

Table 4: Algorithmic nomenclature table
A
The set of active clients in round t.
W
A doubly stochastic matrix to capture the information mixing error. Its definition can be found in (4),
(t())
(t) & sup(t' | < t, E A defines client i's most recent active round. particular, 70()) 1 for all i [m].
The real model client i the beginning of round t Algorithm 1.
x
The auxiliary model at client at the beginning of round t. Refer to Definition for more details. The sequence is for analysis only and is not computed by any clients.
x²
The aggregated real model at the end of round in Algorithm 1.
The auxiliary model at the end of round f 1.
The real model of an active client and auxiliary model of an active client after s-step local computation in round f, respectively. Refer to Algorithm for more details.
21
(f.r)
The real model at client i after r-step local computation.
W², g
The real and auxiliary model mean over all clients in distributed system and in round 1, respectively.
F((x))
The local objective function at client i, which is assumed to be non-convex.
F(x)
The global objective function defined in (1): F(x) A Σ F((x)/m.
(ax())
The local stochastic gradient function at client i taken with respect to æ.
(F(())
The local true gradient function at client taken with respect to æ.
Dj
Client i's local data distribution.
&
An independent stochastic sample drawn from client i's local distribution D.
Table 5: Variable table
L
Lipschitz constant in Assumption 2.
0²
The upper bound of the stochastic gradient variance.
(B,
()
Parameters that capture the averaged gradient dissimilarity between global and local objectives.
p
The spectral norm of a stochastic matrix in expectation.
The number of local computation steps.
m The number of clients in the federated learning system.
The iterate of z, when i E 1
1-1
Vlz (2- ((-1,))
55. ((())))
2)
A
jEAt-11 1
+
7ilg
Σ
(t-2- - 1))
(-D)))( (((r))) (18)
A--1
jEA
r=0
18

---

Local parameter innovation & of the auxiliary sequence.
G (iEA) (t (t-n((1)
Vaila ( - -s((- VR(
+ (IRA9 (1 (1(
[iEAg (t - (t())
(ll(a.")) VF((2))) + +VF(()))
(19)
where the last equality holds because of
z; +1 and re-grouping.
Decomposition in the Proof of Lemma 6. The local parameter innovation of the auxiliary sequence
Go can be decomposed as G & A + sVF. s. Detailed definitions can found below.
[A A (ii (t))) Σ - (l (1r) e V.F(a!
[ A ((E (1) - (VF((a!!))) VF((a!));
[V & VF((x)).
D Useful Inequalities
For completeness and for ease of exposition, present common inequalities that will be frequently used our proofs.
The followings hold for any a, E Rd and any E [m]]
1. Jensen's 's inequality.
a2
a
12 and
Σ a;
S m
a
2
(20)
1=1
2. Young's inequality (a.k.a. Peter-Pate inequality).
|a
2
<|
2
(a1, <
+
for any <>> 0.
(21)
2c
2
Equivalently, we have
||a a2l12 = |a1112 ||a2l12
+ (a1, a2)
+
|| 12 (1 + ||21
for any 0.
(22)
3. Smoothness corollary. Given Assumption 2, it holds that F(a:) F((2))
a1 -a,, 02 / VF(a2 + + a2))dr)
-VFF(a2), ai 02)) + (' (a, - az, VF a2)) VF dr
(VF(a2), ai -az) + f T -|lai azlla a2
< (VF(a)), an aa²) + L la -
(23)
where (a) follows from inequality and Assumption
19

---

E Descent Lemma (Lemma 3)
In this section, we first present bound on multi-step local computation. Then, we apply the bound to the analysis of descent lemma.
F.1
Multi-step perturbation
Lemma 5. For 2 and under Assumption 2, 3 and 1p S 1/(4AL)) we have
E
Σ
F < 8 16n I?? [FF(())
Proof of Lemma 5. The proof shares a similar road map to [61, Lemma 2), but the objective is instead to show an upper bound with respect to [V For 2 1, it holds that
E
F
E
V
(fr)) - VF(())) Fz
|
r=0
SL
E
| (trr)
x
113 Fr
(24)
where inequality (a) holds because of Jensen's inequality, inequality (b) holds because of Assump- 1²!1? F+]. In what follows, we use Velt.h) to denote
tion 2. It remains to bound B[[] B[llax(t-)) (t.rr
(xp (4,k)) and V (iite))) as V V., (a( (,))), respectively, for ease of presentation.
E
((rr) x Ftt E
| (1---1) at. Vete
F
V ((r 1) - V (
2 (c.--1) - xt m (VEIE VF! + VF:) 1/1 Fd
E
(2)
V ((r A pl (1)
F
+ E
(t,r-1) 1) xt m (v A + V |1 Fr
(4)
Fz
+ 1
E
x
(1.--1)
Fz
+ 2 E
( - VE / 3r
25
S np E
V ( 1)
+ 1 + 2s 1
E
(1.-11
Fz
+ 4sn E
|
VE
Fr
4s7
(c)
< 17 + 4sm
V
F! 1
2
+ 1 1 2s -
E
(r--1)
2: 20/33 F(
+ 4sLL
|
x
|
F
2
VF + (1+,
1
||3
ni 0² + zus
1 2s - + 4sT.2 ni
R
2z!
Fd
where equality (c) holds because ve(t.M) is an unbiased estimator of V/(((tr) inequality (d) holds because of Young's 's inequality, inequality (e) holds because of Assumption 2.
1 it holds that By m S a.L.
1
1
2
+ +
<
4s <
2s 1
2s
2s
1
20

---

Unroll the recursion, we have
(1.r))
2
k
(nio2 + 4s7 (
1
28
k=U
8-1
k
(1Ro2 + 4sm1 || (
+
28 -
k=U
2s
[ (1+ 28 -1
2 5-2
[ 28 -1 -1) -1
(nifo + 4smi \
2
2
V3e -1] (1i00² + 4 (1
(0)
4sh 0² + 16s2 '/ || | 1
where inequality (f) holds because of (1 + 1/x)* exp(1), inequality (g) holds because of
/3exp(1) 1 < 4. Plug it back into (24), have the desired result
E
Σ
-P VF(())
F
< 2n + +16 S V
E.2
Descent lemma
Proof of Lemma 3. By Assumption and inequality (23), we have
+ L
F( - F(*') (VF(z"), F((*)) S
x¹)
1
2
(A)
The one-round innovation of z can be rewritten
g++1
z'=
(=t1122) =2))
VEA
o A
m
1 (sEA)
Σ
-Fi()t)-min ti())) (=
(=t (((t)))
171
km)((+)1
8
VF((a)
1 (111)))))(((1111(0) (1((()) 1 m
Σ 1 (t T(())
(x ;
Σ
(b) 70g
1 (iEA)) (t (6-T7(1 (it) Σ
VFi(a (1))) (e, ((. (1(1)))
(1 (1-A4)(-T:(0)) 7T(1))
(VR())) -VF((((()))
m
8
(F((
21

---

where equality (a) using the fact that æ = æ for all ls such that + and equality (b) obtained by adding and subtracting V4, c!(()) and by the fact that (1 (iEAt) + ((Ea)))
Bounding (A).
(A) (VF(=') x -x')
m
11171
(F(E"))
Σ
1 (EA)
(m(00p)( (1-))
V - -e
1=1
r=0
(A.1)
m
7g
(EEA)
(T:())pp)
VF(E"); (1 p)
(F(((()) - v((a!()))
m
(A.11)
Mg
VF(2") VF(22) VF(=)))
7 VF((').
(F(())
1=1
(A.III)
(A.IV)
Bounding (A.I)
E
(A.1) yzd
(a)
VF(E").
1
(1 -p) (t-p) Σ
[P((a!()))) Velaa (e(())))
(ied))
m
( nmaa (VF(**),
m Σ
1-1
(VRR(a!")) ( |a!te)) ااii | [
p.
1
Fr
Σ
(t
R R Σ
r=0
0,
where equality (a) holds because of the law of total expectation, equality (b) holds because 11 (Ge.Ar) is by definition independent of others and Assumption 3.
Bounding (A.II)
(c)
m
2(t pp)
(A.II)
1 (iEA))
[(x())p))
Σ VF(x V.L ((o))
m
1 8
|V
8m
2(t p)2
a-1
+ m
7
1 (eEA
Σ
(+())=p)
Σ
VF((xt) - VF (1.r)
p=1
r=0
22

---

where inequality (c) holds because of Young's 's inequality. It follows that
E (A.TT)
(d)
VF( +
m t-1
(t p)²
m
7 R L
(m(0=)p - p)² (x))
m
Snath 3² 02
t-1
1g
VF((")
Σ Σ
(r(t)) (t- pp) p)²
8
m
321 ng
Mi 83 L
(m100p) - p)? [/( (
m
where inequality (d) holds because of Lemma 5, the last equality using the fact that x. x for all k such that T; +1 k S. I.
Bounding (A.III).
(A.III)
7 m
VF())) - vF((z))
7
VFFE")
2nmyys SL?
x
8
m
where inequality (e) follows from Young's inequality and Assumption 2. It holds that,
(A.II)) Fr] s
7g
VF
12
2T
m Σ
||
x 11
8
11
Bounding (A.IV)
(A.IV) "
[1TF(=3)12
1 m
VF
VF(2') Σ
VF
m
where the equality follows from the identity in Appendix D (3). It holds that
m (F(
m
(AAIV)) Fz]
gg 2
|VF(2*)
+
VF((')
Σ
VF((2t)
m
1 m
I m
n
||VF(=))
+
m Σ
(2{)
m Σ x
-
Putting (A) logether,
8ng s2 00 m
[-1
E (A) (A) FM
<
VF(2')12
1 [x(0=p) (1 (p))
m
211 sT2 m |
2
1122
122
Σ 1=1
m
1" -
m
2m
1
32 3
|m00=pp (t (t- p)2 ///
m
1=1
2
23

---

Bounding (B).
2 l m
(B) S 2L-
fg
(t
Σ
-
-
-=
(B.I)
+ 2L
11 0g
1 ((e)))(t VVF(attt)
m²
(B.1I)
+ 2L
111 0g
V
2m sg
ΣΣ VPi 2
m
(B.III)
(B.IV)
Bounding (B.1) Recall that dmax - se ps. It holds that,
E
(B.D)
(B.I)
F(
2L
Σ E
[Lreass (t- (t- (())
Σ
E VF((2 ve(aa (((())))
/| (((to)) ged
m
2n
Wi s L. 1112
2
1-1 1 (r(())p)) (1 p)?
where equality (f) holds by the law of total expectation and by the independence of event E A'). inequality (g) holds because of Assumption and by definition p S 6max-
Bounding (B.II)
We have,
1/i n
m 1-1
(B.II) Fz
S 2L
Σ
Σ
1 (t - 4n) L20
m
i=1 1=1p=-1
M 2m
+ 2L
fl
Σ (m(()=p) Σ (t-p) I
m
8ng
t-1
(m:00)p) - (t- 2) + 32 8
Σ
(t- p)² t2. 2
m
2
where the last equality using the fact that ax = a for all such that r,(1) +1
Bounding (B.III). E [(B.I]
2n 2 Em -
<
Putting (B) together, we get
2n my L
8ng 8
13
E ( Fz
<
1 (t-00=)) 22
(t) p)2
m²
m
32 8 3 m
(xx00=pp (1 p)²
V Fi (1
p+1
2
1 m
||l|
xi11 + +2Lmin33
Σ
(F
1=1
24

---

Now, everything:
E F( - F(
S
||
||
4
m
(1-
VF
2
2n 2 s Ld mmx o²
(m(0=p)(1 p)2
D!)
m²
p=-1
Mn n 52 1,2 (1 + (g) 0²
(x)())))(( (t-)))p(pppp) ppp
m
+ ST? (1 + 8L)
+
Σ
|21
- x¹12
2m
t=1
+ 32 33 1,2 (1 + (L)
(m(00=p (1 p)2 [F(( p+1
11:
2n n o 2²
S
||
(xx(1)ppp (1 - p))
4
m2
91 > 222
1 (T:(1) r) (t p)² (p)
m
2
sL
m
||
z
2 m
Σ =
m
2m
m
[-1
VF.(( 112
+
35
112
pt)
m
where the last inequality holds because 71y S
9
and that
1/ E.
V=((E()12 2 0.
1000L
25

---

F
Intermediate Results
In this section, present the intermediate results that serve as handy tools in building up proofs afterwards.
F.1 Bounding local and global dissimilarity
Proposition 3. For any I, it holds that
3L
[V((2)) <
||
==11 (8² [ +352.
Proof of Proposition 3.
m
m
VF((2))
(F((2)) VF((') + - +
= m
m
3 m
3 m m
[F( VF((')
VF((' 3
m
3L
| = 333 VF 11 +35 + ///
3L
Σ - x +3 |F( +36?
where inequality (a) follows from Assumptions 2 and 4.
F22
Weight re-equalization (Proposition 1)
Proof of Proposition 1. We show Proposition by induction.
When T 1 and E A", have Ei I (EEAt) (t T+()) ((E (0-1; r;(0)) -h.Thereore, the base case holds.
(()))) (1-):(t)) The induction hypothesis is that EtO IeE (1 focus on K + 1:
K holds for i AK-1, Next, we
K
K Σ (Deag (8-T((t)) + 1 (LEAK) (K-T((K)) 0=
Σ (ieA (t- (t)))
(25)
1=
Now, we have two cases:
Suppose i E AK- then simply have T(K)) = K 1. It follows that Eq. (25) (a) K 1.
where (a) follows from induction hypothesis. Suppose & A-1
((K) Σ
Σ 1 (ee (1 (0-7((1) (1))
1 tiad -(()) deEAKy -x((kK))
t=0
(K) + + (K (())) +1
where (b) follows because 11 (sed) = for Tı (K) S - and induction hypothesis that
[x(kk (ies (I (())) (K) + for i E (T)(K)
E3
Unavailable statistics (Lemma 2)
Proof of Lemma 2.
1-1
E it - (t) = Σ
Σ
II (1- (1 8) - 5
nt
-
26

---

From [15, Section 12, Theorem 12.3 (i)), we know that
I [x)] g(0) / (xx))((X> x) dz,
where X is non-negative random variable, and 9 non-negative strictly increasing differentiable function. It follows that,
E
x
50+2
/ xP (X > dr = -2 Σ l
Σ/
xP >
x) da
n=1 n-1
(a)
20
$
71
F(X > dr
n-1
2
nP 1Xx>n-1l
dr 2 nP (X -- 1],
where inequality (a) holds because CCDF P ((X= > 2) is non-increasing. In particular, for a discrete random variable, we have P(X n 1) = n
n, Vx E (n n, incquality (6) holds because
Therefore.
E (t (((1))
2 < Σ nP (t) 2 = Σ n(1 5)n S 8²
==1
==1
E44 Auxiliary sequence construction and properties (Proposition 2)
Proposition 4. For any 2 O, when & A', it holds that x;;1 ()) (t(+)))) when i E A', holds that z = x. 21+1 x1+1, and 2,+1 = 1+1
2; 1+1 mpng Ti(t
Proof of Proposition 4. The proof is divided into two parts: i & A and i E A',
When i A'. It holds that
1++ 2
2 1+1 (1+1)++
((+1))+
Σ
VF((2t)
x
g
(=
(a) xj
(1+11)++
(1+1))+1
x
k= 1)+1
mm (t + (z)
where equality (a) follows from Definition for inactive clients.
When E A.. Note that if 2 2 x: for each i A'. then by the aggregation rules, know x (1/l - (1/14")) 2 z++1, Then, we know that
at 2 ++1 V AA. Hence, show the Proposition, sufficient to show 2 a ++ holds for E A. which can be shown by induction.
When
21
-++ 2/ +
[2 xi
(0.0)
(0.=)
x
(z) (0,0)
x. x. 0++
(0.+)
27

---

Thus, the base case holds. The induction hypothesis is that 2f++ = =xft+, Aa E A is true for all t 2 O. Now, we focus on
[++1+++
2, 1+1 + n
VF((2,)) - 11+1- 1)) (a. (((+1.00) 2; (
(++1)++
2 + men - (t + V) (1) ((( - + - (t 1)) [ (1(++11.0) - x (1+1,,))
+(++1)+1 mt (t +
1)VF (
+ (1 Tu(( 1)) c.
(1 (1+1)++)
Tx(1 1)) (x: (c+1,0)
xi (e+1
2, ( - (t+ 1 1- 1))
(++10) x; 2
2;
(b) n((11)+1 (1+1- + 1))
(1+1,0)
0ú ((+1,s)
x (+))+
where equality (a) follows from the auxiliary updates 2,, and equality (b) holds because of the induction hypothesis and the fact that 7, + 1) < + 1 and i E A
Proof of Proposition 2. From Propositions 4, we have
z:112 - | (t - (1) - 11) a
((((00)))) (t (t-p2 p- pt 1)² /F
Take expectation over all the randomness
E (t -1)² (Fi(a [
E
x
(b) n Σ ((p--1)((((()) p3 P)- E
v= 11/]
where inequality (a) follows because by definition (T.(0==p) is independent of |V > 12 inequality (b) follows because xft1 xF from Proposition 4.
11?
Σ P( p 1)²E | 1|13"
2
(0)
m
[|
(
2 th
1 2
E
2
(0²
E
||
(="
|1
+
+3m
2
2
82
8
2
3
2?
8z
2
where inequality (c) follows from re-indexing, inequality (d) from Lemma 2.
28

---

F5
Consensus error of the auxiliary sequence
Lemma 6 (Consensus emror of z!). Assuming that mo I 82(2Ls)), and mmg I 8(1 (1)((1) + 1)), under Assumption 2, 3 and 4, holds that
3psn n
m Σ Σ
= =11
2p)282
40ps²1f 1g
(1 vp) c²
40ps
2 '11 flg (3² + +1)
1
T-1
VF
[|
(1 7p)
T
Proof of Lemma 6. When t = 0, z = [==0.... ..,,,)), which immediately leads to
2 (I- = [z0 , =0
1z = =0.
For t 2 1, recall that ((() is doubly stochastic matrix characterize the information mixture, and GP, defined (19), captures the local parameter changes in each round. It can be seen that
z = (z(t-1) m - w(t-))
Expanding Z, we get
2 (I J) (Z q1ll G ((-
(I JJ-
Z 1-1 W (I J]
1-1 J).
Σ
w (I
7m
q=0
8-q
where the last follows from the fact that all clients are initiated at the same weights. Note that 1 W I1 (()) and [[ W(] J. Thus,
W - J
( [I J) = z
J
G
10 - J -
II W -
9=0
where the last equality holds because that 2 = [z ... =)) which immodiately leads to
I W J 3 12 ,00 120 ,=0] 0.
(-1
z
Let matrix notations A A and v Ft define as follows:
G. 1IEAA)
(1 (1)) g(er))) v(((a(()))) (1 (7)()
VP((a(()))) -V((()))))((((()))
[
AA
+ VF((
29

---

It follows that
T -J 11
J)
A
+ VF
9=0
1-1
1-1
Σ
W -J
11 +
Σ
(A + +
W -
11
9=0
q=0
J
+
Σ
A
w
J
A (A
W J
(=9
t=q
Take expectation with respect to randomness in stochastic gradients, denote by Eg [:]:
Be
12 (I
J) 11
EE
A
W ( - J l1
+ E
A +
VF
W -J
q=0
1-1
+ 2Eg
A
W(0
J
A + VF)
9=0
1=q
l=q
6-1
1-1
Bg
Σ
A
W(
J
1/
+ E&
AA + VFW
1 J
4=0
1=y
+
Σ
ES
A
((()
V
W(
4=0
l=q
c-1
(-1
< Eg
1 A
II
w( -
J
11
+ Eg
12 9=0
(A++VE))
(
J
||?
Q=U
F-q
where the last inequality holds because Eg randomness.
A
O. Next, we take expectation over the remaining
[- 11
[-
(9) (I J)
SE
A
+
A
F2)
II
-J
lf
4=0
q=u
Em
1-1
S n
A
11
9=0
E=q
[-1
2n
21
(
-J
11
0=0
E=q
(IT)
2n
F
(
11
(26)
0=
t=q
(1I1)
30

---

Bounding E [D]]
[(0]
E
|
w(
13
t=q
Awoo-J)
1-1
|
Σ
E
A
w
A"
0=0
p=0.ppp
(4) 1-1
|
|i
(27)
Q=0
where inequality (a) holds because of Assumption 3. It remains to bound E |
2
| = Σ
l (1EAa)
Σ ()
Σ
(2 (50r)
(g( ;
(F(( (2((())))
1=1
Eg
| 1 = Σ (iEAt)
Σ
9-1
1 (1 p)2 Σ Eg ||
11.1) :efort) (F((z) (0.r))
1-2 2
S so² 2
(ie
1 (0
Take expectation over the remaining randomness:
9-1
[ (m(0)=))] (q - p)2 (1-p)² s 2mso²
E
A
|
80
E [ [eA)))
Σ
E
p=-1
Therefore,
m T-1
ΣΣ B[D] < E0I
sp (1 p)
0².
mT
82
Bounding E [(I)]
1-1
(-1
(TT) = E
Σ
A
((0)
J
11
Q=0
t=q
t-1
[-1
II W -31
[-]
E
||A
((0)
11
+
Σ
E
A"
W J
A
q=0
p= 0.pp'
t=p
l=g
h-1
J ) 1|
E
|
((t)
||
II W1
9=0 pm 0.pp4g
mmg
-P
P
ep--9
E
A
2
1
9- p=00ppp
31

---

Next, we bound the second term, choose e ==p²r"
|1 + [|77
E
P + [
2
9= PP0-.PP
p=0
Σ
E
E ||
Σ
2
vP- [-l
E
|
(28)
vp
Q=U
Plugging the upper bound in (28) into (27), we get
vP v7-
(8)
VP= - vp
E [
S
Σ
V
1 vp
1 vP
9=0
0=0
2/P < 1
E [|
(29)
where inequality (6) follows because that vØ- S Vp for any q -t
1, and that yp-
2 0. It
remains to bound E [[]] Take expectation with respect to randomness in stochastic gradients:
I 4nf 3 1
(1 (1- p)²0²
m
9-1 1 (1000)0 (1 (VF
+ 16n 24 T,2
where the inequality holds due Lemma 5. Next, we take expectation over the remaining randomness and plug back into (29):
2/p Vp
E [(I)
S
Σ
Vp
E [|
T=0
8p
2
n m.2m
(1 vp)
2
83
/p
2
1/1
A L
m t-1
E |
T-1-1
vp
82
(1- (1-vp)
8p
2 82
ni
3 L
mo² +
(1
(1-vi)
v))
32p
2
82
2
ni
2
2
E
[
g=0
where the last inequality holds because of re-index and grouping. Therefore,
8p
2
E
[(TT)
M 8 T.202
mT
(1
2
82
32p
T
m
E (2
(1 vp)²
82
T
1=1
1=1
8p
2
m
3
L202
64p
2
m
4
Σ
m
1
(1 2
2
82
2
82
64p
m
[1VT,(=))]
E
(1 v
32

---

Bounding E [III)]
Use a similar trick as in bounding E [[I)), , and we get
2 v/P
E [(LI)] = E
VF
II l=q
-
J
17:
-
vp- " P |
vP
so that
2/P
T-1 E
T-1-t
E [(I))) - miT (1
[|
Σ vp
mT
VP)
at
1=
g=1
2p
T-1
m
E ( ||
(1 - vp)
m'I'
4pl2
T-1 m
[|at - =[[b]]
4p
T-1 1
[|]F((=]]]3]]
E
+
E
vD)
m.
(1
vp)
2 mT
Putting them together
E (0) (I- l1?] s (1
spti n
2
(1 + 21.2 0²
mT
vp)² )
t=
8ps 2 T,2
+ 1677 L22
(/2
E
||
21 [2]
(1 vD)²
8ps2n1 12 72
1 1 16
2 $²1.2
2
+
B ||
(1 vD)
Plug in Proposition 2.
T-1
Σ
E Z (1) (I [I]
S (1-
spni mgg
2
(1 + 201 32, 0²
mT
82 (1-vp}
1=
+ (1 vp}²
8ps 8ps2nn?n? n2
mg
1 1677 L22
(2
8z
1 + n L2
2
E
[| [
1. 1.05psn m
0²
9ps² n2 1 T-1
Σ
m
E |
vp)
(1
vp)
T
where the last inequality holds because Tp < (20sL) and 7M S 8/(10sL). Next, plug in Proposition 3.
T-1 ΣE (I- J) [12]
1.05psh2 m
2
27ps nी n
0² +
(1- vp) 2
mT 1=0
(1
vp)²
82
27ps2 ni n (32 12++11
1)
Σ
T-1
E [|
2
27 27
2 L Li 1
Σ
EIEL - =11]]
+
+
(1 2
T
(1 vp) T 1=
t=
It follows that
T E
3psti n
[ ( (I- J) [i]] [
- (1
mT t=
vp)252
40ps n n 2
$
(1 vD)² 2
40ps n 122 (52 + +1)
T-1
Σ
[|
(1 T 2
which is due to the fact that 11lg 5
1-
10sL(
33

---

F.6 Spectral norm upper bound (Lemma 4)
Lemma 4 adapts from [58], we present its proof here for completeness.
Proof of Lemma 4, For ease of exposition, in this proof we drop time index t. We first get the explicit expression for E [W] | + 0]. Suppose that + 0. We have
W
W W W W Way
Σ kE(m)]((i'))
WynWy..
k=1
When & # j and # j', we have
1
W Wy ph
LAp (ee
In addition, we have W Wy 83 (ea and Wy (eea Thus, For j # j', we have
W3
W W [ UUEA)
For j = = we have
1
5) = A (EA) + ((jEA))
In the special case where A 0. simply have W by the algorithmic clauses. Therefore.
E [3 A
0] 2 0 holds for any pair of j.j E [m]. It follows, by the law of total expectation and
for all j.j E [m]] that
E [W | = W
( 0} + [ | ( P 0}
2
E [W,y' 35'
+
For j j', it holds that
E [W 23'
A + 6]
E
1 |s I (yEA)
A
2
IE
-
1
A+0
PiPy
82
|
m
where inequality (a) holds because |A| m: For j = jr, it holds that
E [W3 A
0
1
UEA) + -1-1p (1--))))) A + 0
A
1 82
E
[yEA) + (1-14))4)) ) A 0
2
m
m
Recall that .M E [W?]. Next, we show that each element of M is lower bounded.
8²
Map 2 E [W3,
[1 (1-
m
We note that p(t) (MM) where A2 is the second largest eigenvalue of matrix M. A Markov chain with M as the transition matrix is ergodic as the chain (1) irreducible: M
[1- e1=
c)"" >
O for j.j [m]] and (2) aperiodic (it has self-loops). In addition, W matrix is by definition doubly- stochastic. Hence, M has uniform stationary distribution
1 /m. Furthermore, the irreducible Markov chain is reversible since it holds for all the states that π; Mij = M. The conductance of reversible Markov chain [19] with transition matrix M can be bounded by
Eies.jes Mij
[1 5) S S|
82 [1 - (1 5)m)
(MM) = min Eies 1.
|
LieS Ti
where |S] m |S|
2
m 2
From Cheeger's inequality, we know that
1-d2 2
s 4(M) 5
/2 -2)). Finally, we have
52 [1
(1
8) m
52 [1 (1
5) 5)m)
((M) >
S
8 m
Thus, p(t) = 22 < (M)
(1- m2
<
34

---

G
Convergence Error of z' (Theorem 1)
In the sequel, we recall and assume the following learning rate conditions in (11):
(1 - v
5
7 - 80s(L + 1) 1V)+1) (82 + 1) m 200sL (32 + 1) L2)
Recall that 8max maxt p4 and F - min F(x)).
Proof of Theorem 1. Take expectation over all the randomness, plug in Lemma 6 and Proposition 2. By telescoping sum, it holds that
E
F
F[20)] T
gg
T
Σ
E
2
2n 1 Lómax o² T
m
Σ
t-1
E
L (m(0)==)]
(t- p))
4 T
m
t=
Mg 82 1.20 2
T-1 m
E [11(0)pp]] (t (t-p)- p))
m.
T
+ 2. 2 L2
2
E
(30)
mf
1=0
s
2
T- m
E
x11]]
(31)
2mT
35 L
T-1
m
t-1
|IE
[1 (x(t)=p)] (t - -))p
(32)
mf
Next, we bound (30), (31) and (32), respectively. First, we show that
Σ E
mT
T-1
312 T-1 m
s 3( +3 3 (32 +1
Σ
R
|F
ΣΣ m.T
B ||
==1[]]
T
1= i=1
40ps² 40ps2ming
10ps²nnnn
T-1
9psni n3 L.2
3 1 +
23 3 (82 +1)
+
Σ E x=
|
+
(1 2 o
(1 2p)
(1 vp)
(33)
where the last inequality follows from Lemma 6.
For (30), we have
4.4m 3 3
L2
T-1 1 m
2. 2.2
L22
E
z 12
Tg
Σ
E [|VF)))))
T
82
T
s² ' 2 L2
1
40nf ps 2
1 1+
28
82
(1 vp)²
3 3 14
L2
40ning L2
T-1
(82 1)
E |[F(=')) [
82
(1 vp)²
where the last inequality holds due to (33). For (31), we similarly have
82
T-1
- ΣΣ
< 1.5ps
ni L?
0² + 20ps 1 1?
(1- 2 5²
2mT
(1 vD)282
t=
+ 20ps nn T.2 (32 +1) 1 T-1
T Σ
E
||
[12]
(1 vp)²
35

---

For (32), we have
1
(<ilo [12
88
1?
E [m((tt))p)]] (t - (t=p)²B
T
m
f=1
70 88 1,2
T
1
m
E ( [
mT62
140mg 33 L
T-1
m
140mg 1i 8²122
T-
E
|lo - z:112]
Σ
mT
m8
1=0
1=1
2nd 2n 52
2
70 30 22
T-1
[|
1 +
E
82
82
m.
(a)
2
7lng nia03 5² L
Σ
Σ
E |[VR(()))
82
mf
(b) 4267 Mi s L
40ps²n
426
1n L22 L
40ps² mpns?
T-1
1 1+
2² +
(32 + 1)
1+
Σ B
82
82
(1 vD)²
+ nuTh 80 L220
282
where inequality (a) holds because of (11), inequality (b) holds because of (33).
Putting (30), (31) and (32) together and plugging them back into the telescoping sum, it holds that
E F - F(#9)
T
14 + 1))))n) mi L2 (1 + L2)
20ps"ni'n33 ni' (82 +1)
T-1
1Mg8
Σ E
4
82
(1 vp)
12
33 12 (82 + 1) (1+ 1.2)
Σ E VF( [|]]
T
82
1=
4n mg LD
M n 2 L2
1.5ps nn n3 I
n 0222
mo82
282
(1- 20
282
157 n L2
20ps* 1
3 112
430mg L2C
82
Vp)
82
T-1
Σ
E
|I
6
T
1=
4n 13 s Ldmaxoz
nin2z=LL00
ng 835 L2
o²
ma²
25
(1-
20)
282
15 82
1 L2
20ps
n2 2
430m vp 83 T
vp)
82
where the last inequality holds because of (11).
36

---

Combining the above and rearranging the terms, we get
6 -M
T Σ E
t=0
2Anoog L
Opsningl o² +
3
md2
82
vD)
82
120ps²1ji L
25
(1
vD)2
52
6 (F(22) - F*)
2g o2
15nl 1 1 L
28000 n2 n² L
My
ms²
(1- vp)282
82 vp)
where the last inequality holds because P In terms of asymptotics, we have
T-1 F B [1VFE>)11 x (F(=9)- - F*)
"11gg Lo
dmax
0² + C
n 222
m
82
82 (1 vp) ?
where we use the convention that fl 2 1 for ease of presentation.
37

---

H
Convergence Rate of a' (Corollary 1)
H.1
Convergence error of Algorithm
Corollary 2 (Convergence error of a)), Suppose learning rates conditions in (11) are met for on and "g and Assumptions 1, 2, 3 and 4 hold for T 2 1, holds that
|12] 2 (F(x)) F*)
7eg Lo
6max
o² x
E t=0
22
1i
52
82 (1 vp)
Proof of Corollary 2.
T-1
3 T-1
E
VF
[2]
$ Σ
|IF('))
VF(3')
Σ
E
||F()))
2T
(a)
3T
T-1
T-1
||at
- =112
+
EE
[|VE(>*)] [
T
27
1=
(6)
3L
Σ
E
||
=11
+
T-1 Σ
E
|
T
27
1=
t=
s 3
2
m
12
E
VF
3
Σ B [|
82
T
2T
where inequality (a) follows from Appendix D 2. inequality (6) follows from Assumption 2. Further plug in Proposition 3,
E
|
<
3
T
E
|F
|12]]
+
+n
L
(82
+ 1) T
Σ t=0
E VF(2") [12]
T t=
2T
82
+
LL
L
82
2
1
=''
+
9 9m 2
)
8
2
c
Finally, plug in Lemma 6.
+ ΣΣ E
<
3
9m
222 2L2
2
(B² +1)
90
1
Σ
E
||
2
8
80
T
1=0
9
9
8
2
2 82
9 x 90
802
M
2 2
11
03
2
+ 9m
2 2 212
11
2
200
1i
2 2
2
Σ
EE ||
2
LL2 fl
9n 9 2
(
2+ $2 L2 n
82
12 (F(x")
F*
48 Lb _
31 2 52 L3 2
5600m/ 3600mi11333 n2 L22
8
m
(1 20
282
where the last inequality holds because < 1. In terms of asymptotics, we have
T [ [ (F(*") F*)
milg La
8max
0² +
82 + 2
ST
m
80 vp)²
where we use the convention that 71 2 1 for ease of presentation.
38

---

H.2
Convergence rate of Algorithm 1
Proof of Corollary 1. Choose step-size as 1 tions in (11) are met, it holds that
VTaL' Mg = sôm such that learning rate condi-
T-1 [[ S
(F(x²) F*)
mmax
0² +
sm
0² + 5²
Vsdmm
8 smil
8(1 vp2
39

---

I Additional Results and Interpretations
I.1 Consensus error of Algorithm 1
Corollary 3 (Consensus error of x²). Suppose learning rates conditions are met in (11) nn and "g and Assumptions I, 2, 3 and 4 hold for T 2 1, it holds that
T-1
m
x ='[[] x (F(#") F*)
Tel Lo
8max
R
T
nMgTT
m
82
0² + c
+ +n
1 +
p
82
(1
2
Proof of Corollary 3.
1
2² x211
T
m
1=1
m
2112
ΣΣ
12
3 31 1²12
T
T
T
m
1=0
7-
Σ
| - =1 +
3
Σ
|
1
2
1=
1=1
-
T
(=0
where inequalities (a) and (b) follow from Jensen's 's inequality. Plug in Proposition 2 and take expectation over all the randomness, we get
T-1 -
E [|a! - x11[]]] v
36m
(32 +
E |VF
|
82
T 1=
0=
36 2 2
367/
12
TT2
3
E
-
82
82
x=0
2 361
1g
8
+1)
1
1
Σ
E
[||
36m/ 2 2 82 2
8
82
-
4
-
m
where the last inequality holds because of learning rate condition in (11). Next, plug in Lemma 6:
1
1 T-1
3 m
m E
[|a]
x 211 2
36n n 2
(8² + 1)
1 T-1
Σ E [VFF(*)) [[]]
T
5²
T
0=0
36
2²
+
12 - =112]]]
8²
m
T
1=1
t=0
361 2 2
(32
T-1
E
[12]
1
Σ
E
||
82
4T t=0
t=0
361 1
12psni 2
160ps 600ps21i'13
+
C
82
(1 vpP282
(1 vp)²
Σ
E
|| |12]
+
12 12psn 0² +
360
2 2 2
gg
5² +
160ps2nptn)
2T
(1 vp)28²
82
(1 vp)²
40

---

Finally, we plug in Theorem
(F(x)) Fr)
12mmy Lo o²
28s 1/
1600nf 1 8
E
x²
0² /D)² 52
2 n
m62
02 vD)
where we the fact that 00 x and p 1, and the convention that fg 2 and L for ease of presentation.
In terms of asymptotics, have
m
12] 2 (F(#") - F*)
71 La 8max
+2
Σ
+ m1 2
T
nygsT
m
82
(3(1 - vp)2
1.2 Orders of the asymptotic rates
From Theorem 1, Corollary 2, Corollary 3, easy to see from the theorem statements that they are all of the same asymptotic order, i.e.,
B
Σ
In addition, by applying learning rate conditions in (11) to Lemma and Proposition 2, also see that
T -
Σ
E
=1
B(I [[))
T
t=
Therefore, we conclude that (12), (14) and (15) hold.
41

---

Table 6: Neural network architecture, loss function, learning rate scheduling, training sleps batch size specifications
Datasets
SVHN
CIFAR-10
CINIC-10
Neural network
CNN
CNN
CNN
C(3,32) R M
C(3,32) R- M
C(3,32) - R R- M
C(3233) R M
C(32,32) - R M
C(32.32) R M
Model architecture"
-I(256) R
-D -D-11(122 - R
(((28) L(10)
I(64) R
D-1((26) R D-L((1)
L(10)
Loss function
Cross-entropy loss
Local learning rate T] scheduling
where denotes the global round.
Vt/10+1
Number of local steps
10
Number of global rounds T
2000
Batch size
128
C(# in-channel, out-channel): a 2D convolution layer (kernel size 3. stride 1. padding 1); R: ReLU activation funcctio;; M: 2D max-pool layer (kernel size stride 2); L: (#f outputs): fulle-connncttdd linear layer; D: dropout layer (probability 0.2).
J Numerical Experiments
J.1
Code
The code for reproducing our experiments is available at httpp://ggibbb.comaaiiiig//// FedAWE.
J.2
Experimental setups
Hardware and Software Setups.
Hardware. The simulations are performed on private clus- ter with 64 CPUs, 500 GB RAM and 8 NVIDIA A5000 GPU cards.
Gertiode 1
Software. We code the experiments based on PyTorch 1.13.1 [40] and Python 3.7.16.
Neural Network and Hyper-parameter Specifications. Ta- ble 6 specifies details of the structures of the convolu- tional neural network and training. We initialize CNNs using the Kaiming initialization. The initial local learn- ing rate fju and the global learning 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 Table
Deta (sbe)
Figure 4: An example of data het- erogeneity using Dirichlet(a: 0.1) distribution with clients. z-axis de- notes the categories images, while y-axis denotes the client index. The size of circle refers to the proportion of pictures in given class. The color of a circle distinguishes images with different categories.
The difference between FedAvg over active clients and FedAvg over all clients that the latter counts the contributions of unavailable clients as O's. We set 3 = 0.001
for F3AST [44], which is tuned over a grid of {0.1, 0.05, 0.01, 0.005, 0.001, 0.0005). In addition, as recommended by [55], we choose K 50 in FedAU without further specification. We train CNNs on all datasets for 2000 rounds. Fig. adopts the same hyperparameter setups, yet with only 1000 training rounds.
Datasets and Data Heterogeneity.
Datasets. the datasets we evaluate contain classes of images. Some data enhancement tricks that are standard in training image classifiers are applied during training. Specifically, apply
42

---

Table 7: Initial learning rate no and global learning rate f7
FedAvg active
Fedåvg known
FedAvg all
Algorithms
FedAU
F3AST
FedAWE
MIFA
FedVARP
SVHN
80
fly
1o
1/3
180
1/5
100
f1g
170
fgg
10
fy
78
fly
1o
fly
0.05
1.0
0.1
1.0
0.05
1.0
0.05
1.0
0.05
1.0
0.1
1.0
0.05
1.0
0.05
1.0
CIFAR-10
11g
10
1/
110
1/
10
1g
11g
1o
0.05
1.0
0.1
0.05
0.05
1.0
0.05
1.0
0.1
1.0
0.05
1.0
0.05
1.0
CINIC-10
70
f1y
180
1/3
80
f/3
700
fg
100
fg
100
70
fyy
10
f2y
0.05
1.0
0.1
1.0
0.05
1.0
0.05
1.0
0.05
1.0
0.1
1.0
0.05
1.0
0.05
1.0
random cropping and gradient clipping with max norm of 0.5 to all dataset trainings. Furthermore, random horizontal flipping is applied to CIFAR-10 and CINIC-10.
One full set of experiments takes about hours on SVHN and CIFAR-10 datasets, while about 10 hours on CINIC- 10 dataset.
SVHN [37]. The dataset contains 32x32 colored images of 10 different number digits. In total, there are 73257 train images and 26032 test images.
CIFAR-10 [26]. The dataset contains 32x colored images of 10 different objects. In total, there are 50000 train images and 10000 test images.
CINIC-10112). The dataset contains x2 colored images of 10 different objects. total, there are 90000 train images and 90000 test images.
Data heterogeneity. Fig. 4 visualizes 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 a entails a more non-i.i.d. local data distribution and vice versa.
J.3 Non-stationary client unavailability dynamics
Client unavailability dynamies and visualizations. As specified Section we consider total of four client unavailable dynamics in the form of pl P: fe(t), where P: = (v4, Φ), V ~ Dirichlet(a) and Φ is the distribution to characterize the uneven contributions of each image class. In detail, each element [ø]c is drawn from a uniform distribution Uniform(0, 22). We set & for the first five image classes and e = 0.5 for the remaining five image classes. Fig. plots resulting p, example, wherein P3 are heterogeneous across clients.
16
14
10
0.2
0.4
0.8
1.0
Probubiltyy p.
Next, we formally introduce fa(()'s 's under each dynamic.
Figure 5: histogram of one generated p. example with a total of m = 100 clients. It can be seen that the majority of 'ss are below 0.5.
Stationary: fa(t) A I;
Non-stationary with staircase trajectory:
(1()) (1E(tato+PP22) 0.4 (1E[ko+P//.o0t7))
where P defines period, to E {0, P. Non-stationary with sine trajectory:
ftt A sin (TT / P. (1 (1-7).
where signifies the degree of non-stationary. Non-stationary with interleaved sine trajectory:
ft) (t) (()))))))))))
where (1) - 7 sin (1))n(2/PP))-11133 and &g 0.1 defines cutting-off lower bound. Specifically, on cuts off the sine curve and brings in a period of zero-valued probabilities. As different clients have different pe's, the cut-off points are not synchronized among clients, leading to additional availability heterogeneity.
43

---

0.1
0.5
0.9
0.1
0.5
0.9
10
20
30
40
50
60
70
80
0
10
20
30
40
50
60
70
80
Global round
Global round
000
000 Lino
10
20
30
40
50
60
70
10
20
30
40
50
60
70
(a) Stationary
(b) Non-stationary with staircase trajectory
0.1
0.5
0.9
0.1
0.5
0.9
10
20
30
40
50
70
80
0
10
20
30
40
60
70
80
Global round
Global round
000
000 L-00
10
20
30
40
50
60
70
10
20
30
40
50
60
70
(c) Non-stationary with sine trajectory
(d) Non-stationary with interleaved sine trajectory
Figure 6: Examples 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 a client is available in that round. The y-axis is the base probability p: construct p In other words, more blank space means that client is more scarcely available. We simulate the cases where E {0.1, 0.5, 0.9}. The detailed construction of pl can be found in Appendix J.3
Table The first round 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 dataset in Table 2. which is rounded up to the nearest 10% below for case of presentation. In addition, we sample the mean of test accuracy every 20 global rounds mitigate noisy progress. Some algorithms may never attain the targeted accuracy due their inferior performance, where we use "_" a placeholder.
Datasets
SVHN
CIFARIO
CINIC10
Quarters
1/4
1/2
3/4
3/4
1/4
Test accuracy
20%
40%
60%
80%
15%
30%
45%
60%
10%
20%
30%
40%
FedAME (ours)
40
120
200
820
20
60
200
1360
0
20
120
540
FedAvg over active clients
20
80
160
900
10
20
120
1060
0
20
40
800
FedAvg over all clients
100
420
960
520
FedAU F3АST
60
100
160
840
40
120
200
1080
20
40
160
1300
540
FedAvg with known p/'s MIFA (memory aided)
20
40
100
320
20
140
620
40
400
20
80
140
600
10
20
80
700
0
20
40
240
We choose 7 = 0.3 and P 20 for all non-stationary dynamics. Next, we visualize the probability trajectories along with sampled client availability in Fig. 6. The plots confirm the intuition that interleaved dynamics the most difficult one, e.g., no clients are available in the case of 0.1 therein.
J.4 Additional results
Staleness studies. Table 8 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), FedAWE slightly lags behind FedAvg over active clients. However, when reaching the final stage (the last quarter), FedAWE attains the target accuracy in a comparable or lower number of rounds to FedAvg over active clients in the evaluations SVHN and CINIC-10 datasets. The slowdown of FedAWE on CIFAR-10 10 dataset worth further investigation. In general, we arrive numerically at the conclusion that the staleness incurred by implicit gossiping in FedAWE is mild.
Training curves. In this part, we show the training curves of FedAvg over active clients, FedAWE and MIFA. In particular, the presented results of FedAWE are after exponential moving
44

---

FedAWE
FedAvg
MIFA
FedAWE
FedAug
MIFA
10-2
test accuracy
train loss
10
0.6
0.4
x 10
2 10-1
0.2
250
500
750
1000
1250
1500
1750
2000
0
250
500
750
1000
1250 1500
1750 2000
(a) Evaluation results SVHN dataset without exponential moving average
FedAWE
FedAvg
MIFA
FedNWE
FedAvg
MIFA
10
0.8-
test lest accuracy
train loss
10
0.6-
4x 10
0.4
3 10
0.2
2 10
250
500
750
1000
1250
1500
1750
2000
0
250
500
750
1000
1250
1500
1750 2000
(b) Evaluation results SVHN dataset
FedAWE
FedAvg
MIFA
FodAWE
FedAvg
MIFA
10
0.6-
test accuracy
train loss
6 -0
10
0.2
250
500
750
1000
1250
1500
1750
2000
750
1000 1250
(c) Evaluation results on CIFAR10 dataset
FedAvg
FedAWE
FedAvg
0.5
10
10
test accuracy
train loss
10
0.3
x 10
0.2
6 10-1
0.1
250
500
750
1000
1250
1750
500
750
1000 1250
1750 2000
(d) Evaluation results on CINIC10 dataset
Figure 7: Missing training curves under non-stationary client unavailability dynamics with sine curve
average [5] under a parameter 0.99. Note that this is to ease down the noisy progress, and for neat presentation only, the reported results in the main text and ablation studies are all from raw data. Fig. 7a plots the train loss and test accuracy from raw data. For example, when compared with Fig. 7b, EMA eases down the fluctuations but does not change either the trend or the order of algorithm performance results. All train losses are plotted on a logarithmic scale. The results are consistent with Table 2.
Impact sestem-design parameters. In this part, we study the impact of system-design parameter including the degree of non-stationarity and data heterogeneity under non-stationary with sine
45

---

Table 9: Results different parameter y. p = pi (yssnn22 (2m 1) +
7)).
Unavailable
Dutusets
0.3
0.1
Dynamics
Algorithms
Train
Non-stationary
FedANE (ours)
85.7
1 0.9
85.6
0.9 %
85.7 1 0.5 %
85.7
= 0.5 96
85.8 1 0.5
85.7
0.7 86
(Sine)
82.1
82.0
1.3%
82.3
0.9
FadAvg ever
71.3
2.5%
21.34:2..8
73.2
83.5 + 2.5
73.2
2.8%
74.0
74,9
MWA
FadAl
82.5 + 1,4%
42.5
%6
83.4
0.4%
83,7 + 0.3%
83.6
0.3
1.0%
FedAvg Knowwn pf
NIFA (memoory alided)
84.2 4: 0.4 %
84.1 1: 0.4
84.6 d
0.1 %
84.5 =
0.1 %
84.6 à: 0.1
84.4 0.1 %
Table 10: Results after different Dirichlet parameter & p = pi(y sinnsnnn2n (2 8) + (1 2)).
Unavailable
Dutusets
0.05
1.0
Dynamics
Algorithas
Irain
Test
Train
Test
Irain
Test
Non-stationary (Sine)
PedANE (ours)
82.5 + 2.1
82.5
4: 2.4
85.7
= 0.9 %
85.6 = 0.9
90.6
0.2 %
89.7
0.3 %
Feckrg
FadAvg over
58.5 +: 3.0%
58.5 3.8%
71.3
2.5 %
71.3
2.8%
82.0
0.7
81.9
0.6
MAAA
FedAU
79.5 4: 1.6
79.5
1.7.
82.5
%
82.5
1.3%
88.4
0.1
87.6
0.2
78.9 +-
1.3%
Fedlvg with known pl
84.2 =
1.0
83.5 4: 1.0%
86.3
86.0
1.0%
91.5
0.3
90.3
0.1
NIFA (meemory alded)
82.6 4: 0.1 %
82.6
0.6.6.0..9
84.2
0.4
%
84.1
0.4%
88.4
+ 0.1
%
87.5
0.1
%
trajectory. The results are in Table 9 and Table 10. Overall, FedAWE keeps outperforming the algorithms not assisted by memories known statistics.
In Table 10, clients' local data becomes more heterogeneous when a increases. We can see clear increase trend in accuracy. However, FedAWE remains to attain the best accuracies both train and test when compared the algorithms not aided by memory or known statistics. Moreover, outperforms MIFA, which consumes a lot of storage space, when 0.1 and 1.0. The observations confirm the practicality of FedAWE.
46

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have faithfully stated our contributions in both the abstract and introduction.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please refer to Appendix for details.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The regulatory assumptions are stated Section Due to space limitations, we are unable to present all the missing proofs and intermediate results in the main text. They are deferred to Appendix. Please refer Table of Contents for details.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We provide detailed experimental and the hyperparameter setups in Section 7 and Appendix J.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our evaluations are based on open-accessed datasets that are publically avail- able. An official implementation code is provided through GitHub link.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Experimental setting/details are important parts of reproducing our results. We provide the details in Section 7 and Appendix J to the best of our ability.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Our results are averaged over multiple random seeds and accompanied by error bars
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
47

---

Answer: [Yes]
Justification: Please find the software/hardware specifications in Appendix J.2.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: :
Answer: [Yes]
Justification: The NeurIPS code of ethics is strictly enforced throughout our research.
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have discussed broader impacts in Appendix B. We unaware of any negative impacts.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The existing assets used in this paper has been adequately cited credited to.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We have documented the experiment details in Section 7 and Appendix J.2. In addition, we provide our code with clear details and examples.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects
48


Reviews:
[{"review_id": "gdWys1D8Vo", "reviewer": "Reviewer_DLNT", "summary": "This paper primarily focuses on addressing the issue of intermittent client availability in federated learning, where the problem scenario involves heterogeneity in participation and non-stationary client availability.The authors draw on ideas from other federated learning algorithms, including asynchronous federated learning, and introduce two novel algorithmic structures, \"Adaptive Innovation Echoing\" and \"Implicit Gossiping\", to address the issues of heterogeneity and non-stationary client unavailability.The authors demonstrate through experiments that heterogeneity and non-stationarity significantly impact the convergence performance of federated learning algorithms. Their newly proposed algorithm, FedAWE, exhibits the property of linear speedup while also saving substantial memory. The experimental results are comprehensive and show that their algorithm outperforms others, highlighting its advantages.", "questions": "Firstly, do you believe that the conclusions regarding the heterogeneity part of your experiments in the section \"Heterogeneity and Non-stationarity May Lead to Significant Bias\" overlap with Theorem 1 from the paper \"A Lightweight Method for Tackling Unknown Participation Probabilities in Federated Averaging\"? Or do your conclusions offer any particular insights beyond this theorem?\n    Secondly, the paper “FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning” introduces the FedVARP algorithm, which is similar to the MIFA algorithm but employs a different variance reduction method. Could you also conduct related experiments to compare your algorithm with FedVARP?", "limitations": "The authors' work generalizes the application scenarios for federated learning by relaxing assumptions about client participation. It is hoped that in future research, the authors will incorporate variance reduction and other related techniques within the current algorithm framework to further enhance performance.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The author's article combines the ideas of federated learning algorithms including asynchronous federated learning and peer-to-peer networks. Two novel algorithm architectures, \"Adaptive Innovation Echoing\" and \"Implicit Gossiping\", are proposed, which can greatly reduce memory. At the same time, the article is more general for client availability, only needs to satisfy independent and strictly positive across clients and rounds.", "weaknesses": "In the section \"Heterogeneity and Non-stationarity May Lead to Significant Bias\", the authors only provide experimental evidence to verify that these factors affect the convergence performance of the algorithm. Could authors perhaps reference Theorem 1 and Theorem 2 from the FedAU paper for a theoretical analysis of these two factors? I believe that Theorem 1 from the article \"A Lightweight Method for Tackling Unknown Participation Probabilities in Federated Averaging\" could encompass the authors' experimental results concerning heterogeneity, that is, if the client participation is heterogeneous and the weight selection is not appropriate, it will directly affect the effect of convergence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation for the novelty and generality of our problem setup. Please find our responses to your questions below.\n\n**W1/Q1: reference Theorems 1-2 in the FedAU paper [53] for a theoretical analysis of Section 4.** Yes, we are happy to reference Theorem 1 and Theorem 2 in the FedAU paper in the camera-ready version if the paper gets accepted. Thank you for pointing out our oversight. Those two theorems share a similar spirit with us and will complement our numerical results in Section 4, where we use numerical experiments to illustrate the significant bias incurred under stationary dynamics. However, it is worth noting that our paper focuses on a much harder problem, where the non-stationary dynamics is unstructured. Thus, we generalize their results to the problem of non-stationary dynamics.\n\n**Q1: insights beyond Theorem 1 in the FedAU paper [53].** Theorem 1 in the FedAU paper theoretically characterizes the biased global objective under heterogeneous but stationary client unavailability. However, as we focus on the general case where clients are allowed to have unstructured non-stationary dynamics subject to Assumption 1, we believe it is in general hard to obtain a nice analytical form as that in the FedAU paper. This is because the complex interplay between $p\\_i^t$'s across rounds and clients will inevitably complicate and thus hinder the theoretical analysis. Fortunately, the numerical experiments help us to confirm that non-stationary dynamics will further degrade the performance of FedAvg algorithm.\n\n**Q2: conduct related experiments to compare with FedVARP.** Thank you for the great suggestion. Yes, we are happy to add new experiments on FedVARP for a more in-depth understanding of our work. \n\nSpecifically, we test the FedVARP algorithm under the client unavailability dynamics in Table 1 on page 9 in our manuscript. Please refer to Table 2 in the pdf for complete results. Due to space limit, Table Q2 only lists the comparisons between our algorithm, FedVARP and MIFA under the staircase non-stationary dynamics. \n\nWe can see from Table Q2 that the performance of FedVARP is in general slightly better than MIFA, consistent with the observations in [53] and [R1]. We want to emphasize that it is a bit unfair to compare the proposed algorithm with those variance-reduced algorithms, where they take advantage of significantly more extra memory space proportional to the size of $O(md)$ and thus violate our design principle of this work: efficiency. In fact, most of the clients in cross-device federated learning are mobile or IoT devices with limited storage and memory capacity [19]. The added memory will burden their hardware, eventually impacting regular operations. However, our algorithm can sometimes even outperform them. Similarly to the statements in the manuscript (lines 340-341 on page 9), we attribute this phenomenon to our usage of gradients from always fresh stochastic samples. This is in contrast to their reuse of stored gradients from unavailable clients.\n\n|Algorithms|SVHN (Train)|SVHN (Test)|CIFAR-10 (Train)|CIFAR-10 (Test)|CINIC-10 (Train)|CINIC-10 (Test)|\n|---|---|---|---|---|---|---|\n|**Ours**|$85.9 \\pm 0.8\\\\%$|$85.6 \\pm 1.0\\\\%$|$67.7 \\pm 1.3\\\\%$|$66.0 \\pm 1.2\\\\%$|$47.5 \\pm 2.0\\\\%$|$46.9 \\pm 2.0\\\\%$|\n|MIFA|$84.2 \\pm 0.5\\\\%$|$84.0 \\pm 0.5\\\\%$|$66.7 \\pm 0.7\\\\%$|$65.3 \\pm 0.5\\\\%$|$47.5 \\pm 0.5\\\\%$|$46.9 \\pm 0.5\\\\%$|\n|FedVARP|$84.6 \\pm 0.2\\\\%$|$84.3 \\pm 0.3\\\\%$|$67.3 \\pm 0.3\\\\%$|$66.1 \\pm 0.3\\\\%$|$47.7 \\pm 0.2\\\\%$|$47.2 \\pm 0.1\\\\%$|\n\n**Table Q2: Additional performance comparisons with FedVARP under the staircase non-stationary dynamics.**\n\n**References:**\n\n[R1] Jhunjhunwala, D., et al. (2022). Fedvarp: Tackling the variance due to partial client participation in federated learning. In Uncertainty in Artificial Intelligence (pp. 906-916). PMLR.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hP7DNzkhlf", "reviewer": "Reviewer_i6Qf", "summary": "To address intermittent client availability, the authors study heterogeneous and non-stationary client availability, highlighting the significant impact of such heterogeneity using FedAvg. They propose FedAWE, which (i) compensates for missed computations due to unavailability and (ii) evenly diffuses local updates through implicit gossiping, despite non-stationary dynamics. The authors demonstrate that FedAWE converges to a stationary point for non-convex objectives while achieving the desired linear speedup property, supported by numerical experiments on real-world datasets with varied client unavailability dynamics.", "questions": "Can the authors provide an in-depth analysis on the algorithm's complexity?", "limitations": "The authors have discussed the limitations of algorithms.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1) The authors propose a new algorithm to address the issue of intermittent client availability.\n\n2) The paper is easy to follow, and a large number of cases w.r.t. unavailable dynamics are used for validation.", "weaknesses": "1) The proposed algorithm is intuitive. The weight of the model update $G_i^t$ for each client is modified such that the longer the participation interval rounds, the greater the proportion of model update, which is proportional to $t-\\tau(t)$. However, when the client participation rate is very low (e.g., 1% of clients participate randomly), $t-\\tau(t)$will be expected to be 100, magnified by a factor of 100. This is somewhat unreasonable.\n\n2) The rate of convergence in corollary1, the last term on the right-hand side, apparently dose not show a linear speedup with respect to the number of local steps $s$ and the number of active clients $k$.\n\n3) In the rate of convergence in Corollary 1, it appears that $(1 + L^2)$ combines two variables with different \"physical dimensions\", which suggests that there might be an issue with the proof. For example, the \"physical dimension\" of the learning rate $\\eta$ is $1/L$, and $(1 +\\eta^2 L^2)$ is reasonable, while $(1 + L^2)$ might be incorrect.\n\n4) It is not reasonable to see the performance of \"FedAvg over all clients\" being much lower than \"FedAvg over active clients\" in Table 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for your appreciation for our paper flow and extensive numerical experiments. We believe that many of your concerns can be easily addressed, and we apologize for our lack of clarity on these points. We hope that our response can address your concerns, and the insights discussed here will be incorporated into the camera-ready version if the paper gets accepted.\n\n**W1: on gradient amplification.** We note that solving the issue of client unavailability by amplifying local gradients is widely adopted in the prior literature [19,27,53,52,40]. As pointed out by [13], when the exact availability distribution is known, the most intuitive way to amplify these gradients is to collect only the fastest responses and re-weight according to the response probabilities. Thus, like our method, these weights can be very large when the participation rate is very low. Although somewhat counterintuitive, as suggested by the numerical results in our manuscript and in [13,53], these types of algorithms perform just fine. \n\n**W1: on intuitive algorithm (novelty).** We emphasize that our contribution is highly non-trivial. For example, the counterexample below shows that simply modifying weights accordingly to the participation interval but not postponing broadcast will not debias FedAvg under even stationary availability. The proof is skipped due to space. It highlights the need for both of the two algorithmic components in Section 5. \n\n**[Counterexample].** Suppose that we have two clients such that client \\#1 is always available, while client \\#2 is available only in odd rounds. Each client holds $F\\_i(x)=1/2\\|\\|x-u\\_i\\|\\|^2$ and computes 1 local step. The server boadcasts as in FedAvg [30] and aggregates local updates as $x^{t+1}\\gets 1/\\|{\\mathcal{A}^t}\\|\\sum\\_{i\\in{\\mathcal{A}^t}}x\\_i^{t\\dagger}$, where $x\\_i^{t\\dagger} \\gets x^{t}-(t-\\tau\\_i(t))G\\_i^t$. Choose $x^0=0$ and $\\eta=1/T$. It holds that $$\\lim\\_{T\\rightarrow\\infty}x^T=\\frac{3u\\_1+2u\\_2}{5}.$$\n\n**W2: on speedup in the last term.** We achieve the desired speedup property for a sufficiently large training round $T$, consistent with the prior literature [52,53,60]. For ease of presentation, let \n$C\\_1:=L(F(\\bar{\\mathbf{x}}^0)-F^\\star)+\\sigma^2$, $C\\_2:=((\\sigma^2+\\zeta^2)/\\delta)[(1+L^2)+\\rho/(1-\\sqrt{\\rho})^2]$. In the special case where $k$ clients participate u.a.r., we have $\\delta\\_{\\max}=\\delta=k/m$. The convergence rate in (16) reduces to $$\\frac{1}{T}\\sum\\_{t=0}^{T-1}\\mathbb{E}[\\|\\|\\nabla F(\\bar{\\mathbf{x}}^t)\\|\\|^2] \\lesssim\\frac{C\\_1}{\\sqrt{s\\delta mT}}+\\frac{smC\\_2}{T}.$$ If we ignore the constants hidden behind the asymptotic bound, the first term dominates when $C\\_1/\\sqrt{s\\delta mT}\\ge C\\_2(sm/T)$, i.e., when $T\\ge C\\_2^2/C\\_1^2(s^3m^3\\delta)$. Consequently, the convergence bound reduces further to $$\\frac{1}{T}\\sum\\_{t=0}^{T-1}\\mathbb{E}[\\|\\|\\nabla F(\\bar{\\mathbf{x}}^t)\\|\\|^2]\\lesssim\\frac{C\\_1}{\\sqrt{s\\delta mT}}=\\frac{C\\_1}{\\sqrt{s(k/m)mT}}=\\frac{C\\_1}{\\sqrt{skT}}.$$ Now, we can see that the R.H.S. of the bound indicates a clear speedup w.r.t. the number of local steps $s$ and the number of sampled clients $k$. We will make this clear in the camera-ready version if accepted.\n\n**W3: on the appearance of $(1+L^2)$ in Corollary 1.** We note that the appearance of $L^2$ in Corollary 1 is not a glitch in our proof but a testament that we account for the key parameters in the assumptions. Although we agree with the reviewer that the term $(1 + \\eta^2 L^2)$ would be at the constant level with the learning rate $1/L$, it is not uncommon to find the Lipschitz constant $L$ in the final bound in the prior literature; see, e.g., Theorems 1-3 in [27], Corollary 4 in [53], Theorem 3 in [R1]. \n\nTechnically speaking, the appearance of $L^2$ results from Assumption 4. This assumption is more general than the popular ones in the prior literature on gradient divergence; see details in Table 2 on page 16. Then, together with Assumption 2, Proposition 3 on page 26 holds as follows: $$\\frac{1}{m}\\sum\\_{i=1}^m\\|\\|\\nabla F_i(\\mathbf{z}\\_i^t)\\|\\|^2\\le\\frac{3 L^2}{m} \\sum\\_{i=1}^m \\|\\|\\mathbf{z}\\_i^t-\\bar{\\mathbf{z}}^t\\|\\|^2+3(\\beta^2+1)\\|\\|\\nabla F(\\bar{\\mathbf{z}}^t)\\|\\|^2+3\\zeta^2.$$ Notice that the coefficient of the first term on the R.H.S. is $L^2$ instead of a coupling of $\\eta^2 L^2$. Consequently, we shall see a standalone $L^2$, for example, when we apply the above Proposition 3 to the first term in the second row in Lemma 3.\n\n**W4: on the performance of (FedAvg all).** In numerical experiments, the phenomenon that (FedAvg all) lags behind (FedAvg active) has been observed under stationary availability in [53] and more significantly in [13, Fig. 2] (FedAvg with device sampling). Non-stationary dynamics brings in more uncertainty, so it is expected that things can become even worse. We recall that (FedAvg all) differs from (FedAvg active) by the gradient aggregation rules. Specifically, $$\\text{FedAvg all}:\\\\ G^t\\_{all}:=\\frac{1}{m} \\sum\\_{i=1}^m\\mathbf{1}\\_{\\\\{i\\in{\\mathcal{A}}^t\\\\}}G\\_i^t;\\\\ \\text{FedAvg active}:\\\\  G^t\\_{active}:=\\frac{1}{\\|{\\mathcal{A}}^t\\|}\\sum\\_{i=1}^m\\mathbf{1}\\_{\\\\{i\\in{\\mathcal{A}}^t\\\\}}G\\_i^t.$$ \n\n**Question: provide an in-depth analysis on the algorithm's complexity.** We have briefly discussed the memory and computational complexity in lines 160-165 on page 4, but we are happy to address them in more detail here. A detailed complexity comparison for the baseline algorithms, including ours, can be found in Table 1 in the pdf. Since our algorithm does not draw new stochastic samples for training, there is no increase in sample complexity. It takes $O(1)$ extra memory unit to store the last active round $\\tau\\_i(t)$. The weight echoing step incurs $O(1)$ additional computation to adjust the weight of gradient accumulation. \n\n**References:**\n\n[R1] Fatkhullin, I. et al. (2023). Momentum provably improves error feedback!. Advances in Neural Information Processing Systems, 36.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TBHV0CSqEL", "reviewer": "Reviewer_ZjRF", "summary": "The work studies heterogeneous and non-stationary client availability in FL, showing that it can have a significant impact on the performance of FedAvg. As a solution, the work presents the FedAWE algorithm, which compensate the missed computationd due to unavailability with minimal additional overhead w.r.t. FedAvg and is agnostic to non-stationary participation dynamics. The works presents a convergence proof in non-convex setting and numerical experiments to showcase the problem and assess the effectiveness of the proposed solution.", "questions": "In section 7, heterogeneous clients' data distribution are simulated $\\nu_i \\sim \\text{Dirichlet(0.1)}$, as it is common in FL literature. Then the authors simulate the availabilty function of client $i$ as $p_i^t=p_i\\cdot f_i(t)$, where $f_i(t)$ models the non-stationary dynamics and $p_i=\\langle \\nu_i, \\phi\\rangle$, with $\\phi$ caractering the importance of each image class. Why $p_i$ is defined from the image class distribution $\\nu_i$, given that it models the probability of being sampled? I expect the data distribution and the the availability to be uncorrelated, so maybe have $\\mathbf{p} \\sim \\text{Dirichlet}(\\gamma)$, where $\\gamma$ decides how heterogeneous are the sampling probability of each client.", "limitations": "Limitations of the approach are not sufficiently discussed in section 8.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. **Importance of the research problem.** The work tackles an important and often overlook problem, that is heterogeneous and non-stationary client participation patterns. The research problem is particularly important given that in FL clients are edge devices, which are heterogeneous in computing capabilities and so availability patterns.\n2. **Simple, principled and convenient approach.** The proposed approach is simple to implement following the details in algorithm 1, since it involves the calculation of a discout factor on clients' pseudo gradient and postponing the sending of the updated model.\n3. **Good results.** The provided experimental results underscore the effectiveness of the approach in addressing both non-stationary and heterogeneous client availability. A plus is that authors did provide the code.", "weaknesses": "The biggest weakness of the work is in my opinion the presentation. I found the writing not clear and straightforward enough to make the reader grasp the intuitions behind the technical innovations of the proposed approach. There are too many pointer to the supplementary material, and in most cases it seems matter that needs to be in main paper (e.g. line 131). Also, the implications of the technical lemmas are often poorly discussed (e.g. proposition 1-2, lemma 1-3), leaving the reader confused about the need of that particulare piece of information.\n\nI kindly suggest authors to revise the writing of the manuscript to better highlight the most imporant information to be conveyed, and avoid as much as possible continous pointer to the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation for the motivation, principled algorithm and good results of the paper. We hope that our response can address your concerns.\n\n**W1: on pointers to the supplementary material.** We apologize for not being clear enough in the main text. If the paper gets accepted, we will have one additional page to accommodate those pointers in the main text, including but not limited to line 131, line 224 and line 241 per your suggestions. \n\n**W2: on implications of the technical lemmas.** In the manuscript, each technical lemma is accompanied by brief illustrations either before or after it, but they may not be clear enough. We are happy to elaborate the implications here in detail.\n\n- Proposition 1 indicates that, when a client becomes available, the weight echoing procedure equalizes the number of local improvements with that of the other available peers. It captures the algorithmic intuition to allow the unavailable clients to catch up to missed computations. \n- Proposition 2 builds the connection between the sequence $\\mathbf{x}\\_i^t$ and the auxiliary sequence $\\mathbf{z}\\_i^t$. At a high level, it says that we shall see a bounded approximation error as long as the gradient norm and consensus error of the auxiliary sequence $\\mathbf{z}\\_i^t$ are bounded. Therefore, the problem boils down to bounding those two terms.\n- Lemma 1 is well known in the fully decentralized learning literature to characterize information mixing [33,32,49]. The spectral norm $\\rho$ is expected to be strictly smaller than 1 to ensure exponential decay, which we have shown in Lemma 4.\n- Lemma 2 is an intermediate result to characterize the statistical properties of the unavailable duration. It indicates that despite the lack of structure in the non-stationary dynamics, the expected echoing weight remains finite.\n- Lemma 3 quantifies the progress of the global objective per global round. Similarly to Proposition 2, it points out the need for the other technical lemmas, for example, Lemma 2 for the second term, Proposition 2 for the approximation error.\n\nAgain, we will make sure to improve the presentation if the paper gets accepted.\n\n**Q1: why $p_i$ is defined from the image class distribution.** We note that correlating the local data distribution and the probability of client availability is a common practice in the prior literature. For example, MIFA [13] experiments with a formula for $p\\_i$ so that clients that hold images of smaller digits participate less frequently. Similarly to our construction, FedAU [53] considers $p\\_i$ as an inner product of the clients' local data distribution $\\nu\\_i$ and an external distribution $\\Phi^\\prime$. \n\nMoreover, we recall that the issue of client unavailability fundamentally arises from heterogeneous local data distributions (a.k.a. non-i.i.d. local data). As we have demonstrated in Fig. 2, Section 4, the expected output of FedAvg can be far away from the global optimum under non-i.i.d. local data. Intuitively, when clients hold homogeneous local data, the bias will be much milder even under heterogeneous availability. This is because every client becomes interchangeable when their local data distributions are homogeneous. \n\n**Q2: why not, for example, sample $p\\sim\\mathsf{Dirichlet}(\\gamma)$.** The issue of directly applying the Dirichlet distribution to construct $p\\_i$'s is that the generated $p\\_i$'s are likely to be more concentrated in the presence of a larger client population. Suppose that we have $\\mathbf{p}:=[p\\_1,\\ldots,p\\_m]\\sim\\mathsf{Dirichlet}(\\gamma)$, it holds that $$\\mathbb{E}[p\\_i]=\\frac{1}{m},\\\\ \\mathsf{Var}(p\\_i)=\\frac{m-1}{m^2(m\\gamma+1)}<\\frac{m}{m^2(m\\gamma)}=\\frac{1}{m^2 \\gamma},\\\\ \\forall i\\in[m].$$ In the cross-device federated learning, $m$ could be quite large, leading to small $\\mathbb{E}[p\\_i]$ and $\\mathsf{Var}(p\\_i)$. In other words, the generated $p\\_i$'s are more likely to center around the mean with a larger client population. For example, Fig. 1 and Fig. 2 in the pdf are histograms of $\\mathbf{p}$ realizations with $m=100$ clients, where $\\gamma=0.1$ in the former and $\\gamma=1$ in the latter. It can be seen that all the $p\\_i$'s concentrate around their mean $0.01$, and the range of the generated $p\\_i$'s is around $0.16$ in the former while around $0.06$ in the latter. In contrast, our construction of $p\\_i$'s results in less concentration. We copy Fig. 5 from our manuscript on page 42 and attach it as Fig. 3 in the pdf, which is a histogram of the generated $p\\_i$'s under our construction. Clearly, our $p\\_i$'s are more spread out with a significantly heavier tail over the entire $[0,1]$ interval.\n\n**Limitations: the limitations are not sufficiently discussed in Section 8.** Thank you for bringing this to our attention. Per NeurIPS guideline, we have Section A in the Appendix to elaborate the potential limitations of our work. We briefly reiterate them here for completeness.\n\n- Availability probabilities in the manuscript are theoretically assumed to be independent and strictly positive. It is interesting to theoretically characterize the setting, where we have correlated probabilities under arbitrary probabilistic trajectories. \n- Client unavailability can vary greatly in the presence of heterogeneous and non-stationary dynamics. It is also worth exploring variance-reduction techniques for a more robust update.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all reviewers for their constructive and thorough reviews, and for their careful evaluation of our paper. 

In this global response, we would like to provide a brief summary of the reviews, based on our understanding. Overall, the reviewers confirm that

- our research topic is important and more general than prior literature (Reviewers ZjRF and DLNT);
- our algorithm is simple and convenient (Reviewers ZjRF and DLNT);
- our experiments are extensive (Reviewers i6QF and ZjRF).

The tables and figures in the attached pdf address the concerns raised by each reviewer. Specifically, we have additionally

- compared the extra complexity (in terms of sampling, memory, and computation) incurred by our algorithm, MIFA, and FedAU with FedAvg in Table 1 (Reviewer i6QT);
- conducted experiments on FedVARP for performance evaluations in Table 2 (Reviewer DLNT);
- examined the Dirichlet distribution to generate client availability $p\_i$'s in Fig. 1 and Fig. 2 (Reviewer ZjRF).

In addition, we include a copy of Fig. 5 from our manuscript on page 42 as Fig. 3 in the pdf for comparisons. 

Please find a point-by-point response to all reviewer concerns with individual comments below. Again, thank you for your time and effort in evaluating our paper.

Meta-review: This paper explores Federated Learning (FL) in the context of heterogeneous and non-stationary client availability. Most reviewers commend the effectiveness of the proposed algorithm in addressing these challenges, as well as the rigor of the theoretical analysis and experimental evaluation. One reviewer raised a concern regarding the constant $1+L^2$ in the convergence theorem, suggesting that a term like $1+\eta^2L^2$ might be more appropriate. While this point is valid, the presence of $1+L^2$ does not detract from the overall contribution of the main theorem. We recommend the paper for acceptance, with a suggestion for the authors to refine the term $1+L^2$ to $1+\eta^2L^2$ in the camera-ready version.
Decision: Accept (poster)