{'fraction_non_alphanumeric': 0.04259393437532347, 'fraction_numerical': 0.0169754683780147, 'mean_word_length': 4.535090232025207, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
FedADMM: A Federated Primal-Dual Algorithm Allowing Partial Participation

Federated learning is a framework for distributed optimization that places emphasis on communication efficiency. In particular, it follows a client-server broadcast model and is particularly appealing because of its ability to accommodate heterogeneity in client compute and storage resources, non-i.i.d. data assumptions, and data privacy. Our contribution is to offer a new federated learning algorithm, FedADMM, for solving non-convex composite optimization problems with non-smooth regularizers. We prove converges of FedADMM for the case when not all clients are able to participate in a given communication round under a very general sampling model.


Introduction
Federated learning (FL) [14,20], a novel distributed learning paradigm, has attracted significant attention in the past few years. Federated algorithms take a client/server computation model, and provide scope to train large-scale machine learning models over an edge-based distributed computing architecture. In the paradigm of FL, models are trained collaboratively under the coordination of a central server while storing data locally on the edge/clients. Typically, clients (devices and entities ranging from mobile phones to hospitals, to an internet of things [22,11]) are assumed to be heterogeneous; each client is subject to its own constraints on available computational and storage resources. By allowing data to be stored client-side, the FL paradigm has many favorable privacy properties.
In contrast to "traditional" distributed optimization, FL framework has its own unique challenges and characteristics. First, communication becomes problematic when the number of edge devices/clients is large, or the connection between the central server and a device is slow, e.g., when the mobile phones have limited bandwidth. Second, datasets stored in each client may be highly heterogeneous in that they are sampled from different population distributions, or the amount of data belonging to each client is unbalanced. Third, device/client heterogeneity can severely hinder algorithm performance; differences in hardware, software, and power (connectivity) lead to varying computation speeds among clients, leading to global performance being dominated by the slowest agent. This is known as the "straggler" effect. Additionally, the server may lose control over the clients when they power down or lose connectivity. It is thus common for only a fraction of clients to participate in in each round of the training (optimization) process, and federated optimization algorithms must accommodate this partial participation.
A wealth of algorithms have been developed to address the aforementioned challenges. Notably, work in [20] proposed the now popular FedAvg algorithm, where each client performs multiple stochastic gradient descent (SGD) steps before sending the model to the server for aggregation. Subsequent efforts [14,31,34,17,26] provided theoretical analysis and further empirical performance evaluations. Since the proposal of FedAvg, there has been a rich body of work concentrating on developing federated optimization algorithms, such as; FedProx [28], FedSplit [24], Scaffold [12], FedLin [21], FedDyn [1], FedDR [33] and FedPD [39].
We consider a general unconstrained, composite optimization models formulated as No convexity assumptions on f i are made and g can be non-smooth. Of the previously mentioned federated algorithms, we restrict our attention to FedDR and FedPD. These algorithms are designed to alleviate the unrealistic assumptions required by FedAvg in order to realize desirable theoretical convergence rates. As described in [33], FedDR combines the nonconvex Douglas-Rachford splitting (DRS) algorithm [16] with a randomized block-coordinate strategy. FedDR provably converges when only a subset of clients participate in any given communication round. In contrast, FedPD is a primal-dual algorithm which requires either full participation or no participation by all clients at every per round. Unlike FedDR, FedPD cannot handle optimization problems of the form of (1) for g ≡ 0.
The key observation of this paper is to note that the updating rules of FedPD share a similar form to those of the alternating direction method of multipliers (ADMM) [9], but specifies how the local models are updated to satisfy the flexibility need of FL. Motivated by the fact that ADMM is the dual formulation of DRS [36,7], we provide a new algorithm called FedADMM. Specifically, our contributions are:

Related Work
ADMM and DRS: DRS was first proposed in [5] in the context of providing numerical solutions to heat conduction partial differential equations. Subsequently, it found applications in the solution of convex optimization problems [19,29] and later non-convex problems [16,15,32]. ADMM [10,3] is a very popular iterative algorithm for solving composite optimization problems. The equivalence between DRS and ADMM has been subject of a lot of work [8,6,36,40]. It was first established for convex problems where ADMM is equivalent to applying DRS to the dual problem [8,6]. Recently, these ideas were extended in [32] to show equivalence in the non-convex regime. Inspired by the fact that FedDR can be viewed as a variant of nonconvex DRS applied to the FL framework, we propose a new algorithm, FedADMM and further extend the equivalence of these two algorithms to the FL paradigm.
Federated Learning: FedAvg was first proposed in [20]. However, it works well only with a homogeneous set of clients. It is difficult to analyze the convergence of FedAvg for the heterogeneous setting unless additional assumptions are made [17,18,13,35]. The main reason for this is that the algorithm suffers from client-drift [42] under objective heterogeneity. To address the data and system heterogeneity, FedProx [28] was proposed by adding an extra proximal term [23] to the objective. However, this extra term might degrade the training performance so that FedProx doesn't converge to the global or local stationery points unless the step-size is carefully tuned. Another method called Scaffold [12] uses control variates (or variance reduction) to reduce client-drift at the cost of increased communication incurred by sending extra variables to the server. FedSplit [24] applied the operator splitting schemes to remedy the objective heterogeneity issues, while it only considered the convex problems and required the full participation of clients. As mentioned earlier, FedDR [33] was inspired from DRS, and allowed partial participation. From the primal-dual optimization perspective, FedPD [39] proposed a new concept of participation, which restricted its potential application on real problems. It is also worthwhile to mention that FedDyn [1] is equivalent to FedPD [39] from [38] under the full participation setting, but it allows partial participation. Unlike [37], FedPD and FedDyn can't solve non-smooth or constrained problems. Finally, we refer readers to [11] for a comprehensive understanding of the recent advances in FL.

Preliminaries and Problem Formulation
We consider the canonical Federated learning optimization problem defined as where n is the number of clients, f i denotes the loss function associated to the i-th client. Each f i is nonconvex and Lipschitz differentiable (see Assumptions 2.1 and 2.2 below), and g is a proper, closed, and convex function and is not necessarily smooth. For example, g could be any p norm or an indicator function.
The notation [n] above defines the set {1, 2, . . . , n}. All the norms in the paper are 2 norm. We will frequently make use of the proximal operator [23]. Although typically defined for convex functions, we make no such assumptions.
is called the conjugate function of f .
Note that the conjugate function is closed and convex even when f is not, since it is the piecewise supremum of a set of affine functions.
where expectation is taken with respect to all random variables in the respective algorithm.

Douglas-Rachford Splitting
Douglas-Rachford Splitting (DRS) [5] is an iterative splitting algorithm for solving the optimization problems that can be written as Although originally used for solving convex problems, it has been shown to work well on certain non-convex problems with additional structure. DRS solves problem (4) by producing a series of iterates (y k , z k , x k ) for k = 1, 2, . . . given by where α is a relaxation parameter. When α = 1, (5) is the classical Douglas-Rachford splitting and when α = 2, (5) is a related splitting algorithm called Peaceman-Rachford splitting [25].
If f in problem (4) can decomposed as f (x) = 1 n n i=1 f i (x), then (5) can be modified so as to run in parallel if we include a global averaging step. The resulting algorithm is given below: A full derivation is given in [33]. Equation (6) is called full parallel Douglas-Rachford splitting (DRS).

FedDR
Implicit in the full parallel DRS (6), is the fact that all users are required to participate at every iteration. Instead of requiring all users i ∈ [n] to participate as in (6), work in [33] proposed an inexact randomized block-coordinate DRS algorithm, called FedDR. Here, a subset S k of clients is sampled from a "proper" sampling schemeŜ (See Definition 4 below for details) at each iteration. Each client, i ∈ S k performs a local update (i.e., executes the first three steps in (6)), then sends its local model to server for aggregation. Each client i / ∈ S k does noting. The complete FedDR algorithm is shown in Alg 1.
Randomly sample S k ⊆ [n] with size S.

6:
£ User side 7: for each user i ∈ S k do 8: receivex k from the server. 14: end for 15: £ Server side 16: aggregationx k+1 =x k + 1 n i∈S k ∆x k i 17: updatex k+1 = prox ηg x k+1 18: end for Convergence to an -stationary point of FedDR is guaranteed when the sampling schemeŜ is proper and Assumption 1 and 2 hold [33].
, we call the sampling schemeŜ proper, i.e., every client has a nonzero probability to be selected. Assumption 3. All partial participation algorithms in this paper use a proper sampling scheme.
From the analysis in [27], this assumption includes a lot of sampling schemes such as nonoverlapping uniform and doubly uniform sampling as special cases. The intuition behind proper sampling is to ensure that on average every client has a chance to be selected at every iteration.
In FedDR there are three variables that get updated:x k , x k i and y k i . The variablex k denotes the consensus/average variable to minimize the global model F , x k i denotes the local variable associated to f i , while y k i measures the distance between the global variablex k and local model x k i . To account for the limitations on computation resources for local users, FedDR allows the inexact calculation of the proximal step, i.e., Thus ≈ defines an -close solution. After local clients i ∈ S k update their model and send them back to the server, the server aggregates the updates to update the global model by executing line 16 and 17 in Algorithm 1.

From FedDR to FedADMM
Our first contribution is to derive the FedADMM algorithm from FedDR.

An equivalent formulation
We begin by rewriting problem (2) as the equivalent constrained problem: where x should be interpreted as the global consensus variable. Forming the Lagrangian of (7) and using the definition of the conjugate function, the dual formulation of (7) is max where z = z T 1 , z T 2 , · · · , z T n T ∈ R nd is the vector of dual variables. Problem (8) is clearly equivalent to min z 1 ,z 2 ,··· ,zn Before proceeding to develop an algorithm for solving (9), we first rewrite the full parallel DRS algorithm 6. Changing the execution order of (6) and choosing α = 1 give Introducing the change of variables w k i = x k i − y k i , we have the following parallel DR algorithm Remark 1. Note that (6), (10) and (11) are essentially the same parallel algorithm under a change of execution order and variables.

FedDR-II
From section 3, we observe that the only difference between full parallel DRS and FedDR is that FedDR only requires a subset of clients to update their variables, while full parallel DRS requires full participation. Similarly, by only considering partial participation in (11) 2. The k-th iteration: (k ≥ 0) Sample a proper subset S k ⊆ [n] so that S k represents the subset of active clients.

Communication:
Each user i ∈ S k sends onlyx k i to the server.

Server update:
The server aggregatesx k = 1 n n i=1x k i , and then computex k = prox ηg x k .
6. Communication (Broadcast): Each user i ∈ S k receivesx k from the server.

Client update (Local):
For each user i ∈ S k , given i,k+1 ≥ 0, it updates Each user i / ∈ S k does nothing, i.e.
FedDR and FedDR-II are equivalent because they are partial participation version of (6) and (11) respectively.

Solving the dual problem using FedDR-II
In this subsection, we use FedDR-II to solve the dual problem (9), introducing a new algorithm called FedADMM. We call this algorithm FedADMM because it is derived from applying FedDR-II to the dual problem (9). Let us define the augmented Lagrangian functions associated to (7) as where η denotes penalty parameter. Finally, we define ∆x k i =x k+1 i −x k i . With everything defined, FedADMM is shown in Algorithm 2.

6:
£ Client side 7: for each client i ∈ S k do 8: receivex k from the server.

9:
x k+1 i ≈ arg min £ Server side 15: aggregationx k+1 =x k + 1 n i∈S k ∆x k i 16: updatex k+1 = prox g/η x k+1 17: end for When g ≡ 0, the server-side steps 15-16 of FedADMM reduce to the single step: In this case, the updating rules of FedADMM are essentially the same as FedPD in [39]. Both compute the local model x k+1 i by first minimizing (12), followed by updating the dual variable λ k+1 i , and then aggregatingx k+1 i to achieve the global modelx k+1 . However, FedADMM allows for partial participation (only chooses a subset of clients to update) while FedPD requires all clients to update at each communication rounds, making it less practical and applicable in real world scenarios.
Note that FedADMM can handle the case where g ≡ 0 whereas FedPD didn't consider this more general formulation. Just like step 11 (approximately evaluating prox ηf i ) in FedDR, FedADMM obtains the new local model x k+1 i by inexactly solving (12). Note that we do not specify how to (approximately) solve the proximal steps or Langrangian minimization step in (either) algorithm. Various oracles are specified in [39].

Theoretical Analysis
We now present the main theoretical results of the paper. Namely, an equivalence between FedDR and FedADMM. Based on this, we leverage the FedDR convergence results [33] to show that FedADMM converges under partial participation.
We say that two iterative optimization algorithms are "equivalent" if they produce sequences (x k ) k≥0 and (y k ) k≥0 such that there exists a unique linear mapping between the two sequences. More general equivalence classes are defined and studied in [41].

Theorem 1. (Equivalence between FedDR and FedADMM)
Let (x k i , z k i ,x k ) k≥0 be a sequence generated by FedADMM with penalty parameter η, and (s k i , u k i ,û k i ,v k ) a sequence generated by FedDR with parameter 1 η . Then FedADMM and FedDR are equivalent.
Proof. For each triplet (x k i , z k i ,x k ) at the k-th iteration of FedADMM with stepsize η, define where r = 1/η and when i / where the same sampling realizations S k are used at each iteration for both algorithm.
We have where (a) is due to the dual updates (line 10) in FedADMM algorithm. Moreover, where (c) comes from the FedADMM updating rule (line 11-16 in Alg 2).
Since we have proved the equivalence of FedDR and FedADMM for arbitrary (nonconvex) problems, FedADMM will directly inherit the convergence properties of FedDR, specifically at rate O( 1 k ). The explicit convergence rate of FedADMM is characterized in the following theorem which is a direct application of Theorem 3.1 in [33].
Remark 3. Our convergence analysis can be easily extended to g ≡ 0, as long as we change the suboptimal condition into the gradient mapping as in [33]. To make 1 n n i=1 K+1 k=0 2 i,k ≤ D hold, interested readers could refer to Remark 3.1 in [33].

Remark 4.
Although FedADMM is a partial participation version of FedPD when g ≡ 0, its communication complexity is still O(ε −2 ), which matches the lower bound (up to constant factors) in [39].

Numerical Simulations
To demonstrate the equivalence of FedDR and FedADMM, we conduct diverse simulations on both synthetic and real datasets. It is worthwhile to mention that our goal is to show the equivalence of the algorithms, not to compare their performance with other algorithms. Performance profiling of FedPD and FedDR can be found in [33,39]. We have not attempted to optimize any hyperparameters. All the experiments run on Google Colab with default CPU setup. Datasets: We first generate synthetic non-iid datasets by following the same setup as in [30] and denote them as synthetic-(α, β). Here α controls how much local models differ from each other and β controls how much the local data at each device differs from that of other devices. We run the experiments by using the unbalanced datasets: synthetic-(0, 0), synthetic-(0.5, 0.5) and synthetic-(1, 1). We then compare FedADMM with FedDR on the FEMNIST data set [4]. FEMNIST is a more complex 62-class Federated Extended MNIST dataset. It consists of handwritten characters including: numbers 1-10, 26 upper-and lower-case letters A-Z and a-z from different writers and is also separated by the writers, therefore the dataset is non-iid. Models and Hyper-parameters: For all the synthetic datasets, we use the model described in [33]: a neutral network with a single hidden layer. The network architecture is 60 × 32 × 10 corresponding to input layer × hidden layer × output layer size. For FEMNIST data, we use the same model as [4], which consists of 2 convolutional layers and two fully connected layers,  For all the experiments, we use η = 1 and α = 1. As in [39], we choose stochastic gradient descent as a local solver with 300 local iterations to solve the step 11 in FedDR and the step 9 in FedADMM. The mini-batch size in calculating the stochastic gradient is 2 and the learning rate is 0.01. We stress that we do not attempt to optimize these parameters. Implementation: We use the uniform sampling scheme to select the clients in each round. The total number of clients is 30 and we set the number of active clients in each round as 10.
To provide a fair comparison, we use the same random seeds across all algorithms. After running multiple experiments on different datasets and models, from figure 1 and 2, we could observe that the training accuracy and loss of FedDR and FedADMM coincide at each iteration, which verifies our theoretical analysis in section 5.

Conclusion
We have developed a new federated learning algorithm, FedADMM, for finding stationary points in non-convex composite optimization problems. Current work is focused on incorporating convex constraints into the algorithm, proposing an asynchronous algorithm, asyncFedADMM, and applying it to non-localizable model predictive control problems where communication efficiency is necessary [2].