Year: 2021

Abstract:
Present-day federated learning (FL) systems deployed over edge networks consists of a large number of workers with high degrees of heterogeneity in data and/or computing capabilities, which call for flexible worker participation in terms of timing, effort, data heterogeneity, etc. To achieve these goals, in this work, we propose a new FL paradigm called “Anarchic Federated Learning” (AFL). In stark contrast to conventional FL models, each worker in AFL has complete freedom to choose i) when to participate in FL, and ii) the number of local steps to perform in each round based on its current situation (e.g., battery level, communication channels, privacy concerns). However, AFL also introduces significant challenges in algorithmic design because the server needs to handle the chaotic worker behaviors. Toward this end, we propose two Anarchic Federated Averaging (AFA) algorithms with two-sided learning rates for both cross-device and cross-silo settings, which are named AFA-CD and AFA-CS, respectively. Somewhat surprisingly, even with general worker information arrival processes, we show that both AFL algorithms achieve the same convergence rate order as the state-of-the-art algorithms for conventional FL. Moreover, they retain the highly desirable linear speedup effect in the new AFL paradigm. We validate the proposed algorithms with extensive experiments on real-world datasets.

heading: 1 INTRODUCTION
text: Federated Learning (FL) has recently emerged as an important distributed learning framework that leverages numerous workers to collaboratively learn a joint model (Li et al., 2019a; Yang et al., 2019; Kairouz et al., 2019). Since its inception, FL algorithms have become increasingly powerful and have been able to handle various heterogeneity in data, network environments, worker computing capabilities, etc. Moreover, most of the prevailing FL algorithms (e.g., FedAvg (McMahan et al., 2016) and its variants (Li et al., 2018; Zhang et al., 2020b; Karimireddy et al., 2020b;a; Acar et al., 2021)) enjoy so-called “linear speedup effect,” i.e., the convergence time of an FL algorithm decreases linearly as the number of workers increases (Stich, 2018; Yu et al., 2019; Wang & Joshi, 2018; Khaled et al., 2019; Karimireddy et al., 2020b; Yang et al., 2021; Qu et al., 2020).
To achieve these salient features, most of the existing FL algorithms have adopted a server-centric approach, i.e., the worker behaviors are tightly “dictated” by the server. For example, the server in these FL algorithms can i) determine either all or a subset of workers to participate in each round of FL update; ii) fully control the timing for synchronization and whether to accept/reject information sent from the workers; iii) precisely specify the algorithmic operations (e.g., the number of local steps performed at each worker before communicating with the server), etc.
Despite achieving strong performance guarantees, such a server-centric approach introduces several limitations. Specifically, these server-centric FL algorithms often implicitly rely on the following assumptions: (1) each worker is available for training upon the server’s request and throughout a complete round; (2) all participating workers are willing to execute the same number of local updates and communicate with the server in a synchronous manner following a common clock. Unfortunately, in edge networks where many FL systems are deployed, these assumptions are restrictive or even problematic due to the following reasons. First, many requested edge devices on the worker side may not be available in each round because of, e.g., communication errors or battery outages. Second, the use of synchronous communication and an identical number of local updates across all workers ignores the fact that worker devices in edge-based FL systems are heterogeneous in computation and communication capabilities. As a result, stragglers (i.e., slow workers) could significantly slow
down the training process. To mitigate the straggler effect, various robust FL algorithms have been developed. For example, the server in FedAvg (McMahan et al., 2016) can simply ignore and drop the information from the stragglers to speedup learning. However, this may lead to other problems such as wasted computation/energy (Wang et al., 2019), slower convergence (Li et al., 2018), or biased/unfair uses of worker data (Kairouz et al., 2019). Moreover, the synchronous nature of the server-centric approaches implies many networking problems (e.g., interference between workers, periodic traffic spikes, high complexity in maintaining a network-wide common clock).
The above limitations of the current server-centric FL approaches motivate us to propose a new paradigm in FL, which we call Anarchic Federated Learning (AFL). In stark contrast to servercentric FL, workers in AFL are completely free of the “dictation” from the server. Specifically, each worker has complete freedom to choose when and how long to participate in FL without following any control signals from the server. As a result, the information fed back from workers is inherently asynchronous. Also, each worker can independently determine the number of local update steps to perform in each round based on its current local situation (e.g., battery level, communication channels, privacy concerns). In other words, the amount of local computation at each worker is time-varying, device-dependent, and fully controlled by the worker itself. Clearly, AFL has a much lower server-worker coordination complexity and avoids the aforementioned pitfalls in server-centric FL approaches. However, AFL also introduces significant challenges in algorithmic design on the server-side because the server needs to work much harder to handle the chaotic worker behaviors in AFL (e.g., asynchrony, spatial and temporal heterogeneity in computing). Toward this end, several fundamental questions naturally arise: 1) Is it possible to design algorithms that converge under AFL? 2) If the answer to the previous question is yes, how fast could the algorithms converge? 3) Can the new AFL-based algorithms still achieve the desired “linear speedup effect?”
In this paper, we answer the above fundamental questions of AFL affirmatively. Our main contributions and key results are summarized as follows: • We propose a new FL paradigm called Anarchic Federated Learning (AFL), where the workers are
allowed to engage in training at will and choose the number of local update steps based on their own time-varying situations (computing resources, energy levels, etc.). This loose worker-server coupling significantly simplifies the implementations and renders AFL particularly suitable for FL deployments in edge computing environments. For any AFL algorithms under general worker information arrival processes and non-i.i.d. data across workers, we first establish a fundamental convergence error lower bound that depends on the data heterogeneity in the AFL system. Then, we propose two Anarchic Federated Averaging (AFA) algorithms with two-sided learning rates for two classes of FL problems(cross-device and cross-silo) (Kairouz et al., 2019; Wang et al., 2021).
• For AFL in the cross-device (CD) setting, our AFA-CD algorithm converges to an error ball whose size matches the fundamental lower bound, with an O(1/ √ mT ) convergence rate where m is the
number of collected workers in each round of update and T is the total number of rounds. We note that this convergence rate retains the highly desirable “linear speedup effect” under AFL.1 Moreover, under the special case with uniform workers’ participation (equivalent to uniform workers sampling in conventional FL (Li et al., 2019c; Karimireddy et al., 2020b;a; Acar et al., 2021)), AFA-CD can further converge to a stationary point (i.e., a singleton) at a convergence rate that matches the state-of-the-art of conventional distributed and federated learning.
• For AFL in the cross-silo (CS) setting, our proposed AFA-CS algorithm achieves an enhanced convergence rate of O(1/ √ MT ) by leveraging historical feedback and variance reduction tech-
niques, where M is the total number of workers. This suggests that, not only can “linear speedup” be achieved under AFL-CS, the speedup factor also depends on the total number of workers M instead of the number of collected workers m in each round (M > m). To our knowledge, this result is new in the FL literature.
• We validate the proposed algorithms with extensive experiments on CV and NLP tasks and further explore the effect of the asynchrony and local step number in AFL. We also numerically show that our AFL is a general algorithmic framework in the sense that various advanced FL techniques (e.g., FedProx (Li et al., 2018) and SCAFFOLD (Karimireddy et al., 2020b)) can be integrated as the optimizers in our AFA framework to further enhance the AFL performance. 1To attain -accuracy, it takes O(1/ 2) steps for an algorithm with an O(1/ √ T ) convergence rate, while needing O(1/m 2) steps for another algorithm with an O(1/ √ mT ) convergence rate (the hidden constant in Big-O is the same). In this sense, O(1/ √ mT ) implies a linear speedup with respect to the number of workers.
The rest of the paper is organized as follows. In Section 2, we review related work. In Section 3, we introduce AFL and our AFA algorithms, which are followed by their convergence analysis in Section 4. We present the numerical results in Section 5 and conclude the work in Section 6.

heading: 2 RELATED WORK
text: Server-Centric Federated Learning Algorithms: To date, one of the prevailing FL algorithms is Federated Averaging (FedAvg), which was first proposed in (McMahan et al., 2016) as a heuristic to improve communication efficiency and data privacy for FL. Since then, there have been substantial follow-ups of FedAvg that focus on non-i.i.d. (heterogeneous) data (see, e.g., FedProx (Li et al., 2018), FedPD (Zhang et al., 2020b), SCAFFOLD (Karimireddy et al., 2020b), FedNova (Wang et al., 2020), FedDyn (Acar et al., 2021), and MIME (Karimireddy et al., 2020a)), which are closely related to our work. The main idea for these algorithms is to control the “model drift” (due to heterogeneous datasets and the use of multiple local update steps on the worker side of FedAvg). While these algorithms achieved various degrees of success in dealing with data heterogeneity, they are all server-centric synchronous algorithms that are not easy to implement in edge-based FL due to straggler issues (see discussions in Section 1).
Federated Learning with Flexible Worker Participation: Recently, some attempts have been made to alleviate the strict requirements on worker’s participation, such as allowing different local steps (Ruan et al., 2021; Wang et al., 2020) and asynchronous FL (Avdiukhin & Kasiviswanathan, 2021; Xie et al., 2019). However, most of these works either lack theoretical performance guarantees or require strong assumptions. For example, Ruan et al. (2021) assumed strongly convex loss function and bounded aggregation coefficient; Avdiukhin & Kasiviswanathan (2021) assumed bounded gradients and same computation time per iteration for all workers. Our AFL paradigm considered in this paper is more general and subsumes all the above settings as special cases. We note, however, that AFL differs from conventional FL with flexible worker participation in that the worker’s participation in AFL and its local optimization process are completely determined by the workers, and not by the sampling requests from the server. This is more practical since it allows workers to participate in FL under drastically different situations in network, charging/idle cycles, etc. Due to the complex couplings between various sources of randomness and multiple layers of heterogeneity in spatial and temporal domains in AFL, the training algorithm design for AFL and its theoretical analysis is far from a straightforward combination of existing FL techniques for flexible worker participation.
Asynchronous Distributed Optimization: The asynchrony in AFL also shares some similarity with asynchronous distributed optimization. The basic idea of asynchronous distributed optimization is to forgo the common clock in the system to lower the system implementation complexity in distributed optimization. However, due to extra noise introduced by asynchrony, it is highly non-trivial to establish the convergence performance of asynchronous distributed optimization algorithms. To address this challenge, asynchronous distributed optimization has been studied extensively in the machine learning and optimization literature (see, e.g., Lian et al. (2018); Niu et al. (2011); Agarwal & Duchi (2012); Paine et al. (2013); Xie et al. (2019); Zhang et al. (2020a) and references therein). We note that the AFL paradigm considered in this paper is more general and subsumes asynchronous distributed optimization as a special case. To see this, note that in addition to the asynchronous updates at the server, the workers in AFL could further have different numbers of local update steps. Moreover, the workers may not even need to be work-conserving (i.e., workers could be idle between rounds of updates). As a result, the convergence analysis of AFL is much more challenging.

