FedDR – Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
Year: 2021

Abstract:
We develop two new algorithms, called, FedDR and asyncFedDR, for solving a fundamental nonconvex composite optimization problem in federated learning. Our algorithms rely on a novel combination between a nonconvex Douglas-Rachford splitting method, randomized block-coordinate strategies, and asynchronous implementation. They can also handle convex regularizers. Unlike recent methods in the literature, e.g., FedSplit and FedPD, our algorithms update only a subset of users at each communication round, and possibly in an asynchronous manner, making them more practical. These new algorithms can handle statistical and system heterogeneity, which are the two main challenges in federated learning, while achieving the best known communication complexity. In fact, our new algorithms match the communication complexity lower bound up to a constant factor under standard assumptions. Our numerical experiments illustrate the advantages of our methods over existing algorithms on synthetic and real datasets.

heading: 1 Introduction
text: Training machine learning models in a centralized fashion becomes more challenging and marginally inaccessible for a large number of users, especially when the size of datasets and models is growing substantially larger. Consequently, training algorithms using decentralized and distributed approaches comes in as a natural replacement. Among several approaches, federated learning (FL) has received tremendous attention in the past few years since it was first introduced in [18, 30]. In this setting, a central server coordinates between many local users (also called agents or devices) to perform their local updates, then the global model will get updated, e.g., by averaging or aggregating local models.
Challenges. FL provides a promising solution for many machine learning applications such as learning over smartphones or across organizations, and internet of things, where privacy protection is one of the most critical requirements. However, this training mechanism faces a number of fundamental challenges, see, e.g., [31]. First, when the number of users gets substantially large, it creates communication bottleneck during model exchange process between server and users. Second, the local data stored in each local user may be different in terms of sizes and distribution which poses a challenge: data or statistical heterogeneity. Third, the variety of users with different local storage, computational power, and network connectivity participating into the system also creates a major challenge, known as system heterogeneity. This challenge also causes unstable connection
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
between server and users, where some users may be disconnected from the server or simply dropped out during training. In practice, we can expect only a subset of users to participate in each round of communication. Another challenge in FL is privacy concern. Accessing and sharing local raw data is not permitted in FL. In addition, distributed methods exchange the objective gradient of local users, and private data can be exposed from the shared model such as the objective gradients [51]. Therefore, FL methods normally send the global model to each user at the start of each communication round, each user will perform its local update and send back only the necessary update for aggregation.
Our goal and approach. Our goal in this paper is to further and simultaneously address these fundamental challenges by proposing two new algorithms to train the underlying common optimization model in FL. Our approach relies on a novel combination between randomized block-coordinate strategy, nonconvex Douglas-Rachford (DR) splitting, and asynchronous implementation. While each individual technique or partial combinations is not new, our combination of three as in this paper appears to be the first in the literature. To the best of our knowledge, this is the first work developing randomized block-coordinate DR splitting methods for nonconvex composite FL optimization models, and they are fundamentally different from some works in the convex setting, e.g., [7, 8].
Contribution. Our contribution can be summarized as follows.
(a) We develop a new FL algorithm, called FedDR (Federated Douglas-Rachford), by combining the well-known DR splitting technique and randomized block-coordinate strategy for the common nonconvex composite optimization problem in FL. Our algorithm can handle nonsmooth convex regularizers and allows inexact evaluation of the underlying proximal operators as in FedProx or FedPD. It also achieves the best known O ( ε−2 )
communication complexity for finding a stationary point under standard assumptions (Assumptions 2.1- 2.2), where ε is a given accuracy. More importantly, unlike FedSplit [33] and FedPD [49], which require full user participation to achieve convergence, our analysis does allow partial participation by selecting a subset of users to perform update at each communication round. (b) Next, we propose an asynchronous algorithm, asyncFedDR, where each user can asynchronously perform local update and periodically send the update to the server for proximal aggregation. We show that asyncFedDR achieves the same communication complexity O ( ε−2 )
as FedDR (up to a constant factor) under the same standard assumptions. This algorithm is expected to simultaneously address all challenges discussed above.
Let us emphasize some key points of our contribution. First, the best known O ( ε−2 )
communication complexity of our methods matches the lower bound complexity up to a constant factor as shown in [49], even with inexact evaluation of the objective proximal operators. Second, our methods rely on a DR splitting technique for nonconvex optimization and can handle possibly nonsmooth convex regularizers, which allows us to deal with a larger class of applications and with constraints [47]. Furthermore, it can also handle both statistical and system heterogeneity as discussed in FedSplit [33] and FedPD [49]. However, FedSplit only considers the convex case, and both FedSplit and FedPD require all users to update at each communication round, making them less practical and applicable in FL. Our methods only require a subset of users or even one user to participate in each communication round as in FedAvg or FedProx. In addition, our aggregation step on the server is different from most existing works due to a proximal step on the regularizer. It is also different from [47]. Third, as FedProx [23], we allow inexact evaluation of users’ proximal operators with any local solver (e.g., local SGD or variance reduced methods) and with adaptive accuracies. Finally, requiring synchronous aggregation at the end of each communication round may lead to slow-down in training due to the heterogeneity in computing power and communication capability of local users. It is natural to have asynchronous update from local users as in, e.g., [34, 35, 39]. Our asynchronous variant, asyncFedDR, can fairly address this challenge. Moreover, it uses a general probabilistic model recently introduced in [5], which allows us to capture the variety of asynchronous environments and architectures compared to existing methods, e.g., [39, 44].
Related work and comparison. Federated Averaging (FedAvg) is perhaps the earliest method used in FL. In FedAvg, users perform stochastic gradient descent (SGD) updates for a number of epochs then send updated models to server for aggregation. FedAvg’s practical performance has been shown in many early works, e.g., [18, 29, 48] and tends to become the most popular method for solving FL applications. [26] show that local SGD where users perform a number of local updates before global communication takes place as in FedAvg may offer benefit over minibatch SGD. Similar comparison between minibatch SGD and local SGD has been done in [42, 43]. Analyzing convergence of FedAvg
was very challenging at its early time due to the complexity in its update as well as data heterogeneity. One of the early attempt to show the convergence of FedAvg is in [39] for convex problems under the iid data setting and a set of assumptions. [45] also considers local SGD in the nonconvex setting. Without using an additional bounded gradient assumption as in [39, 45], [41] improves the complexity for the general nonconvex setting while [11] uses a Polyak-Łojasiewicz (PL) condition to improve FedAvg’s convergence results. In heterogeneous data settings, [17] analyzes local GD, where users performs gradient descent (GD) updates instead of SGD. The analysis of FedAvg for non-iid data is given in [24]. The analysis of local GD/SGD for nonconvex problems has been studied in [13]. However, FedAvg might not converge with non-iid data as shown in [33, 49, 50].
FedProx [23] is an extension of FedAvg, which deals with heterogeneity in federated networks by introducing a proximal term to the objective in local updates to improve stability. FedProx has been shown to achieve better performance than FedAvg in heterogeneous setting. Another method to deal with data heterogeneity is SCAFFOLD [16] which uses a control variate to correct the “client-drift" in local update of FedAvg. MIME [15] is another framework that uses control variate to improve FedAvg for heterogeneous settings. However, SCAFFOLD and MIME require to communicate extra information apart from local models. Compared to aforementioned works, our methods deal with nonconvex problems under standard assumptions and with composite settings.
FedSplit [33] instead employs a Peaceman-Rachford splitting scheme to solve a constrained reformulation of the original problem. In fact, FedSplit can be viewed as a variant of Tseng’s splitting scheme [1] applied to FL. [33] show that FedSplit can find a solution of the FL problem under only convexity without imposing any additional assumptions on system or data homogeneity. [49] proposes FedPD, which is essentially a variant of the standard augmented Lagrangian method in nonlinear optimization. Other algorithms for FL can be found, e.g., in [6, 10, 12, 14, 25, 46].
Our approach in this paper relies on nonconvex DR splitting method, which can handle the heterogeneity as discussed in [33]. While the DR method is classical, its nonconvex variants have been recently studied e.g., in [9, 21, 40]. However, the combination of DR and randomized block-coordinate strategy remains limited [7, 8] even in the convex settings. Alternatively, asynchronous algorithms have been extensively studied in the literature, also for FL, see, e.g., [2, 34, 35]. For instance, a recent work [44] analyzes an asynchronous variant of FedAvg under bounded delay assumption and constraint on the number of local updates. [39] proposes an asynchronous local SGD to solve convex problems under iid data. However, to our best knowledge, there exists no asynchronous method using DR splitting techniques with convergence guarantee for FL. In addition, most existing algorithms only focus on non-composite settings. Hence, our work here appears to be the first.
Content. The rest of this paper is organized as follows. Section 2 states our FL optimization model and our assumptions. Section 3 develops FedDR and analyzes its convergence. Section 4 considers an asynchronous variant, asyncFedDR. Section 5 is devoted for numerical experiments. Due to space limit, all technical details and proofs can be found in Supplementary Document (Supp. Doc.).

