Anarchic Federated Learning
Authors: Haibo Yang
Xin Zhang
Prashant Khanduri
Jia Liu
Venue: ICLR 2022 Submitted (2022)

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 {\em linear speedup effect} in the new AFL paradigm. We validate the proposed algorithms with extensive experiments on real-world datasets.

Under review as a conference paper at ICLR 2022
ANARCHIC FEDERATED LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Present-day federated learning (FL) systems deployed over edge networks consists of 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 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 each round based on its current situation (e.g., battery level, communication chan- nels, privacy concerns). However, AFL also introduces significant challenges 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, 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.
show that both AFL algorithms
INTRODUCTION
Federated Learning (FL) has recently emerged as an important distributed learning framework that leverages numerous workers collaboratively learn a joint model (Li 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 "Tinear speedup effect, 1.c., the convergence time of an FL algorithm decreases
linearly y as the number of workers increases (Stich 2018 Yu et al. 2019: Wang & Joshi 2018 Khaled
ct al. 2019 Karimireddy et al. 2020b Yang et al. 2021 Qu et a (020))
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 (c.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: (I) each worker is available for training upon the server's 's request and throughout complete round; (2) all participating workers are willing to execute the same number of local updates and communicate with the server in 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 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 result, stragglers (i.e., slow workers) could significantly slow

---

Under review as a conference paper at ICLR 2022
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 al., 2019). Moreover, the synchronous nature of the server-centric approaches implies many networking problems (c.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 server- centric 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 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-dependee and fully controlled by the worker itself. Clearly, AFL has 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 the previous question 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 contribu- tions 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..d. data across workers, first establish fundamental convergence error lower bound that depends on the data heterogeneity in the AFL system. Then, propose two Anarchic Federated Averaging (AFA) algorithms with two-sided learning rates for two classes of FL problems(cross-
and cross-silo) (Kairouz et al. 2019 Wang et al. (021).
For AFL in the cross-device (CD) setting, our AFA-CD algorithm converges to error ball whose size matches the fundamental lower bound, with O (1IVmTT) convergence rate where 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 Moreover, under the special case with uniform workers' participation (equivalent to uniform workers sampling in conventional FL (Li al. 2019c] Karimireddy et al., 2020b a Acar et al., 2021)), AFA-CD can further converge to a stationary point (i.e., singleton) at convergence rate that matches the -fa 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/V by leveraging historical feedback and variance reduction tech- niques, where M 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 al. 2018) and SCAFFOLD (Karimireddy et al. 2020b)) can be integrated as the optimizers in our AFA framework to further enhance the AFL performance.
'To attain e-accuracy, it takes ((1/²²) steps for an algorithm with an O(IvTT) convergence rate, while needing O(1/me²) steps for another algorithm with an 0(I/mmT) convergence rate (the hidden constant in Big-O is the same). In this sense, ((I/mmT) implies linear speedup with respect to the number of workers.
2

---

Under review as a conference paper at ICLR 2022
The rest of the paper is organized as follows. In Section 2 we review related work. In Section we introduce AFL and our AFA algorithms, which are followed by their convergence analysis in We present the numerical results in Section 5 and conclude the work in Section 6
S
Section 4
2 RELATED WORK
Server-Centric Federated Learning Algorithms: To date, one of the prevailing FL algorithms is Federated Averaging (FedAvg), which was first proposed in (McMahan al. 2016) as 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.id. (heterogeneous) data (see, e.g., FedProx (Li al. 2018). FedPD ZZang et al., 2020b). SCAFFOLD (Karimireddy et al. 2020b), FedNova (Wang) et al. 2020), FedDyn (Acar et al. 202T), and MIME (Karimireddy et al. 2020a)), which are closely related to work. The main idea for these algorithms to control the "model drift" (due to heterogencous 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 beterogeneity, 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 (
Recently, some attempts have been made alleviate the strict requirements on worker's participation, such as allowing different local steps (Ruan et al. 2021 Wang et al.] 2020) and asynchronous FI. (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 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 AFI. and 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 straightforward combination of existing FL techniques for flexible worker participation.
Federated Learning with Flexible Worker Participation:
Ruuan
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 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. (201T); Agarwal Duchi (0112); Paine et al. (2013); ; Xie et al. (2019); Zhang al. (2020a) and references therein). We note that the AFL paradigm considered in this paper is more general and subsumes asynchronous distributed optimization as 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. Morcover, the workers may not even need to be work-conserving (i.c., workers could be idle between rounds of updates). As result, the convergence analysis of AFL is much more challenging.
Asynchronous Distributed Optimization:
3 ANARCHIC FEDERATED LEARNING
1) Overview of Anarchic Federated Learning: The goal of FL is to solve an optimization problem
in the form of minger f(x) == ΣM f((z), where fa(a:) & EG.,D, (fr &i) is the local (non- convex) loss function associated with a local data distribution D, and M is the total number of workers. For the setting with heterogeneous (non-i.i.d.) datasets at the workers, we have D; + Dj, if + j. In terms of the assumption on the size of workers, FL can be classified as cross cross-device FL and cross-sill FL (Kairouz et al., 2019 Wang et al.) (021). 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 subset of workers in each round of update and does not have sufficient.
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1 The Basic Framework of Anarchic Federated Learning (AFL).
At the Server (Coneurrently 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 (Coneurrently with Server):
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 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, has enough memory space to store each worker's s most recent information.
The basic process of AFL is illustrated Algorithm [ Here, the server is responsible for: I) collecting the local updates returned from workers, and 2) aggregating the obtained updates once certain conditions are satisfied (e.g., upon collecting m E (0, M) local updates from workers) to update the global model. In AFL, each worker could be non work-conserving (i..., 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 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 coaamunication-fffcinncee. Note that the above operations can happen concurrently on the server and worker sides, i.e., the processings the workers and the server are independent of each other in the temporal domain.
etc.).
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 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 time- varying number 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 algo- rithms for AFL, it is insightful to first obtain 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 [VV]((x) - (yy(y) S L||x yll. Vx.y E IRd, and i E [M].
Assumption 2. (Unbiased Local Stochastic Gradient) Let g¹ be a random local data sample at worker The local stochastic gradient is unbiased, i.e., [x, the expectation is taken over the local data distribution D..
fx()), vi [m], where
Assumption 3. (Bounded Local and Global Variances) There exist two constants a 2 0 and aG 2 0, such that the variance of each local stochastic gradient estimator bounded by [ (x(x, Et)
[x(x)]] < oZ, Vi E [M) and the global variability of the local gradient of the cost function is bounded by fx() f2x) < 0% Vi [M], Vk.
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 ag to quantify the data heterogeneity among different workers. This assumption is also frequently used in the literature of FL with non- ii.d. datasets (Reddi et al. 2020; Wang et al. 2019 Yang et al. (02T)) as well as in decentralized optimization (Kairouz et al.
2019
4

---

Under review as a conference paper at ICLR 2022
To establish a fundamental convergence error lower bound, consider the most general case where no assumption on the arrival processes of the worker information 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. for proof details):
Theorem (Convergence Error Lower Bound for General Worker Information Arrival Processes). For any level of heterogeneity characterized by ag, there exists loss functions and worker participation process satisfying Assumptions 7 3 for which the output x of any randomized FL algorithm satisfies:
E| [)))( ((oc))
(1)
Remark The lower bound in Theorem I 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.idd 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 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
THE ANARCHIC FEDERATED AVERAGING (AFA) ALGORITTMS
Upon obtaining fundamental understanding of the training algorithm performance limit from the we are now in a position to develop AFL algorithms that are guided
convergence error in Theorem | by our fundamental lower bound. Toward this end, in this section, will develop two anarchic federated averaging (AFA) algorithms for the cross-device (CD) and cross-silo (CS) settings in respectively.
Section 4.1 and 4.2
4.1 THE AFA-CD ALGORITHM FOR CROSS-DEVICE AFL
First, we propose the AFA-CD algorithm for the cross-device AFL setting. As mentioned earlier, cross-device AFL is suitable for cases with massive number of edge devices. In each round of global model update, only 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 [ Here, we use standard stochastic gradient descent (SGD) as the server- and worker-side optimizer. In each update i, L I.....T, the server waits until collecting local updates { (x+.)) from workers to form a set M, with [M]] = m, where Tr. represents the random delay of the local update of worker i, E M, (Server Code. Line 1). Once M, is formed, the server aggregates all local updates G, (x,x,,))) e M2 and updates global model (Server Code, Line 2). We count each global model update as one communication round. Mcanwhile, for each worker, it pulls the current global model parameters with time stamp yu once it decides to participate in training (Worker Code, Line 1). Each worker can then choose desired number of local update steps Ke (could be time-varying and device-dependent) to perform SGD updates for Ke.; times, and then return the rescaled sum of all stochastic gradients with timestamp z the server (Worker Code, Lines 2-3).
1) The AFA-CD Algorithm:
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 := [ }. We let 7 be the maximum delay of workers' returned information, which is defined as T == max (Tr,i). Also, we use fo = fxx) and f. 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 73 choose server-side and wirker-side learning rates and nr such that the following relationships hold: 180n, K2 L and L + +rr2 < 1. Then, the output sequence {xx} generated
by AFedAvg- TSLR-CD with general worker information arrival processes satisfies:
4(fo - -f)) A(0200, aGot)
Σ fxx))1
(2)
miT
5

---