heading: 3 ANARCHIC FEDERATED LEARNING
text: 1) Overview of Anarchic Federated Learning: The goal of FL is to solve an optimization problem in the form of minx∈Rd f(x) := 1M ∑M i=1 fi(x), where fi(x) , Eξi∼Di [fi(x, ξi)] is the local (nonconvex) loss function associated with a local data distributionDi andM is the total number of workers. For the setting with heterogeneous (non-i.i.d.) datasets at the workers, we have Di 6= Dj , if i 6= j. In terms of the assumption on the size of workers, FL can be classified as cross-device FL and cross-silo FL (Kairouz et al., 2019; Wang et al., 2021). Cross-device FL is designed for large-scale FL with a massive number of mobile or IoT devices (M is large). As a result, the server can only afford to collect information from a subset of workers in each round of update and does not have sufficient
Algorithm 1 The Basic Framework of Anarchic Federated Learning (AFL). At the Server (Concurrently with Workers):
1. (Concurrent Thread) Collect local updates returned from the workers. 2. (Concurrent Thread) Aggregate local update returned from the collected workers and
update global model following some server-side optimization process. At Each Worker (Concurrently with Server):
1. Once decided to participate in the training, pull the global model with current timestamp. 2. Perform (multiple) local update steps following some worker-side optimization process. 3. Return the computation result and the associated pulling timestamp to the server, with
extra processing if so desired.
memory space to store workers’ information across rounds. In comparison, the number of workers in cross-silo FL is relatively small. Although the server in cross-silo FL may still have to collect information only from a subset of workers in each round, it has enough memory space to store each worker’s most recent information.
The basic process of AFL is illustrated in Algorithm 1. Here, the server is responsible for: 1) collecting the local updates returned from workers, and 2) aggregating the obtained updates once certain conditions are satisfied (e.g., upon collecting m ∈ (0,M ] local updates from workers) to update the global model. In AFL, each worker could be non-work-conserving (i.e., idling is allowed between each two successive participations in training). Whenever a worker intends to participate in the training, it first pulls the current model parameters from the server. Then, after finishing multiple local update steps (more on this next) with some worker-side optimization process (e.g., following stochastic gradients or additional information such as variance-reduced and/or momentum adjustments), the worker reports the computation results to the server (potentially with extra processing if so desired, such as rescaling, compression for communication-efficiency, etc.). Note that the above operations can happen concurrently on the server and worker sides, i.e., the processings at the workers and the server are independent of each other in the temporal domain.
We remark that AFL is a general computing architecture that subsumes the conventional FL and asynchronous distributed optimization as special cases. From an optimization perspective, the server and the workers may adopt independent optimization processes, thus enabling a much richer set of learning “control knobs” (e.g., separated learning rates, separated batch sizes). More importantly, each worker is able to completely take control of its own optimization process, even using a timevarying number of local update steps and optimizers, which depend on its local dataset and/or its device status (e.g., battery level, privacy preference).
2) A Fundamental Convergence Error Lower Bound of AFL: Before developing training algorithms for AFL, it is insightful to first obtain a fundamental understanding of the performance limit of any AFL training algorithms. Toward this end, we first state several assumptions that are needed for our theoretical analysis throughout the rest of this paper.
Assumption 1. (L-Lipschitz Continuous Gradient) There exists a constant L > 0, such that ‖∇fi(x)−∇fi(y)‖ ≤ L‖x− y‖, ∀x,y ∈ Rd, and i ∈ [M ]. Assumption 2. (Unbiased Local Stochastic Gradient) Let ξi be a random local data sample at worker i. The local stochastic gradient is unbiased, i.e., E[∇fi(x, ξi)] = ∇fi(x), ∀i ∈ [m], where the expectation is taken over the local data distribution Di.
Assumption 3. (Bounded Local and Global Variances) There exist two constants σL ≥ 0 and σG ≥ 0, such that the variance of each local stochastic gradient estimator is bounded by E[‖∇fi(x, ξi) − ∇fi(x)‖2] ≤ σ2L, ∀i ∈ [M ], and the global variability of the local gradient of the cost function is bounded by ‖∇fi(x)−∇f(x)‖2 ≤ σ2G, ∀i ∈ [M ],∀k.
The first two assumptions are standard in the convergence analysis of non-convex optimization (see, e.g., (Ghadimi & Lan, 2013; Bottou et al., 2018)). For Assumption 3, the bounded local variance is also a standard assumption. We utilize a universal bound σG to quantify the data heterogeneity among different workers. This assumption is also frequently used in the literature of FL with noni.i.d. datasets (Reddi et al., 2020; Wang et al., 2019; Yang et al., 2021) as well as in decentralized optimization (Kairouz et al., 2019).
To establish a fundamental convergence error lower bound, we consider the most general case where no assumption on the arrival processes of the worker information is made, except that each worker’s participation in FL is independent of each other. In such general worker information arrival processes, we prove the following fundamental lower bound of convergence error by constructing a worst-case scenario (see Appendix B.1 for proof details): Theorem 1 (Convergence Error Lower Bound for General Worker Information Arrival Processes). For any level of heterogeneity characterized by σG, there exists loss functions and worker participation process satisfying Assumptions 1- 3 for which the output x̂ of any randomized FL algorithm satisfies:
E‖∇f(x̂)‖2 = Ω(σ2G), (1) Remark 1. The lower bound in Theorem 1 indicates that no algorithms for AFL could converge to a stationary point under general worker information arrival processes, due to the significant system heterogeneity and randomness caused by such general worker information arrivals. The possible system heterogeneity coupled with non-i.i.d. data result in objective value drifts, which further lead to an inevitable error in convergence. We note that our lower bound also holds for non-i.i.d. FL including synchronous FedAvg and its variants, thus also providing insights for conventional FL. To ensure convergence to a stationary point, extra assumptions for the worker information arrivals have to be made, e.g., uniformly distributed arrivals (see Theorem 3) and bounded delays (see Theorem 4).

heading: 4 THE ANARCHIC FEDERATED AVERAGING (AFA) ALGORITHMS
text: Upon obtaining a fundamental understanding of the training algorithm performance limit from the convergence error in Theorem 1, we are now in a position to develop AFL algorithms that are guided by our fundamental lower bound. Toward this end, in this section, we will develop two anarchic federated averaging (AFA) algorithms for the cross-device (CD) and cross-silo (CS) settings in Section 4.1 and 4.2, respectively.

heading: 4.1 THE AFA-CD ALGORITHM FOR CROSS-DEVICE AFL
text: 1) The AFA-CD Algorithm: First, we propose the AFA-CD algorithm for the cross-device AFL setting. As mentioned earlier, cross-device AFL is suitable for cases with a massive number of edge devices. In each round of global model update, only a small subset of workers are used in the training. The server is assumed to have no historical information of the workers. As shown in Algorithm 2, AFA-CD closely follows the AFL architecture shown in Algorithm 1. Here, we use standard stochastic gradient descent (SGD) as the server- and worker-side optimizer. In each update t, t = 1, . . . , T , the server waits until collecting m local updates {Gi(xt−τt,i)} from workers to form a setMt with |Mt| = m, where τt,i represents the random delay of the local update of worker i, i ∈Mt (Server Code, Line 1). OnceMt is formed, the server aggregates all local updates Gi(xt−τt,i), i ∈Mt and updates global model (Server Code, Line 2). We count each global model update as one communication round. Meanwhile, for each worker, it pulls the current global model parameters with time stamp µ once it decides to participate in training (Worker Code, Line 1). Each worker can then choose a desired number of local update steps Kt,i (could be time-varying and device-dependent) to perform SGD updates for Kt,i times, and then return the rescaled sum of all stochastic gradients with timestamp µ to the server (Worker Code, Lines 2–3).
2) Convergence Analysis of the AFA-CD Algorithm: We first conduct the convergence of AFA-CD under general worker information arrival processes. We let K be the maximum local update steps, which is defined as K := maxt∈[T ],i∈[M ]{Kt,i}. We let τ be the maximum delay of workers’ returned information, which is defined as τ := maxt∈[T ],i∈Mt{τt,i}. Also, we use f0 = f(x0) and f∗ to denote the initial and the optimal objective values, respectively. Then, we have the following convergence result for the AFA-CD algorithm (see proof details in Appendix B.2): Theorem 2 (AFA-CD with General Worker Information Arrival Processes). Under Assumptions 1- 3, choose server-side and worker-side learning rates η and ηL such that the following relationships hold: 180η2LK
2L2τ < 1 and 2LηηL + 3τ2L2η2η2L ≤ 1. Then, the output sequence {xt} generated by AFedAvg-TSLR-CD with general worker information arrival processes satisfies:
1
T T−1∑ t=0 E‖∇f(xt)‖2 ≤ 4(f0 − f∗) ηηLT + 4 ( αLσ 2 L + αGσ 2 G ) , (2)
Algorithm 2 The AFA-CD Algorithm for Cross-Device AFL. At the Server (Concurrently with Workers):
1. In the t−th update round, collect m local updates {Gi(xt−τt,i), i ∈Mt} returned from the workers to form the setMt, where τt,i represents the random delay of the worker i’s local update, i ∈Mt.
2. Aggregate and update: Gt = 1m ∑ i∈Mt Gi(xt−τt,i), xt+1 = xt − ηGt.
At Each Worker (Concurrently with Server): 1. Once decided to participate in the training, retrieve the parameter xµ from the server and
its timestamp, set the local model: xiµ,0 = xµ. 2. Choose a number of local steps Kt,i, which can be time-varying and device-dependent.
Let xiµ,k+1 = x i µ,k − ηLgik, where gik = ∇fi(xiµ,k, ξik), k = 0, . . . ,Kt,i − 1. 3. Sum and rescale the stochastic gradients: Gi(xµ) = 1Kt,i ∑Kt,i−1 j=0 g i j . Return Gi(xµ).
where αL , [ 2ηηL m + 3τ2L2η2η2L 2m + 15η2LKL 2 2 ] and αG , [ 3 2 + 45K 2L2η2L ] .
With Theorem 2, we immediately have the following convergence rate result for AFA-CD, which implies the highly desirable “linear speedup effect” can be achieved by AFA-CD. Corollary 1 (Linear Speedup to Error Ball). By setting ηL = 1√T , and η = √ m, the convergence rate of AFA-CD with general worker information arrival processes is:
1
T T−1∑ t=0 E‖∇f(xt)‖2 = O (
1
m1/2T 1/2
) +O ( τ2
T
) +O ( K2
T
) +O(σ2G).
Remark 2. First, we note that the non-vanishing error term O(σ2G) in Corollary 1 matches the lower bound in Theorem 1. This implies that the convergence error of AFL-CD is order-optimal. Recall that this non-vanishing convergence error is a direct consequence of objective function drift under the general worker information arrivals (no assumption on the arrivals of the worker participation in each round of update), which is independent of the choices of learning rates, the number of local update steps, and the number of global update rounds (more discussion in the supplementary material). Also, for a sufficiently large T , the dominant term O( 1
m1/2T 1/2 ) implies that AFA-CD achieves the linear
speedup effect before reaching a constant error neighborhood with size O(σ2G). Remark 3. The conditions for the learning rates η and ηL are a natural extension of SGD. When τ = 0 (synchronous setting) and K = 1 (single local update), the condition becomes ηηL ≤ 12L , which recovers the same learning rate condition for SGD in (Ghadimi & Lan, 2013). Also, the suggested worker-side learning rate ηL is independent of local update steps. This is different from previous work that ηL depends heavily on local update steps (Wang et al., 2020; Yang et al., 2021), thus making it more practical for implementation.
Given the weak convergence result implied by the lower bound in Theorem 1 under general workers’ information arrivals, it is important to understand what extra assumptions on the worker information arrivals are needed in order to guarantee convergence. Toward this end, we consider a special case where the arrivals of worker returned information in each round for global update is uniformly distributed among the workers. In this setting,Mt can be viewed as a subset with size m independently and uniformly sampled from [M ] without replacement. For FL systems with a massive number of workers, this assumption of uniformly distributed arrivals is a good approximation for worker participation in cross-device FL (McMahan et al., 2016; Li et al., 2019a). Also, one can map this setting into the conventional cross-device FL systems with uniform worker sampling in partial worker participation, which is a widely-used assumption (McMahan et al., 2016; Li et al., 2019c; 2018; Yang et al., 2021; Wang et al., 2020). For this special case, the convergence performance of AFA-CD can be improved as follows (see proof details in Appendix B.3):
Theorem 3. Under Assumptions 1- 3, choose server-side and worker-side learning rates η and ηL such that the following relationships hold: η2L[6(2K
2−3K+ 1)L2] ≤ 1, 120L2K2η2Lτ + 4(LηηL+ L2η2η2Lτ 2) M−mm(M−1) (90K 2L2η2Lτ + 3τ) < 1. Then, the output sequence {xt} generated by AFA-CD
Algorithm 3 The AFA-CS Algorithm for Cross-Silo AFL. At the Server (Concurrently with Workers):
1. In the t−th update round, collect m local updates {Gi(xt−τti )} from the workers to form the setMt. 2. Update worker i’s information in the memory using the returned local update Gi. 3. Aggregate and update: Gt = 1M ∑ i∈[M ] Gi, xt+1 = xt − ηGt.
At Each Worker (Concurrently with Server): Same as AFA-CD Worker Code.
with uniformly distributed worker information arrivals satisfies:
1
T T−1∑ t=0 E‖∇f(xt)‖22 ≤ 4(f0 − f∗) ηηLT + 4 ( αLσ 2 L + αGσ 2 G ) , (3)
where αL and αG are constants that are defined as:
αL , [( LηηL m + τ2L2η2η2L m + 5KL2η2L ) + (LηηL + L 2η2η2Lτ 2) M −m m(M − 1) (15KL2η2L) ] ,
αG , [ 30K2L2η2L + (LηηL + L 2η2η2Lτ 2)
M −m m(M − 1) (90K2L2η2L + 3)
] .
Furthermore, by choosing the server- and worker-side learning rates appropriately, we immediately have the following linear speedup convergence result for AFA-CD: Corollary 2 (Linear Speedup to Stationary Point). By setting ηL = 1√T and η = √ m, the convergence rate of AFA-CD with uniformly distributed worker information arrivals is:
1
T T−1∑ t=0 E‖∇f(xt)‖22 = O( 1 m1/2T 1/2 ) +O ( τ2 T ) +O ( K2 T ) +O ( K2 m1/2T 3/2 ) +O ( K2τ2 T 2 ) .
Remark 4. For a sufficiently large T , the linear speedup effect to a stationary point (rather than a constant error neighborhood) can be achieved with any finitely bounded maximum local update steps K and maximum delay τ , i.e., O( 1√
mT ). Note this rate does not depend on the delay τ and
local computation steps K after sufficiently many rounds T , the negative effect of using outdated information in such asynchronous setting vanishes asymptotically. Further, for σG = 0 (i.i.d. data) and K = 1 (single local update step), our AFA-CD algorithm is exactly the same as the AsySG-con algorithm (Lian et al., 2018) in asynchronous parallel distributed optimization. It can be readily verified that AFA-CD achieves the same rate as that of the AsySG-con algorithm. When τ = 0 (synchronous setting) and Kt,i = K (same number of local update steps across workers), AFA-CD becomes the generalized synchronous FedAvg algorithm with two-sided learning rates (Yang et al., 2021; Karimireddy et al., 2020b; Reddi et al., 2020). Remarkably, the result of AFA-CD shows that we can achieve a faster convergence rate than O( √ K/ √ mT ) in (Yang et al., 2021) and the same rate as FedAvg analysis in (Karimireddy et al., 2020b).