heading: 2 Nonconvex Optimization Models in Federated Learning
text: The underlying optimization model of many FL applications can be written into the following form:
min x∈Rp
{ F (x) := f(x) + g(x) = 1
n n∑ i=1 fi(x) + g(x) } , (1)
where n is the number of users, and each fi is a local loss of the i-th user, which is assumed to be nonconvex and L-smooth (see Assumptions 2.1 and 2.2 below), and g is a proper, closed, and convex regularizer. Apart from these assumptions, we will not make any additional assumption on (1). We emphasize that the use of regularizers g has been motivated in several works, including [47].
Let dom(F ) := {x ∈ Rp : F (x) < +∞} be the domain of F and ∂g be the subdifferential of g [1]. Since (1) is nonconvex, we only expect to find a stationary point, which is characterized by the following optimality condition. Definition 2.1. If 0 ∈ ∇f(x∗) + ∂g(x∗), then x∗ is called a [first-order] stationary point of (1).
The algorithms for solving (1) developed in this paper will rely on the following assumptions. Assumption 2.1 (Boundedness from below). dom(F ) 6= ∅ and F ? := infx∈Rp F (x) > −∞.
Assumption 2.2 (L-smoothness). All functions fi(·) for i ∈ [n] := {1, · · · , n} are L-smooth, i.e., fi is continuously differentiable and there exists L ∈ (0,+∞) such that
‖∇fi(x)−∇fi(y)‖ ≤ L‖x− y‖, ∀x, y ∈ dom(fi). (2)
Assumptions 2.1 and 2.2 are very standard in nonconvex optimization. Assumption 2.1 guarantees the well-definedness of (1) and is independent of algorithms. Assuming the same Lipschitz constant L for all fi is not restrictive since if fi is Li-smooth, then by scaling variables of its constrained formulation (see (11) in Supp. Doc.), we can get the same Lipschitz constant L of all fi.
Proximal operators and evaluation. Our methods make use of the proximal operators of both fi and g. Although fi is L-smooth and nonconvex, we still define its proximal operator as
proxηfi(x) := argminy
{ fi(y) + 1 2η‖y − x‖ 2 } , (3)
where η > 0. Even fi is nonconvex, under Assumption 2.2, if we choose 0 < η < 1L , then proxηfi is well-defined and single-valued. Evaluating proxηfi requires to solve a strongly convex program. If proxηfi can only be computed approximately up to an accuracy ≥ 0 to obtain z, denoted by x+ :≈ proxηfi(x), if ‖x+ − proxηfi(x)‖ ≤ i. Note that instead of absolute error, one can also use a relative error as ‖x+ − proxηfi(x)‖ ≤ i‖x+ − x‖ as in [37]. For the convex function g, its proximal operator proxηg is defined in the same way as (3). Evaluating proxηfi can be done by various existing methods, including local SGD and accelerated GD-type algorithms. However, this is not our focus in this paper, and therefore we do not specify the subsolver for evaluating proxηfi .
Gradient mapping. As usual, let us define the following gradient mapping of F in (1). Gη(x) := 1η ( x− proxηg(x− η∇f(x)) ) , η > 0. (4) Then, the optimality condition 0 ∈ ∇f(x∗) + ∂g(x∗) of (1) is equivalent to Gη(x∗) = 0. However, in practice, we often wish to find an ε-approximate stationary point to (1) defined as follows. Definition 2.2. If x̃ ∈ dom(F ) satisfies E [ ‖Gη(x̃)‖2 ] ≤ ε2, then x̃ is called an ε-stationary point of (1), where the expectation is taken overall the randomness generated by the underlying algorithm.
Note that, for Gη(x̃) to be well-defined, we require x̃ ∈ dom(F ). In our algorithms below, this requirement is fulfilled if x̃ ∈ dom(f), which is often satisfied in practice as dom(f) = Rp.

