FedDR – Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
Authors: Quoc Tran-Dinh
Nhan Pham
Dzung T. Phan
Lam M. Nguyen
Venue: NeurIPS 2021 Poster (2021)
Keywords: Randomized Douglas-Rachford splitting method
nonconvex federated optimization
asynchronous algorithm

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 im- plementation. 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 sys- tem 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.

FedDR - Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
Quoe Tran-Dinh and Nhan H. Pham Department of Statisties and Operations Research, The University of North Carolina at Chapel Hill
318 Hanes Hall, UNC-Chaper Hill, NC 27599-3260 quoctd@email unc. edu, nhanph@live, unc. edu
Dzung T. Phan and Lam M. Nguyen IBM Research, Thomas J. Watson Research Center, Yorktown Heights, NY, USA. phandu@us. ibm. com, lamnguyen. mww.diimm..mmmmmmm com
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 novel combination between nonconvex mouglas-Rachfow splitting method, randomized block-coordinate strategies, and asynchronous im- plementation. They can also handle convex regularizers. Unlike recent methods in the literature, c.g., FedSplit and FedPD, algorithms update only subset users at each communication round, and possibly in an asynchronous manner, making them more practical. These new algorithms can handle statistical and sys- tem heterogeneity, which are the two main challenges in federated learning, while achieving the best known communication complexity. In fact, 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.
algorithms
Introduction
Training machine learning models in 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 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, 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 aggregating local models.
Challenges. FL provides promising solution for many machine learning applications such as learning over smartphones or across organizations, and internet of things, where privacy protection one of the most critical requirements. However, this training mechanism faces number of fundamental challenges, see, c.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 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 (NcurIPS 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 each round of communication. Another challenge in FI. is privacy concern. Accessing and sharing local raw data is not permitted in FI.. 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 [5I]. 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 to further and simultaneously address these funda- mental challenges by proposing two new algorithms to train the underlying common optimization model in FL. Our approach relies on a novel combination between randomized clordccoe strategy, nonconvex Douglas-Rachford Rachford (DR) splitting, and asynchronous implementation. While each individual technique or partial combinations 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- Mook-ccordd DR splitting methods for nonconvex composite FL. optimization models, and they are fundamentally different from some works in the convex setting, e.g.,
Contribution. Our contribution can be summarized follows.
(a) We develop new FL algorithm, called FedDR (Federated -angglss,,c by combin- ing the well- DR splitting technique and randomized coockccoordinate 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 (e-2) communication complexity for finding stationary point under standard assumptions (Assumptions 2.1 (.2)). where s is 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 asyn- chronously perform local update and periodically send the update to the server for proximal aggregation. We show that asyncFedDR achieves the same communication complexity O (E as FedDR (up to a constant factor) under the same standard assumptions. This algorithm expected to simultaneously address all challenges discussed above.
Let us emphasize some key points of our contribution. First, the best known O (c-2) communication complexity of our methods matches the lower bound complexity up constant factor shown in [49], even with inexact evaluation of the objective proximal operators. Second, our methods rely on 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, 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 (33 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, c.g., [34 35 39). Our asynchronous variant, asyneFedDRR can fairly address this challenge. Moreover, it uses general probabilistic model recently introduced in (5), which allows us to capture the variety of asynchronous environments and architectures compared existing methods, e.g., 33
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 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 |4 43). Analyzing convergence of FedAvg
2

---

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. [5] also considers local SGD in the nonconvex setting.
Without using an additional bounded gradient assumption as in 33 45 41 improves the complexity for the general nonconvex setting while [ uses a Polyak-t.ojasiewiie (PL. condition to improve FedAvg's ss convergence results. In heterogeneous data settings, [77] 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 [3]
However, FedAvg might not converge with non-iid data as shown in
B3 49 [5]]
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 heterogeneous setting. Another method to deal with data heterogeneity is SCAFFOLD [16 which uses control variate to correct the "client-drift" in local update of FedAvg. MIME [5] 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.
FedProx
FedSplit 33] instead employs a Peaceman Rachford splitting scheme to solve a constrained reformu- lation of the original problem. In fact, FedSplit can be viewed as a variant of Tseng's splitting scheme [ applied to FL. B3] show that FedSplit can find 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 66 10
12
14
25, 46).
Our approach in this paper relies on nonconvex DR splitting method, which can handle the heterogene- ity as discussed in (33]. While the DR method is classical, its nonconvex variants have been recently However, the combination of DR and randomized block-coordinate
studied e.g., in p
40
strategy remains limited 7 g even in the convex settings. Alternatively, asynchronous algorithms
have been extensively studied in the literature, also for FL, see, e.g.. 2 34 33). 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 non-composite settings. Hence, our work here appears to be the first
Content. The rest of this paper organized as follows. Section 2 states our FL optimization model and our assumptions. Section 3 develops FedDR and analyzes its convergence. Section considers considess an asynchronous variant, FedDRR Section is devoted for numerical experiments. Due space limit, all technical details and proofs can be found in Supplementary Document (Supp. Doc.).
2 Nonconvex Optimization Models in Federated Learning
The underlying optimization model of many FL applications can be written into the following form:
1 F(x) = f() g(x) - Σ f((x) + f((x)+ )(x)).
min ZERP
(1)
where n is the number of users, and each f; is local loss of the i-th user, which is assumed to be nonconvex and L-smooth (see Assumptions and beloww, and g is proper, closed, and convex regularizer. Apart from these assumptions, we will not make any additional assumption on (L). We emphasize that the use of regularizers has been motivated in several works, including 47).
Let dom(F (F) : {i R" F(x) < +oo} be the domain of F and 0g be the subdifferential of g [. Since I is nonconvex, we only expect to find a stationary point, which characterized by the following optimality condition.
Definition 2.1. 0 E vz(=*) + 0g(x")) ) then x² is called a [first-order] stationary point of [
The algorithms for solving @ developed in this paper will rely on the following assumptions.
Assumption 2.1 (Boundedness from below). dom(F) * 0 and F := infeeR F(x) > -00.
3

---

Assumption 2.2 (L-smoothness), All functions f.(.) for [n] := {1, ,n) are L-smooth, i.e. fi is continuously differentiable and there exists (0, + +00) such that [V Vf((i)ll S L| - vll, Vx,y E dom(f))
(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 I. for all J, is not restrictive since if f, is Ta-smooth, then by scaling variables of its constrained formulation (see [1I in Supp. Doc.), we can get the same Lipschitz constant of all fi-
Proximal operators and evaluation. Our methods make use of the proximal operators of both fi and g. Although is L-smooth and nonconvex, we still define its proximal operator
pr (x) ;= argmin { f(y)) + 2n
=||²),
(3)
where 17 > O. Even fi is nonconvex, under Assumption 2.2 if we choose 0 0< < L. then prox,, well-defined and valued. Evaluating prox, requires solve a strongly convex program. If prox,f: can only be computed approximately up to an accuracy é 2 0 to obtain 2, denoted by 4 : prox,s, (t), if ||++ - prox,s, (x)]l S 6;. Note that instead of absolute error, one can also use a relative error as ||++ - prox,f, nf. (x)] || S <,||= - øl as in (37] For the convex function g. its proximal operator prox,g defined in the same way as (.. Evaluating prox,,. can be done by various existing methods, including local SGD and accelerated GD-type algorithms. However, this is our focus in this paper, and therefore do not specify the subsolver for evaluating prox,f."
Gradient mapping. As usual, let us define the following gradient mapping of F in (T.
(x) = 1 (x pg 7 f(z)))
> 0.
(4)
1) Then, the optimality condition E ff(==) 0g(x") of ①I is equivalent to (z²x) O. However, in practice, we often wish to find an e-approximate stationary point to (T) defined as follows.
Definition 2.2. If ã E dom(A) F) satisfies E [ S x², then á is called e-stationary point of T where the expectation is taken overall the randomness generated by the underlying algorithm.
Note that, for (i) to be well-defined, we require E dom(F). In our algorithms below, this requirement is fulfilled if ã dom(f), which is often satisfied in practice dom(s) R.".
3 FedDR Algorithm and Its Convergence Guarantee
Prior to our work, FedSplit 333 exploits similar update steps as ours by adopting the Peaceman- Rachford splitting method to solve the convex and non-composite instances of (T). FedSplit can overcome some of the key challenges as discussed earlier. Following this idea, take the advantages of the DR splitting method to first derive new variant to handle the nonconvex composite problem [II This new algorithm is synchronous and we call it FedDR. The central idea is as follows: First, we reformulate resulting problem. Finally, we combine such a scheme with randomized block-coordinate strategy.
I into (12) by duplicating variables. Next, we apply a DR splitting scheme to the
The complete algorithm is presented in Algorithm [ where its full derivation in Supp. Doc. A.
Let us make the following remarks. Firstly, FedDR mainly updates of three sequences {**), { and {uf}. While h² is an averaged model to approximately minimize the global objective function F. xt act as local models trying to optimize a regularized local loss function w.r.t. its local data distribution, and v keeps track of the residuals from the local models to the global one. Secondly, we allow of to be an approximation of prox,,, f. (v.²) ) up to an accuracy 4, 2 0 as defined in B3) i.e., ||a - prox, (ut)ll II S fi, for all E [m] if k = O and for all i E S if k > O. If E = 0, then get the exact evaluation x. prox, of (v.) ). Approximately evaluating prox f; can be done, e.g., by local SGD as in FedAvg. Thirdly, Algorithm iis different from existing randomized proximal gradient-based methods since we rely Here, three iterates y - and o. at Step are updated sequentially, making it challenging to analyze convergence. Lastly, the subset of active users S₁ is sampled from random set-valued mapping S. As specified in Assumption 3.1 this sampling mechanism covers a wide range of sampling strategies. Clearly, if S [n) and g = O, then Algorithm 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 ( and Algorithm] I are completely different from [47]
DR splitting scheme and handle composite settings.

---

Algorithm 1 (FL with Randomized DR (FedDR))
1: Initialization: Take æ² E clom(F) Choose 1] > 0 and a > and accuracies <..0 2 0 (i [n])
Initialize the server with æ0 := x and 1o = x Initialize each user i E [r]] with vf == x", x. ss prax, (v and af == 22 - v..
2: For k == o.... do
3: [Active users] Generate proper realization Sy S [x] of (see Assumption 3.1.
4: [Communication) Each user E St receives h from the server.
5: [Local update] For each user E S₁ do: Choose Ei,K+1 2 0 and update
vh+1 v + aa(" -x;;, + prox,f; (yt 1 and F 2x, yi k+1
6: [Communication) Each user E Sg sends Art = 1.41 1.t back to the server.
7: [Sever aggregation] The server aggregates gk+1 := z + Eies. A
8: [Sever update] Then, the sever updates r*+1
prox,g (iht)).
9: End For
3.1 Convergence of Algorithm
Let us consider a proper sampling scheme S of [n],, which a random set-valued mapping with values in 2fn), the collection of all subsets of [n]. Let Sş be an iid realization of & and F& := a (So, ,Ss) be the o-algebra generated by So. SR. We first impose the following assumption about the distribution of our sampling scheme S.
Assumption 3.1. There exist PI. P. such that P(i E 8) = P. > 0 for all i [n].
This assumption covers large class of sampling schemes as discussed in [36 including non- overlapping uniform and doubly uniform. This assumption guarantees that every user has a non- negligible probability to be updated. Note that p; = -Esaes P(S) due to Assumption 3.1 For the sake of notation, we also denote p == min i [m]] >0 0.
The following theorem characterizes convergence of Algorithm I with inexact evaluation of prox, Sup. Doc. for more details about the choice
Due to space limit, we refer the reader to Lemma A.6 (.6mma of stepsizes and related constants. The proof of this theorem is defered Sup. Doc. A.5
Theorem 3.1. Suppose that Assumptions 2./ 2.2 and
3.7 hold. Let {xx ; vt ah. 5²)} be generated Then, the following holds
by Algorithm using stepsizes and v) defined in (33
K
S C[
F+
K
Σ K=
E
(C + C3 (5)
K
K+1
K+1
n(K
K
k=0
where B. pr. and p2 are explicitly defined by (35 and
C= ((1+))) C2:= and C3 := 11 +
(1+nL)
BB
Let kK be selected uniformly at from { ,,.,,,K } as the output of Algorithm Let the accuracies c, for all i E [n] and k 2 0 at Step 5 be chosen such that 1 EE K+l
Gi S M for given constant M >> 0 and all K 2 0. Then, if we run Algorithml for at most
C [ (x F*] + (C2 + Ca)M
K=
O (E 2)
22
iterations, then J.K is e-stationary point of ① in the sense of Desinition
2.2
Remark 3.1. [Choice accuracies <] To guarantee 1 -m= Ek 2x M in Theorem 3.1 for
a given constant M > 0 and for all K 2 0. one can choose, e.g., 2, = 2(++1== for all i E n and K+I Ek=0 EK+ C 4 E T+TIJ= < M. Note that,
M
A > 0. In this case, we can easily show that 1 ΣE=E
K+1
instead of using absolute accuracies, one can also use relative accuracies as ||ei, < 01| 11 for a given constant 0 > O, which more practical, while still achieving a similar convergence guarantee. Such idea has been widely used in the literature, including (28) (see Supp. Doc. Doc.(A.7)
5

---

Remark 3.2 (Comparison). Since ①I is nonconvex, our O 3 communication complexity is the sate-offthh-arr, matching the lower bound complexity (up constant factor) 449 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 variant of the Peaceman- Rachford splitting method, i.c. a = and only considers convex non-composite case while we use a relaxation parameter < 2 and for more general nonconvex composite problem (T.
The following corollary specifies the convergence of Algorithm with specific choice of stepsizes and exact evaluation of fr whose proof in Sup. Doc. A.6
Corollary 3.1. Suppose that Assumptions 2. 2.2 and 3./ hold. Let {ax) uI, u ,/, x²1) be generated by Algorithm!! 7 using stepsizes a = 1, 17 31. and pj n' Under exact evaluation of prox,5.' i.e. 6r, = for all i E [m]] and 2 0, the following bound holds
K
160Ln
Σ
S
[F(x") F*).
K+1
3(K +1)
Let a.K be selected uniformly at random from {59 ...
kk} as the output of Algorithm
Then after
at most
K 160Ln F(x F*]
3=2
communication rounds, KKK becomes an E-stationary point of (defined by Definition 2.2
4 AsyncFedDR and Its Convergence Guarantee
Motivation. Although FedDR has been shown to converge, it is more practical to account for the system heterogeneity of local users. Requiring synchronous aggregation the end of each communication round may lead to slow down in training. 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, only consider S₁- == {i the exact evaluation of prox, and bounded delay, but extensions to general S₁ and inexact frox,,, are similar to Algorithm
4.1 Derivation of asyncFedDR
Let us first explain the main idea of asyneFedDR. At each iteration k, each user receives delay copy gk-d", of z from the server with a delay d', The active user in will update its own local model (ul, of, aaf) in an asynchronous mode without waiting for others to complete. Once completing its update, user in just sends an increment A.k 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 i& is chosen from realization (ix, dd²) of joint random vector (ik, d² at the k-th iteration. Here, we do not assume is be uniformly random or independent of the delay dk. This allows Algorithm 2 to capture the variety of asynchronous implementations and architectures. Note that _² k at Step is delayed version of æ² which only exists on the server when user & is reading. However, right after, x² may be updated by another user.
Illustrative example. To better understand the update of asyncFedDR, Figure depicts a simple scenario where there are 4 users (C1- C4) asynchronously perform updates and with 9()) 0. At iteration l = 4, user C44 finishes its update so that the server performs updates. During this process,
user C1 starts its update by receiving global model - from server which is the average of (44, 222 44. (4). At iteration L = 7, C'l finishes its update. Although in and T. do not change during this time, i.e. #9 #1 and 3-. d:4. fe and ig have been updated at k = 5, 6 from user C2 and C3, respectively. Therefore, the global model Ø² used perform the update at k 7 is actually aggregated from (#f, 2 .5. #f) not (#9, 26, .g. af). In other words, each user receives a delay estimate = where d (di, d%) is delay vector and dē max{t [k] it = i}. i.c. the

---

Algorithm 2 (Asynchronous FedDR (asyncFedDR))
1: Initialization: Take æº (F) and choose rj > and a > 0.
Initialize the server with z := x" and x == O. Initialize each user E [xx] with yf = xd x = prox s, (v.). and i.. == =2=? - -y..
2: For k := 0,... K do
3: Select is such that (ix,d") ) is realization of (bk, d²).
4: [Communication] User is receives _² zk-di, delayed version of 3h with the delay di.
5: [Local update] User is updates
k+1 : vi. + a( di 2
b+1 = prox (w(++!) and a/tt = 20/4 Vie
k++
Vit
Other users maintain y. |+ = yf 2i k+1 == xt. and sht1 = af for i i ix.
6: [Communication) User is sends A == ab+1 - t back to the server.
7: [Sever aggregation] The server aggregates #++1 == I² + A
8: [Sever update] Then, the sever updates gk+1 = prox, (5ht1).
9: End For
last time à; gets updated up iteration k. Note that when di 0 for all i, Algorithm synchronous variant, i.e. a special variant of Algorithm with Sy = {ix]-
2 reduces its
A
A
A
A
C2
UP
UP
UP
k=4
kmS
k-6
k=7
km
k=9
Figure 1: Asynchronous update with 4 users and without regularizer g. Here, "A" blocks represent server process and "UP" blocks represent user process; C1 C1-Ca are communication rounds.
4.2 Convergence analysis
Since we treat the active user in and the delay vector d jointly each iteration & as a realization of a joint random vector (ig, d²), we adopt the probabilistic model from (5] analyze Algorithm 2
This new model allows us cope with more general class of asynchronous variants of our method.
Probabilistic model. Let c* = (ik, d²) be a realization of random vector e* = (ix, d containing
the user index is E [n]] and the delay vector d² (di. d E D= = 1. , presented at the kethe iteration, respectively. We consider & + random variables that form a random vector go.k = (Eo ..,...... )*). We also use go.k = (5", " ......... {*) for & + possible values of the random vector g0:h: Let Q be the sample space of all sequences w == {(i,, dt H=z0. We define a cylinder C.ke := (w Ω (Wo. wx) = g0=k] } and C. is the set of all possible (x(k)))) when E 0, 00....,4 take all possible values, where W/ is the (-th element of Let Fx == (Ce)) be the o-algebra generated by Ce and F C() For each Cu (E we also equip with probability p(_0:k) (((Ck()0))), Then, (2, forms probability space. Assume that p(c0:k) == Piik = c > 0. Our conditional probability is defined as p((i, d) g0.k) == F(C (PCCC where p((i,d) d) go:k) = 0 if p(gukk) O. We refer to Supp. Doc. B.2 for more details of our probabilistic model.
To analyze Algorithm 2 impose Assumption 4.1 on the implementation below.
Assumption 4.1. For all i [r] and E EΩ, there exists at least one /. E {0, 1..,, ,7) with T 0. such that
Σ p((i d) | (0b4t-11) P if O(skk) 0, dED
7

---

for given p > 0 and any k 2 0. Assume also that di S 7 and d:, 0 for all & 2 0 and i, ig [n]].
Assumption implies that during an interval of T iterations, every user has a non-negligible positive probability to be updated. Note that if the user is is active, then it uses recent value with no delay, ie.. d as Assumption 4.1 Moreover, the bounded delay assumption d S T is standard to
analyze convergence of asynchronous algorithms, see e.g. [5 32 34 35 44)
Suppose that choose 0 â and 17 in Algorithm and > are respectively computed by
where
27 n is given, and a²
v 7a
2f S n,
2 S n, otherwise,
2T((++))
ā
and ;=
(8)
2 2+c
8a 4
otherwise.
Next, we introduce the following two constants:
2(1-0)- (2-a) Lon
if 2T S n,
=
n
Laon aal+)
otherwise.
(9)
agn
Sa (1+22 +2Tmp)
+ 8n (
D
Bain2
Then, both P 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 hold for ① Let ā, 1 p. and D be given by with stepsizes a (0,
{ and respectively. Let (( v x²} be generated by Algorithm 2
and 1) E (). Then, the following bound holds:
K
O[F(x") - F+)
E
(F
(10)
K+1
K+1
K=
where Ć = 2(1+yL) depending on n, I, 17, Oz T, T, and nuj²p
Let æ be selected uniformly at random from {5 ...,.....""""................... ,KK
as the output of Algorithm 2 Then, after at most K = O (E-2) iterations, a is an e-stationary point of (1) as in Definition 2.2
Remark 4.1. From Theorem 4.1
that asyneFedDR achieves the same worst-case commu- nication complexity O (c-2 (up to a constant factor) as FedDR, but with smaller a and 17.
Numerical Experiments
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 compare for this setting. We use training loss, training accuracy, and test accuracy as our performance metrics.
Implementation. To compare synchronous algorithms, and FedProx in (23 and implement FedDR and FedPD on top of it. To conduct the asynchronous examples, implement are run on a Linux-based server with multiple nodes and configuration: 24-core 2.50GHz Intel processors, 30M cache, and 256GB RAM.
reuse the implementation of FedAvg
algorithms based the asynchronous framework in 3. All experiments
Models and hyper-parameterr selection. Our models are neural networks, and their detail 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, 77 for FedPD, and a and 7 for FedDR are tuned from wide range of values. For each dataset, 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 [2 38 to gener- ate one iid dataset synthetic-iid and three non-iid datasets: synthetic- (r, for (r,s)

---

synthetic-(0.5.00
3.0
0.6
Train oss
2.5
TestAce
2.0
0.4
0.4
FedAvg
1.5
FedProx
0.2
0.2
FedPD
FedDR
100 Rounds
150
50
100
150
Rounds
Figure 2: The performance of algorithms on non-iid synthetic datasets without user sampling
{(0, 0), (0.5, 0.5), (1, We first compare these algorithms without using the user sampling scheme, Le. all users perform update at each communication round, and for non-composite model of (T).
We report the performance of these algorithms one non-iid dataset in Figure 2 but more results can 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 each communication round. Note that using user sampling scheme in this case can save one-third of communication cost each round. Figure depicts the performance algorithms on one dataset, see also Sup. Doe.
synthetic-(0.5.00.
0.8
Tount
2.5
TestAce
2.0
FedAvg
FedProx
1.0
FedPO
0.5
FedDR
Bytos
Bytos
Bytes
Figure 3: The performance of 4 algorithms with user sampling scheme on non-iid synthetic datasets.
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 an extended version of the MNIST dataset [9 where the data is partitioned by the writer of the digit/character. It has 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 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. depicts the performance of algorithms in terms of communication cost. From Fig. FedDR can achieve lower loss value and higher training accuracy than other algorithms while FedPD can reach the same test accuracy as ours the end. Overall, FedDR seems working better than other algorithms in this test.
Results with the -oor regularizer. We now consider the composite setting with g(x) := 0.01 ||~||| to verify Algorithm I on different inexactness levels 61 by varying the learning rate (Ir) and the number of local SGD epochs to approximately evaluate prox, (v/"). We run Algorithm on the FEMNIST dataset, and the results are shown in Figure 5
We observe that Algorithm works best when local learning rate is 0.003 which aligns with 24 for the non-composite case. also performs better when we decrease 6i,k by increasing the number of epochs in evaluating frox,f.- This performance confirms theoretical results in Supp. Doc. A.5

---

FEMNIST
0.8
0.8
TestAc
FedAvg
FedProx
0.2
0.0
FeaDR
1e9
Figure 4: The performance of 4 algorithms the FEMNIST dataset.
FEMNIST, g I1-111
1.0
2.0
Trainkec
Textfcc
MN
0.000
00000
0.805
0.008
0.01
50
100
150
200
100
150
200
50
100
150
200
Comm. Rounds
Comm. Rounds
Comm. Rounds
FEMNIST, - || 111
1.00
0.85
0.95
0.80
Trainlets
0.90
0.75
0.85
0.70
epoch =
opoch
0.80
0.65
epech
0.75
0.60
epoch 20
epoch
150
200
100
150
200
50
100
150
200
Comm. Rounds
Comm, Rounds
* Comm. Rounds
Figure 5: The performance of FedDR on FEMNIST dataset in composite setting.
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 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 twice fast the slowest one.
MNIST
0.15
3.56
0.96
Theet
0.30
0.35
0.54
0.84
asyndFedDR
0.00
3000
4500
6000
0.50
1500
3000
4300
6000
0.00
1500
3000
4500
6000
Time
Time
Figure The performance of FedDR and asDDcFedDR on the MNIST dataset.
The results of variants are presented in Figure 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 heterogeneous computing power.
Acknowledgments and Disclosure of Funding
The work of Quoe Tran-Dinh is partially supported by the Office of Naval Research (ONR), grant No. N00014-20-1-225 The authors would also like to thank all the anonymous reviewers and the ACs for their constructive comments to improve the paper.
10

---

References
[1] H. H. Bauschke and P. Combettes. Convex analysis and monotone operators theory in Hilbert 2nd edition, 2017.
spaces. Springer-Verie
[2] D.P. Bertsekas and J. N. Tsitsiklis. Parallel and distributed computation: Numerical methods. Prentice Hall, 1989.
[3] Jesse Cai. Implementing DistBelief.
2018.
[4] Caldas, M. Duddu, P. Wu, Li, Konečný, H. B. McMahan, V. Smith, and Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv:/812.01097 2018.
[5] L. Cannelli, F. Facchinei, V. Kungurtsev, and G. Scutari. Asynchronous parallel algorithms for nonconvex optimization. Math. Program., pages 1-34, 2019.
[6] Z. Charles and J. Konečný. Convergence and accuracy trade-offs in federated learning and meta-learning. In International Conference on Artificial Intelligence and Statistics, pages 2575-2583. PMLR, 2021.
[7] P. Combettes and J. Eckstein. Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions. Math. Program., 168(1) (66()))6556672, 2018.
[8] L. Combettes and J.-C. Pesquet. Stochastic -uasi-Fejér coorddiiat fixed point iterations with random sweeping. SIAM J. Optim., 25(2): 2015.
[9] M. N. Dao and M. K. Tam. A Lyapunov-type approach to convergence of the Douglas-Rachfort algorithm for a nonconvex setting. J. Global Optim., 73(1):83-112, 2019.
[10] E. Gorbunov, Hanzely, and P. Richtárik. Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statisties, pages 3556-3564.
PMLR, 2021.
[11] Haddadpour, M. M. Kamani, M. Mahdavi, and V. Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pages 1082-11094, 2019.
[12] Haddadpour, M. M. Kamani, A. Mokhtari, and M. Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference on Artificial Intelligence and Statistics, pages 2350-2358. PMLR, 2021.
[13] Haddadpour and M. Mahdavi. On the convergence local descent methods in federated learning. arXiv preprint 1900:4/910. 2019.
[14] F. Hanzely, S. Hanzely, S. Horváth, and P. Richtárik. Lower bounds and optimal algorithms for personalized federated learning. arXiv preprint arXiv:2010.0237.. 2020.
[15] S. P. Karimireddy, M. Jaggi, S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. A. Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.033 03600, 2020.
[16] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. Seaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[17] A. Khaled, K. Mishchenko, and P. Richtárik. First analysis of local GD heterogeneous data. arXiv preprint arXiv: 195 2019.
[18] J. Konečny, H. B. McMahan, D. Ramage, and Richtárik. Federated optimization Distributed machine learning for on- intelligence. arXiv preprint arXin:1610.02557) 2016.
[19] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (66(1)):22)) 1):2278-2324, 1998.
[20] G. Li and T. K. Pong. Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim., 25(4):2434-2460, 2015.

---

[21] G. Li and T. K. Pong. Douglas-Rachforr Rachford splitting for nonconvex optimization with application nonconvex feasibility problems. Math. Program., 159(1-2):771401, 2016.
[22] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-66 10,0006000000 2020.
[23] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. In I. Dhillon, D. Papailiopoulos, and V. Sze, editors, Proceedings of Machine Learning and Systems, volume 2. pages 429-450, 2020.
[24] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang. On the convergence of FedAvg on non-iid data. In International Conference on Learning Representations (ICLR), 2019.
[25] X. Li, M. Jiang, X. Zhang, M. Kamp, and Q- Dou. FedBN: Federated learning non-iid features via local batch normalization. In International Conference on Learning Representations (ICLR), 2020.
[26] Lin, S. U. Stich, K. K. Patel, and M. Jaggi. Don't use large mini-batches, use local SGD, In International Conference on Learning Representations (ICLR), 2019.
[27] P. L. Lions and B. Mercier. Splitting algorithms for the sum of two nonlinear operators. SIAM J. Num. Anal., 16:964-977 979, 1979.
[28] Y. Liu, Y. Xu, and W. Yin. Acceleration of primal-dual methods by preconditioning and simple subproblem procedures. Sci. Comput., 86(2):1-34, 2021.
[29] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication-efficeent learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[30] B. McMahan and D. Ramage. Federated learning: Collaborative machine learning without centralized training data. Google Research Blog, Jul 2017.
[31] Brendan McMahan et al. Advances and open problems in federated learning, Foundations and Trends@ in Machine Learning, 14(1), 2021.
[32] L. Nguyen, P. H. Nguyen, M. Dijk, P. Richtárik, K. Scheinberg, and M. Takác. SGD and Hogwild! convergence without the bounded gradients assumption. In International Conference on Machine Learning, pages 3750-3758. PMLR, 2018
[33] R. Pathak and M. Wainwright. FedSplit: An algorithmic framework for fast federated optimization. In Advances in Neural Information Processing Systems, vol. 33, pages 7057-7066, 2020.
[34] Z. Peng, Y. Xu, M. Yan, and W. Yin. ARock: an algorithmic framework for asynchronous parallel coordinate updates. SIAM J. Scientific Comput., 38(5):2851-2879 2016
[35] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent. J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances Neural Information Processing Systems 24, pages 693-701. Curran Associates, Inc., 2011.
[36] P. Richtárik and M. Takáč. Parallel coordinate descent methods for big data optimization. Math. Program., 156(1-2):433 484, 2016.
[37] R.T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM J. Control Optim., 14:877-898. 1976.
[38] O. Shamir, N. Srebro, and T. Zhang. Communication-efficee distributed optimization using an approximate newton-type method, In International conference on machine learning, pages 1000-1008, 2014.
[39] U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, pages 1-17, 2018.
12

---

[40] A. Themelis and P. Patrinos. Douglas Mauglas-Racfford splitting and ADMM for nonconvex optimiza- tion: Tight convergence results. SIAM Optim.. 30(1):149- 181, 2020.
[41] Wang and G. Joshi. Cooperative SGD: A unified framework for the design and analysis of communication-efficin SGD algorithms. ICML Workshop Coding Theory for Machine Learning, pages 1-5, 2019.
[42] B. Woodworth, K. K. Patel, and N. Srebro. Minibatch vs local SGD for heterogeneous distributed learning. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), 2020.
[43] B. Woodworth, K. K. Patel, S. U. Stich, Z. Dai, B. Bullins, H. B. McMahan, O. Shamir, and N. Srebro. Is local SGD better than minibatch SGD? In International Conference on Machine Learning (ICML), pages 10334-10343, 2020.
[44] C. Xie, S. Koyejo, and Gupta. Asynchronous federated optimization. arXiv preprint arXiv: 1903.03933 2019.
[45] H. Yu, S. Yang. and S. Zhu. Parallel restarted sgd with faster convergence and less communica- tion: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 5693-5700, 2019.
[46] Yu, L. Wynter, and S. H. Lim. Fed+: A family of fusion algorithms for federated learning. arXiv preprini urXiv:2009.06303, 2020.
[47] H. Yuan, M. Zaheer, and S. Reddi. Federated composite optimization. International Conference on Machine Learning, pages 11233-12260 2021.
[48] Zhang, De Sa, I. Mitliagkas, and C. Ré. Parallel SGD: When does averaging help? arXiv preprint 16066073655 2016.
[49] X. Zhang, M. Hong, S. Dhople, W. Yin, and Y. Liu. FedPD: A federated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005. 114188 2020.
[50] Y. Zhao, M. Li, L. Lai, N. Suda, D. Civin, and V. Chandra. Federated learning with non-iid data. arXiv preprini arXiv: 005800 2018.
[51] L. Zhu, Z. Liu, and S. Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems, pages
2019.
13


Reviews:
[{"review_id": "v-unzTO99P1", "reviewer": "Reviewer_A2nV", "summary": "\nThis 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.", "questions": "", "limitations": "", "rating": 7, "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": "\nMajor concerns:\n\n1. My first concern is regarding the inexactness evaluations of \\prox_{\\eta f_i}.\n\n   (1) First, in theorems 3.1 and 4.1, it would be much better if that fact that the error tolerances \\eps_{i, k} should be square summable (which is stated in the proof in the appendix). \n\n   (2) Secondly, in order to have square summable error tolerances, more and more inner loops (e.g., SGD or other solvers) are needed to solve these subproblems. This would make the total stochastic gradient complexity to be quite high. Note that what's presented in theorems 3.1 and 4.1 is the outer iteration complexity. \n\n   (3) A possible remedy is to apply warm-start on each subproblem and only solve it for a fixed number of iterations. Then, there will be a \"bounded relative error\", which will not hurt the overall 1/K convergence rate. \n\nThis idea has been applied in the following analysis of inexact preconditioned PDHG (or equivalently, ADMM). More specifically, please refer to Theorem 4 of this paper: \n\nLiu, Yanli, Yunbei Xu, and Wotao Yin. \"Acceleration of Primal–Dual Methods by Preconditioning and Simple Subproblem Procedures.\" Journal of Scientific Computing 86.2 (2021): 1-34.\n\nSince the analysis in the above paper also depends on a Lyapunov function, which looks quite similar to this work (Lemma A.5 and Lemma B.1). I think that this may help improve the overall stochastic gradient complexity of this work.\n\n(4) In the experiments, it should also be mentioned how many inner loops of SGD are applied in FedDR, asyncFedDR, as well as other algorithms. And a comparison of stochastic gradient complexity should be provided, in addition to the communication complexity presented. \n\nMinor concerns:\n1. The analysis also looks similar to those of ARock ([33] in this paper), where the bounded delay is also assumed and a Lyapunov type analysis is done, would you please provide some comparisons? \n2. On line 63, [nonsmooth] seems to be a typo.\n3. On line 79, early should be earliest. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "rqacBhEqni8", "reviewer": "Reviewer_TPm9", "summary": "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.", "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": "I would like to express my appreciation for your submission to NeurIPS 2021. This paper is overall well-written and I enjoyed reading it. This paper proposes FedDR which differs from existing works FedSplit, FedPD by allowing non-convex objective, partial participation and convex composite regularizers.  My main concerns are as follows:\n\n1. The algorithm FedDR requires an inner solver to compute the proximal operator of f. Although the authors kindly provide an inexact variant that allows for inexact approximation of prox_f, the additional inner computation is still not factored into the overall complexity. Therefore, it is hard to calibrate the complexities of FedDR with other first-order canonical algorithms such as FedAvg. (I acknowledge the same complain could apply to other prior works along this line such as FedPD and FedSplit.)\n\n2. This paper is mostly compared with the FedSplit and FedPD literature. However, as noted on line 128, the composite federated optimization has been explored by [45, Federated Composite Optimization] for the convex case. Though I agree with the author’s claim that FedDR is different from the algorithms in [45], this paper misses necessary comparisons with [45] either theoretically or empirically. For example, how does FedDR compare with [45] (theoretically and empirically) when the objective f is convex? \n\n3. The theorem 3.1 is somewhat concerning as the constant C still depends on the hyperparameter $\\alpha$ and $\\eta$. Is it possible to state a cleaner bound with specific variables $\\alpha, \\eta$ so that the dependency can be eliminated? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the main review section for limitations that needs improvement.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "k4LZDQgDCfL", "reviewer": "Reviewer_irs2", "summary": "The authors present an application of Douglas-Rachford for consensus optimization in federated learning. Their algorithm, unlike in prior work, explicitly handles subsampled clients, bounded delays, and also provides guarantees under for hypoconvex problems (smooth but not necessarily convex). \n", "questions": "", "limitations": "", "rating": 6, "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": "\nThe authors present a version of Douglas-Rachford that supports bounded delays and client subsampling for federated optimization. The techniques (stochastic approximation of the DR operator via client subsampling, and dealing with bounded delays) are more or less standard, and the results are not surprising.\n\nQuestions/comments:\n- The authors claim that FedSplit and FedPD do not allow for sub-sampling among clients (e.g. ll. 53-54, ll 66-67, of the submission). However, it is unclear to me that FedSplit and FedPD are non-convergent under client subsampling; are the authors claiming that if these algorithms are modified to allow random sub-selection of devices/agents/users/clients on each round, that these algorithms will not converge? \n- ll.103-104 is technically incorrect, FedSplit is an application of Peaceman-Rachford, not Douglas-Rachford; although similar, the latter is an \"averaged\" version of Peaceman-Rachford. \n- Can the authors comment on the convergence properties of FedDR with random subsampling of the clients/users under more standard complexity assumptions (e.g. F is convex (but not necessarily strongly convex) and smooth / F is strongly convex and smooth; in the latter case, FedDR should be able to attain linear convergence in expectation)? \n- It would be useful to state a corollary of Theorem 3.1 in the case alpha = 1, eta = c/L, and p_i = 1/n (uniform sampling), which corresponds to standard Douglas-Rachford with uniformly sampling and the optimal selection of the step-size. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the questions & comments section above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "_Xf8orQTFOO", "reviewer": "Reviewer_ZGGt", "summary": "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.", "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 use of $G_\\beta(\\tilde x)$ in Definition 2.2 as a stochastic quantity is confusing. In (4), $G_\\beta(x)$ is defined deterministically. Is this definition meaning that a stochastic approximation of $G_\\beta(x)$ generated by some algorithm is small? Or is $\\tilde x$ not a point in the domain of $F$ but rather a random variable that tends to have small $G_\\beta(\\tilde x)$?\n\n-The intuition for each $x_i$ and $y_i$ used in FedDR rely on the series of reformulations presented in Appendix A. Including some interpretation of these quantities in the main text would help readability.\n\n-It is interesting that the different components do not need to be sample uniformly in Assumption 3.1. Some intuition on how varied $p_i\\neq p_j$ is handled without leading to bias would be helpful.\n\n-Deferring the full statement of convergence results to the appendix is disappointing. Guarantees under inexact proximal evaluations are one of the works claimed contributions but do not appear anywhere in the main text.\nIn particular, a full description of the cost of an inexact method would include the cost of the SGD subroutine employed to approximate each strongly convex subproblem. This cost seems particularly important to include since the $\\epsilon_{i,k}$ choice recommended in the appendix is quite small (namely, $\\epsilon/(k+1)$). Including such costs would likely lead to a runtime worse than the claimed $O(\\epsilon^-2)$ rate.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper discusses the important challenges to federated learning in terms of privacy concerns and homogeneity assumptions upfront. The work makes some modest progress towards designing methods around these societal impacts but is primarily focused on computational advances rather than societal ones.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Federated learning algorithms based on operator splitting or ADMM are more sophisticated than simple algorithms such as FedAvg or FedProx, and they bring more flexibility and rigor in algorithm design. The proposed FedDR method and its asynchronous versions extends the classical Douglas-Rachford splitting method, combining with randomized block-coordinate updates, to the federated learning setting with nonconvex loss functions. 

The idea of applying operator splitting methods to federated learning has been proposed in a few recent works, but the reviewers are supportive of the generality and technical results obtained in this paper. They make solid contribution to the Federated Learning literature. 
Decision: Accept (Poster)