heading: 4.2 THE AFA-CS ALGORITHM FOR CROSS-SILO FL
text: 1) The AFA-CS Algorithm: As mentioned earlier, cross-silo FL is suitable for collaborative learning among a relatively small number of (organizational) workers. Thanks to the relatively small number of workers, each worker’s feedback can be stored at the server. As a result, the server could reuse the historical information of each specific worker in each round of global update.
As shown in Algorithm 3, the AFA-CS algorithm also closely follows the AFL architecture as shown in Algorithm 1. In each round of global model update, a subset of workers could participate in the training (Server Code, Line 1). Compared to AFA-CD, the key difference in AFA-CS is in Line 2 of the Server Code, where the server stores the collected local updates {Gi} for each worker i ∈Mt into the memory space at the server (Server Code, Line 2). As a result, whenever a worker i returns a local update to the server upon finishing its local update steps, the server will update the memory space corresponding to worker i to replace the old information with this newly received update from
worker i. Similar to AFA-CD, every m new updates in the AFA-CS algorithm trigger the server to aggregate all the Gi, i ∈ [M ] (newly received information if i ∈ Mt or stored information if i /∈Mt) and update the global model. The Worker Code in AFA-CS is exactly the same as AFA-CD and its description is omitted for brevity.
2) Convergence Analysis of the AFA-CS Algorithm: For cross-silo AFL, our AFA-CS algorithm achieves the following convergence performance (see proof details in Appendix C): Theorem 4. Under Assumptions 1- 3, choose sever- and worker-side learning rates η and ηL in such a way that there exists a non-negative constant series {βµ}τ−1u=0 satisfying the following relationship:
12LηηL + 540(M −m′)2
M2 (1 + LηηL)K
2L2η2L(1 + τ) + 180K 2L2η2L + 320L 3K2ηη3L<1, (4)
ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) 3τL2 + (βu+1 − βu) ≤ 0, (5)
ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) 3τL2 − βτ−1 ≤ 0, (6)
3
2M σ2L ≤ (
1 2 − β0ηηL)E‖Gt‖22, (7)
the output sequence {xt} generated by the AFA-CS algorithm for general worker information arrival processes with bounded delay (τ := maxt∈[T ],i∈[M ]{τt,i}) satisfies:
1
T T−1∑ t=0 E‖∇f(xt)‖22 ≤ 4(V (x0)− V (x∗)) ηηLT + 4 ( αLσ 2 L + αGσ 2 G ) , (8)
where αL and αG are constants defined as follows:
αL , [ 3LηηL
2M + 5KL2η2L(
9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL))],
αG , ( 9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL))(30K 2L2η2L),
and V (·) is defined as V (xt) , f(xt) + ∑τ−1 u=0 βu‖xt−u − xt−u−1‖2, m′ is the number of updates in the memory space with no time delay (τt,i = 0). Remark 5. To see how stringent the conditions for learning rates in Theorem 4 are, note that Eq. (4) implies that O(ηηL + ηη3LK2 + τK2η2L + τK2ηη3L) < 1. With a sufficiently small learning rate ηL for given bounded time delay τ and maximum local steps K, Eq. (4) can be satisfied. Eqs. (5)–(6) imply that {βµ}τ−1u=0 is a non-negative decreasing series with difference O(ηηLτ + η2η2Lτ). As a result, β0 = Ω(ηηLτ2 + η2η2Lτ
2). Plugging it into Eq. (7) yields that the update term Gt should be larger than the variance term σ2L/M , which can be satisfied if the number of workers M is sufficiently large or σ2L is sufficiently small (i.e., workers use a sufficiently large batch size).
By choosing appropriate learning rates, we immediately have stronger linear speedup convergence: Corollary 3 (Linear Speedup). By setting ηL = 1√T , and η = √ M , the convergence rate of the AFA-CS algorithm for general worker information arrival processes with bounded delay is:
1
T T−1∑ t=0 E‖∇f(xt)‖22 = O (
1
M1/2T 1/2
) +O ( K2
T
) +O ( K2M1/2
T 3/2
) .
Remark 6. Compared to Corollary 1, we can see that, by reusing historical data, the AFA-CS algorithm can eliminate the non-vanishing O(σ2G) error term even for general worker information arrival processes with bounded delay. The bounded delay implicitly requires each workers at least participate in the training process, eliminating the worse-case scenario shown in Theorem 1. On the other hand, although the server only collects m workers’ feedback in each round of global model update, the server leverages all M workers’ feedback by reusing historical information. Intuitively, this translates the potential objection function drift originated from general worker information arrival process into the negative effect of delayed returns G(xt−τt,i) from workers. It can be shown that such a negative effect of delayed returns vanishes asymptotically as the number of communication rounds T gets large and in turn diminishes the convergence error.
Remark 7. AFA-CS achieves a stronger linear speedup O(1/ √ MT ), which is new in the FL literature to our knowledge. Specifically, even though partial (m) workers participation is used in each round, AFA-CS is able to achieve a surprising speedup with respect to total number of workers M (M > m). Also, AFA-CS generalizes the lazy aggregation strategy in distributed learning (e.g., LAG (Chen et al., 2018)) by setting K = 1 (single local update), τ = 0 (synchronous setting) and σL = 0 (using full gradient descents instead of stochastic gradients) and further improve the rate of LSAG (Chen et al., 2020) from O(1/ √ T ) to O(1/ √ MT ).

heading: 5 NUMERICAL RESULTS
text: In this section, we conduct experiments to verify our theoretical results. We use i) logistic regression (LR) on manually partitioned non-i.i.d. MNIST dataset (LeCun et al., 1998), ii) convolutional neural network (CNN) for manually partitioned CIFAR-10 (Krizhevsky, 2009), and iii) recurrent neural network (RNN) on natural non-i.i.d. dataset Shakespeare (McMahan et al., 2016). In order to impose data heterogeneity in MNIST and CIFAR-10 data, we distribute the data evenly into each worker in label-based partition following the same process in the literature (e.g., McMahan et al. (2016); Yang et al. (2021); Li et al. (2019c)). Therefore, we can use a parameter p to represent the classes of labels in each worker’s dataset, which signifies data heterogeneity: the smaller the p-value, the more heterogeneous the data across workers (cf. Yang et al. (2021); Li et al. (2019c) for details). Due to space limitation, we relegate the details of models, datasets and hyper-parameters, and further results of CNN and RNN to the appendix.
In Figure 1, we illustrate the test accuracy for LR on MNIST with different p-values. We use the classical FedAvg algorithm (McMahan et al., 2016) for conventional FL with uniform worker sampling as a baseline, since it corresponds to the most ideal scenario where workers are fully cooperative with the server. We examine the learning performance degradation of AFA algorithms (due to anarchic worker behaviors) compared to this ideal baseline. For our AFA-CD and AFA-CS with general worker information arrival processes, the test accuracy is comparable to or nearly the same as that of FedAvg. This confirms our theoretical results and validates the effectiveness of our AFA algorithms. We further evaluate the impacts of various factors in AFL, including asynchrony, heterogeneous computing, worker’s arrival process, and non-i.i.d. datasets, on convergence rate of our proposed AFA algorithms. Note that AFL subsumes FedAvg and many variants when the above hyper-parameters are set as constant. Also, AFL coupled with other FL algorithms such as FedProx (Li et al., 2018) and SCAFFOLD (Karimireddy et al., 2020b) is tested. Our results show that the AFA algorithms are robust against all asynchrony and heterogeneity factors in AFL. Due to space limitation, we refer readers to the appendix for all these experimental results.

heading: 6 CONCLUSIONS
text: In this paper, we propose a new paradigm in FL called “Anarchic Federated Learning” (AFL). In stark contrast to conventional FL models where the server and the worker are tightly coupled, AFL has a much lower sever-worker coordination complexity, allowing a flexible worker participation. We propose two Anarchic Federated Averaging algorithms with two-sided learning rates for both cross-device and cross-silo settings, which are named AFA-CD and AFA-CS, respectively. We show that both algorithms retain the highly desirable linear speedup effect in the new AFL paradigm. Moreover, we show that our AFL framework works well numerically by employing advance FL algorithms FedProx and SCAFFOLD as the optimizer in worker’s side.

heading: Appendix
text: In this supplementary material, we provide the detailed proofs for all theoretical results in this paper. Before presenting the proofs, we introduce some notations that will be used subsequently.. We assume there exists M workers in total in the FL systems. In each communication round, we assume a subsetMt of workers to be used, with |Mt| = m. We use Gi(xt) to represent the local update returned from worker i, i ∈ [M ] given global model parameter x0t = xt. Also, we define Gi(xt) , 1Kt,i ∑Kt,i−1 j=0 ∇fi(x j t , ξt,i), where x j t represents the trajectory of the local model in the worker. We use ∆i to denote the average of the full gradients long the trajectory of local updates, i.e., ∆i(xt) =
1 Kt,i ∑Kt,i−1 j=0 ∇fi(x j t ). With the above notations, we are now in a position to present the
proofs of the theoretical results in this paper.

heading: A PROOFS OF LEMMA 1 AND LEMMA 2
text: We start with proving two results stated in the following two lemmas, which will be useful in the rest of the proofs.
Lemma 1. E[Gi(xt)] = ∆i(xt), E[‖Gi(xt)−∆i(xt)‖2] ≤ σ2L,∀i ∈ [M ].
Proof. Taking the expectation of Gi(xt), we have:
E [ Gi(xt) ] = E
[ 1
Kt,i Kt,i−1∑ j=0 ∇fi(xjt , ξt,i) ]
= 1
Kt,i Kt,i−1∑ j=0 E∇fi(xjt , ξt,i)
= ∆i(xt).
Also, by computing the mean square error between Gi(xt) and ∆i(xt), we have:
E[‖Gi(xt)−∆i(xt)‖2] = E [ ‖ 1 Kt,i Kt,i−1∑ j=0 ∇fi(xjt , ξt,i)− Kt,i−1∑ j=0 ∇fi(xjt )‖2 ]
= 1 K2t,i E [ ‖ Kt,i−1∑ j=0 ∇fi(xjt , ξt,i)− Kt,i−1∑ j=0 ∇fi(xjt )‖2 ]
≤ 1 Kt,i Kt,i−1∑ j=0 E [ ‖∇fi(xjt , ξt,i)− Kt,i−1∑ j=0 ∇fi(xjt )‖2 ]
≤ σ2L.
This completes the proof of Lemma 1. Lemma 2. For a fixed set Mt with cardinality m, E [∥∥∑ i∈Mt Gi(xt−τt,i) ∥∥2] ≤∥∥∑
i∈Mt ∆i(xt−τt,i) ∥∥2 +mσ2L.
Proof. By the definition of variance (E[(X − E[X])2] = E[X2]− [E[X]]2), we have: E [∥∥ ∑
i∈Mt
Gi(xt−τt,i) ∥∥2] = E[∥∥ ∑
i∈Mt
Gi(xt−τt,i)−∆i(xt−τt,i) ∥∥2]+ ∥∥ ∑
i∈Mt
∆i(xt−τt,i) ∥∥2
≤ mσ2L + ∥∥ ∑ i∈Mt ∆i(xt−τt,i) ∥∥2.
Here {Gi(xt−τt,i)−∆i(xt−τt,i)} forms a martingale difference sequence.

heading: B PROOF OF THE PERFORMANCE OF THE AFA-CD ALGORITHM
text: In this section, we provide the proofs of the theoretical results of the AFA-CD algorithm. We consider two cases: i) general worker information arrival processes and ii) uniformly distributed worker information arrivals. As mentioned earlier, for general worker information arrival processes, we do not make any assumptions on the worker information arrival processes except the independence of workers’ participation. For uniformly distributed worker information arrivals,Mt can be viewed as a subset with size m independently and uniformly sampled from [M ] without replacement. The similar convergence analysis for independently and uniformly sampling with replacement can be derived in the same way following the techniques in (Yang et al., 2021; Li et al., 2019c).