heading: 3 FedDR Algorithm and Its Convergence Guarantee
text: Prior to our work, FedSplit [33] exploits similar update steps as ours by adopting the PeacemanRachford splitting method to solve the convex and non-composite instances of (1). FedSplit can overcome some of the key challenges as discussed earlier. Following this idea, we take the advantages of the DR splitting method to first derive a new variant to handle the nonconvex composite problem (1). This new algorithm is synchronous and we call it FedDR. The central idea is as follows: First, we reformulate (1) into (12) by duplicating variables. Next, we apply a DR splitting scheme to the resulting problem. Finally, we combine such a scheme with a randomized block-coordinate strategy.
The complete algorithm is presented in Algorithm 1, where its full derivation is in Supp. Doc. A.1.
Let us make the following remarks. Firstly, FedDR mainly updates of three sequences {x̄k}, {xki } and {yki }. While x̄k is an averaged model to approximately minimize the global objective function F , xki act as local models trying to optimize a regularized local loss function w.r.t. its local data distribution, and yki keeps track of the residuals from the local models to the global one. Secondly, we allow xki to be an approximation of proxηfi(y k i ) up to an accuracy i,k ≥ 0 as defined in (3), i.e., ‖xki − proxηfi(y k i )‖ ≤ i,k for all i ∈ [n] if k = 0 and for all i ∈ Sk−1 if k > 0. If i,k = 0, then we get the exact evaluation xki := proxηfi(y k i ). Approximately evaluating proxηfi can be done, e.g., by local SGD as in FedAvg. Thirdly, Algorithm 1 is different from existing randomized proximal gradient-based methods since we rely on a DR splitting scheme and can handle composite settings. Here, three iterates yki , x k i , and x̂ k i at Step 5 are updated sequentially, making it challenging to analyze convergence. Lastly, the subset of active users Sk is sampled from a random set-valued mapping Ŝ. As specified in Assumption 3.1, this sampling mechanism covers a wide range of sampling strategies. Clearly, if Sk = [n] and g = 0, then Algorithm 1 reduces to FedSplit, but for the nonconvex case. Hence, our convergence guarantee below remains applicable, and the guarantee is sure. Note that both our model (1) and Algorithm 1 are completely different from [47].
Algorithm 1 (FL with Randomized DR (FedDR)) 1: Initialization: Take x0 ∈ dom(F ). Choose η > 0 and α > 0, and accuracies i,0 ≥ 0 (i ∈ [n]).
Initialize the server with x̄0 := x0 and x̃0 := x0. Initialize each user i ∈ [n] with y0i := x0, x0i :≈ proxηfi(y 0 i ), and x̂ 0 i := 2x 0 i − y0i .
2: For k := 0, · · · ,K do 3: [Active users] Generate a proper realization Sk ⊆ [n] of Ŝ (see Assumption 3.1). 4: [Communication] Each user i ∈ Sk receives x̄k from the server. 5: [Local update] For each user i ∈ Sk do: Choose i,k+1 ≥ 0 and update
yk+1i := y k i + α(x̄ k − xki ), xk+1i :≈ proxηfi(y k+1 i ), and x̂ k+1 i := 2x k+1 i − y k+1 i .
6: [Communication] Each user i ∈ Sk sends ∆x̂ki := x̂ k+1 i − x̂ki back to the server. 7: [Sever aggregation] The server aggregates x̃k+1 := x̃k + 1n ∑ i∈Sk ∆x̂ k i .
8: [Sever update] Then, the sever updates x̄k+1 := proxηg ( x̃k+1 ) . 9: End For