Under review as a conference paper at ICLR 2022
Algorithm 2 The AFA-CD Algorithm for Cross-Device AFL.
At the Server (Concurrently with Workers);
1. In the thth update round, collect local updates (G -.,x)) ., the workers to form the set Mr, where 72, represents the random delay the worker i's local update, i MM-
M,} returned from
2. Aggregate and update: G, = - Eiem, Gi(Xe-ra)) Xx+1 = X, - -/
At Each Worker (Concurrently with Server):
1. Once decided to participate in the training, retrieve the parameter Xn from the server and its timestamp, set the local model: x Xy.
2. Choose a number of local steps Ke,s. which can be üime-varying and device-dependent.
Let x p,
x p.k 7.. where g
Vii( 2,k: ( k 0..... K
Sum and rescale the stochastic gradients: G.(X,,) Kes Σj=0 g). Return Gx
where or, A
3+ 3>"22n""i
15n/ KL? and og A 45
2m
2
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 (Linear Speedup to Error Ball). By setting aL VT' and r = vm, the convergence
rate of AFA-CD with general worker information arrival processes is:
K2 T
+ [X m1/221/22
+ +
+
0
+ O
Remark 2. First, we note that the non-vanishing error term O in Corollary [ matches the lower bound in Theorem[I] 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 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 sufficiently large T, the dominant term O /=/////zz implies that AFA-CD achieves the linear speedup effect before reaching constant
neighborhood with size (g
Remark 3. The conditions for the learning rates and 7/5 are natural extension of SGD. When = 0 (synchronous setting) and K = 1 (single local update), the condition becomes 777 S 2I which recovers the same learning rate condition for SGD in (Ghadimi & Lan 2013). Also, the suggested worker-side learning rate nı is independent of local update steps. This is different from previous work that 7/ 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 ! Judeer 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 special case where the arrivals of worker returned information in each round for global update is uniformly dis- tributed among the workers. this setting. M, can be viewed as subset with size m independently and uniformly sampled from [M] without replacement. For FL systems with 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, can map this setting into the conventional cross-device FL. systems with uniform worker sampling in partial worker participation, which widely-used assumption (McMahan et al.) 2016 [i 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 follows (see proof details Appendix(B.3)
Theorem 3. Under Assumptions 7 73 choose server-side and worker-side learning rates n and n such that the following relationships hold: ni. [6[(6( 3K 1))? 1, 120L K2nft + + L 12 ni 72) M-m (90K2 2 3r) Then, the output sequence {x:} generated by AFA-CD
m(M-1)

---

Under review as a conference paper at ICLR 2022
Algorithm 3 The AFA-CS Algorithm for Cross-Silo AFL.
At the Server (Concurrently with Workers);
1. In the t-th update round, collect local updates (x+ from the workers to form the set M,-
2. Update worker i's information in the memory using the returned local update G
3. Aggregate and update: G, M LiE[M] G,, Xt+1 = X, r/Gr.
At Each Worker (Concurrently with Server): Same as AFA-CD Worker Code.
with uniformly distributed worker information arrivals satisfies:
-
Σ
E (xx))
acod))
(3)
M.T
t=0
where L. and ag are constants that are defined as:
aL A
LAME
+
L2
55L2) + +Lome + ( M m
mnM - 1) (15KL
m
m
M ( + +3)
0g A
S0K2LL' + (Lmmz + =z'n'n1,77 m(M 1)
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 aL = vT and rj = m,, the conver- gence rate of AFA-CD with uniformly distributed worker information arrivals is:
T
Σ
(x = OC 1/2/T/22 + 1=0
+
7 T
+
K2 T
+0
1/233/2
K2
+
K2 72
Remark 4. For a sufficiently large T, the linear speedup effect to a stationary point (rather than constant error neighborhood) can be achieved with any finitely bounded maximum local update steps K and maximum delay т, i.e., O( ((r)) Note this rate does not depend on the delay T 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 OG (i.i.d. data) and K = 1 (single local update step), our AFA-CD algorithm is exactly the same the AsySG-con algorithm (Lian al. 2018) asynchronous parallel distributed optimization. verified that AFA-CD achieves the same rate that of the AsySG-con algorithm. When (synchronous setting) and Ke = 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., 20206] Reddi et al. 2020). Remarkably. the result of AFA-CD shows that
can be readily
0
we can achieve a faster convergence rate than O K /mT) in (Yang et al. 2021) and the same
rate FedAvg analysis in (Karimireddy al. 2020b)
4.2 THE AFA-CS ALGORITHM FOR CROSS-SILO FL
1) The AFA-CS Algorithm: As mentioned earlier, cross-silo FL is suitable for collaborative learning among relatively small number of (organizational) workers. Thanks 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[I [ 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 (G.) for each worker i E M into the memory space at the server (Server Code, Line 2). As result, whenever worker i returns local update to the server upon finishing its local update steps, the server will update the memory space corresponding worker i replace the old information with this newly received update from
7

---

Under review as a conference paper at ICLR 2022
worker i. Similar to AFA-CD, every new updates in the AFA-CS algorithm trigger the server to aggregate all the G i E [M] (newly received information if E M, or stored information i M2) and update the global model. The Worker Code in AFA-CS is exactly the same 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 (::
Theorem Under Assumptions 7 choose sever- and worker-side learning rates di and тι in such
a way that there exists non-negative constant series { F satisfying the following relationship:
12LmL + 540(M m²)?
(1 (1+ LIML) m/ +) + 180K3 320L K2m <1, (4)
M
9(M - m²)
mL
(1 LMML)
3TL² + +But1 -Bu) s 0,
(5)
2M2
9(M - -m')²
(1 LAME)
3r1.² -B--1 $0,
(6)
2M2
1
2M L S ( BoTmLBBl|,,EE
the output sequence }x,} generated by the AFA-CS algorithum for general worker information arrival processes with bounded delay (T == [e satisfies:
T-1 Σ t-
(Z)) - Vxx)) + 4aaoo + aGgg))
EIVS(x))1 S
(8)
M
where 0r,, and are constants defined as follows:
a0 A 3TmML
9(M mm)²²
+5KL2 (
(1+ (1+Lama) Lnma)
+(2 3lmmm)))
2M
M
A 9(M - m²)
0G
(1 + LIME) +
2
+ +..mm
2
and V-) is defined as V(x.) [(x,) + -u 3n x x.- 113, mn' is the number of updates in the memory space with no time delay (Tr, = 0).
Remark 5. To see how stringent the conditions for learning rates in Theorem 4 are, note that Eq. (4)
implies that O(mpL + T K + +TK + =k?mm/ < 1. With a sufficiently small learning rate 7y
for given bounded time delay and maximum local steps K, Eq. (4) can be satisfied. Eqs. (5 (5)-6) imply that (3p, [3 is non-negative decreasing series with difference O + r/² T). As
result, 3o = 2(pp) + n² 7²). Plugging it into Eq. (7) yields that the update term G. should be
larger than the variance term o f./ /M, which can be satisfied if the number of workers M is sufficiently large or of is sufficiently small (i.e., workers use a sufficiently large batch size).
By choosing appropriate learning rates, immediately have stronger linear speedup convergence: Corollary 3 (Linear Speedup). By setting nL = - and n VM, the convergence rate of the AFA-CS algorithm for general worker information arrival processes with bounded delay is:
Σ T
1
= o M1/2T1/2 (
+
K2 T
+
0
122
T3/2
1=0
Remark 6. Compared to Corollary [ we can see that, by reusing historical data, the AFA-CS algorithm can eliminate the non-vanishing O(oE.) error term even for general worker information arrival processes with bounded delay. The bounded delay implicitly requires each workers least participate in the training process, eliminating the worse-case scenario shown in Theorem [ 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 G(x;-7,.) 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.
8

---

Under review as a conference paper at ICLR 2022
1.0
Text Accuracy
Best Accuracy
077
577
S 15
Text S
Folles
lolley
488 (
A65
40
ABL C5
ADL-C
00 40 ao
200
220 140
20 49
300 140
20 40 s0
00 100 123 140
100 240 Communicatton Round
Communication Round
(a) p 1.
(b) 2.
(c) p 5.
(d) p 10.
Figure 1: Test accuracy for logistic regression on non-i..d. MNIST with different p-values.
Remark 7. AFA-CS achieves a stronger linear speedup O O(1/V DTT, 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 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.. 2018) by setting K = 1 (single local update), T 0 (synchronous setting) and (using full gradient descents instead stochastic gradients) and further improve the rate of
LAG (Chen et al.
Tr =
LSAG (Chen et al.
2020) from (1/vTT) to (1//VMT).
5 NUMERICAL RESULTS
In this section, conduct experiments to verify 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, 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. (22T): Li et al. (2019c)). Therefore, can use a parameter p to represent the classes of labels in each worker's is dataset, which signifies data heterogeneity: the smaller the p-value, the more heterogeneous the data across workers (ef. Yang al.] (202T); Li al. (2019c) for details). Due to space limitation, we relegate the details of models, datasets and typer-parameters, and further results of CNN and RNN to the appendix.
In Figure I we illustrate the test accuracy for LR on MNIST with different p-values. We use the classical FedAvg algorithm (McMahan et al. (0166) for conventional FL with uniform worker sampling as 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 that of FedAvg. This confirms theoretical results and validates the effectiveness of our AFA algorithms. We further evaluate the impacts of various factors in AFI., 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 spper-parameters are set as constant. Also, AFL coupled with other FL algorithms such as FedProx (Li et al., (018) and SCAFFOLD (Karimireddy et al./ (2200b) 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.
CONCLUSIONS
In this paper, we propose 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 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 the optimizer in worker's side.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Conference on Learning Representations, 2021.
Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In 2012 IEEE 5 IEEE Conference on Decision and Control (CDC), pp. 5451-5452. IEEE, 2012.
Dmitrii Avdiukhin and Shiva Kasiviswanathan. Federated learning under arbitrary communication patterns. In International Conference on Machine Learning, pp. 425-435, PMLR, 2021.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Tianyi Chen, Georgios B Giannakis, Tao Sun, and Wotao Yin. Lag: Lazily aggregated gradient for communication--fffiieee distributed learning. In NeurlPS, 2018.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Lasg: Lazily aggregated stochastic gradients for communication-efiin -effetiinnnnfee distributed learning. arXiv preprint arXiv:2002. 1360, 2020.
Aaron Defazio and Léon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. arXiv preprint arXiv: 2018.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-236) 2013.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint
2019.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mchryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.03600 2020a.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sehastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143. PMLR, 2020b.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd on heteroge- neous data, arXiv preprint drXiv:1909.04715. 2019.
Jakub Konecný, H Brendan McMahan, Daniel Ramage, and Peter Richtárík. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv: 2016.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Nicolas Le Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In NIPS, 2012.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based based learning applied to document recognition. Proceedings of the IEEE, 86(11):2288-2324 1998.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint arXiv:7812.06121 2018.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. arXiv preprint arXiv:1908.07873 2019a.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. arXiv preprint urXiv:/908 10497, 2019b.
Xiang Li. Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang, On the convergence of fedavg non-iid data. arXiv preprint 1907. 1899, 2019c.
10

---

Under review as a conference paper at ICLR 2022
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pp. 3043-3052. PMLR, 2018.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication-effiiieenn learning of deep networks from decentralized data, arXiv preprint arXiv: 2016.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- tional Conference on Machine Learning, pp. 4615-4625. PMLR, 2019.
Feng Niu, Benjamin Recht, Christopher Ré, and Stephen J Wright. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. arXiv preprint arXiv: 106.5730, 2011.
Thomas Paine, Hailin Jin, Jianchao Yang, Zhe Lin, and Thomas Huang. Gpu asynchronous stochastic gradient descent to speed up neural network training. arXiv preprint arXiv:1312.6186 2013.
Zhaonan Qu, Kaixiang Lin, Jayant Kalagnanam, Zhaojian Li, Jiayu Zhou, and Zhengyuan Zhou Federated learning's 's blessing: Fedavg has linear speedup. arXiv preprini arXiv:2007.05690, 2020.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecny, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint
00020 2020.
Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, and Carlee Joe- bee-ong. Towards flexible device partici- pation in federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 3403-3411. PMLR, 2021.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Progranming, 162(1-2):33-112, 2017.
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.0976 2018.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effiieee sgd algorithms. arXiv preprint arXiv: 1808.88576 2018.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective
inconsistency problem in heterogeneous federated optimization. arXiv preprint arXiv:2007.07481, 2020.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, al. field guide federated optimization. arXiv preprini urXiv: 100.:22077.9111 2021.
Shigiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. JEEE Journal on Selected Areas in Communications, 37(6):1205 1221, 2019.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint 1rXiv:1903.03934, 2019.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non- { federated learning. In International Conference on Learning Representations, 2021. URL / h/tpgr/i///peereiie... hwtp:/wwwwwweeeeeeee....m.eeeeee n hwtp:/nnntttttteeeeeeee id= jDdzh5ul-d
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
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, pp. 7184-7193. PMLR, 2019.
Xin Zhang, Jia Liu, and Zhengyuan Zhu. Taming convergence for asynchronous stochastic gradient descent with unbounded delay in non-convex learning. In 2020 59th IEEE Conference on Decision and Control (CDC). pp. 3580-3585. IEEE, 2020a.

---

Under review as a conference paper at ICLR 2022
Xinwei Zhang, Mingyi Hong. Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data, arXiv preprint arXi::2005.11410 2020b.
12

---

Under review as a conference paper at ICLR 2022
Appendix
In this supplementary material, 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, assume subset M, of workers to be used, with |M,] m. We use G; to represent the local update returned from worker i [M] given global model parameter x Xt- Also, define Kt,; -K,s V where x! represents the trajectory of the local model in the worker. We use A, to denote the average of the full gradients long the trajectory of local updates, i.e., (xxx) Ke, Σك= I fx((). With the above notations, we are now position to present the proofs of the theoretical results this paper.
(x,)) -
A PROOFS OF LEMMA I AND LEMMA 2
We start with proving two results stated the following two lemmas, which will be useful in the rest of the proofs.
Lemma 1. [x.] =x(x)), (x.) (x S oo. [M]
Proof. Taking the expectation of G; (x+), we have:
K
B [x.] = E
V(((x(
K
j=0
Ki--1
EV fV Er,))
Ki,
1=0
(x)x).
Also, by computing the mean square error between (x;) and (x,)), we have:
K
E| (x.) - (xx)) [|l
Σ
[x((()
K
j=n
K
K
Σ
[x((1)
K2
1,5
1=
==
Kra-1
Kra-1
E [ Exd) - Σ
{x(())
K
j=0
j=0
oo
This completes the proof of Lemmal I
E G.(x)-na))1
Lemma 2. For fixed set Mr with cardinality
E
EiEM, (x moo
Proof.
By the definition of variance (E[(X- [[X]]]== E[X - [E[X] we have:
E Σ G((x++
E
Σ Gx(xe-Ta)) - (x + Σ (x
iEME
IEM.
iEM
I <mo +
Σ Ax(x--T,))1
iEMi
Here (Gx(x)))..) (x(x)_.,.)) forms martingale difference sequence.
13

---

Under review as a conference paper at ICLR 2022
B PROOF OF THE PERFORMANCE OF THE AFA-CD ALGORITHM
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 make any assumptions on the worker information arrival processes except the independence of workers' participation. For uniformly distributed worker information arrivals, M, can be viewed as subset with size 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 ct al. 2021 Li et al. 2019c).
B.1 LOWER BOUND FOR GENERAL WORKER INFORMATION ARRIVAL PROCESSES
Theorem (Convergence Error Lower Bound for General Worker Information Arrival Processes). For any level of heterogeneity characterized by aG. there exists loss functions and worker participation process satisfying Assumptions for which the output & of any randomized FL algorithm satisfies:
E f( (lo²))
(1)
Proof. We prove the lower bound by considering worst-case scenario for simple one-dimensional
functions. Let the FL system has two workers with the following loss functions: fi(x = (x
(x G) fxx
(x) + f2(x)) = x G². It is easy verify that V fxx)
ff(x) S 4G á and (x)) [x < 4G og. We consider special case for the general arrival process when only the first one worker participates in the training, equivalent to
optimizing (x) rather than / (x). In such case, any decent algorithm would return & -G + c,
where E is a small error term. As a result, E|] f ((a2).
B.2 GENERAL WORKER INFORMATION ARRIVAL PROCESSES
Theorem 2 (AFA-CD with General Worker Information Arrival Processes). Under Assumptions 73 choose server-side and worker-side learning rates 1) and πr such that the following relationships hold: 180T,, K2ILTT= < and L + +3 +3r2LLnn'' < 1. Then, the output sequence {x,} generated
by AFedAvg-TTSS -SL---SRCCC CD with general worker information arrival processes satisfies:
4(fo f4) A(aro) + agod).
Σ [
MiT
where 0.L A
2 +
37 2
15 KL
and og 1,22
2m
Proof. Due to the L-smoothness assumption, taking expectation of f(x(+1) over the randomness in communication round we have:
[[f(x++1) < f(x:) + (x)(x)), E[x++1 xel) + E[[|x++1 x
A
First, we bound the term A₂ as follows:
A2 = E||x++1 1 - 12
1 m
n,²nn, E
Gx(xx
m
(al) 7
A (x
1|
oz
where (al) is due to Lemma 2
Next, we bound the term A₁ as follows:
A (V)();), E[xx+1 xx))
14

---

Under review as a conference paper at ICLR 2022
m Σ
R
G (x(x)na))
1=1
(a2) 2 ML [x
1
Mall
Σ
(x + 2 ML [V 1
(x (x )|
2
1=1
As
where (a2) is due to Lemma and the fact that (x,y) = 211x11 + ||yl² - ||x - y) To further bound the term A3, we have:
1 m m
A3 [Vx(x)
(x
V fxx)) (x
[V - +x - +
- (x(x
(03)
(x,) 4 f(x(-Te)))1 (()
+ 3 V fi( - (x
(ad)
3L
m
m
||x m 2 -30g + m
(x (x1
m
A4
where (a3) followings from the inequality ||x] + x2 + + xx < > | /x,11111. 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:
A =
1
Σ
Ix:
xe- 1
171
AE mm)
(05)
S
Xx X xt-
=
Xk-1 xx112
km k
MM Σ
(x ?
=
k=t
iEMi
= E
Σ
Σ
Gi(Xk-To,
m
k= Te,u TEM2
(06)
Σ
G2(X !112
<
m²
k= A=t-Te,a
iEMs
(07)
17 T
t-1
Σ
Ax )13) rmoi] +
<
m
kos TE,
iEMo
15

---

Under review as a conference paper at ICLR 2022
In the derivations above, we let argmax ||x, -xe-rs I1?, which yields (a5). Note also that the maximum delay assumption 2 Tke Vi [M] implies (a6). Lastly, (a7) follows from Lemma 2
To further bound the term As, we have:
As- (x)(())) (((x)
Ke,s-1
= VV
[xx((--T,,)))' )1?
Ki
j=0
Km--1
IV - v(((x 1|
= K1,5 j=0
1 K1
(08)
|xX-TL
x
Ki
1=0
As
(o9)
S 5K,, I 12 (o) + (K,, + 30K3
/ )l?
(m10) < 5K n - 30
where (08) due to the L-smoothness assumption (Assumption 1), and (a9) follows from the bound of Ag shown below. Here, we denote maximum number of local steps of all workers as K, i.e., Ki,s S. K, Vt,i. i. This definition of K implies (a10).
Now, it remains to bound term As in the derivations above. Note that the bounding proof of As in what follows is the same as Lemma in (Reddi et al. 2020). we restate the proof here in order for this paper to be self-contained. For any worker in the k-th local step, we have the following results for the norm of parameter changes for one local computation:
Ag = = xx| = [i[| x - - X, - 71.6
- B A-1 Xx - 36-n ( VS(( + V - v.((xx))
+ (xx:) vf(xx) + V (xx:))111
$ (1 + 2K- |E[ X 1- x, - VFx(('
-
GK ML (V [((( [ (VI, -V((x)))1
+K |I f
51++ 2K DE[1 x- xx + + + -KK B1IBI - x,l1
+ [KKK)] 066 + 6K| n1 {1(21)
= =11 + 2K
+ 6K 1/ L 11
xel1 + ni
+ 6k(m)
(al1)
1
2 (1+
+ K - 111x
xel1 + o + 6K
6k M/ (xxx))11
where (al1) follows from the fact that bズ + 6K < マー if < पशズ 3
Unrolling the recursion, we obtain:
--
E||| x| - x. xx11 S Σ (1 +
K - - +
+ +
0=
S (K (K-1) + K - )k - 11b2 + +
< 5Kn (o,, (KK + 30K 1/ [xx
16

---

Under review as a conference paper at ICLR 2022
With the above results of the terms A1 through As, we have:
L
B[f(x++)] - f(x))= < (Vf(x)), E E|x++1
xel)
Ell X(+1 xel1
2
A1
A2
1
2 mLll,
(x
ML [Vx)
-
Σ
(x
2
==1
Aa
mi
LIfUi of.
+
Σ> 1
111
m²
m
i=1
1
m
Tnp m²
m
Lapui of
2 Mh [
mell
(x 312+ +
A (x )122
m i=1
m
3
31
1
m
37ML
+ SMLLE +
1MLL
| X1-Te,1 112
fi( ) (x 11
2
m
2m
As
A
Ln
Lnfnni o2
mL [Vxx))
2 ML
A A (x.- 01
(x A [ re. )12 1/
2
m
3
3L2 +
(x(x-re),) + rmo
+ 2
2
MM7
m2
31m
1 m m
+ 2
[5K
" (oz + +6Ko)) + 30 I
[
1
m. [Vx(2))
ML
45mm R2
V
)1?
2
Li
m
3T1j"11
m
Me,
(x4 -x, 0112
Σ
1>
A [xk 31. )112
2m2
m²
2m2
k=1-Te,
Ln
15mm KL
3
02 +
ML + 2 12 o
m
2m
Summing the above inequality from t= 0 to TT yields:
Ex(xT)
f(xo)
T
/ + 45mm K2mm?k21'0 2 1
MLL
V f(x fxx 1|
2
1=1
37 1,
Me
Ax(xI
A (xx0-11))11
2m2
m²
2m
L=
im1
km Te..
L 2
37 L2
15mm KL
3
+ 245K2 12 0%
+ T
07 + T
TI
778
2m
2
(012)
1
$
2 mn + 45m² K2 22T
[V,((x))1
37 17 mi nn
m
ML
+
A (x
2m 2
m²
2m2
t=
+
Ln
3r 12222n ni.
15mm K2
07 + T
- MT + 45K2 T.2 45K2T?2m 1.
3
0z
m
2m
2
2
17

---

Under review as a conference paper at ICLR 2022
(o13) 7-
ML [ Vx(()))
Lami 372121101222
15m 15 KT2
3
+ T TymL
07. + Tyme
+ 4 1. og
2m
2
2
T-1
(e11)
Σ
f + Tyme oozo + tco
where (a12) is due to maximum time delay T in the system, (a13) holds if 1 s 1 45m K2
ie., 180nf,K2L' L2T 1, and
La Ln'ni oz 3L"r"" mi
I 0. i... 2L7ML + 3r L' 17 n² - 1.
2m
m²
2m
Lastly, (a14) follows from the following definitions: at
2 +
3- 1,27,,
2m
+
15m7 kI?
2
aG
1 + 4 Rearranging terms, we have:
T-1
4(So (.)
[V(()))
+ + +GG
ML
and the proof is complete.
Corollary 1 (Linear Speedup to Error Ball). By setting vr. v and 11 = vm, the convergence rate of AFA-CD with general worker information arrival processes is:
1 T-1 E [
(
22
K2
Σ T
m//2211/2
+
O
Proof. Let 7T. = - and = v /m. It then follows that:
2 11/27//2 + +
a7 0
K2
0G aG = 0 + +0
T
This completes the proof.
B.3 UNIFORMLY DISTRIBUTED WORKER INFORMATION ARRIVALS
Now, we consider the special case where all workers have statistically identical speed that the worker information arrivals are uniformly distributed. As mentioned earlier, this special case acts as widely-used assumption FL and could deepen our understanding on the AFA-CD algorithm's performance in large-scale AFL systems.
Theorem 3. Under Assumptions 7 3 choose server-side and worker-side learning rates and
such that the following relationships hold: nî - < 1, 120L "onL""""f 4(Lmp
12312 ni. 72) M-m
/ " (90K<2 L + 3r) 1. Then, the output sequence {xt} generated by AFA-CD with uniformly distributed worker information arrivals satisfies:
T-1 Σ
T
<
MiT 4(aLo) - acoo))
(3)
where 0, and ag are constants that are defined as:
[ LaME
22 55T221) + (Tami + 1211211(72)
M - m
ar A
+
m(M - 1) (15KT2n
m
m
M m
0G A
30K2I.2 + (TamE + 12 m M 1)
(90 T +3)
18

---

Under review as a conference paper at ICLR 2022
Proof. The one-step update can be rewritten as: X(+1 x; -my G. For cross-device FL, G. 1 EieM, Gx(X,_r..), where Ti, is the delay for client i in terms of the current global communication round t. When Tt. 0, Vi M,, it degenerates to synchronous FL with partial worker participation.
Due to the L-smoothness in Assumption 1, taking expectation of (x++11 over the randomness in communication round f, we have:
L Ell x(+1 - xi11
B[f(x++1) S f(x)) + (x((),, E[x(+1 - xil) + 2
Aa
We first bound A2 as follows:
A2 E X| - -x,1 1|2
1 Σ
- [E|
G G
iEMM,
(61) n
E
Ax (x )l1 + mo?
m12
I m
E
Li
(.)A M1
of.
where (b1) is due to Lemma assumption.
2 and (b2) is due to the uniformly independent information arrival
To bound the term A1, we have:
A = [x)((x;), E[x++1 - xx]}
MM (ff())) E. m seM;
Σ (xL-)
(83)
mM (fxx)
Σ (x(x-TT)))
M
xE[M
(64)
2 mm V fxxx)11
mill
Σ
M
(E[M]
vf(x)) - M
1 Σ (xt-Te))
+ 2 TL
kE[M]
As
where (b3) is due to the uniformly independent worker information arrival assumption and Lemma (b4) due to the fact that (x, y) = [[|x||2 + ||yl| ||x 2
To further bound the term Ag, we have:
A3 = [Vx
Σ (x
M
RE|M
(B5)
(x.)
(xxx |1
M
ME
1
Σ [V((x.))
M
M
1
Σ
V)((x)) V)((x-n.))) - - (x(xx-77.))) ||
M
M
19

---

Under review as a conference paper at ICLR 2022
(b6)
2 V - V 211 - (x 211
M
[E[M]]
(67)
21
M
112+2
2
M
x
fi(( - (x
M
M
As
A4
where (65) is due to the fact that fx(x)= Mo EiEMM (x)) (66) follows from the inequality ||x + X2 + ..... + xall² S n Ei= |x,|?, and (b7) follows from the L-smoothness assumption (Assumption 1).
For Ai and As, we have the same bounds as in the case of general worker information arrival processes:
A4
S
R
Σ Ax(x + rmoil
m2
k=
NEMe
M
T
(iX rmo?
m²
k=l-Te.
As < 5 + 6Ko2) + 30K3 ((x
With the above results of the term A through As, we have:
[x S V fxxt), Ee(xe+1 - xxo) + L
Ee
Bellxxi+1 -x, 11?
2
11
A2
mL [fxx)]| [ 2 2 1
Σ Ax(x( + *2mm || [V((x))
1
Σ (xx
M sE[M]
M
kE[M]
As
nf m²
M
LaR of m
T(i E (x
21
2 m/
V 21
2 m.
1
1
Σ
no 1112
Loioni m²
E
Σ
M
Tii E Mr) Ai (x
M
iE[M]
1
2
2 M
Lai oi
2 7
Xt
X X
V fi(t - (x )11
M
M
m
1=1
As
Aa
$ 2 mEl fx(x)))
1
2 =
1
1
Σ
A -,, 111+
Ln E m²
Σ lif (x)
M SE[M]
11212 T m²
+ +mp 1?2
E
ile Me),
fmott)
Te.p
5KL 6Ko2) + 3 LZ M
1 Σ [V
Iof2ni 2 m
of
+ miL
ME[M]
(18)
[mtll (30m
fx ) (307) 122
+
MUL
L Σ 1((x-1)))1
M
12
E
M I Mi),
2M
m²
1=1
20

---

Under review as a conference paper at ICLR 2022
mi
M
Σ
E
Σ
T(i T (x)
m²
k=t-TeP
LL + 5 nz.
+
o
+
+ +30nk2L27) o2:
17
m
where (b8) follows from j == argmax [ar) [V 11 Note j is dependent on but we omit it for brevity.
Summing the above inequality from == 0 to = 1 yields:
Ex(x) fxx)
+30 (x, (x 01
ML
Ln Σ 112
El
M
(
2M
m²
1=
(E[MS]
L m2 t
1-1 Σ
Ell Σ
liee (x) |1??
m²
SE[M]
mn
72 LL2 mi
T
+ 5kkLL + +30nk2 22
m
m
(00)
T
Mr. [(x)) + (30m 2 1T
Lniani m²
MA
Σ (xxx)_))))1
E|
Σ
Lii e (x
2M
1=
<E[M]
(E[M]
L L" 3
E
T (x
m²
KE[M]
Lni
L2
+ T 07
+
+ +5KnL2'1)) + 30m
where (b9) is due to the fact that the delay in the system is less than T.
By letting z, (x) (omitting the communication round index t for notation simplicity), have that:
M
2
2
Σ
1|z,12+
Σ
Zj);
BE MM
(b10)
Σ
M |2:11
Σ
||z - 2
2 isj
[c(M]]
M
E
Σ
Ii E M,zz,1=
Σ P Mobllzol? + Σ Pfi,j E MeH(z,,zz)
VE M
it1
(b11)
1| + m(m - 1)
M(M - 1) Σ
(2 2j}
M
RE[M]
(b12)
m²
||2.112 m(m 1)
Σ | - 12
M
2M( -
KE[M]
where (b10) and (b12) are due to the fact that (x.y)
= b|lli| 2+ ||yl| 1|1x||11 - +|||x|2++1x+ [2],
(b11) follows from the fact that P(i- Mi}
m and P(i.j Mi}
M(M-1) It then follows
mfm-1)
21

---

Under review as a conference paper at ICLR 2022
that:
M
Σ
M
zi
Ln
QT. m²
E1|
Σ
M
l(i
M,]zil?+
+
L2 12 m²
BB1 Σ
M
li Mi]zil?
2.
Ln
122 M
M
MM
+
||z;|2
2M
M
i=1
MILL
Ln
m
1)
Σ
12: - -2y11
4M2
m2
m²
2M 1)
i71
MM
+
Ln
m2 M
MM
Ln mL
1.2
m(m 1
11
Σ
M
|
2M
M
2M
m²
m²²
(M - 1) 1
La
1.2
3
r²
m(m - -1)
M
+
+
Σ
||
M
M
m2
m²
(M
xm1
M m mM (M 1)
(L. ni. 12n)"mi,²))
Σ ||,112
Note also that:
||2.||2 | (Xe- T.. )112
| (x)- V Tx - Vf((x-TT.)) - 1)12
S 3/| A (x - f.((xx )1 + ((( Vf(x +3 f
$ 3 ( - (x n. )1 +300 + 3/
As
Using the above results, we finally have:
Ex(x)) f(xo)
1
MLLIVS((XII1 +
(xx))1
2
Lninn m²
M
Me
Axxx-1)))
BB
Li E (x
2M
17 mL 2
M
E
Mi E (x)A
m²
Ln
L
+T
of
+
+ 2 2
2 MMLlIV
[(Lm"ni ni + 1)
m(M - 1) [115LL L 2 nn (o 6Ko2)
M m
M
12 1/ M
1
Σ
||V 12 + +30 + M Σ [V
SE[M]
72 1
+T
+
+ 5KnL2n)) + 30m L 121
m
m
mxx))x((x))l'xx
22

---

Under review as a conference paper at ICLR 2022
L - 2 + 301 30L2 + + [Lmm + 12
M m m(M - -1
(00K +3))
+ x
LIML + L + +5KL2n)) + (LyML + =)
M m
m(M (15kL222))
M - m (90K L3 + +3) m(M - 1)
+ [30K2 + (Lomz + 1131)1277
(b13) 1
MmlVV Tym. an.o + tc02)
where (b13) follows from the fact that
M - m
- 2
30L2K3n2 n/. [(LMML + +L2
(90k>LL''? 3T)
m(M 1)
if 120L2 K3 mE + 4(LML =[²n)"1(=²)
m(M-MM 11 (90K> + 33) < L
M-m
aL [( LAML +
~L221122 5KL + (Lym + 1'1)"11177
M m
(15KL2T1))
m
m
m(M 1)
and
M (90K2 + +3] m(M - 1)
aG = [30 + (Lmm =).
Lastly, by rearranging and telescoping, we have
4(J0 Sc)
T Σ [lV)(x))|
4 aco2]
miT
This completes the proof.
Corollary 2 (Linear Speedup to Stationary Point). By setting nu = vT and rj = mm, the conver- gence rate of AFA-CD with uniformly distributed worker information arrivals is:
2 T
K² T
K2
K272
E (
= O m//2/1/2 +
O
+
+
+ +0
T 1=0
m 1/233//2
7
Proof. Let 7L
v and 17 mm. It then follows that:
a1 0( m1/2T1/2 + 22
1
K +0 0
K
Kr²
( 0
+
ml/273322
72
aG 0 m + 0 x2
+ + K2
K2
K2T2
0 m
m + 0
T2 )
T
and the proof is complete.
C PROOF OF THE PERFORMANCE RESULTS OF THE AFA-CS ALGORITHM
Theorem 4. Under Assumptions 7- choose sever- and worker-side learning rates n) and πı in such a way that there exists non-negative constant series T=) satisfying the following relationship:
12LmE + 540(M m²)
(1 + Lamr) + + 180K 3200. K2 <1, (4)
M
19MM - m²)
77
(1 + Tami) 331. + (But1 (.,) S 0,
(5)
2M2
23

---

Under review as a conference paper at ICLR 2022
1(M 1MM - m')?
(1 LmmL) 3r 50- 50,
(6)
2M2
3
1
2M
L
12 Boymr) G.
the output sequence } generated by the AFA-CS algorithu for general worker information arrival processes with bounded delay (T == (T satisfhes:
T-1 -E
- +
BlV
+
mi
where a and ag are constants defined as follows:
3LMTL
9(M
m²)
3 (1+ Lnmr.) (1+LmT))
+ +5KL2 12
+(2 3Lmmm)))
2M
M
9(M - -m')2
OG
(1 LAME)
+(2 +3lkm)))(3kk
M²
and V-) is defined as V(x.) A [(x)) + Ex= 3ul xx- - Xt-u-1 11?, mn is the number of updates in the memory space with time delay (Tt,) 0).
Proof. We divide the stochastic gradient returns G, into two groups one is for those without delay (G,( i Mr, MMl m') and the other for those with delay (x+.))7) E Mi, [M1
M M'm')
Then, the update step can be written as follows:
X++1 X2
Me
Σ G((x))+
+ Σ
(((xe-ra))
(10)
M
iEM.
iEM;
7
Σ
G((x))+
Σ
- -G(e
(11)
.E[M]
iEME
Due to the L-smoothness assumption, taking expectation of f(x(+1) over the randomness in commu- nication round t, we have:
E[f(x++ s f(x)) + (x,(),, E[x++1 x1l) + L Ell X,+1 11
A1
A2
We first bound A2 as follows:
Aa
[[[[x++1 Xx [2]
Gx(x,) + Σ G((xe-ra))) 19
B
M2
ie.M
iEME
'f'n2 B
[Gi(x.) Ax(x:)
M
iEMM
'1
Σ (G((x)mm.)) Ax(x)-1()) + (x(x)m)))) (x(x:)] + Σ (x(x)))
SEME
SE(M
3 Mi.
Σ (G.().) - A((x)]+ Σ (Gi(Xe-T(.) (x 2
M
iEMe
REMS
22
+ E
Σ |x,
A((x))]
+E
Σ (x
iEMM
xE[M
1/
3(M m)))
307
2
122 Σ ||))())) - Ax(x 12
|| Σ 2x(xi)12
00
M
2
M2
NEM;
[E[M]]
24

---

Under review as a conference paper at ICLR 2022
31 mz
3(M ml)
$
o7. +
,....
Σ
|4((x)) - -x
M
M
iEM;
6772
Σ
[4,(x;) - vx((x)))1 V
M
iE[M]
To bound the term A1, we have:
A [ X,+1 xi)
-E
(x(x);
Me
Σ Gi(xx)+ Σ Go(
M
iEM
iEMB
Σ Gr(x)) + Σ
(i(
2
2M2
iEM.
BEME
1
Vf(x)))
1 1 Σ Gx(x,)+
+ Σ (((xx-T))))
2
M
i.M.
iEME
(41)
Mi
| [xx)
177 E1
2
(X++1 - xx)]1
2
1H1I..
1/
E|| Σ [V,((xx,) Gx(x) + Σ [V/((xx)) (x1x111))
2M
iEM.
SEM;
ML
| fxx:)11
1 -
2
21/7..
177L +
E
Σ [x((x)) - Ax(x)) + A:(X)) (x,)
2M
i.ME
[V(((x)) - (((x))+ ((x) (.(X)TT))) + -i(x - G((xI-T,1)]
+
M.M;
MML
V fxx:)11
1 -E|x++1- x2
2
24pTI..
+
E
Σ (xx, - (x))++ +
Σ (x)) - Gx(x)]
2M
[E[Md]
Σ (x,) (x(1-T())) + (x(x(t)))) (XL-Trr)) 2
iEME
< 2
M
V f(x))11
2//11.. -El(x++1 - x+11++
37ML
E
Σ [Ax(x)) (x
2M
iEMM
31111.
- Ai(2)) /
-
2M²
iE[M]
[Ax(x)) Gx(x:) + Σ A.(x--T.)) Gx(
2M
NEM.
iEM
M
fxxx))1
1
E E1 x
X
3(M - mm' m'mME
Σ E A((x))
(x(x)_))))) 2
20MT
2M2
iEMS
379L
- - (xx)))
311 0f.
+
2M
2M
KE[M
where (cl) follows from the update step of the algorithm specified in Eq. 10
25

---

Under review as a conference paper at ICLR 2022
Combining A1 abd Ag, we have:
L
[[f(x++1]] f(xx)= S (V)())), E[x++1 xel) +
E
Xx+1 Xx
2
A
Ao
<f(x,) MM | (xx))2
1
|E|xx11 - x:112
+ 33M m m'mm
3L m ?
Σ iEME
E
Ax(x))
- (x
2M
2M2
C1
31M
+
+
(f((x)) (x(x)
2M
M
REIM
3TM
mZ
+
o7.
07. n
(12)
2M
2M
For each worker i, we have:
C2 = [[v)((x)) (xx))
K..-1
[[V]((x))
Ke,i Σ
{x((2))1
Σ
[V,,),, vx((2))
Kr j=0
Kra-
T.2
x
Ki
j=0
5KL 5KL (o + +Kog)
where (c2) follows from the same bound of A6 specified Eq.
Also, note that:
C1 (xx,) .x)
$ (xx) v)((x)) Vf(( - 2 / - (x(x(-r,
< (x,) v V/( -
) (x )1( +3. x1-
(x,) fx 11 Vf( (x) +3L
Σ X X1-1-111
S (x)) V)((x)) V/ A. (x:- )112 3r L2
X X1-1-1112
where is the maximum delay, i.e.. - max Te.) Vt E [T] E [M]. Plugging C1 and C22 into the inequality in Eq.
12
we have:
L
(lf(x++1)1 < (V)(x)),, 1[xe+1 xx))
E elllxe+1 - xxel2
2
d1
<f(x;)
Me
[xx))
1
IE] [E||x=+1 - xel12
2
21/1TT.
(9( - mmmmm
9L( m ?
+
Σ E
V(((x:) A.(x;)
2M
2M
NEMs
26

---

Under review as a conference paper at ICLR 2022
9(M - mdmm
9 - m m
E
(x((x ((
2M
2M
iEME
(M - mmmmm
9L(M - m n2))21 2
37L
E
Xt-u
2M
2M2
4=0
+
+
(xi( - (x(x))
2M
M
KE(M]
3M
2M L + 3
02 +
3La/ n/ V [x(x))1?
2M
<x(x)) ML | [xx))1
1
EE| xx|xx+1111 - x+11
9(M m²)
+ ((2 3 + 3.T.m1)) (5KT 6Kog) 303 V[x
+ mm
(1 + TaME)
2M²
9(M m²
+ MM
(1 L7ME)
(5KL2 + +6Kog)
L' 2
Σ VF(xx=r(,)11)
2M
M m iEM
9(M m²)
T-1
+ 1771
(1 (1+ LMMr.)
3r
E
Xt-n X, x
2M
10=0
31ML
I G.. + 3L n/. V fxx:)12
+ 2M
T +
2M
9(M - m²)²
+ =(2 + 3Lmmm) 30K ) 3LMLL V f fxx))1
3
=f(x)) 1M7
(1 + LMm
2M
19(M - mm')²
E1 x
xel2 MM
(1 LMML) + +12 + +3LmmL) [5KL ( + 6Koo)l
27ML
M
19MM m²)²
+ 1771.
(1 LTMr.)
(30K2L22
Σ [x,
2M
M m
99M - m²)²
37M 2
3L 2
+ 177
(1 LMML)
3rL
E Xi-u X
2M 0f,
2M 0
2
u=U
Now, define Vxx)) f(x.) + Bu Xc-u-1l13. Based the above bound of [[f(x++1)] - f(x)), it then follows that:
EX(x++1) - V(x.)
=Ef(x+1) - (xx:
2-2
+ Σ (Bu+1 -
X2 x----111 +Bollat41 - x111 B7-1 - -x---211
[
(9MM - -m²)2
3 (1+ LamE) + + 300K 3L [xx))
5 1/
2
2M2
9(M
m²)²
(1 Tamr.) + +12 3
+3Tmm.)) [KTT2 + +KKo2)
+ 1/7
M
9(M m²)²
+ M77
(1 + LnmE.)
(30K M Σ
2M2
iEM
99M - m²)
T-2
+ |MM
(1 + L
3TL2² + (Bu+1 - Bw))
Σ
IE
Xt-u - X
2.
a=0
27

---

Under review as a conference paper at ICLR 2022
(9 ml)?
+ lmz
(1 + LTML) 3T - -8--111x(---1 - X x1-1-2
2M2
311L
02 + 3L
+ (50
||12411 - x211² 1
2M o..
21/LLL
2M
Telescoping the above inequality from 1 = 0 T - 1 of the above inequality yields:
EV(xT)
(xx))
S ML
Σ
1
19( m²)?
(1+ LMML)
(2 + 3Lmm))
3
30K2
3LmM [Vx((x))) 1|
2
2M²
1=0
9(M
m²)²
(1 + Lnmu) (n--imi) (30K
T-1
+ 1
Σ
[V
2M
M m
JEM;
9(M m²)?
(1+ LMML) + +(2 +3Lmm)) [5KL mn 6Koa)l
3
+ MLT
M
9(M m2)
T-2
MML
(1 + L
3TL2 + (But1 - Bu)l
Xt-u X x
2M
4=0
C3
9(M m²)²
(1 + Lami.)
3r B7-1] [|xt---1 xt-1-211
2M
C4
1
3mmr.
3LT
+ (30
| x=
07.
oT.
2
2M
2M
C5
(c3)
1
T-1
V (xx))12
4 ML
3L.TML
+ 5TKK3 TI (9MM - m/)2
(1 Lami) + 3. 15+3Lmm)
)o2
+ mm
2M
M
9(M m²)²
(1 + Lamn.) + ( + 3lmm.)) (30K3 (30K2T22,))''s
3
+ m
M
where (c3) holds if the following conditions are satisfied:
1
1
99M m²)²
3 (1 + LMML)
=/2 + 3Lmm)) 300 3LmML
4
2
2M²
19(M (9m)2
(1 +mm))) (00TK2L?'1))
2M2
9(M - m²)
C3 [ML
(1 + L(ME)
3TL2 + (But1 -Bu)] 0,
2.
9(M m²y²
C4 [M/r
(1+ LmmE)
3TI² - 9 50
2.
1
C5 5 +
2 <
3)
2M
2
By rearranging the inequality, have:
T-1
1
[xx(21)
ML
28

---

Under review as a conference paper at ICLR 2022
<V(zo)
(x(TT)
3LMM
19M -m')2
3 (1+ Lama) + 1/2 + ++3mmm))) oo2
+ M.T
5KT.
2M
M
19(M m²)
(1 + LimL) + ( + 3Lmm)) (30K2
+ MLT
M
That is,
T Σ
4(V(x0) - -V(x))
E
+ 4(azo? + agoāgh
T 1=
MLT
where az =
3Lmm 2M
+ 5K 2
9(M-m') M
(1 LiME)) + ( +LLmL))
ag
[0(M-m'P (
M2
(1
LIML) + + + 3LmL)) L37)) This completes the proof.
Corollary 3 (Linear Speedup). By setting Wi = - and n = VM, the convergence rate of the AFA-CS algorithm for general worker information arrival processes with bounded delay is:
1 T-1
= o M1/2T1/2 ( +0
K2
K²M
B V
T 1=0
T
T3/2
Proof. Let 1/r. V and 11 M. It then follows that:
al 0 M1/2T1/2/ /2 +0 K KM1/2
T ) 0
T3/2
ag 0 K2
12
( 0
T3/22
This completes the proof.
D DISCUSSION
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) == M. ΣieM, f((x).
For uniformly independent sampling, the surrogate object function approximately equals to f(x:
t EM fi() in expectation, i.e., B[](()) = fxx However, the surrogate object function f(x)
may deviate from (xx with arbitrarily independent sampling. More specifically, for uniformly independent sampling, the bound of fx,) f(x,))l is independent of og (Ag term in B.3 On the other hand, for arbitrarily independent sampling, // (xx)x))=(xx)) <((r)) (Ag term in B.2
This deviation may happen in every communication round, so it is non-vanishing even with intinity communication rounds. As 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. 20200. When we set 0 and K = K, Vt, i, AFA-CD generalizes FedAvg. In such sense, the convergence error also exists 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 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.
29

---

Under review as a conference paper at ICLR 2022
Variance Reduction: If we view the derivation between local loss function and global loss function V I og. Vi E [m], Vt as shown in Assumption 3 the AFA-CS algorithm is indeed a variance reduction (VR) method, akin to SAG (Le Roux et al. 2012
as global variance, i.c..
Schmidt et al., 2017). SAG maintains an estimate stochastic gradient v; i E [x] 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 (v) = V (ff(zz)) stored in the memory space, but then use the average of all stored stochastic gradients as the estimate of a full gradient update the model (Ie+1 = 2₁ :t 9t Ei= 0;). In such way, SAG is able to have 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 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.idd 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 (Konecný al.. 2016). The key difference is that we apply the VR on the server side to control the global variance while previous works foeus 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.
E EXPERIMENTS
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.
E. MODEL AND DATASETS
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.idd 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 Ll 2018) and are now widely used as benchmarks in FL. studies (Li et al. 2019c Yang et al. 10
For MNIST and CIFAR-10, 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 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 10, each worker has samples with ten classes, which 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 built from The Complete Works of William Shakespeare (MeMahan 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 sequence of 80 characters, embeds each of the characters into learned 8-dimensional space and outputs one character per training sample after two LSTTM layers and a densely-connecter layer. The dataset and model are taken from LEAF (Li al. 2018).
For MNIST and CIFAR-IO, we use global learning rate 7 = 1.0 and local learning rate T)r = 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 17 = 50, the local learning rate is 7 = 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, randomly choose m workers from [M] to participate in the training.
30

---

Under review as a conference paper at ICLR 2022
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 partici- pated worker choose 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 fixed local update steps, In contrast, each worker takes a random local update steps uniformly sampled from [1, 2 x cj for dynamic local steps. To emulate the effect of various worker's arrival processes, use uniform sampling without replacement to simulate the uniformly distributed worker information ar- rivals, 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 informa- tion 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.
Table I CNN Architecture for CIFAR-10.
Layer Type
Size
Convolution + ReLu
5 32
Max Pooling
2 x 2
Convolution + ReLu
5 64
Max Pooling
x 2
Fully Connected + ReLU
1024 x 512
Fully Connected + ReLU
512 x 128
Fully Connected
128 x 10
E.2 FURTHER EXPERIMENTAL RESULTS
Table Test Accuracy for comparison of asynchrony and local steps.
Synchrony
Asynchrony
Models/ Dataset
Non-i.id. index (p)
Worker number
Local steps
Constant steps
Dynamic steps
Constant Steps
Dynamic
Steps
p =
5/10
5
0.8916
0.8915
0.8888
0.8868
p 2
5/10
5
0.8906
0.8981
0.8901
0.8931
p 5
5/10
5
0.9072
0.9075
0.9059
0.9048
= 10
5/10
5
0.9114
0.9111
0,9129
0,9143
p = 1
5/10
10
0.8743
0.8786
0.8701
0.8734
LR/ MNIST
P = 2
5/10
10
0.8687
0.8813
0.8661
0.8819
P 5
5/10
10
0.9016
0.9050
0.9034
0.9065
= 10
5/10
10
0.9124
0.9135
0,9112
0.9111
P 1
20/100
5
0.8898
0.8973
0.8909
0.8938
P 2
20/100
5
0.8968
0.9007
0.8955
0.9000
P 5
20/100
5
0.9088
0.9088
0.9097
0.9078
P 10
20/100
5
0.9111
0.9106
0.9126
0.9125
p 1
5/10
5
0.7474
0.7606
0.7319
0.7350
CNN/ CIFAR-10
P 2
5/10
5
0.7677
0.7944
0.7662
0.777
P 5
5/10
5
0.7981
0.802
0.8065
0.799
p 10
5/10
5
0.808
0.8072
0.8065
0.8119
RNN/ Shakespeare
72/143
50
0.4683
0.4831
0.4606
0.4687
Effect of asynchrony, local update steps, and non-i.id. level. In table 2 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 synchrony with constant steps. When using asynchrony or/and dynamic local steps, the top-1 test accuracy shows
31

---

Under review as a conference paper at ICLR 2022
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 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 As the non-i..d. level increases (smaller value), the top-1 test accuracy decreases.
important factor for the model performance.
Next, we study convergence speed of the accuracy for the model training under different settings. Figure 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 10 and 5, the curves of all algorithms are almost identical. Specifically, in Figure 4 the test accuracy curves of the LSTT 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
1.0
1.0
0.9
Test Accuracy
0.8
Test Accuracy
0.8
0.7
0.6
Synchrony Constant Asynchrony + Constant
0.6
Synchrony + Constant
0.5
Asynchrony + Constant
Synchrany Dynamic Asynchrony Dynamic
Synchrony + Dynamic
0.4
0.4
Asynchrony Dynamic
0.3
20
60 80 100 120 140 40
20
40 60 80 100 120 140 Communication Round
Communication Round
p=
(b) pb)
1.0
0.9
Test Accuracy
Test Accuracy
0.8
0.8
0.7
0.7
0.6
Synchrany Constant
Synchrony Constant
0.5
Asynchrony Constant
0.5
Asynchrony Constant
Synchrony Dynamic
Synchrony Dynamic
0.4
Asynchrony Dynamic
0.4
Asynchrony Dynamic
0.3
60 80 100 120 140 Communication Round
0.3
20
40
60 100 120 140
Communication Round
(c) (=)p=bs 5.
(d) p = 10.
Figure 2: Test accuracy for LR MNIST with worker number 5/10, local steps 5.
32

---

Under review as a conference paper at ICLR 2022
0.8
0.8
Test Accuracy
0.7-
Test Accuracy
0.7
0.6
0.6
0.5
Synchrony Constant
0.5
Synchrony
Constant
Asynchrony Constant
Asynchrony Constant
0.4
Synchrony Dynamic
0.4
Synchrony Dynamic
Asynchrony Dynamic
Asynchrony Dynamic
2000
4000 6000 8000 10000
2000
4000 6000 8000 10000
Communication Round
Communication Round
(a) p 1.
(b) 2.
0.8
0.8
Test Accuracy
0.7
Test Accuracy
0.7
0.6
0.6
0.5
Synchrony + Constant
0.5
Synchrony Constant
Asynchrony Constant
Asynchrony + Constant
Synchrony Dynamic
Synchrony Dynamic
Asynchrony Dynamic
Asynchrony + Dynamic
0.3
0.3
4000 6000 8000 10000
8000 Communication Round
Communication Round
(c)
(d) = 10.
Figure 3: Test accuracy for CNN CIFAR-10 with worker number 5/10, local steps 5.
Test Accuracy
0.45
0.40
0.35
0.30
Synchrony Constant
0.25
Akynchrany Constant
Synchrany Dynamic
0.20
Asynchrony Dynamic
0.15
50
100
150
200 250 300
Communication Round
Figure Test accuracy for LSTM on Shakespeare with worker number 72/143, local steps 50.
33

---

Under review as a conference paper at ICLR 2022
Table 3: Test Accuracy of FedProx and SCAFFOLD.
Models/ Dataset
Non-i.i.d. index (p)
Worker number
Local steps
AFL
AFL.
FedProx
SCAFFOLD
FedProx
SCAFFOLD
p =
5/10
5
0.8893
0.8928
0.8775
0.8946
p = 2
5/10
5
0.8868
0.8970
0.8832
0.8954
p = 5
5/10
5
0.9036
0.9032
0.9004
0.9019
LR/ MNIST
p = 10
5/10
5
0.9075
0.9057
0.9054
0.9022
p = 1
5/10
10
0.8752
0,8789
0.8669
0.8838
p = 2
5/10
10
0.8685
0.8967
0.8789
0.8978
p = 5
5/10
10
0.9019
0.9047
0.8998
0.9029
10
5/10
10
0.9072
0.9071
0.9052
0.9038
p = 1
5/10
5
0.7488
0.1641
0.7415
0.3935
CNN/ CIFAR-I0
p = 2
5/10
5
0.7728
0,6315
0.7890
0.6971
p 5
5/10
5
0.7931
0.7828
0.8031
0.7884
10
5/10
5
0,8150
0,8083
0.8143
0.8051
RNN
72/143
50
0.4690
0.4794
0.4550
0.4515
Shakespeare
Utilizing FedProx and SCAFFOLD the optimizer on the worker-side. Here, 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 ZZhng et al. 2020b) and FedDyn (Acar et al. 2021). In such algorithms,, no information exchange between worker and server needed. On the other hand, SCAFFOLD represents VR-based (variance reduction) algorithms. It needs 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 (Konecný et al.) 2016).
In Table 3, we show the effectiveness of utilizing existing FL algorithmss FedProx and SCAFFOLD, in the AFL framework. For FedProx and SCAFFOLD, steps settings. When incorporating these two advanced FL algorithms the AFL framework, we study the effects of asynchrony and dynamic local steps. We set μ 0.1 default in FedProx algorithm. We can see from That FedProx performs as good as FedAvg does (compare with performance degradation in AFL. framework by utilizing FedProx as the worker's s optimizer. However, while SCAFFOLD performs well for LR on MNIST, dose not work well for CNN on CIFAR-I0, 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 al. 202T, 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.
examine synchrony and constant local
the results in Table 2) Also, there
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 consistent with the larger convergence eттor 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 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.
34

---

Under review as a conference paper at ICLR 2022
1.0
1.0
0.9
Accuracy
Test Accuracy
0.8
0.8
0.7
0.6
0.6
0.5
uniform sampling
uniform sampling
biased sampling
biased sampling
0.4-
0.4
VR blased sampling
VR on blased sampling
0.3
20
40 60 80 100 120 140
20
40 60 80
100 120 140
Communication Round
Communication Round
(a) p.
(b) p=
1.0
1.0
0.9
0.9
Test Accuracy
0.8
Test Accuracy
0.8
0.7
0.7
0.6
0.6
0.5
uniform sampling
uniform sampling
biased sampling
blased sampling on sampling
0.4
0.4
VR biased sampling
0.3
60 80 100 120 140 Communication Round
0.3
20
40 60 80 100 120 140 Communication Round
(c)p=1 5.
(d) 10.
Figure 5: Test accuracy for LR on MNIST with asynchrony and dynamic local steps.
0.8
uniform sampling
sampling
Test Accuracy
on biased sampling hmg
Test Accuracy
0.7
0.7
0.6-
0.6
uniform sampling biased sampling biased sampling
0.4
0.4
0.3
2000
4000
6000
8000
10000
2000
4000 6000 8000 10000
Communication Round
Communication Round
(a) p
(b) p= 2.
0.8
0.8
Test Accuracy
0.7
Test Accuracy
0.7
0.6
0.6
0.5
0.5
uniform sampling
uniform sampling
0.4
biased sampling
biased sampling
VR on biased sampling
VR on biased sampling
0.3
2000
8000 10000
0.3
6000 8000 10000 Communication Round
2000
Communication Round
(c) = 5.
(d) 10.
Figure 6: Test accuracy for CNN CIFAR-I0 with asynchrony and dynamic local steps.
35


Reviews:
[{"review_id": "P3ZHSIC93tQ", "reviewer": "Reviewer_bjgp", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "## Convergence results\n\n1) Why can't assumption 3 be relaxed to bound the heterogeneity only at any stationary point of $f$, i.e., $\\|\\|\\nabla f_i(x^\\star) - \\nabla f(x^\\star)\\|\\|^2 = \\|\\|\\nabla f_i(x^\\star)\\|\\|^2 \\leq \\sigma_G^2$, such as in [this work](https://arxiv.org/pdf/2006.04735.pdf)? This kind of an assumption better captures the heterogeneity of workers and is useful in understanding interpolation problems (c.f., [this work](https://arxiv.org/abs/2106.02720)). Regardless it should be clarified what are $x_k$'s in assumption 2 and 3, and assumption 3 needs an expectation because $x_k$'s are random variables(?). \n\n2) There is no need to introduce $G$ in Theorem 1, instead just say that it is valid for any level of heterogeneity characterized by $\\sigma_G$. Moreover, **the theorem is very vaguely stated and in a sense wrong**. \n\n    - What do you mean by \"any AFL algorithm\"? Is SGD on each machine initialized at $0$ with a zero learning rate, not an AFL algorithm? That gets to the stationary point of the lower bound function exactly in zero steps! You need to give a lower bound for every optimization algorithm, for any setting of initialization and hyper-parameters (c.f., the [lower bounds here](https://arxiv.org/pdf/2006.04735.pdf) and in the references therein). \n    - Also, you allow for an arbitrary number of local steps on each machine i.e., $K=\\infty$, so that you can ignore the $\\epsilon$ in the lower bound proof. This is not the assumption under which you analyze your algorithms, so it is incorrect to use this lower bound to claim that the results are tight in $\\sigma_G$. In fact, if one assumes that worker step-size is small and $K, \\tau < \\infty$ then that would allow for a more optimistic lower bound, and a better baseline for your upper bounds. In that case, $\\epsilon$ will depend on the $\\eta, K, \\tau$ like it should.  \n    - And what does it mean that the theorem holds for non-iid FL? The [lower bound here](https://arxiv.org/pdf/2006.04735.pdf) is already smaller than $\\sigma_G^2$ (albeit for the convex setting, which is fine because your function is convex as well)! \n\n3) In corollary 1, I do not buy that there should be a $\\sigma_G^2$ term. This is because I don't believe the lower bound in Theorem 1 for the reasons stated above. With a small enough client step-size, it should be possible to have a decaying term w.r.t. $\\sigma_G$. \n\n4) You discuss in detail how it is important to improve the dependence on systems heterogeneity in the current federated learning guarantees. As an idea, anarchic federated learning sounds very enticing, but the result in theorem 3 is not AFL, it is just uniform partial client participation. Thus the theoretical result falls short of giving any novel insights. \n    - We already have results, in the setting where the local updates are non-uniform but bounded, and when the gradient updates are delayed (asynchronous updates). How is your result not just a combination of both of them? I was hoping your analysis doesn't require these boundedness assumptions. What is worse is that the dependence is somewhat worse here. For instance, the effect of delay has already been captured in [this paper](https://arxiv.org/pdf/1909.05350.pdf) (it has a $\\tau$ dependence vs your $\\tau^2$), and it has even been improved to depend on $\\tau_{avg}$ instead of depending on the worst delay in [this paper](https://arxiv.org/pdf/2106.11879.pdf). The latter is very significant, especially in actual anarchic federated learning, where some workers might participate very intermittently, but others might not. If the dependence on $\\tau$ can't be avoided, it should at least have been reduced to $\\tau_{avg}$. \n    - Finally, how is this rate equivalent to the rate provided in the Scaffold paper in the non-iid FL setting? Their leading term is $1/\\sqrt{mKT}$ which is better than your $1/\\sqrt{mT}$ term. It is both **incorrect and misleading to assume that $K$ is a constant** and not a lever we'd like to move to see how the rate changes!  \n\n5) I think it is indeed interesting to see a speedup in terms of $M$ instead of $m$ in corollary 3. In my opinion, this was the most interesting result in the paper. Overall, I think the paper can improve its writing to remove the focus from Theorem 1, 2 and instead direct it to the improved results for partial client sampling with asynchrony in theorem 3 and 4 (of course while improving upon the dependencies I point out above). \n\n## Experiments\n\nIt is unclear to me what to make of the experiments provided in the main paper. How was the anarchic behavior of the machines emulated in figure 1? It would make sense to bring some of this discussion from the appendix to the main paper. \n\n\n***\n## Minor comments\n\n1) Linear speed-up is an abused term in FL literature. It would be good to specify somewhere that (i) this is just convergence to a first-order stationary point, which might not completely capture the performance while training neural networks, and (ii) the linear speedup is conditional (even theoretically), i.e., it holds only till the number of machines is not too large (c.f., [this paper](https://arxiv.org/abs/1811.03600)). \n\n> We count each global model update as one communication round.  \n\n2) We are not in the intermittent communication setting anymore, what does a communication round even mean? Devices are asynchronously pulling and pushing in this model. What does this mean then?  \n\n3) Don't hide the dependence on $L$ and $\\sigma_L^2$ in the corollaries. It makes it difficult to compare different terms in convergence with known convergence results. Moreover, it would make more sense to put the relevant baselines in a table to show a direct comparison with non-iid FL rates. It might also save some space.\n\n\n\n\n\n", "summary_of_the_paper": "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.\n\nThe 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.    ", "summary_of_the_review": "I don't believe that the provided results or the techniques used in this paper are surprising. The convergence results provided here are not tight in all the constants, and some of the assumptions made to provide those are too restrictive and don't morally allow anarchic behavior. As a result, I am not in favor of accepting this paper in its current state. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "K2PQWksCinS", "reviewer": "Reviewer_8n7V", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Advantages:\n\n* It provides convergence guarantees for the proposed asynchronous algorithms in federated settings.\n\n* It also characterizes the lower bound without any assumptions on the client communication pattern, which provides useful reference points on the improvements of the analysis with additional assumptions.\n\nConcerns:\n\n* The proposed algorithms are very similar to those proposed in this paper (https://arxiv.org/abs/2106.06639, Federated Learning with Buffered Asynchronous Aggregation).  Although the paper I mentioned lets the server sample clients asynchronously, algorithmically looks like these two works are doing the same thing. I understand the submission is more general and improves the analysis in certain ways (e.g., without bounded gradient), but the main algorithms and some motivation are largely overlapping. It would be very helpful to clarify the major differences, if there are any.\n\n* I am confused by the difference and the motivation for two variants designed for cross-device and cross-silo settings. (1) I think the server in both settings is assumed to be powerful in terms of memory and computation. Can the work give some references on why the server is assumed to have no historical information of the works? (2) The submission assumes uniform arrival for cross-device FL, and bounded delay for cross-silo FL. They both control the staleness of the model updates (to make sure the global model some device starts from is not too stale compared with the current global model for aggregation). Both of them are reasonable for cross-silo FL; and hence, to me, there isn’t a clear mapping between which setting is more compatible with which assumption. \n\n* I think one motivation for asynchronous training is that it leads to faster convergence (empirically) in the presence of stragglers. This point should be validated empirically (by simulating systems heterogeneity, for example). \n\n* In practice, the delays may be unbounded (e.g., when each device only participates once or twice during the training); so the two assumptions can be too strong.\n\nMinor:\n\n* Why does the lower bound also hold for FedAvg (described in Remark 1)? Under proper step-sizes, there is usually no constant error term.\n\n\n* The last paragraph in Section 3 (1) spends much text highlighting that AFL is a general computing architecture. But this (using any local solver with different hyperparameters, allowing for device-specific local steps) is not a unique property of AFL, and lots of previous federated optimization methods also support this. \n\n* At the end of the first paragraph of related work (Sec 2), I don't think calling server-centric synchronous algorithms are not easy to implement is accurate or justified.\n\n* The phrase 'general worker information arrival process' appears for the first time in the abstract, which is a bit abrupt and unclear---what is a worker information arrival process? general in what sense? \n\n* The empirical evaluation does not describe how the stragglers are simulated precisely. For example, the starting points of the clients uniformly sampled (or sampled in a biased way) correspond to which time stamp? Does the 'bias sampling' scheme (described in the appendix) correspond to the bounded delay case?", "summary_of_the_paper": "This work proposes a different worker-server asynchronous communication pattern in federated learning, designs algorithms for cross-device and cross-silo settings, and analyzes the convergence of the proposed asynchronous schemes in the cases without assumptions on worker participation, and with some assumptions on the distribution of the active workers or bounded delay. It also empirically demonstrates that the asynchronous scheme achieves competitive performance compared with synchronous baselines.", "summary_of_the_review": "I think studying asynchronous and device-centric communication in the context of FL is definitely interesting, and I feel the algorithms and the analysis in the paper are correct and solid. My major concerns are the first three points in the 'concerns' part of my comments, especially the differences between the submission and that related work.\n\n====update====\n\nI have read the authors' responses. However, I don't think the differences from the previous work (https://arxiv.org/abs/2106.06639) are significant. My concerns regarding the uniform arrival and bounded delay assumptions in federated learning, the experiments, etc remain. Therefore, I do not think this submission in its current form is ready for publication and I retain my original score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CpBEVOlu5SF", "reviewer": "Reviewer_rgtg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The overall idea of AFL is interesting and the theoretical results of AFA-CD and AFA-CS look reasonable. However, I found the following issues regarding AFL concerning. I hope the authors can address them in the rebuttal.\n\n- The convergence rate of AFA-CD can be bad under the general worker information arrival process (truly anarchic). Take the equation in Corollary 1 for example, by the definition of $\\tau$ and $K$, they can be as large as $O(T)$ if a few workers set their delay and local steps to be so. The algorithm 2 and 3 provides no guarantee that such delayed gradient will be rejected. That is, if a client starts local steps from $t=0$ and decide to submit its update at $T$, which is the *complete freedom* stated in the paper, algorithm 2 and 3 will incorpoate this update and ruin the training.\n\n- The assumption of uniform distributed arrival of worker information is not realistic. The participants of cross-device federated learning have various computational power and communication frequency, etc.\nSo this assumption is most likely not true. It means in reality, AFL cannot achieve the same performance as FedAvg as FedAvg can enforce uniform sampling of clients.\n\n- The assumption of bounded maximum delay and local steps is contrary to the \"anarchic\". In addition, the worker learning rate $\\eta_L$ depends on the maximum delay. It can not be decided under the truly anarchic case.\n\n- AFL is much more vulnerable to attacks than FedAvg. As the worker has the freedom to choose when to join training, the chance of attacker updates being incorporated in the aggregatrion is drastically increased by simply being eager to communicate to the server. This makes AFL vulnerable to backdoor/Byzantine attacks even if there is only a small percent of attackers. On the other hand, the FedAvg uniformly sample the clients and have a low chance of selecting many attackers.\n\n### Typos\n- Page 1, \"stragglers (i.e. show workers)\" => \"slow workers\"\n- Page 2, \"Clearly, AFL has a much lower sever-worker coordination\" => \"server-worker\"\n- Page 4, \"Although the sever in cross-silo\" => \"server\"\n\n======\n\nPost-rebuttal: I have read the authors' rebuttal and found them addressed my concerns so I decide to raise the score to 6.\n\n", "summary_of_the_paper": "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\n", "summary_of_the_review": "The anarchic federated learning is vulnerable to attacks and can be slower than FedAvg because of unbounded delay, local steps, and heterogeneity of clients.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "85JgdCUc1Yo", "reviewer": "Reviewer_Ubxj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This work is well positioned with the attractive properties of clients being \"autonomous\" in deciding whether to join the FL in each round. But, fundamentally, the studied FL problem is equivalent to asynchronous FL with random client selection (by the server), because the randomness due to the \"free will\" of the clients is statistically equivalent to being randomly selected by the server. Then, some additional degrees of freedom are considered, such as having different local steps and different delays. Nevertheless, these freedoms eventually are \"masked\" by the worse-case representations in Theorem 1, suggesting that it is equivalent to have these participating clients perform $K$ local update steps and delay at $\\tau$. Furthermore, these worst cases are over both clients and time, suggesting that they are indeed the \"worst\" of the entire FL process. This result is quite discouraging. For example, throughout the whole FL process of say 500 rounds, if there is one and only one instance of a client having a large step size or large delay, Theorem 1 says this will dominate the entire convergence, which is counter-intuitive.\n\nI'm willing to give the authors a chance to address these concerns, and I'll be open to adjusting the score accordingly. To me, the work itself is very interesting, but the aforementioned two issues should be addressed.\n\nSome other comments:\n(1) The requirement of having to wait for $m$ local updates is quite restrictive. Since the clients have the freedom to choose not to participate, there is always the chance that less than $m$ clients actually participate. Plus, waiting for $m$ local updates naturally leads to the straggler problem.\n\n(2) On page 6, the authors claimed that only when considering the special case of uniformly distributed delay would we have the case of sampling $m$ clients from $[M]$ without replacement. As stated in my main concern, I do not believe this is the case. Rather, your model, even with non-uniformly distributed delay, is still equivalent to sampling $m$ clients from $[M]$ without replacement.\n\n(3) Following up on (2), Theorem 3 is not well explained. It is unclear why with an additional assumption of uniformly distributed delay, one can improve Theorem 3, which relies only on the worst case delay.\n\n(4) Theorem 2 has a dependence on $\\alpha_L$, which scales with $\\tau^2$. This term may becoming dominating if $\\tau$ is large, as opposed to the $\\sigma_G$ term. This is however hidden in Corollary 1, which is worth discussing.\n\n(5) Typo: CS-AFL in page 2 should be AFL-CS. ", "summary_of_the_paper": "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. ", "summary_of_the_review": "As mentioned in the main review, I believe this work has potential and is interesting, but difference to asynchronous FL with random client selection (by the server) and addressing the worst-case behavior that dominates the convergence bounds are the two concerns I have.\n\n========\n\nPost-rebuttal: I have read the authors' responses and some (responses 3 and 4) have clarified confusions I had, which is helpful. The other responses are largely in line with my understanding of the paper. Overall, my review of this paper does not change. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper on 'anarchic' federated learning (FL) envisions an FL framework where edge clients can act independently instead of their participation being controlled by a central server. The idea is certainly promising, however, the reviewers pointed out the following main issues:
1) Technical gaps in the theoretical analysis need to be addressed
2) Bounded delay assumptions are too strong and are mismatching with the 'anarchic' goal of the framework
3) The linear speed-up claim should be better explained and justified.
The paper generated lots of post-rebuttal discussions. However, the concerns about the theoretical analysis still remain, and therefore I recommend rejection. I hope the authors will take these constructive comments into account when revising the paper.
Decision: Reject