heading: B.1 LOWER BOUND FOR GENERAL WORKER INFORMATION ARRIVAL PROCESSES
text: Theorem 1 (Convergence Error Lower Bound for General Worker Information Arrival Processes). For any level of heterogeneity characterized by σG, there exists loss functions and worker participation process satisfying Assumptions 1- 3 for which the output x̂ of any randomized FL algorithm satisfies:
E‖∇f(x̂)‖2 = Ω(σ2G), (1)
Proof. We prove the lower bound by considering a worst-case scenario for simple one-dimensional functions. Let the FL system has two workers with the following loss functions: f1(x) = (x + G)2, f2(x) = (x−G)2, f(x) = 12 (f1(x) + f2(x)) = x
2 +G2. It is easy to verify that ‖∇f1(x)− ∇f(x)‖2 ≤ 4G2 = σ2G and ‖∇f2(x) − ∇f(x)‖2 ≤ 4G2 = σ2G. We consider a special case for the general arrival process when only the first one worker participates in the training, equivalent to optimizing f1(x) rather than f(x). In such case, any decent algorithm would return x̂ = −G+ , where is a small error term. As a result, E‖∇f(x̂)‖2 = Ω(σ2G).

heading: B.2 GENERAL WORKER INFORMATION ARRIVAL PROCESSES
text: Theorem 2 (AFA-CD with General Worker Information Arrival Processes). Under Assumptions 1- 3, choose server-side and worker-side learning rates η and ηL such that the following relationships hold: 180η2LK
2L2τ < 1 and 2LηηL + 3τ2L2η2η2L ≤ 1. Then, the output sequence {xt} generated by AFedAvg-TSLR-CD with general worker information arrival processes satisfies:
1
T T−1∑ t=0 E‖∇f(xt)‖2 ≤ 4(f0 − f∗) ηηLT + 4 ( αLσ 2 L + αGσ 2 G ) , (2)
where αL , [ 2ηηL m + 3τ2L2η2η2L 2m + 15η2LKL 2 2 ] and αG , [ 3 2 + 45K 2L2η2L ] .
Proof. Due to the L-smoothness assumption, taking expectation of f(xt+1) over the randomness in communication round t, we have:
E[f(xt+1)] ≤ f(xt) + 〈 ∇f(xt),E[xt+1 − xt] 〉︸ ︷︷ ︸ A1 + L 2 E[‖xt+1 − xt‖2︸ ︷︷ ︸ A2 .
First, we bound the term A2 as follows:
A2 = E‖xt+1 − xt‖2
= η2η2LE‖ 1
m m∑ i=1 Gi(xt−τt,i)‖2
(a1) ≤ η 2η2L m2 ‖ m∑ i=1 ∆i(xt−τt,i)‖2 + η2η2L m σ2L,
where (a1) is due to Lemma 2. Next, we bound the term A1 as follows: A1 = 〈 ∇f(xt),E[xt+1 − xt] 〉
= −ηηL 〈 ∇f(xt),E 1
m m∑ i=1 Gi(xt−τt,i) 〉
(a2) = −1
2 ηηL‖∇f(xt)‖2 −
1 2 ηηL‖ 1 m m∑ i=1 ∆i(xt−τt,i)‖2 + 1 2 ηηL ‖∇f(xt)− 1 m m∑ i=1
∆i(xt−τt,i)‖2︸ ︷︷ ︸ A3 ,
where (a2) is due to Lemma 1 and the fact that 〈x,y〉 = 12 (‖x‖ 2 + ‖y‖2 − ‖x− y‖2). To further bound the term A3, we have:
A3 = ‖∇f(xt)− 1
m m∑ i=1 ∆i(xt−τt,i)‖2
≤ 1 m m∑ i=1 ‖∇f(xt)−∆i(xt−τt,i)‖2
= 1
m m∑ i=1 ‖∇f(xt)−∇f(xt−τt,i) +∇f(xt−τt,i)−∇fi(xt−τt,i) +∇fi(xt−τt,i)−∆i(xt−τt,i)‖2
(a3)
≤ 1 m m∑ i=1 [ 3‖∇f(xt)−∇f(xt−τt,i)‖2 + 3‖∇f(xt−τt,i)−∇fi(xt−τt,i)‖2
+ 3‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2 ]
(a4) ≤ 3L 2
m m∑ i=1
‖xt − xt−τt,i‖2︸ ︷︷ ︸ A4
+3σ2G + 3
m m∑ i=1
‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2︸ ︷︷ ︸ A5 ,
where (a3) followings from the inequality ‖x1 + x2 + · · · + xn‖2 ≤ n ∑n i=1 ‖xi‖2, and (a4) is due to the L-smoothness assumption (Assumption 1) and bounded global variance assumption (Assumption 3).
To further bound the term A4, we have:
A4 = 1
m ∑ i∈[m] ‖xt − xt−τt,i‖2
(a5)
≤ ‖xt − xt−τt,u‖2
= ‖ t−1∑
k=t−τt,u
xk+1 − xk‖2
= E‖ t−1∑
k=t−τt,u
1 m ηηL ∑ i∈Mk Gi(xk−τk,i)‖2
= E [ η2η2L m2 ‖ t−1∑ k=t−τt,u ∑ i∈Mk Gi(xk−τk,i)‖2 ]
(a6) ≤ E [ η2η2L m2 τ t−1∑ k=t−τt,u ‖ ∑ i∈Mk Gi(xk−τk,i)‖2 ]
(a7) ≤ E [ η2η2Lτ
m2 [( t−1∑ k=t−τt,u ‖ ∑ i∈Mk ∆i(xk−τk,i)‖2) + τmσ2L] ] .
In the derivations above, we let u := argmaxi∈[M ] ‖xt − xt−τt,i‖2, which yields (a5). Note also that the maximum delay assumption τ ≥ τk,i,∀i ∈ [M ] implies (a6). Lastly, (a7) follows from Lemma 2.
To further bound the term A5, we have:
A5 = ‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2
= ‖∇fi(xt−τt,i)− 1
Kt,i Kt,i−1∑ j=0 ∇fi(xjt−τt,i)‖ 2
= 1
Kt,i Kt,i−1∑ j=0 ‖∇fi(xt−τt,i)−∇fi(x j t−τt,i)‖ 2
(a8) ≤ L 2
Kt,i Kt,i−1∑ j=0 ‖xt−τt,i − x j t−τt,i‖
2︸ ︷︷ ︸ A6
(a9)
≤ 5Kt,iL2η2L(σ2L + 6Kt,iσ2G) + 30K2t,iL2η2L‖∇f(xt−τt,i)‖2
(a10)
≤ 5KL2η2L(σ2L + 6Kσ2G) + 30K2L2η2L‖∇f(xt−τt,i)‖2,
where (a8) is due to the L-smoothness assumption (Assumption 1), and (a9) follows from the bound of A6 shown below. Here, we denote maximum number of local steps of all workers as K, i.e., Kt,i ≤ K,∀t, i. This definition of K implies (a10). Now, it remains to bound term A6 in the derivations above. Note that the bounding proof of A6 in what follows is the same as Lemma 4 in (Reddi et al., 2020). we restate the proof here in order for this paper to be self-contained. For any worker i in the k-th local step, we have the following results for the norm of parameter changes for one local computation:
A6 = E[‖xit,k − xt‖2] = E[‖xit,k−1 − xt − ηLgit,k−1‖2] ≤ E[‖xit,k−1 − xt − ηL(git,k−1 −∇fi(xit,k−1) +∇fi(xit,k−1)−∇fi(xt)
+∇fi(xt)−∇f(xt) +∇f(xt))‖2]
≤ (1 + 1 2K − 1 )E[‖xit,k−1 − xt‖2] + E[‖ηL(git,k−1 −∇fi(xit,k−1))‖2]
+ 6KE[‖ηL(∇fi(xit,k−1)−∇fi(xt))‖2] + 6KE[‖ηL(∇fi(xt)−∇f(xt)))‖2] + 6K‖ηL∇f(xt))‖2
≤ (1 + 1 2K − 1 )E[‖xit,k−1 − xt‖2] + η2Lσ2L + 6Kη2LL2E[‖xit,k−1 − xt‖2]
+ 6Kη2Lσ 2 G + 6K‖ηL∇f(xt))‖2
= (1 + 1
2K − 1 + 6Kη2LL 2)E[‖xit,k−1 − xt‖2] + η2Lσ2L + 6Kη2Lσ2G + 6K‖ηL∇f(xt))‖2
(a11)
≤ (1 + 1 K − 1 )E[‖xit,k−1 − xt‖2] + η2Lσ2L + 6Kη2Lσ2G + 6K‖ηL∇f(xt))‖2,
where (a11) follows from the fact that 12K−1 + 6Kη 2 LL 2 ≤ 1K−1 if η 2 L ≤ 16(2K2−3K+1)L2 .
Unrolling the recursion, we obtain:
E[‖xit,k − xt‖2] ≤ k−1∑ p=0 (1 + 1 K − 1 )p[η2Lσ 2 L + 6Kσ 2 G + 6Kη 2 L‖ηL∇f(xt))‖2]
≤ (K − 1)[(1 + 1 K − 1 )K − 1][η2Lσ2L + 6Kη2Lσ2G + 6K‖ηL∇f(xt))‖2]
≤ 5Kη2L(σ2L + 6Kσ2G) + 30K2η2L‖∇f(xt)‖2. (9)
With the above results of the terms A1 through A5, we have: E[f(xt+1)]− f(xt) ≤ 〈 ∇f(xt),E[xt+1 − xt] 〉︸ ︷︷ ︸ A1 + L 2 E[‖xt+1 − xt‖2︸ ︷︷ ︸ A2
= −1 2 ηηL‖∇f(xt)‖2 − 1 2 ηηL‖ 1 m m∑ i=1 ∆i(xt−τt,i)‖2 + 1 2 ηηL ‖∇f(xt)− 1 m m∑ i=1
∆i(xt−τt,i)‖2︸ ︷︷ ︸ A3
+ Lη2η2L m2 ‖ m∑ i=1 ∆i(xt−τt,i)‖2 + Lη2η2L m σ2L
≤ −1 2 ηηL‖∇f(xt)‖2 − 1 2 ηηL‖ 1 m m∑ i=1 ∆i(xt−τt,i)‖2 + Lη2η2L m2 ‖ m∑ i=1 ∆i(xt−τt,i)‖2 + Lη2η2L m σ2L
+ 3
2 ηηLσ
2 G +
3L2
2 ηηL
[ 1
m m∑ i=1
‖xt − xt−τt,i‖2︸ ︷︷ ︸ A4
] +
3ηηL 2m m∑ i=1
‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2︸ ︷︷ ︸ A5
≤ −1 2 ηηL‖∇f(xt)‖2 − 1 2 ηηL‖ 1 m m∑ i=1 ∆i(xt−τt,i)‖2 + Lη2η2L m2 ‖ m∑ i=1 ∆i(xt−τt,i)‖2 + Lη2η2L m σ2L
+ 3
2 ηηLσ
2 G +
3L2
2 ηηL
[ η2η2Lτ
m2 ( t−1∑ k=t−τt,u ‖ m∑ i=1 ∆i(xk−τk,i)‖2 + τmσ2L) ]
+ 3ηηL
2 [5KL2η2L(σ 2 L + 6Kσ 2 G) + 30K
2L2η2L 1
m m∑ i=1 ‖∇f(xt−τt,i)‖2]
≤ −1 2 ηηL‖∇f(xt)‖2 + 45ηη3LK2L2 1 m m∑ i=1 ‖∇f(xt−τt,i)‖2
+ [ − ηηL
2m2 + Lη2η2L m2 ] ‖ m∑ i=1 ∆i(xt−τt,i)‖2 + 3τη3η3L 2m2 t−1∑ k=t−τt,u ‖ m∑ i=1 ∆i(xk−τk,i)‖2
+ [ Lη2η2L m + 3τ2L2η3η3L 2m + 15ηη3LKL 2 2 ] σ2L + [ 3 2 ηηL + 45K 2L2ηη3L ] σ2G.
Summing the above inequality from t = 0 to t = T − 1 yields: Ef(xT )− f(x0)
≤ T−1∑ t=0 [ − 1 2 ηηL‖∇f(xt)‖2 + 45ηη3LK2L2 1 m m∑ i=1 ‖∇f(xt−τt,i)‖2 ]
+ T−1∑ t=0 [ [− ηηL 2m2 + Lη2η2L m2 ]‖ m∑ i=1 ∆i(xt−τt,i)‖2 + 3τL2η3η3L 2m2 t−1∑ k=t−τt,u ‖ m∑ i=1 ∆i(xk−τk,i)‖2 ]
+ T [ Lη2η2L m + 3τ2L2η3η3L 2m + 15ηη3LKL 2 2 ] σ2L + T [ 3 2 ηηL + 45K 2L2ηη3L ] σ2G
(a12) ≤ T−1∑ t=0 [ − 1 2 ηηL + 45ηη 3 LK 2L2τ ] ‖∇f(xt)‖2
+ T−1∑ t=0 [ − ηηL 2m2 + Lη2η2L m2 + 3τ2L2η3η3L 2m2 ] ‖ m∑ i=1 ∆i(xt−τt,i)‖2
+ T [ Lη2η2L m + 3τ2L2η3η3L 2m + 15ηη3LKL 2 2 ] σ2L + T [ 3 2 ηηL + 45K 2L2ηη3L ] σ2G
(a13) ≤ T−1∑ t=0 −1 4 ηηL‖∇f(xt)‖2
+ TηηL [ LηηL m + 3τ2L2η2η2L 2m + 15η2LKL 2 2 ] σ2L + TηηL [ 3 2 + 45K2L2η2L ] σ2G
(a14) = T−1∑ t=0 −1 4 ηηL‖∇f(xt)‖2 + TηηL [ αLσ 2 L + αGσ 2 G ] ,
where (a12) is due to maximum time delay τ in the system, (a13) holds if 14 ≤ [ 1 2 − 45η 2 LK 2L2τ ],
i.e., 180η2LK 2L2τ < 1, and [ − ηηL2m2 + Lη2η2L m2 + 3L2τ2η3η3L 2m2 ] ≤ 0, i.e., 2LηηL + 3τ2L2η2η2L ≤ 1.
Lastly, (a14) follows from the following definitions: αL = [ 2ηηL m + 3τ2L2η2η2L 2m + 15η2LKL 2 2 ] , αG =[
3 2 + 45K 2L2η2L ] . Rearranging terms, we have:
1
T T−1∑ t=0 ‖∇f(xt)‖2 ≤ 4(f0 − f∗) ηηLT + 4 [ αLσ 2 L + αGσ 2 G ] ,
and the proof is complete. Corollary 1 (Linear Speedup to Error Ball). By setting ηL = 1√T , and η = √ m, the convergence rate of AFA-CD with general worker information arrival processes is:
1
T T−1∑ t=0 E‖∇f(xt)‖2 = O (
1
m1/2T 1/2
) +O ( τ2
T
) +O ( K2
T
) +O(σ2G).
Proof. Let ηL = 1√T , and η = √ m. It then follows that:
αL = O( 1 m1/2T 1/2 ) +O(τ
2
T ) +O(K T ).
αG = O(σ2G) +O( K2
T ).
This completes the proof.

heading: B.3 UNIFORMLY DISTRIBUTED WORKER INFORMATION ARRIVALS
text: Now, we consider the special case where all workers have a statistically identical speed so that the worker information arrivals are uniformly distributed. As mentioned earlier, this special case acts as a widely-used assumption in FL and could deepen our understanding on the AFA-CD algorithm’s performance in large-scale AFL systems. Theorem 3. Under Assumptions 1- 3, choose server-side and worker-side learning rates η and ηL such that the following relationships hold: η2L[6(2K
2−3K+ 1)L2] ≤ 1, 120L2K2η2Lτ + 4(LηηL+ L2η2η2Lτ 2) M−mm(M−1) (90K 2L2η2Lτ + 3τ) < 1. Then, the output sequence {xt} generated by AFA-CD with uniformly distributed worker information arrivals satisfies:
1
T T−1∑ t=0 E‖∇f(xt)‖22 ≤ 4(f0 − f∗) ηηLT + 4 ( αLσ 2 L + αGσ 2 G ) , (3)
where αL and αG are constants that are defined as:
αL , [( LηηL m + τ2L2η2η2L m + 5KL2η2L ) + (LηηL + L 2η2η2Lτ 2) M −m m(M − 1) (15KL2η2L) ] ,
αG , [ 30K2L2η2L + (LηηL + L 2η2η2Lτ 2)
M −m m(M − 1) (90K2L2η2L + 3)
] .
Proof. The one-step update can be rewritten as: xt+1 − xt = −ηηLGt. For cross-device FL, Gt = 1 m ∑ i∈Mt Gi(xt−τt,i), where τt,i is the delay for client i in terms of the current global communication round t. When τt,i = 0,∀i ∈ Mt, it degenerates to synchronous FL with partial worker participation.
Due to the L-smoothness in Assumption 1 , taking expectation of f(xt+1) over the randomness in communication round t, we have:
E[f(xt+1)] ≤ f(xt) + 〈 ∇f(xt),E[xt+1 − xt] 〉︸ ︷︷ ︸ A1 + L 2 E[‖xt+1 − xt‖2︸ ︷︷ ︸ A2
We first bound A2 as follows:
A2 = E‖xt+1 − xt‖2
= η2η2LE‖ 1
m ∑ i∈Mt Gi(xt−τt,i)‖2
(b1) ≤ η 2η2L m2 E [ ‖ m∑ i=1 ∆i(xt−τt,i)‖2 +mσ2L ]
(b2) ≤ η 2η2L m2 E‖ M∑ i=1 I{i ∈Mt}∆i(xt−τt,i)‖2 + η2η2L m σ2L,
where (b1) is due to Lemma 2 and (b2) is due to the uniformly independent information arrival assumption.
To bound the term A1, we have: A1 = 〈 ∇f(xt),E[xt+1 − xt] 〉 =− ηηL 〈 ∇f(xt),E 1
m ∑ i∈Mt Gi(xt−τt,i) 〉
(b3) = − ηηL 〈 ∇f(xt), 1
M ∑ i∈[M ] ∆i(xt−τt,i) 〉
(b4) = − 1
2 ηηL‖∇f(xt)‖2 −
1 2 ηηL‖ 1 M ∑ i∈[M ] ∆i(xt−τt,i)‖2
+ 1
2 ηηL ∥∥∥∥∇f(xt)− 1M ∑ i∈[M ] ∆i(xt−τt,i) ∥∥∥∥2︸ ︷︷ ︸ A3 ,
where (b3) is due to the uniformly independent worker information arrival assumption and Lemma 1, (b4) is due to the fact that 〈x,y〉 = 12 (‖x‖
2 + ‖y‖2 − ‖x− y‖2). To further bound the term A3, we have:
A3 = ‖∇f(xt)− 1
M ∑ i∈[M ] ∆i(xt−τt,i)‖2
(b5) = ∥∥ 1 M ∑ i∈[M ] [∇fi(xt)−∆i(xt−τt,i)] ∥∥2
≤ 1 M ∑ i∈[M ] ∥∥∇fi(xt)−∆i(xt−τt,i)∥∥2 = 1
M ∑ i∈[M ] ∥∥∇fi(xt)−∇fi(xt−τt,i) +∇fi(xt−τt,i)−∆i(xt−τt,i)∥∥2
(b6)
≤ 1 M ∑ i∈[M ] [ 2‖∇fi(xt)−∇fi(xt−τt,i)‖2 + 2‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2 ] (b7)
≤ 2L 2
M M∑ i=1 ∥∥xt − xt−τt,i∥∥2︸ ︷︷ ︸ A4 + 2 M M∑ i=1 ∥∥∇fi(xt−τt,i)−∆i(xt−τt,i)∥∥2︸ ︷︷ ︸ A5 ,
where (b5) is due to the fact that ∇f(x) = 1M ∑ i∈[M ]∇fi(x), (b6) follows from the inequality
‖x1 + x2 + · · · + xn‖2 ≤ n ∑n i=1 ‖xi‖2, and (b7) follows from the L-smoothness assumption (Assumption 1).
For A4 and A5, we have the same bounds as in the case of general worker information arrival processes:
A4 ≤ E [ η2η2Lτ
m2 [( t−1∑ k=t−τt,µ ‖ ∑ i∈Mk ∆i(xk−τk,i)‖2) + τmσ2L] ]
≤ η 2η2Lτ
m2
[ ( t−1∑ k=t−τt,µ E‖ M∑ i=1 I{i ∈Mk}∆i(xk−τk,i) ∥∥2) + τmσ2L].
A5 ≤ 5KL2η2L(σ2L + 6Kσ2G) + 30K2L2η2L‖∇f(xt−τt,i)‖2,
With the above results of the term A1 through A5, we have: Et[f(xt+1)]− f(xt) ≤ 〈 ∇f(xt),Et[xt+1 − xt] 〉︸ ︷︷ ︸ A1 + L 2 Et[‖xt+1 − xt‖2︸ ︷︷ ︸ A2
= −1 2 ηηL‖∇f(xt)‖2 − 1 2 ηηL‖ 1 M ∑ i∈[M ] ∆i(xt−τt,i)‖2 + 1 2 ηηL ‖∇f(xt)− 1 M ∑ i∈[M ]
∆i(xt−τt,i)‖2︸ ︷︷ ︸ A3
+ Lη2η2L m2 E‖ M∑ i=1 I{i ∈Mt}∆i(xt−τt,i)‖2 + Lη2η2L m σ2L
≤ −1 2 ηηL‖∇f(xt)‖2 − 1 2 ηηL‖ 1 M ∑ i∈[M ] ∆i(xt−τt,i)‖2 + Lη2η2L m2 E‖ M∑ i=1 I{i ∈Mt}∆i(xt−τt,i)‖2
+ 1
2 ηηL
[ 2L2
M M∑ i=1
‖xt − xt−τt,i‖2︸ ︷︷ ︸ A4
+ 2
M M∑ i=1
‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2︸ ︷︷ ︸ A5
] + Lη2η2L m σ2L
≤ −1 2 ηηL‖∇f(xt)‖2 − 1 2 ηηL‖ 1 M ∑ i∈[M ] ∆i(xt−τt,i)‖2 + Lη2η2L m2 E‖ M∑ i=1 I{i ∈Mt}∆i(xt−τt,i)‖2
+ ηηLL 2
[ η2η2Lτ
m2 ( t−1∑ k=t−τt,µ E‖ M∑ i=1 I{i ∈Mk}∆i(xk−τk,i)‖2 + τmσ2L) ]
+ ηηL [ 5KL2η2L(σ 2 L + 6Kσ 2 G) + 30K 2L2η2L 1
M ∑ i∈[M ] ‖∇f(xt−τt,i)‖2 ] + Lη2η2L m σ2L
(b8) ≤ [ − 1
2 ηηL‖∇f(xt)‖2 + (30ηK2L2η3L)‖∇f(xt−τt,j )‖2 ] + [ − ηηL
2M2 ‖ M∑ i=1 ∆i(xt−τt,i)‖2 + Lη2η2L m2 E‖ M∑ i=1 I{i ∈Mt}∆i(xt−τt,i)‖2
+ L2η3η3Lτ
m2
t−1∑ k=t−τt,µ E‖ M∑ i=1 I{i ∈Mk}∆i(xk−τk,i)‖2 ]
+ σ2L [ Lη2η2L m + τ2L2η3η3L m + 5KηL2η3L ] + 30ηK2L2η3Lσ 2 G,
where (b8) follows from j := argmaxi∈[M ] ‖∇f(xt−τt,i)‖2. Note j is dependent on t but we omit it for brevity.
Summing the above inequality from t = 0 to t = T − 1 yields: Ef(xT )− f(x0)
≤ T−1∑ t=0 [ − 1 2 ηηL‖∇f(xt)‖2 + (30ηK2L2η3L)‖∇f(xt−τt,j )‖2 ]
+ T−1∑ t=0 [ − ηηL 2M2 ‖ ∑ i∈[M ] ∆i(xt−τt,i)‖2 + Lη2η2L m2 E‖ M∑ i=1 I{i ∈Mt}∆i(xt−τt,i)‖2
+ L2η3η3Lτ
m2
t−1∑ k=t−τt,µ E‖ ∑ i∈[M ] I{i ∈Mk}∆i(xk−τk,i)‖2 ]
+ T [ σ2L(
Lη2η2L m + τ2L2η3η3L m + 5KηL2η3L) + 30ηK 2L2η3Lσ 2 G ] (b9)
≤ T−1∑ t=0 [ − 1 2 ηηL‖∇f(xt)‖2 + (30ηK2L2η3Lτ)‖∇f(xt)‖2 ]
+ T−1∑ t=0 [ − ηηL 2M2 ‖ ∑ i∈[M ] ∆i(xt−τt,i)‖2 + Lη2η2L m2 E‖ ∑ i∈[M ] I{i ∈Mt}∆i(xt−τt,i)‖2
+ L2η3η3Lτ 2
m2 E‖ ∑ i∈[M ] I{i ∈Mt}∆i(xt−τt,i)‖2 ]
+ T [ σ2L(
Lη2η2L m + τ2L2η3η3L m + 5KηL2η3L) + 30ηK 2L2η3Lσ 2 G
] ,
where (b9) is due to the fact that the delay in the system is less than τ .
By letting zi = ∆i(xt−τt,i) (omitting the communication round index t for notation simplicity), we have that:
‖ M∑ i=1 zi‖2 = ∑ i∈[M ] ‖zi‖2 + ∑ i 6=j 〈zi, zj〉,
(b10) = ∑ i∈[M ] M‖zi‖2 − 1 2 ∑ i 6=j ‖zi − zj‖2,
E‖ M∑ i=1 I{i ∈Mt}zi‖2 = ∑ i∈[M ] P{i ∈Mt}‖zi‖2 + ∑ i 6=j P{i, j ∈Mt}〈zi, zj〉
(b11) =
m
M ∑ i∈[M ] ‖zi‖2 + m(m− 1) M(M − 1) ∑ i6=j 〈zi, zj〉
(b12) =
m2
M ∑ i∈[M ] ‖zi‖2 − m(m− 1) 2M(M − 1) ∑ i 6=j ‖zi − zj‖2,
where (b10) and (b12) are due to the fact that 〈 x,y 〉 = 12 [‖x‖ 2+‖y‖2−‖x−y‖2] ≤ 12 [‖x‖ 2+‖y‖2], (b11) follows from the fact that P{i ∈ Mt} = mM and P{i, j ∈ Mt} = m(m−1) M(M−1) . It then follows
that:
− ηηL 2M2 ‖ M∑ i=1 zi‖2 + Lη2η2L m2 E‖ M∑ i=1 I{i ∈Mt}zi‖2 + L2η3η3Lτ 2 m2 E‖ M∑ i=1 I{i ∈Mt}zi‖2
= [ − ηηL
2M + ( Lη2η2L M + L2η3η3Lτ 2 M ) ] M∑ i=1 ‖zi‖2
+ [ ηηL 4M2 − (Lη 2η2L m2 + L2η3η3Lτ 2 m2 ) m(m− 1) 2M(M − 1) ]∑ i 6=j ‖zi − zj‖2
≤ [ − ηηL
2M + ( Lη2η2L M + L2η3η3Lτ 2 M ) + ( ηηL 2M − (Lη 2η2L m2 + L2η3η3Lτ 2 m2 ) m(m− 1) (M − 1) ) ] M∑ i=1 ‖zi‖2
= [ ( Lη2η2L M + L2η3η3Lτ 2 M )− (Lη 2η2L m2 + L2η3η3Lτ 2 m2 ) m(m− 1) (M − 1) ] M∑ i=1 ‖zi‖2
= [ (Lη2η2L + L 2η3η3Lτ 2)
M −m mM(M − 1) ] M∑ i=1 ‖zi‖2.
Note also that: ‖zi‖2 = ‖∆i(xt−τt,i)‖2
= ‖∆i(xt−τt,i)−∇fi(xt−τt,i) +∇fi(xt−τt,i)−∇f(xt−τt,i) +∇f(xt−τt,i)‖2
≤ 3‖∆i(xt−τt,i)−∇fi(xt−τt,i)‖2 + 3‖∇fi(xt−τt,i)−∇f(xt−τt,i)‖2 + 3‖∇f(xt−τt,i)‖2 ≤ 3 ‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2︸ ︷︷ ︸ A5 +3σ2G + 3‖∇f(xt−τt,i)‖2.
Using the above results, we finally have: Ef(xT )− f(x0)
≤ T−1∑ t=0 [ − 1 2 ηηL‖∇f(xt)‖2 + (30ηK2L2η3Lτ)‖∇f(xt)‖2 ]
+ T−1∑ t=0 [ − ηηL 2M2 ‖ M∑ i=1 ∆i(xt−τt,i)‖2 + Lη2η2L m2 E‖ M∑ i=1 I{i ∈Mt}∆i(xt−τt,i)‖2
+ L2η3η3Lτ 2
m2 E‖ M∑ i=1 I{i ∈Mt}∆i(xk−τk,i)‖2 ]
+ T [ σ2L(
Lη2η2L m + τ2L2η3η3L m + 5KηL2η3L) + 30ηK 2L2η3Lσ 2 G ] ≤ T−1∑ t=0 [ − 1 2 ηηL‖∇f(xt)‖2 + (30ηK2L2η3Lτ)‖∇f(xt)‖2 ]
+ T−1∑ t=0 [[ (Lη2η2L + L 2η3η3Lτ 2) M −m m(M − 1) ][ (15KL2η2L(σ 2 L + 6Kσ 2 G)
+ 90K2L2η2L 1
M ∑ i∈[M ] ‖∇f(xt−τt,i)‖2 + 3σ2G + 3 M M∑ i=1 ‖∇f(xt−τt,i)‖2) ]]
+ T [ σ2L(
Lη2η2L m + τ2L2η3η3L m + 5KηL2η3L) + 30ηK 2L2η3Lσ 2 G ] ≤ T−1∑ t=0 ηηL‖∇f(xt)‖2×
[ − 1
2 + 30L2K2η2Lτ +
[ (LηηL + L 2η2η2Lτ 2)
M −m m(M − 1)
] (90K2L2η2Lτ + 3τ) ] + TηηLσ
2 L×[[
( LηηL m + τ2L2η2η2L m + 5KL2η2L) + (LηηL + L 2η2η2Lτ 2) M −m m(M − 1)
(15KL2η2L) ]
+ [ 30K2L2η2L + (LηηL + L 2η2η2Lτ 2)
M −m m(M − 1)
(90K2L2η2L + 3) ] σ2G ] (b13)
≤ T−1∑ t=0 −1 4 ηηL‖∇f(xt)‖2 + TηηL [ αLσ 2 L + αGσ 2 G ] ,
where (b13) follows from the fact that
1 4 ≤ [ 1 2 − 30L2K2η2Lτ − [ (LηηL + L 2η2η2Lτ 2) M −m m(M − 1) ] (90K2L2η2Lτ + 3τ) ] if 120L2K2η2Lτ + 4(LηηL + L 2η2η2Lτ 2) M−mm(M−1) ] (90K2L2η2Lτ + 3τ) < 1,
αL = [ ( LηηL m + τ2L2η2η2L m + 5KL2η2L) + (LηηL + L 2η2η2Lτ 2) M −m m(M − 1) (15KL2η2L) ] ,
and αG = [ 30K2L2η2L + (LηηL + L 2η2η2Lτ 2)
M −m m(M − 1)
(90K2L2η2L + 3) ] .
Lastly, by rearranging and telescoping, we have
1
T T−1∑ t=0 E‖∇f(xt)‖2 ≤ 4(f0 − f∗) ηηLT + 4 [ αLσ 2 L + αGσ 2 G ] .
This completes the proof. Corollary 2 (Linear Speedup to Stationary Point). By setting ηL = 1√T and η = √ m, the convergence rate of AFA-CD with uniformly distributed worker information arrivals is:
1
T T−1∑ t=0 E‖∇f(xt)‖22 = O( 1 m1/2T 1/2 ) +O ( τ2 T ) +O ( K2 T ) +O ( K2 m1/2T 3/2 ) +O ( K2τ2 T 2 ) .
Proof. Let ηL = 1√T , and η = √ m. It then follows that:
αL = O( 1 m1/2T 1/2 ) +O(τ
2
T ) +O(K T ) +O( K m1/2T 3/2 ) +O(Kτ
2
T 2 ),
αG = O( 1 m1/2T 1/2 ) +O(τ
2
T ) +O(K
2
T ) +O( K
2
m1/2T 3/2 ) +O(K
2τ2
T 2 ),
and the proof is complete.

heading: C PROOF OF THE PERFORMANCE RESULTS OF THE AFA-CS ALGORITHM
text: Theorem 4. Under Assumptions 1- 3, choose sever- and worker-side learning rates η and ηL in such a way that there exists a non-negative constant series {βµ}τ−1u=0 satisfying the following relationship:
12LηηL + 540(M −m′)2
M2 (1 + LηηL)K
2L2η2L(1 + τ) + 180K 2L2η2L + 320L 3K2ηη3L<1, (4)
ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) 3τL2 + (βu+1 − βu) ≤ 0, (5)
ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) 3τL2 − βτ−1 ≤ 0, (6)
3
2M σ2L ≤ (
1 2 − β0ηηL)E‖Gt‖22, (7)
the output sequence {xt} generated by the AFA-CS algorithm for general worker information arrival processes with bounded delay (τ := maxt∈[T ],i∈[M ]{τt,i}) satisfies:
1
T T−1∑ t=0 E‖∇f(xt)‖22 ≤ 4(V (x0)− V (x∗)) ηηLT + 4 ( αLσ 2 L + αGσ 2 G ) , (8)
where αL and αG are constants defined as follows:
αL , [ 3LηηL
2M + 5KL2η2L(
9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL))],
αG , ( 9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL))(30K 2L2η2L),
and V (·) is defined as V (xt) , f(xt) + ∑τ−1 u=0 βu‖xt−u − xt−u−1‖2, m′ is the number of updates in the memory space with no time delay (τt,i = 0).
Proof. We divide the stochastic gradient returns { Gi} into two groups, one is for those without delay (Gi(xt), i ∈Mt, |Mt| = m′) and the other is for those with delay (Gi(xt−τt,i), i ∈Mct , |Mct | = M −m′). Then, the update step can be written as follows:
xt+1 − xt = − ηηL M [ ∑ i∈Mt Gi(xt) + ∑ i∈Mct Gi(xt−τt,i) ] (10)
= − η M [ ∑ i∈[M ] Gi(xt) + ∑ i∈Mct ( Gi(xt−τt,i)−Gi(xt) )] . (11)
Due to the L-smoothness assumption, taking expectation of f(xt+1) over the randomness in communication round t, we have:
E[f(xt+1)] ≤ f(xt) + 〈 ∇f(xt),E[xt+1 − xt] 〉︸ ︷︷ ︸ A1 + L 2 E[‖xt+1 − xt‖2︸ ︷︷ ︸ A2
We first bound A2 as follows:
A2 = E[‖xt+1 − xt‖2]
= η2η2L M2 E [∥∥∥∥ ∑
i∈Mt Gi(xt) + ∑ i∈Mct Gi(xt−τt,i) ∥∥∥∥2]
= η2η2L M2 E [∥∥∥∥ ∑
i∈Mt
[Gi(xt)−∆i(xt)]
+ ∑ i∈Mct [Gi(xt−τt,i)−∆i(xt−τt,i) + ∆i(xt−τt,i)−∆i(xt)] + ∑ i∈[M ] ∆i(xt) ∥∥∥∥2]
= 3η2η2L M2 [ E ∥∥∥∥ ∑ i∈Mt [Gi(xt)−∆i(xt)] + ∑ i∈Mct [Gi(xt−τt,i)−∆i(xt−τt,i)] ∥∥∥∥2
+ E ∥∥∥∥ ∑ i∈Mct [∆i(xt−τt,i)−∆i(xt)] ∥∥∥∥2 + E∥∥∥∥ ∑ i∈[M ] ∆i(xt) ∥∥∥∥2]
≤ 3η 2η2L M σ2L + 3(M −m′) M2 η2η2L ∑ i∈Mct ‖∆i(xt)−∆i(xt−τt,i)‖2 + 3η2η2L M2 ‖ ∑ i∈[M ] ∆i(xt)‖2
≤ 3η 2η2L M σ2L + 3(M −m′) M2 η2η2L ∑ i∈Mct ‖∆i(xt)−∆i(xt−τt,i)‖2
+ 6η2η2L M ∑ i∈[M ] ‖∆i(xt)−∇fi(xt)‖2 + 6η2η2L‖∇f(xt)‖2.
To bound the term A1, we have: A1 =E 〈 ∇f(xt),xt+1 − xt 〉 =E 〈 ∇f(xt),−
ηηL M [ ∑ i∈Mt Gi(xt) + ∑ i∈Mct Gi(xt−τt,i) ]〉
=− ηηLE [ 1
2 ‖∇f(xt)‖2 +
1
2M2 ∥∥∥∥ ∑ i∈Mt Gi(xt) + ∑ i∈Mct Gi(xt−τt,i) ∥∥∥∥2
− 1 2 ∥∥∥∥∇f(xt)− 1M [ ∑ i∈Mt Gi(xt) + ∑ i∈Mct Gi(xt−τt,i)] ∥∥∥∥2] (c1) = − ηηL
2 ‖∇f(xt)‖2 − ηηL 2 E‖ 1 ηηL (xt+1 − xt)‖2
+ ηηL 2M2 E‖ ∑ i∈Mt [∇fi(xt)−Gi(xt)] + ∑ i∈Mct [∇fi(xt)−Gi(xt−τt,i)]‖2
=− ηηL 2 ‖∇f(xt)‖2 − 1 2ηηL E‖xt+1 − xt‖2
+ ηηL 2M2 E ∥∥∥∥ ∑ i∈Mt [∇fi(xt)−∆i(xt) + ∆i(xt)−Gi(xt)]
+ ∑ i∈Mct [∇fi(xt)−∆i(xt) + ∆i(xt)−∆i(xt−τt,i) + ∆i(xt−τt,i)−Gi(xt−τt,i)] ∥∥∥∥2
=− ηηL 2 ‖∇f(xt)‖2 − 1 2ηηL E‖xt+1 − xt‖2
+ ηηL 2M2 E ∥∥∥∥ ∑ i∈[M ] [∇fi(xt)−∆i(xt)] + ∑ i∈Mt [∆i(xt)−Gi(xt)]
+ ∑ i∈Mct [∆i(xt)−∆i(xt−τt,i) + ∆i(xt−τt,i)−Gi(xt−τt,i)] ∥∥∥∥2
≤− ηηL 2 ‖∇f(xt)‖2 − 1 2ηηL E‖xt+1 − xt‖2 + 3ηηL 2M2 E ∥∥∥∥ ∑ i∈Mct [∆i(xt)−∆i(xt−τt,i)] ∥∥∥∥2
+ 3ηηL 2M2 ∥∥∥∥ ∑ i∈[M ] ∇fi(xt)−∆i(xt) ∥∥∥∥2
+ 3ηηL 2M2 E ∥∥∥∥ ∑ i∈Mt [∆i(xt)−Gi(xt)] + ∑ i∈Mct ∆i(xt−τt,i)−Gi(xt−τt,i) ∥∥∥∥2
≤− ηηL 2 ‖∇f(xt)‖2 − 1 2ηηL E‖xt+1 − xt‖2 + 3(M −m′)ηηL 2M2 ∑ i∈Mct E ∥∥∥∥∆i(xt)−∆i(xt−τt,i)∥∥∥∥2
+ 3ηηL 2M ∑ i∈[M ] ∥∥∥∥∇fi(xt)−∆i(xt)∥∥∥∥2 + 3ηηL2M σ2L where (c1) follows from the update step of the algorithm specified in Eq. 10.
Combining A1 abd A2, we have:
E[f(xt+1)]− f(xt) ≤ 〈 ∇f(xt),E[xt+1 − xt] 〉︸ ︷︷ ︸ A1 + L 2 E[‖xt+1 − xt‖2︸ ︷︷ ︸ A2
≤f(xt)− ηηL
2 ‖∇f(xt)‖2 −
1
2ηηL E‖xt+1 − xt‖2
+
( 3(M −m′)ηηL
2M2 + 3L(M −m′)η2η2L 2M2 ) ∑ i∈Mct E ∥∥∥∥∆i(xt)−∆i(xt−τt,i)∥∥∥∥2︸ ︷︷ ︸
C1
+ ( 3ηηL 2M + 3Lη2η2L M ) ∑ i∈[M ] ∥∥∥∥∇fi(xt)−∆i(xt)∥∥∥∥2︸ ︷︷ ︸ C2
+ 3ηηL 2M σ2L + 3Lη2η2L 2M σ2L + 3Lη 2η2L‖∇f(xt)‖2 (12)
For each worker i, we have:
C2 = ‖∇fi(xt)−∆i(xt)‖2
= ‖∇fi(xt)− 1
Kt,i Kt,i−1∑ j=0 ∇fi(xjt )‖2
= 1
Kt,i Kt,i−1∑ j=0 ‖∇fi(xt)−∇fi(xjt )‖2
≤ L 2
Kt,i Kt,i−1∑ j=0 ‖xt − xjt‖2
(c2)
≤ 5KL2η2L(σ2L + 6Kσ2G) + 30K2L2η2L‖∇f(xt)‖2, where (c2) follows from the same bound of A6 specified in Eq. (9).
Also, note that:
C1 = ‖∆i(xt)−∆i(xt−τt,i)‖ ≤ 3‖∆i(xt)−∇fi(xt)‖2 + 3‖∇fi(xt)−∇fi(xt−τt,i)‖2 + 3‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2
≤ 3‖∆i(xt)−∇fi(xt)‖2 + 3‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2 + 3L2‖xt − xt−τt,i‖2
≤ 3‖∆i(xt)−∇fi(xt)‖2 + 3‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2 + 3L2‖ τt,i−1∑ u=0 xt−u − xt−u−1‖2
≤ 3‖∆i(xt)−∇fi(xt)‖2 + 3‖∇fi(xt−τt,i)−∆i(xt−τt,i)‖2 + 3τL2 τ−1∑ u=0 ‖xt−u − xt−u−1‖2,
where τ is the maximum delay, i.e., τ = max{τt,i},∀t ∈ [T ], i ∈ [M ]. Plugging C1 and C2 into the inequality in Eq. (12), we have:
E[f(xt+1)]− f(xt) ≤ 〈 ∇f(xt),E[xt+1 − xt] 〉︸ ︷︷ ︸ A1 + L 2 E[‖xt+1 − xt‖2︸ ︷︷ ︸ A2
≤f(xt)− ηηL
2 ‖∇f(xt)‖2 −
1
2ηηL E‖xt+1 − xt‖2
+
( 9(M −m′)ηηL
2M2 + 9L(M −m′)η2η2L 2M2 ) ∑ i∈Mct E ∥∥∥∥∇fi(xt)−∆i(xt)∥∥∥∥2
+
( 9(M −m′)ηηL
2M2 + 9L(M −m′)η2η2L 2M2 ) ∑ i∈Mct E ∥∥∥∥∇fi(xt−τt,i)−∆i(xt−τt,i)∥∥∥∥2
+
( 9(M −m′)2ηηL
2M2 + 9L(M −m′)2η2η2L 2M2
) 3τL2 τ−1∑ u=0 E ∥∥∥∥xt−u − xt−u−1∥∥∥∥2
+ ( 3ηηL 2M + 3Lη2η2L M ) ∑ i∈[M ] ∥∥∥∥∇fi(xt)−∆i(xt)∥∥∥∥2 +
3ηηL 2M σ2L + 3Lη2η2L 2M σ2L + 3Lη 2η2L‖∇f(xt)‖2
≤f(xt)− ηηL
2 ‖∇f(xt)‖2 −
1
2ηηL E‖xt+1 − xt‖2
+ ηηL
( 9(M −m′)2
2M2 (1 + LηηL) + (
3 2 + 3LηηL)
) (5KL2η2L(σ 2 L + 6Kσ 2 G) + 30K 2L2η2L‖∇f(xt)‖2)
+ ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) (5KL2η2L(σ 2 L + 6Kσ 2 G) + 30K 2L2η2L 1 M −m ∑ i∈Mct ‖∇f(xt−τt,i)‖2)
+ ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) 3τL2 τ−1∑ u=0 E ∥∥∥∥xt−u − xt−u−1∥∥∥∥2
+ 3ηηL 2M σ2L + 3Lη2η2L 2M σ2L + 3Lη 2η2L‖∇f(xt)‖2
=f(xt)− ηηL [ 1 2 − ( 9(M −m′)2 2M2 (1 + LηηL) + ( 3 2 + 3LηηL) ) 30K2L2η2L − 3LηηL ] ‖∇f(xt)‖2
− 1 2ηηL
E‖xt+1 − xt‖2 + ηηL ( 9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL)
) [5KL2η2L(σ 2 L + 6Kσ 2 G)]
+ ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) (30K2L2η2L
1 M −m ∑ i∈Mct ‖∇f(xt−τt,i)‖2)
+ ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) 3τL2 τ−1∑ u=0 E ∥∥∥∥xt−u − xt−u−1∥∥∥∥2 + 3ηηL2M σ2L + 3Lη2η2L2M σ2L.
Now, define V (xt) = f(xt) + ∑τ−1 u=0 βu‖xt−u − xt−u−1‖2. Based on the above bound of E[f(xt+1)]− f(xt), it then follows that:
EV (xt+1)− V (xt) =Ef(xt+1)− f(xt)
+ τ−2∑ u=0 (βu+1 − βu)‖xt−u − xt−u−1‖2 + β0‖xt+1 − xt‖2 − βτ−1‖xt−τ−1 − xt−τ−2‖2
≤− ηηL [ 1 2 − ( 9(M −m′)2 2M2 (1 + LηηL) + ( 3 2 + 3LηηL) ) 30K2L2η2L − 3LηηL ] ‖∇f(xt)‖2
+ ηηL
( 9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL)
) [5KL2η2L(σ 2 L + 6Kσ 2 G)]
+ ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) (30K2L2η2L
1 M −m ∑ i∈Mct ‖∇f(xt−τt,i)‖2)
+ [ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) 3τL2 + (βu+1 − βu)] τ−2∑ u=0 E ∥∥∥∥xt−u − xt−u−1∥∥∥∥2
+ [ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) 3τL2 − βτ−1]‖xt−τ−1 − xt−τ−2‖2
+ (β0 − 1
2ηηL )‖xt+1 − xt‖2 + 3ηηL 2M σ2L + 3Lη2η2L 2M σ2L.
Telescoping the above inequality from t = 0 to T − 1 of the above inequality yields: EV (xT )− V (x0)
≤− ηηL T−1∑ t=0 [ 1 2 − ( 9(M −m′)2 2M2 (1 + LηηL) + ( 3 2 + 3LηηL) ) 30K2L2η2L − 3LηηL ] ‖∇f(xt)‖2
+ ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) (30K2L2η2L T−1∑ t=0
1 M −m ∑ i∈Mct ‖∇f(xt−τt,i)‖2)
+ ηηLT
( 9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL)
) [5KL2η2L(σ 2 L + 6Kσ 2 G)]
+ T−1∑ t=0 [ηηL ( 9(M −m′)2 2M2 (1 + LηηL) ) 3τL2 + (βu+1 − βu)]︸ ︷︷ ︸
C3
τ−2∑ u=0 E ∥∥∥∥xt−u − xt−u−1∥∥∥∥2
+ T−1∑ t=0 [ηηL ( 9(M −m′)2 2M2 (1 + LηηL) ) 3τL2 − βτ−1]︸ ︷︷ ︸
C4
‖xt−τ−1 − xt−τ−2‖2
+ (β0 − 1
2ηηL ) T−1∑ t=0 ‖xt+1 − xt‖2 + 3ηηLT
2M σ2L︸ ︷︷ ︸
C5
+ 3LTη2η2L
2M σ2L
(c3)
≤ − 1 4 ηηL T−1∑ t=0 ‖∇f(xt)‖2
+ ηηL
[ 3LTηηL
2M + 5TKL2η2L
( 9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL)
)] σ2L
+ ηηLT
( 9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL)
) (30K2L2η2L)σ 2 G,
where (c3) holds if the following conditions are satisfied:
1 4 ≤ [ 1 2 − ( 9(M −m′)2 2M2 (1 + LηηL) + ( 3 2 + 3LηηL) ) 30K2L2η2L − 3LηηL ] − ( 9(M −m′)2
2M2 (1 + LηηL)
) (30τK2L2η2L),
C3 = [ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) 3τL2 + (βu+1 − βu)] ≤ 0,
C4 = [ηηL
( 9(M −m′)2
2M2 (1 + LηηL)
) 3τL2 − βτ−1] ≤ 0,
C5 ≤ 0← 3 2M σ2L ≤ ( 1 2 − β0ηηL)E‖Gt‖2.
By rearranging the inequality, we have:
1 4 ηηL T−1∑ t=0 ‖∇f(xt)‖2
≤V (x0)− EV (xT )
+ ηηLT
[ 3LηηL
2M + 5KL2η2L
( 9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL)
)] σ2L
+ ηηLT
( 9(M −m′)2
M2 (1 + LηηL) + (
3 2 + 3LηηL)
) (30K2L2η2L)σ 2 G,
That is,
1
T T−1∑ t=0 E‖∇f(xt)‖2 ≤ 4(V (x0)− V (x∗)) ηηLT + 4[αLσ 2 L + αGσ 2 G],
where αL = [ 3LηηL 2M + 5KL 2η2L ( 9(M−m′)2 M2 (1 +LηηL) + ( 3 2 + 3LηηL) )] , αG = ( 9(M−m′)2 M2 (1 +
LηηL) + ( 3 2 + 3LηηL) ) (30K2L2η2L). This completes the proof.
Corollary 3 (Linear Speedup). By setting ηL = 1√T , and η = √ M , the convergence rate of the AFA-CS algorithm for general worker information arrival processes with bounded delay is:
1
T T−1∑ t=0 E‖∇f(xt)‖22 = O (
1
M1/2T 1/2
) +O ( K2
T
) +O ( K2M1/2
T 3/2
) .
Proof. Let ηL = 1√T , and η = √ M . It then follows that:
αL = O( 1 M1/2T 1/2 ) +O(K T ) +O(KM
1/2
T 3/2 ).
αG = O( K2 T ) +O(K 2M1/2 T 3/2 ).
This completes the proof.