heading: 3.1 Convergence of Algorithm 1
text: Let us consider a proper sampling scheme Ŝ of [n], which is a random set-valued mapping with values in 2[n], the collection of all subsets of [n]. Let Sk be an iid realization of Ŝ and Fk := σ(S0, · · · ,Sk) be the σ-algebra generated by S0, · · · ,Sk. We first impose the following assumption about the distribution of our sampling scheme Ŝ. Assumption 3.1. There exist p1, · · · ,pn > 0 such that P ( i ∈ Ŝ ) = pi > 0 for all i ∈ [n].
This assumption covers a large class of sampling schemes as discussed in [36], including nonoverlapping uniform and doubly uniform. This assumption guarantees that every user has a nonnegligible probability to be updated. Note that pi = ∑ S:i∈S P(S) due to Assumption 3.1. For the sake of notation, we also denote p̂ := min{pi : i ∈ [n]} > 0. The following theorem characterizes convergence of Algorithm 1 with inexact evaluation of proxηfi . Due to space limit, we refer the reader to Lemma A.6 in Sup. Doc. for more details about the choice of stepsizes and related constants. The proof of this theorem is defered to Sup. Doc. A.5. Theorem 3.1. Suppose that Assumptions 2.1, 2.2, and 3.1 hold. Let {(xki , yki , x̂ki , x̄k)} be generated by Algorithm 1 using stepsizes α and η defined in (33). Then, the following holds
1
K + 1 K∑ k=0 E [ ‖Gη(x̄k)‖2 ] ≤ C1[F (x 0)− F ?] K + 1 + 1 n(K + 1) K∑ k=0 n∑ i=1 ( C2 2 i,k + C3 2 i,k+1 ) , (5)
where β, ρ1, and ρ2 are explicitly defined by (35), and
C1 := 2(1+ηL)2(1+γ2) η2β , C2 := ρ1C1, and C3 := ρ2C1 + (1+ηL)2(1+γ2) η2γ2 .
Let x̃K be selected uniformly at random from {x̄0, · · · , x̄K} as the output of Algorithm 1. Let the accuracies i,k for all i ∈ [n] and k ≥ 0 at Step 5 be chosen such that 1n ∑n i=1 ∑K+1 k=0 2 i,k ≤M for a given constant M > 0 and all K ≥ 0. Then, if we run Algorithm 1 for at most
K :=
⌊ C1[F (x
0)− F ?] + (C2 + C3)M ε2
⌋ ≡ O ( ε−2 )
iterations, then x̃K is an ε-stationary point of (1) in the sense of Definition 2.2.
Remark 3.1. [Choice of accuracies ki ] To guarantee 1 n ∑n i=1 ∑K+1 k=0 2 i,k ≤M in Theorem 3.1 for a given constant M > 0 and for all K ≥ 0, one can choose, e.g., 2i,k := M2(k+1)2 for all i ∈ [n] and k ≥ 0. In this case, we can easily show that 1n ∑n i=1 ∑K+1 k=0 2 i,k = M 2 ∑K+1 k=0 1 (k+1)2 ≤M . Note that, instead of using absolute accuracies, one can also use relative accuracies as ‖ i,k‖2 ≤ θ‖xk+1i −xki ‖2 for a given constant θ > 0, which is more practical, while still achieving a similar convergence guarantee. Such an idea has been widely used in the literature, including [28] (see Supp. Doc. A.7).
Remark 3.2 (Comparison). Since (1) is nonconvex, our O ( ε−2 )
communication complexity is the state-of-the-art, matching the lower bound complexity (up to a constant factor) [49]. However, different from the convergence analysis of FedSplit and FedPD [49], our flexible sampling scheme allows us to update a subset of users at each round and still obtains convergence. This can potentially further resolve the communication bottleneck [22]. We note that FedSplit is a variant of the PeacemanRachford splitting method, i.e. α = 2 and only considers convex non-composite case while we use a relaxation parameter α < 2 and for a more general nonconvex composite problem (1).
The following corollary specifies the convergence of Algorithm 1 with a specific choice of stepsizes and exact evaluation of proxηfi , whose proof is in Sup. Doc. A.6.
Corollary 3.1. Suppose that Assumptions 2.1, 2.2, and 3.1 hold. Let {(xki , yki , x̂ki , x̄k)} be generated by Algorithm 1 using stepsizes α = 1, η = 13L , and pi = 1 n . Under exact evaluation of proxηfi , i.e.
i,k = 0 for all i ∈ [n] and k ≥ 0, the following bound holds
1
K + 1 K∑ k=0 E [ ‖Gη(x̄k)‖2 ] ≤ 160Ln 3(K + 1) [F (x0)− F ?]. (6)
Let x̃K be selected uniformly at random from {x̄0, · · · , x̄K} as the output of Algorithm 1. Then after at most
K :=
⌊ 160Ln[F (x0)− F ?]
3ε2
⌋ ≡ O ( ε−2 ) ,
communication rounds, x̃K becomes an ε-stationary point of (1) (defined by Definition 2.2).