heading: D DISCUSSION
text: Convergence Error: The case with uniformly distributed worker information arrivals under AFL can be viewed as a uniformly independent sampling process from total workers [M ] under conventional FL. Also, the case with general worker information arrival processes under AFL can be equivalently mapped to an arbitrarily independent sampling under conventional FL. In each communication round, the surrogate objection function for partial worker participation in FL is f̃(x) := 1|Mt| ∑ i∈Mt fi(x). For uniformly independent sampling, the surrogate object function approximately equals to f(x) := 1 M ∑M i=1 fi(x) in expectation, i.e., E[f̃(x)] = f(x). However, the surrogate object function f̃(x) may deviate from f(x) with arbitrarily independent sampling. More specifically, for uniformly independent sampling, the bound of ‖∇f(xt)− f̃(xt)‖2 is independent of σG (A3 term in B.3). On the other hand, for arbitrarily independent sampling, ‖∇f(xt)− f̃(xt)‖2 ≤ O(σ2G) (A3 term in B.2). This deviation may happen in every communication round, so it is non-vanishing even with infinity communication rounds. As a result, such deviation is originated from the arbitrary sampling coupling with non-i.i.d. datasets. In other words, it is irrelevant to the optimization hyper-parameters such as the learning rate, local steps and others, which is different from the objective inconsistency due to different local steps shown in Wang et al. (2020). When we set τ = 0 and Kt,i = K,∀t, i, AFA-CD generalizes FedAvg. In such sense, the convergence error also exists in currently synchronous FL algorithms with such arbitrarily independent sampling and non-i.i.d. dataset. Moreover, this sampling process coupling with non-i.i.d. dataset not only results in convergence issue but also potentially induces a new source of bias/unfairness (Mohri et al., 2019; Li et al., 2019b). So how to model the practical worker participation process in practice and in turn tackle these potential bias are worth further exploration.
Variance Reduction: If we view the derivation between local loss function and global loss function as global variance, i.e., ‖∇fi(xt)−∇f(xt)‖2 ≤ σ2G, ∀i ∈ [m],∀t as shown in Assumption 3, the AFA-CS algorithm is indeed a variance reduction (VR) method, akin to SAG (Le Roux et al., 2012; Schmidt et al., 2017). SAG maintains an estimate stochastic gradient vi, i ∈ [n] for each data point (n is the size of the dataset). In each iteration, SAG only samples one data point (say, j) and update the stochastic gradient on latest model (vj = ∇fj(xt)) stored in the memory space, but then use the average of all stored stochastic gradients as the estimate of a full gradient to update the model (xt+1 = xt − ηtgt, gt = 1n ∑n i=1 vi). In such way, SAG is able to have a faster convergence rate by reducing the local variance due to the stochastic gradient. AFA-CS algorithm performs in the similar way. The server in the AFA-CS algorithm maintains a parameter for each worker as an estimate of the returned stochastic gradient. In each communication round, the server only receives m updates in the memory space but updates the global model by the average of all the M parameters. As a result, not only can it diminish the convergence error derived from the non-i.i.d. dataset and general worker information arrival processes (arbitrarily independent sampling), but also accelerate the convergence rate with a linear speedup factor M . Previous works have applied VR methods in FL, notably SCAFFOLD (Karimireddy et al., 2020b) and FedSVRG (Konecnỳ et al., 2016). The key difference is that we apply the VR on the server side to control the global variance while previous works focus on the worker side in order to tackle the model drift due to local update steps. Applying VR methods on server and worker side are orthogonal, and thus can be used simultaneously. We believe other variance reduction methods could be similarly extended on the server side in a similar fashion as what we do in AFA-CD. This will be left for future research.

heading: E EXPERIMENTS
text: In this section, we provide the detailed experiment settings as well as extra experimental results that cannot fit in the page limit of the main paper.

heading: E.1 MODEL AND DATASETS
text: We run three models on three different datasets, including i) multinomial logistic regression (LR) on manually partitioned non-i.i.d. MNIST, ii) convolutional neural network (CNN) for manually partitioned non-i.i.d. CIFAR-10, and iii) recurrent neural network (RNN) on natural non-i.i.d. Shakespeare datasets. These dataset are curated from previous FL papers (McMahan et al., 2016; Li et al., 2018) and are now widely used as benchmarks in FL studies (Li et al., 2019c; Yang et al., 2021).
For MNIST and CIFAR-10, each dataset has ten classes of images. To impose statistical heterogeneity, we split the data based on the classes (p) of images each worker contains. We distribute the data to M = 10(or 100) workers such that each worker contains only certain classes with the same number of training/test samples. Specifically, each worker randomly chooses p classes of labels and evenly samples training/testing data points only with these p classes labels from the overall dataset without replacement. For example, for p = 2, each worker only has training/testing samples with two classes, which causes heterogeneity among different workers. For p = 10, each worker has samples with ten classes, which is nearly i.i.d. case. In this way, we can use the classes (p) in worker’s local dataset to represent the non-i.i.d. degree qualitatively.
The Shakespeare dataset is built from The Complete Works of William Shakespeare (McMahan et al., 2016). We use a two-layer LSTM classifier containing 100 hidden units with an embedding layer. The learning task is the next-character prediction, and there are 80 classes of characters in total. The model takes as input a sequence of 80 characters, embeds each of the characters into a learned 8-dimensional space and outputs one character per training sample after two LSTM layers and a densely-connected layer. The dataset and model are taken from LEAF (Li et al., 2018).
For MNIST and CIFAR-10, we use global learning rate η = 1.0 and local learning rate ηL = 0.1. For MNIST, the batch size is 64 and the total communication round is 150. For CIFAR-10, the batch size is 500 and the total communication round is 10000. For the Shakespeare dataset, the global learning rate is η = 50, the local learning rate is ηL = 0.8, batch size is b = 10, and the total communication round is 300. In the following tables and figure captions, we use “m/M” to denote that, in each communication round, we randomly choose m workers from [M ] to participate in the training.
We study the asynchrony and heterogeneity factors in AFL, including asynchrony, heterogeneous computing, worker’s arrival process, and data heterogeneity. To simulate the asynchrony, each participated worker choose one global model from the last recent five models instead of only using the latest global model for synchronous case. To mimic the heterogeneous computing, we simulate two cases: constant and dynamic local steps. For constant local steps, each participated worker performs a fixed c local update steps. In contrast, each worker takes a random local update steps uniformly sampled from [1, 2× c] for dynamic local steps. To emulate the effect of various worker’s arrival processes, we use uniform sampling without replacement to simulate the uniformly distributed worker information arrivals, and we use biased sampling with probability [0.19, 0.19, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.01, 0.01] without replacement for total 10 workers to investigate potential biases with general worker information arrival processes. To study the data heterogeneity, we use the value p as a proxy to represent the non-i.i.d. degree for MNIST and CIFAR-10.