heading: 4 AsyncFedDR and Its Convergence Guarantee
text: Motivation. Although FedDR has been shown to converge, it is more practical to account for the system heterogeneity of local users. Requiring synchronous aggregation at the end of each communication round may lead to slow down in training. It is natural to have asynchronous update from local users as seen, e.g., in [35, 39]. However, asynchronous implementation remains limited in FL. Here, we propose asyncFedDR, an asynchronous variant of FedDR, and analyze its convergence guarantee. For the sake of our analysis, we only consider Sk := {ik}, the exact evaluation of proxηfi , and bounded delay, but extensions to general Sk and inexact proxηfi are similar to Algorithm 1.

heading: 4.1 Derivation of asyncFedDR
text: Let us first explain the main idea of asyncFedDR. At each iteration k, each user receives a delay copy x̄k−d
k ik of x̄k from the server with a delay dkik . The active user ik will update its own local model
(yki , x k i , x̂ k i ) in an asynchronous mode without waiting for others to complete. Once completing its update, user ik just sends an increment ∆x̂kik to the server to update the global model, while others may be reading. Overall, the complete asyncFedDR is presented in Algorithm 2.
In our analysis below, a transition of iteration from k to k + 1 is triggered whenever a user completes its update. Moreover, at Step 3, active user ik is chosen from a realization (ik, dk) of a joint random vector (̂ik, d̂k) at the k-th iteration. Here, we do not assume ik to be uniformly random or independent of the delay dk. This allows Algorithm 2 to capture the variety of asynchronous implementations and architectures. Note that x̄k−d k ik at Step 4 is a delayed version of x̄k, which only exists on the server when user ik is reading. However, right after, x̄k may be updated by another user.
Illustrative example. To better understand the update of asyncFedDR, Figure 1 depicts a simple scenario where there are 4 users (C1 - C4) asynchronously perform updates and with g(·) = 0. At iteration k = 4, user C4 finishes its update so that the server performs updates. During this process, user C1 starts its update by receiving a global model x̄4−d 4 i4 from server which is the average of (x̂41, x̂ 4 2, x̂ 4 3, x̂ 4 4). At iteration t = 7, C1 finishes its update. Although x̂1 and x̂4 do not change during this time, i.e. x̂61 = x̂ 4 1 and x̂ 6 4 = x̂ 4 4, x̂2 and x̂3 have been updated at k = 5, 6 from user C2 and C3, respectively. Therefore, the global model x̄k used to perform the update at k = 7 is actually aggregated from (x̂61, x̂ 4 2, x̂ 5 3, x̂ 6 4) not (x̂ 6 1, x̂ 6 2, x̂ 6 3, x̂ 6 4). In other words, each user receives a delay estimate x̄k−d k
where dk = (dk1 , · · · , dkn) is a delay vector and dki = max{t ∈ [k] : it = i}, i.e. the
Algorithm 2 (Asynchronous FedDR (asyncFedDR)) 1: Initialization: Take x0∈dom(F ) and choose η > 0 and α > 0.
Initialize the server with x̄0 := x0 and x̃0 := 0. Initialize each user i ∈ [n] with y0i := x0, x0i := proxηfi(y 0 i ), and x̂ 0 i := 2x 0 i − y0i .
2: For k := 0, · · · ,K do 3: Select ik such that (ik, dk) is a realization of (̂ik, d̂k). 4: [Communication] User ik receives x̄
k−dkik , a delayed version of x̄k with the delay dkik . 5: [Local update] User ik updates
yk+1ik := y k ik + α(x̄k−d k ik − xkik), x k+1 ik := proxηfik (yk+1ik ), and x̂ k+1 ik := 2xk+1ik − y k+1 ik .
Other users maintain yk+1i := y k i , x k+1 i := x k i , and x̂ k+1 i := x̂ k i for i 6= ik.
6: [Communication] User ik sends ∆kik := x̂ k+1 ik − x̂kik back to the server. 7: [Sever aggregation] The server aggregates x̃k+1 := x̃k + 1n∆ k ik
. 8: [Sever update] Then, the sever updates x̄k+1 := proxηg ( x̃k+1 ) . 9: End For
last time x̂i gets updated up to iteration k. Note that when dki = 0 for all i, Algorithm 2 reduces to its synchronous variant, i.e. a special variant of Algorithm 1 with Sk = {ik}.