heading: E.2 FURTHER EXPERIMENTAL RESULTS
text: Effect of asynchrony, local update steps, and non-i.i.d. level. In table 2, we examine three factors by comparing the top-1 test accuracy: synchrony versus asynchrony, constant steps versus dynamic steps and different levels of non-i.i.d. dataset. The worker sampling process is uniformly random sampling to simulate the uniformly distributed worker information arrivals. The baseline is synchrony with constant steps. When using asynchrony or/and dynamic local steps, the top-1 test accuracy shows
no obvious differences. This observation can be observed in all these three tasks. Asynchrony and dynamic local update steps enable each worker to participate flexibly and loosen the coupling between workers and the server. As a result, asynchrony and dynamic local steps introduce extra heterogeneity factors, but the performance of the model is as good as that of the synchronous approaches with constant local steps. Instead, the data heterogeneity is an important factor for the model performance. As the non-i.i.d. level increases (smaller p value), the top-1 test accuracy decreases.
Next, we study convergence speed of the test accuracy for the model training under different settings. Figure 2 illustrates the test accuracy for LR on MNIST with different non-i.i.d. levels. We can see that asynchrony and dynamic local steps result in zigzagging convergence curves, but the final accuracy results have negligible differences. The zigzagging phenomenon is more dramatic as the non-i.i.d. level gets higher. Interestingly, from Figure 3 and Figure 4, we can see that for less non-i.i.d. settings such as p = 10 and p = 5, the curves of all algorithms are almost identical. Specifically, in Figure 4, the test accuracy curves of the LSTM model oscillates under asynchrony and dynamic local steps. Another observation is that it takes more rounds to converge as the non-i.i.d. level of the datasets increases. This trend can be clearly observed in Figure 3.
Utilizing FedProx and SCAFFOLD as the optimizer on the worker-side. Here, we choose FedProx and SCAFFOLD as two classes of algorithms in existing FL algorithms. FedProx represents these algorithms that modifies the local objective function. Other algorithms belonging to this category includes FedPD (Zhang et al., 2020b) and FedDyn (Acar et al., 2021). In such algorithms, no extra information exchange between worker and server is needed. On the other hand, SCAFFOLD represents VR-based (variance reduction) algorithms. It needs an extra control variate to perform the “variance reduction” step, so extra parameters are required in each communication round. Other algorithms in this class includes FedSVRG (Konecnỳ et al., 2016).
In Table 3, we show the effectiveness of utilizing existing FL algorithms, FedProx and SCAFFOLD, in the AFL framework. For FedProx and SCAFFOLD, we examine synchrony and constant local steps settings. When incorporating these two advanced FL algorithms in the AFL framework, we study the effects of asynchrony and dynamic local steps. We set µ = 0.1 as default in FedProx algorithm. We can see from Table 3 that FedProx performs as good as FedAvg does (compare with the results in Table 2). Also, there is no performance degradation in AFL framework by utilizing FedProx as the worker’s optimizer. However, while SCAFFOLD performs well for LR on MNIST, it dose not work well for CNN on CIFAR-10, especially in cases with higher non-i.i.d. levels. One possible reason is that the control variates can become stale in partial worker participation and in turn degrade the performance. Previous work also showed similar results (Acar et al., 2021; Reddi et al., 2020). If we view the SCAFFOLD ( in synchrony and constant steps setting) as the baseline, no obvious performance degradation happens under AFL with SCAFFOLD being used as the worker’s optimizer.
Effects of different worker information arrival processes. In order to generate different workers’ arrival processes, we use uniform sampling without replacement to simulate the uniformly distributed worker information arrivals and use biased sampling to simulate the potential bias in general worker information arrival processes. In Figures 5 and 6, we illustrate the effect of the sampling process for LR on MNIST and CNN on CIFAR-10 with asynchrony and dynamic local steps. For highly non-i.i.d. datasets (p = 1), the biased sampling process degrades the model performance. This is consistent with the larger convergence error as shown in our theoretical analysis. On the other hand, for other non-i.i.d. cases with p = 2, 5, 10, such biased sampling dose not lead to significant performance degradation. When applying variance reduction on such biased sampling process by reusing old gradients as shown in AFA-CS, we can see that AFA-CS performs well on MNIST, but not on CIFAR-10. We conjecture that AFA-CS, as a variance reduction method, does not always perform well in practice. This observation is consistent with the previous work (Defazio & Bottou, 2018; Reddi et al., 2020), which also demonstrated the ineffectiveness of variance reduction methods in deep learning and some cases of FL.

Review summaries:
In order to address the issues of FedAvg (e.g. straggler, waste computation, slow convergence), this paper proposes a new federated training scheme "anarchic federated learning" (AFL) as an alternative. Instead of uniformly sampling participant clients, AFL let all workers to decide their number of local steps, when to communicate, and their step-sizes / batch sizes. The authors established a theoretical convergence rate of AFL and show that it recovers the rate of FedAvg under the assumption of uniform distributed arrival of worker information and bounded maximum delay and local steps. The authors also provides empirical evaluations on some experiments to demonstrate that 

This paper proposes a general FL framework, called anarchic federated learning (AFL), that allows voluntary client participation of clients, with individual update steps and delay. Algorithms for both cross-device and cross-silo are presented. Convergence upper bounds and a lower bound are derived. Experimental results are reported to demonstrate the effectiveness of the proposed algorithm. 

This paper analyses a variant of generalized federated averaging ([Wang et al.](https://arxiv.org/abs/2107.06917)) with partial worker participation and asynchrony in the stateful (i.e., the worker specific data can be saved on the server) and stateless settings, which characterize cross-silo and cross-device federated learning ([Kairouz et al.](https://arxiv.org/abs/1912.04977?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%253A+arxiv%252FQSXk+%2528ExcitingAds%2521+cs+updates+on+arXiv.org%2529)) respectively. Specifically for each global update, the server uses fresh gradients from $m$ out of $M$ machines, where each machine can make some local SGD updates starting from a stale global iterate (i.e., the gradients are delayed). This setting is termed *anarchic federated learning* (AFl) when the workers can have an arbitrary number of local steps and gradient delays.  The authors first provide a lower bound for convergence to a first-order stationary point in the AFL setting. Then they upper bound the convergence of their algorithms in the stateful and stateless setting when the local updates and delay are bounded. Under some regimes, and assumptions on the worker sampling and delay distribution, a linear convergence speed-up can be shown w.r.t. the number of machines ($m$ for the stateless setting and $M$ for the stateful setting). Some experiments are provided to measure the effect of the anarchic worker behavior.