heading: 4.2 Convergence analysis
text: Since we treat the active user ik and the delay vector dk jointly at each iteration k as a realization of a joint random vector (̂ik, d̂k), we adopt the probabilistic model from [5] to analyze Algorithm 2. This new model allows us to cope with a more general class of asynchronous variants of our method.
Probabilistic model. Let ξk := (ik, dk) be a realization of a random vector ξ̂k := (̂ik, d̂k) containing the user index îk ∈ [n] and the delay vector d̂k = (d̂k1 , · · · , d̂kn) ∈ D := {0, 1, · · · , τ}
n presented at the k-the iteration, respectively. We consider k + 1 random variables that form a random vector ξ̂0:k := (ξ̂0, · · · , ξ̂k). We also use ξ0:k = (ξ0, ξ1, · · · , ξk) for k + 1 possible values of the random vector ξ̂0:k. Let Ω be the sample space of all sequences ω := {(ik, dk)}k≥0. We define a cylinder Ck(ξ0:k) := {ω ∈ Ω : (ω0, · · · , ωk) = ξ0:k} and Ck is the set of all possible Ck(ξ0:k) when ξt, t = 0, · · · , k take all possible values, where ωl is the l-th element of ω. Let Fk := σ(Ck) be the σ-algebra generated by Ck and F := σ(∪∞k=0Ck). For each Ck(ξ0:k) we also equip with a probability p(ξ0:k) := P(Ck(ξ0:k)). Then, (Ω,F ,P) forms a probability space. Assume that p(ξ0:k) := P(ξ̂0:k = ξ0:k) > 0. Our conditional probability is defined as p((i, d) | ξ0:k) := P(Ck+1(ξ0:k+1))/P(Ck(ξ0:k)), where p((i, d) | ξ0:k) := 0 if p(ξ0:k) = 0. We refer to Supp. Doc. B.2 for more details of our probabilistic model.
To analyze Algorithm 2, we impose Assumption 4.1 on the implementation below.
Assumption 4.1. For all i ∈ [n] and ω ∈ Ω, there exists at least one t ∈ {0, 1, · · · , T} with T > 0, such that ∑
d∈D
p((i, d) | ξ0:k+t−1) ≥ p̂ if p(ξ0:k) > 0, (7)
for a given p̂ > 0 and any k ≥ 0. Assume also that dki ≤ τ and dkik = 0 for all k ≥ 0 and i, ik ∈ [n].
Assumption 4.1 implies that during an interval of T iterations, every user has a non-negligible positive probability to be updated. Note that if the user ik is active, then it uses recent value with no delay, i.e., dkik = 0 as in Assumption 4.1. Moreover, the bounded delay assumption d k i ≤ τ is standard to analyze convergence of asynchronous algorithms, see e.g., [5, 32, 34, 35, 44].
Suppose that we choose 0 < α < ᾱ and 0 < η < η̄ in Algorithm 2, where c := 2τ 2−n n2 is given, and ᾱ > 0 and η̄ > 0 are respectively computed by
ᾱ := { 1 if 2τ2 ≤ n, 2
2+c otherwise, and η̄ :=
 √ 16−8α−7α2−α 2L(2+α) if 2τ 2 ≤ n, √ 16−8α−(7+4c+4c2)α2−α
2L[2+(1+c)α] otherwise. (8)
Next, we introduce the following two constants:
ρ :=  2(1−α)−(2+α)L2η2−Lαη αηn if 2τ 2 ≤ n,
n2[2(1−α)−(2+α)L2η2−Lαη]−α(1+η2L2)(2τ2−n) αηn3 otherwise.
D := 8α 2(1+L2η2)(τ2+2Tnp̂) + 8n2(1+L2η2+Tα2p̂)
p̂α2n2 .
(9)
Then, both ρ and D are positive. We emphasize that though these formulas look complicated, they are computed explicitly without any tuning. Theorem 4.1 proves the convergence of Algorithm 2, whose analysis is in Supp. Doc. B. Theorem 4.1. Suppose that Assumption 2.1, 2.2, and 4.1 hold for (1). Let ᾱ, η̄, ρ, and D be given by (8) and (9), respectively. Let {(xki , yki , x̄k)} be generated by Algorithm 2 with stepsizes α ∈ (0, ᾱ) and η ∈ (0, η̄). Then, the following bound holds:
1
K + 1 K∑ k=0 E [ ‖Gη(x̄k)‖2 ] ≤ Ĉ [ F (x0)− F ? ] K + 1 , (10)
where Ĉ := 2(1+ηL) 2D
nη2ρ > 0 depending on n,L, η, α, τ, T, and p̂.
Let x̃K be selected uniformly at random from {x̄0, · · · , x̄K} as the output of Algorithm 2. Then, after at most K := O ( ε−2 )
iterations, x̃K is an ε-stationary point of (1) as in Definition 2.2. Remark 4.1. From Theorem 4.1, we can see that asyncFedDR achieves the same worst-case communication complexity O ( ε−2 ) (up to a constant factor) as FedDR, but with smaller α and η.

heading: 5 Numerical Experiments
text: To evaluate the performance of FedDR and asyncFedDR, we conduct multiple experiments using both synthetic and real datasets. Since most existing methods are developed for non-composite problems, we also implement three other methods: FedAvg, FedProx, and FedPD to compare for this setting. We use training loss, training accuracy, and test accuracy as our performance metrics.
Implementation. To compare synchronous algorithms, we reuse the implementation of FedAvg and FedProx in [23] and implement FedDR and FedPD on top of it. To conduct the asynchronous examples, we implement our algorithms based on the asynchronous framework in [3]. All experiments are run on a Linux-based server with multiple nodes and configuration: 24-core 2.50GHz Intel processors, 30M cache, and 256GB RAM.
Models and hyper-parameters selection. Our models are neural networks, and their detail is given in Supp. Doc. C. As in [23], we use the same local solver (SGD) for all algorithms and run the local updates for 20 epochs. Parameters for each algorithm such as µ for FedProx, η for FedPD, and α and η for FedDR are tuned from a wide range of values. For each dataset, we pick the parameters that work best for each algorithm and plot their performance on the chosen parameters.
Results on synthetic datasets. We compare these algorithms using synthetic dataset in both iid and non-iid settings. We follow the data generation procedures described in [23, 38] to generate one iid dataset synthetic-iid and three non-iid datasets: synthetic-(r,s) for (r, s) =
{(0, 0), (0.5, 0.5), (1, 1)}. We first compare these algorithms without using the user sampling scheme, i.e. all users perform update at each communication round, and for non-composite model of (1).
We report the performance of these algorithms on one non-iid dataset in Figure 2, but more results can be found in Sup. Doc. C. FedDR and FedPD are comparable in these datasets and they both outperform FedProx and FedAvg. FedProx works better than FedAvg which aligns with the results in [23]. However, when comparing on more datasets, our algorithm overall performs better than others.
Now we compare these algorithms where we sample 10 users out of 30 to perform update at each communication round for FedAvg, FedProx, and FedDR while we use all users for FedPD since FedPD only has convergence guarantee for this setting. In this test, the evaluation metric is plotted in terms of the number of bytes communicated between users and server at each communication round. Note that using user sampling scheme in this case can save one-third of communication cost each round. Figure 3 depicts the performance of 4 algorithms on one dataset, see also Sup. Doc. C.
From Figure 3, FedDR performs well compared to others. FedProx using user sampling scheme performs better and is slightly behind FedPD while FedDR, FedPD, and FedProx outperform FedAvg.
Results on FEMNIST datasets. FEMNIST [4] is an extended version of the MNIST dataset [19] where the data is partitioned by the writer of the digit/character. It has a total of 62 classes (10 digits, 26 upper-case and 26 lower-case letters) with over 800,000 samples. In this example, there are total of 200 users and we sample 50 users to perform update at each round of communication for FedAvg, FedProx, and FedDR while we use all users to perform update for FedPD. Fig. 4 depicts the performance of 4 algorithms in terms of communication cost. From Fig. 4, FedDR can achieve lower loss value and higher training accuracy than other algorithms while FedPD can reach the same test accuracy as ours at the end. Overall, FedDR seems working better than other algorithms in this test.
Results with the `1-norm regularizer. We now consider the composite setting with g(x) := 0.01 ‖x‖1 to verify Algorithm 1 on different inexactness levels i,k by varying the learning rate (lr) and the number of local SGD epochs to approximately evaluate proxηfi(y k i ). We run Algorithm 1 on the FEMNIST dataset, and the results are shown in Figure 5.
We observe that Algorithm 1 works best when local learning rate is 0.003 which aligns with [23] for the non-composite case. It also performs better when we decrease i,k by increasing the number of epochs in evaluating proxηfi . This performance confirms our theoretical results in Supp. Doc. A.5.
FEMNIST
FEMNIST, g = || ||1
Results using asynchronous update. To illustrate the advantage of asyncFedDR over FedDR, we conduct another example to train MNIST dataset using 20 users. Since we run these experiments on computing nodes with identical configurations, we simulate the case with computing power discrepancy between users by adding variable delay to each user’s update process such that the difference between the fastest user may be up to twice as fast as the slowest one.
MNIST
The results of two variants are presented in Figure 6, see Supp. Doc. C for more examples. We can see that asyncFedDR can achieve better performance than FedDR in terms of training time which illustrate the advantage of asynchronous update in heterogeneous computing power.
Acknowledgments and Disclosure of Funding
The work of Quoc Tran-Dinh is partially supported by the Office of Naval Research (ONR), grant No. N00014-20-1-2088. The authors would also like to thank all the anonymous reviewers and the ACs for their constructive comments to improve the paper.

Review summaries:
 This paper proposes FedDR and asyncFedDR for FL, which combines DRS and the randomized BCD strategy. Detailed convergence guarantees are also provided, which seems clear and correct to me. The authors also provide numerical results to support their theoretical claims.

This paper presents a new method for federated learning with a nonconvex but smooth objective function. The proposed method is based on Douglas Rachford Splitting to decompose the objective and randomized coordinate methodology to allow a random selection of users to update at each iteration. An extension to asynchronous settings is presented, allowing modeling of communication delays and similar practical considerations. The convergence of these methods (potential using inexact proximal calculations) is bounded by the typical O(\epsilon^-2) rate. Reasonable numerics are given showing the potential effectiveness of such a scheme on synthetic and real datasets.

This paper proposes FedDR, which extends FedSplit by allowing non-convex objective, partial participation and convex composite regularizers. This work also studies the asynchronous variant of FedDR. Detailed proofs and experiments are provided.