Model Fusion from Unauthorized Clients in Federated Learning

Abstract

A key feature of federated learning (FL) is that not all clients participate in every communication epoch of each global model update. The rationality for such partial client selection is largely to reduce the communication overhead. However, in many cases, the unselected clients are still able to compute their local model updates, but are not “authorized” to upload the updates in this round, which is a waste of computation capacity. In this work, we propose an algorithm FedUmf—Federated Learning with Unauthorized Model Fusion that utilizes the model updates from the unselected clients. More specifically, a client computes the stochastic gradient descent (SGD) even if it is not selected to upload in the current communication epoch. Then, if this client is selected in the next round, it non-trivially merges the outdated SGD stored in the previous round with the current global model before it starts to compute the new local model. A rigorous convergence analysis is established for FedUmf, which shows a faster convergence rate than the vanilla FedAvg. Comprehensive numerical experiments on several standard classification tasks demonstrate its advantages, which corroborate the theoretical results.

1. Introduction

In various large-scale machine learning (ML) applications, a massive amount of data is generated at the network edge nodes. Federated learning (FL) is a novel ML algorithm paradigm, which can effectively enable massive participants (or organizations) to execute ML algorithms and ensure privacy security without exchanging data. As a novel distributed ML paradigm, FL can deal with data isolation, allowing collaborators to train models together without sharing proprietary materials, breaking through data separation in technology and achieving collaborative ML. In particular, rather than transferring a plethora of data, all participants in FL smartly fit local ML models from their respective data and upload to the back-end server, where a global model is aggregated. In recent years, FL has achieved good performance on many commercial projects (e.g., Pixel 2 uses FL mode to personalize settings for users) and ML tasks (e.g., Gboard uses FL for prediction) [1].

It is well known that increasing communication efficiency is one of the most urgent bottlenecks in FL. There are two main reasons. First, the size of current deep learning models is usually very significant, e.g., millions of parameters. Second, the number of terminal devices participating the FL proliferates rapidly, e.g., a massive number of Internet-of-Things (IoT) devices. To address these problems, the FedAvg algorithm [2] adopts partial client participation. In FedAvg, the server randomly selects a certain portion of the total clients for model upload in each communication round, and the selected (“authorized”) clients perform local model training and upload the trained models to the server for aggregation. This simple yet effective approach has enjoyed great empirical success, as it provides a flexible trade-off between a large amount of participating clients and significant communication overhead.

The novel idea of this paper, however, is motivated by the existing partial client participation mechanism in FedAvg. In particular, the unselected clients stay idle in the current communication round and only the authorized clients actively compute model updates and send the new local models to the server. The key innovation of this work is that those unselected clients are still able to execute the model update even without authorization for model upload, which greatly wastes the computation power of those idle clients. On the other hand, in the existing literature, it has been shown that more clients participating in each round leads to a faster convergence rate. This paradox poses a new challenge: how to allow the clients without authorization to join in FL while keeping the communication overhead low.

In this paper, we propose a novel algorithm FedUmf—Federated Learning with Unauthorized Model Fusion to address the aforementioned challenge. FedUmf effectively leverages the computation capacity of the idle clients while keeping the number of selected clients unchanged to maintain low communication overhead. More specifically, in each round, rather than staying idle, the unselected clients also train the model in parallel with the selected counterparts. The resulting model update by running, e.g., stochastic gradient descent (SGD), will be temporarily stored locally at the clients and does not upload to the server. If any unselected client receives authorization in the next round, the stored SGD during the previous round will be fused with the global model before the new SGD is calculated in a non-trivial way that is one of the key novelties of this paper. On the other hand, if the client fails to be selected again in the next round, the previous stored SGD will be overwritten with the new SGD computed from the new received global model. Note that in this paper, we assume that all clients can receive the global model broadcast by the server in each round. This is reasonable in a wireless broadcast scenario. In some studies, it is assumed that only partial clients can receive broadcast from the server, which is different from the setting in this paper. As we can see, the FedUmf algorithm leverages the computation capacity of the unselected clients without requiring increasing the selected clients, which may also accelerate the convergence of FL. To the best of our knowledge, this work is the first that exploits the “idle” clients without authorization in each round to boost FL performance without increasing the communication overhead.

The main contributions of this paper are summarized as follows.

• We propose FedUmf, which enables clients that are not authorized to upload model in each round to compute model updates and fuse the update later when they receive the upload authorization.
• We rigorously prove the convergence behavior of FedUmf for both strongly convex and non-convex loss functions. The results show that FedUmf strictly dominates the standard FedAvg.
• We selected the standard MNIST and CIFAR10 data set in the experiment, and carried out standardized preprocessing. Extensive experiments were conducted on two common data distributions (both independent and identically distributed (IID) and non-IID data distributions).
• We combine FedUmf with the state-of-art algorithm to show good test accuracy and the fastest convergence speed.

This paper will be described in the following sections. Related works are surveyed in Section 2. The FedUmf algorithm is described in Section 3 and rigorously analyzed in Section 4. Numerical experiments are presented in Section 5. Finally, Section 6 concludes the paper.

2. Related Works

Federated learning has gained much attention since its seminal work [2,3]. The proposed FedAvg design in [2] periodically aggregates the local SGD [4] updates from massive clients with possibly non-IID datasets and obtains the global model. Detailed surveys of FL can be found in [5,6,7].

In [8,9,10,11,12,13], quantized compression is applied from multiple perspectives to improve the communication efficiency of FL. Ref. [14] proposes an algorithm with periodic averaging using quantization. An efficient FL protocol involving a hierarchical aggregation mechanism in a local area network (LAN) was proposed in [15], because it has abundant bandwidth and almost negligible monetary cost over WAN. Ref. [16] proposes an algorithm that achieves a compromise between gradient accuracy and communication efficiency. In [17], a combination of random rotation, subsampling, and quantization is used to decrease the transmission bandwidth. The authors in [18] applied quantization for both gradients and model parameters, and [19] developed a new algorithm that outperforms FedAvg in heterogeneous datasets. Ref. [20] proposed QSGD to achieve a compromise between convergence time and communication cost. The authors in [21] derive the convergence rate by using gradient quantization for non-convex optimization problems. Ref. [22] proposes a novel mechanism, which uses heterogeneous models to optimize the training. Ref. [23] designs an algorithm to efficiently solve the trade-off between the number of clients and transmission energy.

Another line of research that is related to this work is the study of asynchronous FL, that is, using out-of-date SGD. Synchronous training can make the model update more orderly and accurate, but the number of clients participating in the training is limited. Asynchronous training usually allows more clients to participate in model training [24,25] than synchronous training, but the cost is that the SGD used might be very dated, which may deteriorate the performance. Ref. [26] proposes a novel asynchronous adjustment method for SGD, which adjusts the learning rate according to the staleness of the offline time of the gradient, and provides theoretical guarantees for the convergence of the algorithm. In order to adapt to the access of more edge devices and improve flexibility and scalability, a novel joint optimization algorithm supporting heterogeneous terminals was proposed by [27]. Ref. [28] mitigates the straggler problem caused by device heterogeneity. Ref. [29] proposes a novel technology to compensate delay caused by asynchronous learning. However, in the previous literature, most research in FL have not considered utilizing the unselected clients to enhance the performance, while this work aims to take advantage of these neglected clients, which may bring extra benefits. In our paper, we also utilize the model updated from the unselected clients in the previous round. However, the update is not staler than one round, and the whole system is still synchronous.

3. The FedUmf Algorithm

In this section, we introduce the federated learning system in detail and propose our algorithm named FedUmf.

3.1. The FL Model and FedAvg

We aim to learn a global model parameterized by $\theta$ that minimizes the following learning problem.

$$\begin{array}{c}\hfill \underset{\theta \in {\mathbb{R}}^d}{min}\ell (\theta )=\underset{\theta \in {\mathbb{R}}^d}{min}\frac{1}{m}\sum _{z\in \mathcal{D}}l(\theta ;z),\end{array}$$

(1)

where $\ell :{\mathbb{R}}^d\to \mathbb{R}$ is the differentiable loss function averaged over the total dataset $\mathcal{D}$ with size m, $\theta \in {\mathbb{R}}^d$ is the variable of machine learning model (parameter vector) that we would like to optimize, and $l(\theta ;z)$ is the loss function evaluated at data sample z and model $\theta$. We assume that there are n clients in the FL setting. The problem can be redefined as

$$\begin{array}{c}\hfill \underset{\theta \in {\mathbb{R}}^d}{min}\ell (\theta )=\underset{\theta \in {\mathbb{R}}^d}{min}\sum _{i\in \left[n\right]}\frac{m_i}{m}{\ell }_i(\theta ),\end{array}$$

(2)

where ${\ell }_i:{\mathbb{R}}^d\to \mathbb{R}$ is the local loss function for client i, averaged over its local dataset ${\mathcal{D}}_i$ with $m_i$ data samples, and ${\sum }_i{m}_i=m$, i.e., ${\ell }_i(\theta )=\frac{1}{m_i}{\sum }_{z\in {\mathcal{D}}_i}l(\theta ;z)$. Due to the space limitation, we only present the analysis for equal dataset size. Our solution can be easily extended to the case when $m_i$ are heterogeneous. An illustration of the considered system is given in Figure 1.

In order to deal with Problem (1), the authors put forward FedAvg in [2]. At the start of every epoch $t\in \left[T\right]\triangleq \{1,2,\cdots ,T\}$, the server broadcasts the current global model ${\theta }_t$ to all clients. Then, the server chooses a subset of clients $S_t$ at random, with these clients authorized to upload their models. Assume that $|S_t|=M$; that is, a total of M clients are selected in each epoch. Then, each client $i\in S_t$ updates its local model by using K times of local SGD, obtaining ${\theta }_{t+1}^i$. After the model update stage, the authorized clients upload their updates to the parameter server through uplink communication. Then, the server aggregates local model updates from selected clients to update the global model; i.e., ${\theta }_{t+1}=\frac{1}{M}{\sum }_{i\in \left[S_t\right]}{\theta }_{t+1}^i$. After going through T rounds of learning process, the final global model is obtained on the server.

3.2. FedUmf Algorithm Description

We formally describe the FedUmf algorithm in Algorithm 1. We denote $g_t^i$ as the stored SGD for client i at round t, The number of all clients participating in training is N. First, we initialize a global weight ${\theta }_1$ for the server and distribute it to all clients in the first round. At the same time, an update gradient $g_0^i=0$ is initialized for all clients. At the start of each round t, the server randomly chooses an authorization set $S_t$, where clients are allowed to upload their model updates. We adopt $S_t^c$ to denote the complement set of $S_t$, i.e., the set of unselected clients. As all the clients can obtain the global model broadcast by the server in the beginning of every round, we denote ${\theta }_{t,0}^i\leftarrow {\theta }_t$. In addition, if any selected client i at this round was not selected in the previous round, i.e., $i\in S_t\cap S_{t-1}^c$, gradient fusion from the previous stored SGD is executed ${\theta }_{t,0}^i\leftarrow {\theta }_{t,0}^i+\frac{\alpha {\eta }_t}{{\eta }_{t-1}}{g}_{t-1}^i$. $\alpha \in (0,1]$ is a fusion coefficient, which is a tuning parameter. Multiplying $\frac{{\eta }_t}{{\eta }_{t-1}}$ modulates the learning rate. Notice that if the authorized client was also selected in the previous round, it indicates that the client has already contributed its previous gradient and there is no need to fuse its gradient. Then, each client $i\in S_t$ updates its local model by using K times of local SGD, obtaining ${\theta }_{t+1}^i$. All clients compute and store the gradient for the current round by $g_t^i={\theta }_{t+1}^i-{\theta }_{t,0}^i$. After receiving the model updates uploaded from all authorized clients, the server aggregates the global model by ${\theta }_{t+1}\leftarrow \frac{1}{M}{\sum }_{i\in S_t}{\theta }_{t+1}^i$.

Figure 2 displays the algorithm workflow. It is clear that FedUmf is novel because of the fusion of previous SGD from unselected clients in the model update process.

Algorithm 1: FedUmf

Initialize the weight ${\theta }_1$; Initialize the gradient $g_0^i=0,\forall i$; $S_0=⌀$;

4. Analysis of Convergence

In this section, we display the convergence performance analysis result of FedUmF. For the purpose of better illustrating of our key idea, we assume one local SGD occurs at each round, i.e., $K=1$, while in the experiment section, we simulate multiple local SGD updates scenarios. We also consider both strongly convex and non-convex loss functions.

4.1. Strongly Convex Loss Function

The optimal solution to Problem (2) is denoted by ${\theta }^{*}$. We first claim some commonly adopted assumptions used in literature, e.g., [14,21,30]. Specifically, $\forall i\in \left[n\right]$. We make the following assumptions.

Assumption 1.

Each function ${\ell }_i$ is L-smooth: $\parallel \tilde{\nabla }{\ell }_i(\theta )-\tilde{\nabla }{\ell }_i(\widehat{\theta })\parallel \le L\parallel \theta -\widehat{\theta }\parallel$ for any $\theta ,\widehat{\theta }\in {\mathbb{R}}^d$;

Assumption 2.

Each function ${\ell }_i$ is μ-strongly convex: $\langle \tilde{\nabla }{\ell }_i(\theta )-\tilde{\nabla }{\ell }_i(\widehat{\theta }),\theta -\widehat{\theta }\rangle \ge \mu {\parallel \theta -\widehat{\theta }\parallel }^2$ for any $\theta ,\widehat{\theta }\in {\mathbb{R}}^d$;

Assumption 3.

The second moment of a stochastic gradient for all function ${\ell }_i$ is bounded: $\mathbb{E}\parallel \tilde{\nabla }{\ell }_i{(\theta )\parallel }^2\le {\sigma }^2$.

Assumption 1 indicates that the gradient of ${\ell }_i$ is Lipschitz continuous. In this section, Assumption 2 assumes that the loss function is strongly convex. However, this assumption no longer holds for the analysis of the non-convex situation in the next section. Assumption 3 implies that the variance of stochastic gradients is uniformly bounded [31].

We first present three lemmas, which will be used to prove Theorem 1 later.

Lemma 1.

Under the conditions that Assumptions 1 to 3 hold, we have $\mathbb{E}\parallel {\theta }_{t+1}-{\theta }^{*}{\parallel }^2=\mathbb{E}\parallel {\overline{\theta }}_{t+1}-{\theta }^{*}{\parallel }^2+\mathbb{E}{\parallel {\theta }_{t+1}-{\overline{\theta }}_{t+1}\parallel }^2$, where ${\overline{\theta }}_{t+1}={\sum }_{i\in \left[n\right]}\frac{1}{n}{\theta }_{t+1}^i$.

Proof. 

First we have

$$\begin{array}{cc}\hfill & \mathbb{E}\parallel {\theta }_{t+1}-{\theta }^{*}{\parallel }^2=\mathbb{E}{\parallel {\theta }_{t+1}-{\overline{\theta }}_{t+1}+{\overline{\theta }}_{t+1}-{\theta }^{*}\parallel }^2\hfill \\ \hfill & =\mathbb{E}\parallel {\overline{\theta }}_{t+1}-{\theta }^{*}{\parallel }^2+\mathbb{E}{\parallel {\theta }_{t+1}-{\overline{\theta }}_{t+1}\parallel }^2\hfill \\ \hfill & +2\mathbb{E}\langle {\theta }_{t+1}-{\overline{\theta }}_{t+1},{\overline{\theta }}_{t+1}-{\theta }^{*}\rangle .\hfill \end{array}$$

(3)

Notice that

$$\begin{array}{cc}\hfill & \mathbb{E}\left[{\theta }_{t+1}\right]=\mathbb{E}\left[\sum _{i\in S_t}\frac{1}{M}{\theta }_{t+1}^i\right]\stackrel{(\mathrm{a})}{=}\sum _{i\in \left[n\right]}\frac{1}{n}{\theta }_{t+1}^i={\overline{\theta }}_{t+1},\hfill \end{array}$$

(4)

where the equality (a) is because of the randomness of $S_t$.

Noticing that the random sampling error ${\theta }_{t+1}-{\overline{\theta }}_{t+1}$ is independent of ${\overline{\theta }}_{t+1}-{\theta }^{*}$, which leads to the desired result. □

Lemma 2.

When Assumptions 1 to 3 hold, we have

$$\begin{array}{cc}\hfill & \mathbb{E}\parallel {\theta }_{t+1}-{\overline{\theta }}_{t+1}{\parallel }^2\le \frac{(n-M)(n+3M){\eta }_t^2{\sigma }^2}{M(n-1)n}.\hfill \end{array}$$

(5)

Proof. 

First, we can write:

$$\begin{array}{cc}\hfill & {\mathbb{E}}_{S_t}\parallel {\theta }_{t+1}-{\overline{\theta }}_{t+1}{\parallel }^2={\mathbb{E}}_{S_t}{\parallel \sum _{i\in S_t}\frac{1}{M}{\theta }_{t+1}^i-{\overline{\theta }}_{t+1}\parallel }^2\hfill \\ \hfill & ={\mathbb{E}}_{S_t}{\parallel \frac{1}{M}(\sum _{i\in S_t}{\theta }_{t+1}^i-\sum _{i\in S_t}{\overline{\theta }}_{t+1})\parallel }^2\hfill \\ \hfill & =\frac{1}{M^2}{\mathbb{E}}_{S_t}{\parallel \sum _{i\in \left[n\right]}\mathbb{1}(i\in S_t)({\theta }_{t+1}^i-{\overline{\theta }}_{t+1})\parallel }^2\hfill \\ \hfill & =\frac{1}{M^2}\left[\sum _{i\in \left[n\right]}Pr(i\in S_t){\parallel ({\theta }_{t+1}^i-{\overline{\theta }}_{t+1})\parallel }^2+\sum _{i\ne j}Pr(i,j\in S_t)\langle {\theta }_{t+1}^i-{\overline{\theta }}_{t+1},{\theta }_{t+1}^j-{\overline{\theta }}_{t+1}\rangle \right]\hfill \\ \hfill & =\frac{1}{nM}[\sum _{i\in \left[n\right]}{\parallel ({\theta }_{t+1}^i-{\overline{\theta }}_{t+1})\parallel }^2+\frac{M-1}{nM(n-1)}\sum _{i\ne j}\langle {\theta }_{t+1}^i-{\overline{\theta }}_{t+1},{\theta }_{t+1}^j-{\overline{\theta }}_{t+1}\rangle ]\hfill \\ \hfill & =\frac{1}{M(n-1)}(1-\frac{M}{n})\sum _{i\in \left[n\right]}{\parallel ({\theta }_{t+1}^i-{\overline{\theta }}_{t+1})\parallel }^2,\hfill \end{array}$$

(6)

where we adopt the equation that

$$\sum _{i\in \left[n\right]}{\parallel ({\theta }_{t+1}^i-{\overline{\theta }}_{t+1})\parallel }^2+\sum _{i\ne j}\langle {\theta }_{t+1}^i-{\overline{\theta }}_{t+1},{\theta }_{t+1}^j-{\overline{\theta }}_{t+1}\rangle =0.$$

On the other hand, the following holds

$$\begin{array}{cc}\hfill & \sum _{i\in \left[n\right]}\mathbb{E}{\parallel ({\theta }_{t+1}^i-{\overline{\theta }}_{t+1})\parallel }^2\hfill \\ \hfill & =\sum _{i\in \left[n\right]}\mathbb{E}{\parallel ({\theta }_{t+1}^i-{\theta }_t)-({\overline{\theta }}_{t+1}-{\theta }_t)\parallel }^2\hfill \\ \hfill & \le \sum _{i\in \left[n\right]}\mathbb{E}{\parallel ({\theta }_{t+1}^i-{\theta }_t)\parallel }^2,\hfill \end{array}$$

(7)

where the last inequality holds due to ${\mathbb{E}\parallel \theta -\mathbb{E}\theta \parallel }^2\le \mathbb{E}{\parallel \theta \parallel }^2$.

There are three cases for ${\theta }_{t+1}^i$.

(1).

For client $i\in S_t\cap S_{t-1}$, we have

$${\theta }_{t+1}^i={\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t).$$

(2).

For client $i\in S_t\cap S_{t-1}^C$, we have

$${\theta }_{t+1}^i=({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1}))-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})).$$

(3).

For the other client $i\in S_t^C$, we have

$${\theta }_{t+1}^i={\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t).$$

Thus, it follows

$$\begin{array}{cc}\hfill & \sum _{i\in \left[n\right]}{\parallel ({\theta }_{t+1}^i-{\theta }_t)\parallel }^2\hfill \\ \hfill & =\sum _{i\in (S_t\cap S_{t-1})}\parallel {\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)-{\theta }_t\parallel +\sum _{i\in S_t\cap S_{t-1}^C}\parallel {\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})-{\theta }_t\parallel \hfill \\ \hfill & +\sum _{i\in S_t\cap S_{t-1}^C}\parallel {\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)-{\theta }_t\parallel \hfill \\ \hfill & =\sum _{i\in (S_t\cap S_{t-1})\cup S_t^C}\parallel {\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t){\parallel }^2+\sum _{i\in S_t\cap S_{t-1}^C}{\parallel {\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})+{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1}))\parallel }^2\hfill \\ \hfill & \le {\eta }_t^2\left[\sum _{i\in (S_t\cap S_{t-1})\cup S_t^C}\parallel \tilde{\nabla }{\ell }_i({\theta }_t){\parallel }^2+2\sum _{i\in S_t\cap S_{t-1}^C}\parallel \tilde{\nabla }{\ell }_i({\theta }_{t-1}){\parallel }^2+2\sum _{i\in S_t\cap S_{t-1}^C}{\parallel \tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1}))\parallel }^2\right].\hfill \end{array}$$

(8)

The reason for the last inequality is that ${\parallel a+b\parallel }^2\le {2\parallel a\parallel }^2+2{\parallel b\parallel }^2.$

Plugging Equation (8) into (6) and taking the expectation on both sides yields

$$\begin{array}{cc}\hfill & \mathbb{E}\parallel {\theta }_{t+1}-{\overline{\theta }}_{t+1}{\parallel }^2\le \frac{(n-M)(n+3M){\eta }_t^2{\sigma }^2}{M(n-1)n},\hfill \end{array}$$

(9)

where we have used the fact that $|S_t\cap S_{t-1}^C|\le M$ and Assumption 3. □

Lemma 3.

When Assumptions 1 to 3 hold, we have

$$\begin{array}{cc}\hfill & \mathbb{E}\parallel {\overline{\theta }}_{t+1}-{\theta }^{*}{\parallel }^2\le \hfill \\ \hfill & (1-2\mu {\eta }_t-\frac{2M(n-M)\mu {\eta }_t}{n^2}+\frac{2{\eta }_t^{2}M(n-M)}{n^3})\mathbb{E}{\parallel {\theta }_t-{\theta }^{*}\parallel }^2\hfill \\ \hfill & +\frac{4M(n-M)L^2{\eta }_{t-1}^2{\sigma }^2}{n}+\frac{L^2{\eta }_t^{2}M(n-M){\sigma }^2}{n}\hfill \\ \hfill & +\frac{{\eta }_t^2{(n+M)}^2{\sigma }^2}{n^2}.\hfill \end{array}$$

(10)

Proof. 

First of all, we can know that

$$\begin{array}{cc}\hfill & \parallel {\overline{\theta }}_{t+1}-{\theta }^{*}{\parallel }^2={\parallel \frac{1}{n}\sum _{i\in \left[n\right]}{\theta }_{t+1}^i-{\theta }^{*}\parallel }^2\hfill \\ \hfill & =\parallel \frac{1}{n}(\sum _{i\in S_t\cap S_{t-1}}{\theta }_{t+1}^i+\sum _{i\in S_t\cap S_{t-1}^C}{\theta }_{t+1}^i+\sum _{i\in S_t^C}{\theta }_{t+1}^i)-{\theta }^{*}{\parallel }^2\hfill \\ \hfill & =\parallel \frac{1}{n}{(\sum _{i\in (S_t\cap S_{t-1})\cup S_t^C}({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t))+\sum _{i\in S_t\cap S_{t-1}^C}(({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1}))-{\eta }_t\nabla {\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))-{\theta }^{*}\parallel }^2\hfill \\ \hfill & =\parallel {\theta }_t-\frac{1}{n}\sum _{i\in \left[n\right]}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)-\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t(\tilde{\nabla }{\ell }_i({\theta }_t)-\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))-{\theta }^{*}{\parallel }^2\hfill \\ \hfill & =\parallel {\theta }_t-{\theta }^{*}{\parallel }^2-2\langle {\theta }_t-{\theta }^{*},\frac{1}{n}\sum _{i\in \left[n\right]}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)\rangle \hfill \\ \hfill & -2\langle {\theta }_t-{\theta }^{*},\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})\rangle +2\langle {\theta }_t-{\theta }^{*},\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t(\tilde{\nabla }{\ell }_i({\theta }_t)-\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))\rangle \hfill \\ \hfill & +\parallel \frac{1}{n}\sum _{i\in (S_t\cap S_{t-1})\cup S_t^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})){\parallel }^2.\hfill \end{array}$$

(11)

We will investigate the expectation of each term in the right hand side of Equation (11). In regard to the second term, we can obtain that

$$\begin{array}{cc}\hfill & -2\mathbb{E}\langle {\theta }_t-{\theta }^{*},\frac{1}{n}\sum _{i\in \left[n\right]}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)\rangle \le -2\mu {\eta }_t\mathbb{E}{\parallel {\theta }_t-{\theta }^{*}\parallel }^2,\hfill \end{array}$$

(12)

which is due to Assumption 2.

For the third term in the right hand side of Equation (11), we take the expectation, which yields

$$\begin{array}{cc}\hfill & 2\mathbb{E}\langle {\theta }_t-{\theta }^{*},\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})\rangle \hfill \\ \hfill & =\frac{2{\eta }_t}{n}\mathbb{E}\langle {\theta }_t-{\theta }^{*},\sum _{i\in S_t\cap S_{t-1}^C}\tilde{\nabla }{\ell }_i({\theta }_t)\rangle +\frac{2{\eta }_t}{n}\mathbb{E}\langle {\theta }_t-{\theta }^{*},\sum _{i\in S_t\cap S_{t-1}^C}(\tilde{\nabla }{\ell }_i({\theta }_{t-1})-\tilde{\nabla }{\ell }_i({\theta }_t))\rangle \hfill \\ \hfill & \stackrel{(\mathrm{a})}{=}\frac{2{\eta }_t}{n}\mathbb{E}\langle {\theta }_t-{\theta }^{*},\frac{M(n-M)}{n^2}\sum _{i\in \left[n\right]}\tilde{\nabla }{\ell }_i({\theta }_t)\rangle +\frac{2{\eta }_t}{n}\mathbb{E}\langle {\theta }_t-{\theta }^{*},\frac{M(n-M)}{n^2}\sum _{i\in \left[n\right]}(\tilde{\nabla }{\ell }_i({\theta }_{t-1})-\tilde{\nabla }{\ell }_i({\theta }_t))\rangle \hfill \\ \hfill & \ge \frac{2M(n-M)\mu {\eta }_t}{n^2}\mathbb{E}\parallel {\theta }_t-{\theta }^{*}{\parallel }^2-\frac{{\eta }_t^{2}M(n-M)}{n^3}\mathbb{E}\parallel {\theta }_t-{\theta }^{*}{\parallel }^2-\frac{M(n-M)}{n^3}\mathbb{E}{\parallel \sum _{i\in \left[n\right]}(\tilde{\nabla }{\ell }_i({\theta }_{t-1})-\tilde{\nabla }{\ell }_i({\theta }_t))\parallel }^2,\hfill \end{array}$$

(13)

where the equality (a) is established because of the randomness of $S_t$, and the reason why the last inequality holds is due to the help of the inequality $2\langle a,b\rangle \ge -{\parallel a\parallel }^2-{\parallel b\parallel }^2.$

For the expectation of the fourth term in Equation (11), it follows

$$\begin{array}{cc}\hfill & 2\mathbb{E}\langle {\theta }_t-{\theta }^{*},\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t(\tilde{\nabla }{\ell }_i({\theta }_t)-\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))\rangle \hfill \\ \hfill & \stackrel{(\mathrm{a})}{=}2\mathbb{E}\langle {\theta }_t-{\theta }^{*},\frac{M(n-M)}{n^3}\sum _{i\in \left[n\right]}{\eta }_t(\tilde{\nabla }{\ell }_i({\theta }_t)-\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))\rangle \hfill \\ \hfill & \stackrel{(\mathrm{b})}{\le }\frac{{\eta }_t^{2}M(n-M)}{n^3}\mathbb{E}\parallel {\theta }_t-{\theta }^{*}{\parallel }^2+\frac{M(n-M)}{n^3}\mathbb{E}{\parallel \sum _{i\in \left[n\right]}(\tilde{\nabla }{\ell }_i({\theta }_t)-\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))\parallel }^2\hfill \\ \hfill & \stackrel{(\mathrm{c})}{\le }\frac{{\eta }_t^{2}M(n-M)}{n^3}\mathbb{E}\parallel {\theta }_t-{\theta }^{*}{\parallel }^2+\frac{L^2{\eta }_t^{2}M(n-M)}{n^3}\mathbb{E}{\parallel \sum _{i\in \left[n\right]}\tilde{\nabla }{\ell }_i({\theta }_{t-1})\parallel }^2\hfill \\ \hfill & \stackrel{(\mathrm{d})}{\le }\frac{{\eta }_t^{2}M(n-M)}{n^3}\mathbb{E}{\parallel {\theta }_t-{\theta }^{*}\parallel }^2+\frac{L^2{\eta }_t^{2}M(n-M){\sigma }^2}{n},\hfill \end{array}$$

(14)

where the equality (a) holds because of the randomness of $S_t$, the inequality (b) holds due to $2\langle a,b\rangle \le {\parallel a\parallel }^2+{\parallel b\parallel }^2$, and the inequalities (c) and (d) come from Assumptions 1 and 3, respectively.

Regarding the expectation of the last term in Equation (11), we have

$$\begin{array}{cc}\hfill & \mathbb{E}\parallel \frac{1}{n}\sum _{i\in (S_t\cap S_{t-1})\cup S_t^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})){\parallel }^2\hfill \\ \hfill & \le \frac{{\eta }_t^2(n+M)}{n^2}\mathbb{E}[\sum _{i\in (S_t\cap S_{t-1})\cup S_t^C}\parallel \tilde{\nabla }{\ell }_i({\theta }_t){\parallel }^2+\sum _{i\in S_t\cap S_{t-1}^C}\parallel \tilde{\nabla }{\ell }_i({\theta }_{t-1}){\parallel }^2+\sum _{i\in S_t\cap S_{t-1}^C}{\parallel \tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1}))\parallel }^2]\hfill \\ \hfill & \le \frac{{\eta }_t^2{(n+M)}^2{\sigma }^2}{n^2},\hfill \end{array}$$

(15)

where the first inequality is because of the Cauchy–Schwarz inequality, and the last inequality holds due to Assumption 3.

Taking the expectation on both sides of Equation (11) and plugging in Equations (13)–(15) yields

$$\begin{array}{cc}\hfill & \mathbb{E}\parallel {\overline{\theta }}_{t+1}-{\theta }^{*}{\parallel }^2\hfill \\ \hfill & \le (1-2\mu {\eta }_t-\frac{2M(n-M)\mu {\eta }_t}{n^2}+\frac{2{\eta }_t^{2}M(n-M)}{n^3})\mathbb{E}{\parallel {\theta }_t-{\theta }^{*}\parallel }^2\hfill \\ \hfill & +\frac{M(n-M)}{n^3}\mathbb{E}{\parallel \sum _{i\in \left[n\right]}(\tilde{\nabla }{\ell }_i({\theta }_{t-1})-\tilde{\nabla }{\ell }_i({\theta }_t))\parallel }^2\hfill \\ \hfill & +\frac{L^2{\eta }_t^{2}M(n-M){\sigma }^2}{n}+\frac{{\eta }_t^2{(n+M)}^2{\sigma }^2}{n^2}.\hfill \end{array}$$

(16)

Next we analyze the second term in the right hand side of Equation (16).

$$\begin{array}{cc}\hfill & \mathbb{E}\parallel \sum _{i\in \left[n\right]}(\tilde{\nabla }{\ell }_i({\theta }_{t-1})-\tilde{\nabla }{\ell }_i({\theta }_t)){\parallel }^2\hfill \\ \hfill & \le \mathbb{E}\parallel \sum _{i\in \left[n\right]}(L({\theta }_{t-1}-{\theta }_t)){\parallel }^2\hfill \\ \hfill & =L^2{n}^2\mathbb{E}{\parallel {\theta }_{t-1}-{\theta }_t\parallel }^2\hfill \\ \hfill & =L^2{n}^2\mathbb{E}\parallel \frac{1}{M}\sum _{i\in S_{t-1}\cap S_{t-2}}{\eta }_{t-1}\tilde{\nabla }{\ell }_i({\theta }_{t-1})+\frac{1}{M}\sum _{i\in S_{t-1}\cap S_{t-2}^C}{\eta }_{t-1}\tilde{\nabla }{\ell }_i({\theta }_{t-2})\hfill \\ \hfill & +\frac{1}{M}\sum _{i\in S_{t-1}\cap S_{t-2}^C}{\eta }_{t-1}\tilde{\nabla }{\ell }_i({\theta }_{t-1}-{\eta }_{t-1}\tilde{\nabla }{\ell }_i({\theta }_{t-2})){\parallel }^2\hfill \\ \hfill & \stackrel{(\mathrm{a})}{\le }\frac{2L^2{n}^2{\eta }_{t-1}^2}{M}[\sum _{i\in S_{t-1}\cap S_{t-2}}\mathbb{E}\parallel \tilde{\nabla }{\ell }_i({\theta }_{t-1}){\parallel }^2+\sum _{i\in S_{t-1}\cap S_{t-2}^C}\mathbb{E}{\parallel \tilde{\nabla }{\ell }_i({\theta }_{t-2})\parallel }^2\hfill \\ \hfill & +\sum _{i\in S_{t-1}\cap S_{t-2}^C}\mathbb{E}{\parallel \tilde{\nabla }{\ell }_i({\theta }_{t-1}-{\eta }_{t-1}\tilde{\nabla }{\ell }_i({\theta }_{t-2}))\parallel }^2]\hfill \\ \hfill & \stackrel{(\mathrm{b})}{\le }4L^2{n}^2{\eta }_{t-1}^2{\sigma }^2,\hfill \end{array}$$

(17)

where the inequality (a) comes from Cauchy–Schwarz inequality and (b) is due to Assumption 3.

Therefore, we have

$$\begin{array}{cc}\hfill & \mathbb{E}\parallel {\overline{\theta }}_{t+1}-{\theta }^{*}{\parallel }^2\hfill \\ \hfill & \le (1-2\mu {\eta }_t-\frac{2M(n-M)\mu {\eta }_t}{n^2}+\frac{2{\eta }_t^{2}M(n-M)}{n^3})\hfill \\ \hfill & \ast \mathbb{E}\parallel {\theta }_t-{\theta }^{*}{\parallel }^2+\frac{4M(n-M)L^2{\eta }_{t-1}^2{\sigma }^2}{n}\hfill \\ \hfill & +\frac{L^2{\eta }_t^{2}M(n-M){\sigma }^2}{n}+\frac{{\eta }_t^2{(n+M)}^2{\sigma }^2}{n^2}.\hfill \end{array}$$

(18)

□

We are now put forward the key theorem on the convergence of FedUmf as follows.

Theorem 1.

With the condition that Assumptions 1 to 3 hold, and if the step size is chosen as ${\eta }_t=\frac{1}{\mu t}$, there exists a constant $t_0$ such that for any $t>t_0$, the convergence rate of FedUmf satisfies:

$$\mathbb{E}\parallel {\theta }_t-{\theta }^{*}{\parallel }^2\le \frac{t_0}{t}\mathbb{E}{\parallel {\theta }_{t_0}-{\theta }^{*}\parallel }^2+\frac{2C_0}{t-1}+\frac{C_1}{t},$$

(19)

where $C_0=\frac{4M(n-M)L^2{\sigma }^2}{n{\mu }^2}$, $C_1=\frac{L^{2}M(n-M){\sigma }^2}{n{\mu }^2}+\frac{{(n+M)}^2{\sigma }^2}{n^2{\mu }^2}+\frac{(n-M)(n+3M){\sigma }^2}{M(n-1)n{\mu }^2}.$

Proof. 

Through Lemmas 1, 2, and 3, we can obtain

$$\begin{array}{cc}\hfill & \mathbb{E}\parallel {\theta }_{t+1}-{\theta }^{*}{\parallel }^2\hfill \\ \hfill & \le (1-2\mu {\eta }_t-\frac{2M(n-M)\mu {\eta }_t}{n^2}+\frac{2{\eta }_t^{2}M(n-M)}{n^3})\mathbb{E}{\parallel {\theta }_t-{\theta }^{*}\parallel }^2+\frac{4M(n-M)L^2{\eta }_{t-1}^2{\sigma }^2}{n}\hfill \\ \hfill & +\frac{L^2{\eta }_t^{2}M(n-M){\sigma }^2}{n}+\frac{{\eta }_t^2{(n+M)}^2{\sigma }^2}{n^2}+\frac{(n-M)(n+3M){\eta }_t^2{\sigma }^2}{M(n-1)n}.\hfill \end{array}$$

(20)

Notice that when ${\eta }_t\le \frac{1}{n}$, we have $\frac{2M(n-M)\mu {\eta }_t}{n^2}>\frac{2{\eta }_t^{2}M(n-M)}{n^3}$. We substitute the step size ${\eta }_t=\frac{1}{\mu t}$, and $a_t\triangleq \mathbb{E}{\parallel {\theta }_t-{\theta }^{*}\parallel }^2$. This leads to

$$a_{t+1}\le \left(1-\frac{2}{t}\right)a_t+\frac{C_0}{{(t-1)}^2}+\frac{C_1}{t^2}.$$

(21)

Now, we prove the theorem using induction. First, we notice that Equation (19) obviously holds when $t=t_0$. Next, we assume Equation (19) holds when $s>t_0$, i.e., $a_s\le \frac{t_0}{s}{a}_{t_0}+\frac{2C_0}{s-1}+\frac{C_1}{s}$. We can know

$$\begin{array}{cc}\hfill & a_{s+1}\le \left(1-\frac{2}{s}\right)a_s+\frac{C_0}{{(s-1)}^2}+\frac{C_1}{{(s)}^2}\hfill \\ \hfill & \le \left(1-\frac{2}{s}\right)\left(\frac{t_0}{s}{a}_{t_0}+\frac{2C_0}{s-1}+\frac{C_1}{s}\right)+\frac{C_0}{{(s-1)}^2}+\frac{C_1}{s^2}\hfill \\ \hfill & =\frac{s-2}{s^2}{t}_0{a}_{t_0}+\frac{2s^2-5s+4}{s{(s-1)}^2}{C}_0+\frac{s-1}{s^2}{C}_1\hfill \\ \hfill & \le \frac{t_0}{s+1}{a}_{t_0}+\frac{2C_0}{s}+\frac{C_1}{s+1},\hfill \end{array}$$

(22)

which leads to the final result. □

Remark 1.

Theorem 1 demonstrates that the convergence rate of FedUmf is $O(1/T)$, which is as same as the conventional parallel SGD [31].

Remark 2.

In Equation (19), the term $\frac{2M(n-M)\mu {\eta }_t}{n^2}-\frac{2{\eta }_t^{2}M(n-M)}{n^3}$ represents the extra benefit brought by FedUmf, i.e., a greater decay rate for the distance between the current model and the optimum than the counterpart in FedAvg, which implies a faster convergence rate.

4.2. Non-Convex Loss Function

Neural networks are often trained using non-convex loss functions. We now pay attention to the convergence performance for non-convex loss functions; i.e., we will not consider Assumption 2 in the analysis. Specially, it is well-known that SGD may converge to a local optimum for a non-convex loss function, and evaluating the expected gradient norm as an indicator of convergence is a common practice. In particular, an algorithm achieves an $ϵ$-suboptimal solution if

$$\sum _{t=1}^T\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2\le ϵ,$$

which guarantees the convergence to a stationary point [11,32,33].

Theorem 2.

Suppose Assumptions 1 and 3 are established. When the step size is substituted as ${\eta }_t=\frac{1}{L\sqrt{T}}$, the convergence of  FedUmf  with non-convex loss functions satisfies

$$\frac{1}{T}\sum _{t=1}^T\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2\le \frac{2L\left(\ell ({\theta }_0)-f^{*}\right)}{\sqrt{T}}+\frac{D}{\sqrt{T}},$$

(23)

where $D=\frac{2L{\sigma }^{2}M(n-M)}{n}+\frac{LM(n-M){\sigma }^2}{2n}+\frac{{(n+M)}^2{\sigma }^2}{2n^2}+\frac{(n-M)(n+3M){\sigma }^2}{2M(n-1)n}.$

We establish the following lemma before providing the full proof of Theorem 2.

Lemma 4.

When Assumption 1 holds, we can obtain

$$\begin{array}{cc}\hfill & \mathbb{E}\ell ({\theta }_{t+1})\le \mathbb{E}\ell ({\overline{\theta }}_{t+1})+\frac{L}{2}\mathbb{E}{\parallel {\theta }_{t+1}-{\overline{\theta }}_{t+1}\parallel }^2,\hfill \\ \hfill & \mathbb{E}\ell ({\overline{\theta }}_{t+1})\le \mathbb{E}\ell ({\theta }_t)-{\eta }_t\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2-\hfill \\ \hfill & \frac{M(n-M){\eta }_t}{n^2}\mathbb{E}\parallel \nabla \ell ({\theta }_t){\parallel }^2+\frac{{\eta }_t^{2}M(n-M)}{n^3}\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2+\frac{2L^2{\eta }_{t-1}^2{\sigma }^{2}M(n-M)}{n}+\hfill \end{array}$$

(24)

$$\begin{array}{c}\hfill \frac{L^2{\eta }_t^{2}M(n-M){\sigma }^2}{2n}+\frac{{\eta }_t^2{(n+M)}^2{\sigma }^{2}L}{2n^2}.\end{array}$$

(25)

Proof. 

To prove Equation (24), we note that

$$\begin{array}{cc}\hfill \ell ({\theta }_{t+1})& =\ell ({\overline{\theta }}_{t+1}+{\theta }_{t+1}-{\overline{\theta }}_{t+1})\hfill \\ \hfill & \le \ell ({\overline{\theta }}_{t+1})+\langle \nabla \ell ({\overline{\theta }}_{t+1}),{\theta }_{t+1}-{\overline{\theta }}_{t+1}\rangle +\frac{L}{2}{\parallel {\theta }_{t+1}-{\overline{\theta }}_{t+1}\parallel }^2,\hfill \end{array}$$

(26)

where the inequality is established because of the L-smoothness of function ℓ. Taking expectation on both sides, we can know that $\mathbb{E}\left[{\theta }_{t+1}\right]=\mathbb{E}\left[{\overline{\theta }}_{t+1}\right]$ and the random sampling error ${\theta }_{t+1}-{\overline{\theta }}_{t+1}$ is independent of $\nabla \ell ({\overline{\theta }}_{t+1})$. This yields $\mathbb{E}\ell ({\theta }_{t+1})\le \mathbb{E}\ell ({\overline{\theta }}_{t+1})+\frac{L}{2}\mathbb{E}{\parallel {\theta }_{t+1}-{\overline{\theta }}_{t+1}\parallel }^2.$

In order to prove Equation (25), we have $\ell ({\overline{\theta }}_{t+1})=\ell (\frac{1}{n}{\sum }_{i\in \left[n\right]}{\theta }_{t+1}^i)$

$$\begin{array}{cc}\hfill & =\ell (\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}}({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t))+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1}))-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1}))\hfill \\ \hfill & +\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t))\hfill \\ \hfill & =\ell ({\theta }_t-\frac{1}{n}\sum _{i\in (S_t\cap S_{t-1})\cup S_t^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)-\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)\hfill \\ \hfill & -\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})-\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t(\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1}))))\hfill \\ \hfill & =\ell \left({\theta }_t-\frac{1}{n}\sum _{i\in \left[n\right]}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_t)-\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t(\tilde{\nabla }{\ell }_i({\theta }_t)-\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))\right)\hfill \\ \hfill & \le \ell ({\theta }_t)-\langle \nabla \ell ({\theta }_t),\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})\rangle \hfill \\ \hfill & -\langle \nabla \ell ({\theta }_t),{\eta }_t\nabla \ell ({\theta }_t)\rangle +\langle \nabla \ell ({\theta }_t),\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t(\tilde{\nabla }{\ell }_i({\theta }_t)-\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))\rangle +\hfill \\ \hfill & \frac{L{\eta }_t^2}{2}{\parallel \frac{1}{n}\sum _{i\in (S_t\cap S_{t-1})\cup S_t^C}\tilde{\nabla }{\ell }_i({\theta }_t)+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}\tilde{\nabla }{\ell }_i({\theta }_{t-1})+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1}))\parallel }^2.\hfill \end{array}$$

(27)

The reason why the inequality holds relies on the L-smoothness of ℓ.

We will investigate the expectation of each term in the right hand side of Equation (27).

For the second term in the right hand side of Equation (27), we can obtain

$$\begin{array}{cc}\hfill & \mathbb{E}\langle \nabla \ell ({\theta }_t),\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})\rangle \hfill \\ \hfill & =\frac{{\eta }_t}{n}\mathbb{E}\langle \nabla \ell ({\theta }_t),\sum _{i\in S_t\cap S_{t-1}^C}\tilde{\nabla }{\ell }_i({\theta }_t)\rangle \hfill \\ \hfill & +\frac{{\eta }_t}{n}\mathbb{E}\langle \nabla \ell ({\theta }_t),\sum _{i\in S_t\cap S_{t-1}^C}(\tilde{\nabla }{\ell }_i({\theta }_{t-1})-\tilde{\nabla }{\ell }_i({\theta }_t))\rangle \hfill \\ \hfill & \stackrel{(\mathrm{a})}{=}\frac{{\eta }_t}{n}\mathbb{E}\langle \nabla \ell ({\theta }_t),\frac{M(n-M)}{n^2}\sum _{i\in \left[n\right]}\tilde{\nabla }{\ell }_i({\theta }_t)\rangle +\hfill \\ \hfill & \frac{{\eta }_t}{n}\mathbb{E}\langle \nabla \ell ({\theta }_t),\frac{M(n-M)}{n^2}\sum _{i\in \left[n\right]}(\tilde{\nabla }{\ell }_i({\theta }_{t-1})-\tilde{\nabla }{\ell }_i({\theta }_t))\rangle \hfill \\ \hfill & \stackrel{(\mathrm{b})}{\ge }\frac{M(n-M){\eta }_t}{n^2}\mathbb{E}\parallel \nabla \ell ({\theta }_t){\parallel }^2-\frac{{\eta }_t^{2}M(n-M)}{2n^3}\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2\hfill \\ \hfill & -\frac{M(n-M)}{2n^3}\mathbb{E}{\parallel \sum _{i\in \left[n\right]}(\tilde{\nabla }{\ell }_i({\theta }_{t-1})-\tilde{\nabla }{\ell }_i({\theta }_t))\parallel }^2\hfill \\ \hfill & \stackrel{(\mathrm{c})}{\ge }\frac{M(n-M){\eta }_t}{n^2}\mathbb{E}\parallel \nabla \ell ({\theta }_t){\parallel }^2-\frac{{\eta }_t^{2}M(n-M)}{2n^3}\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2\hfill \\ \hfill & -\frac{2L^2{\eta }_{t-1}^2{\sigma }^{2}M(n-M)}{n},\hfill \end{array}$$

(28)

where the equality (a) holds because of the randomness of $S_t$, the inequality (b) holds due to $2\langle a,b\rangle \ge -{\parallel a\parallel }^2-{\parallel b\parallel }^2$, and the inequality (c) comes from Equation (17).

For the third term in the right hand side of Equation (27), we have

$$\begin{array}{c}\hfill \mathbb{E}\langle \nabla \ell ({\theta }_t),{\eta }_t\nabla \ell ({\theta }_t)\rangle ={\eta }_t\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2.\end{array}$$

(29)

For the fourth term in the right hand side of Equation (27), we have

$$\begin{array}{cc}\hfill & \mathbb{E}\langle \nabla \ell ({\theta }_t),\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}{\eta }_t(\tilde{\nabla }{\ell }_i({\theta }_t)-\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))\rangle \hfill \\ \hfill & \stackrel{(\mathrm{a})}{=}\mathbb{E}\langle \nabla \ell ({\theta }_t),\frac{M(n-M)}{n^3}\sum _{i\in \left[n\right]}{\eta }_t(\tilde{\nabla }{\ell }_i({\theta }_t)-\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))\rangle \hfill \\ \hfill & \stackrel{(\mathrm{b})}{\le }\frac{{\eta }_t^{2}M(n-M)}{2n^3}\mathbb{E}\parallel \nabla \ell ({\theta }_t){\parallel }^2+\frac{M(n-M)}{2n^3}\mathbb{E}{\parallel \sum _{i\in \left[n\right]}(\tilde{\nabla }{\ell }_i({\theta }_t)-\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1})))\parallel }^2\hfill \\ \hfill & \stackrel{(\mathrm{c})}{\le }\frac{{\eta }_t^{2}M(n-M)}{2n^3}\mathbb{E}\parallel \nabla \ell ({\theta }_t){\parallel }^2+\frac{L^2{\eta }_t^{2}M(n-M)}{2n^3}\mathbb{E}{\parallel \sum _{i\in \left[n\right]}\tilde{\nabla }{\ell }_i({\theta }_{t-1})\parallel }^2\hfill \\ \hfill & \stackrel{(\mathrm{d})}{\le }\frac{{\eta }_t^{2}M(n-M)}{2n^3}\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2+\frac{L^2{\eta }_t^{2}M(n-M){\sigma }^2}{2n},\hfill \end{array}$$

(30)

where the equality (a) holds because of the randomness of $S_t$, the inequality (b) holds due to $2\langle a,b\rangle \le {\parallel a\parallel }^2+{\parallel b\parallel }^2$, the inequality (c) comes from Assumption 1, and the inequality (d) comes from Assumption 3.

For the last term in the right hand side of Equation (27), it follows

$$\begin{array}{cc}\hfill & \frac{L{\eta }_t^2}{2}\mathbb{E}{\parallel \frac{1}{n}\sum _{i\in (S_t\cap S_{t-1})\cup S_t^C}\tilde{\nabla }{\ell }_i({\theta }_t)+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}\tilde{\nabla }{\ell }_i({\theta }_{t-1})+\frac{1}{n}\sum _{i\in S_t\cap S_{t-1}^C}\tilde{\nabla }{\ell }_i({\theta }_t-{\eta }_t\tilde{\nabla }{\ell }_i({\theta }_{t-1}))\parallel }^2\hfill \\ \hfill & \le \frac{{\eta }_t^2{(n+M)}^2{\sigma }^{2}L}{2n^2},\hfill \end{array}$$

(31)

where the last inequality comes from Equation (15).

Plugging Equations (28)–(31) into (27) and taking the expectation on both sides yields

$$\begin{array}{cc}\hfill & \mathbb{E}\ell ({\overline{\theta }}_{t+1})\le \mathbb{E}\ell ({\theta }_t)-{\eta }_t\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2\hfill \\ \hfill & -\frac{M(n-M){\eta }_t}{n^2}\mathbb{E}\parallel \nabla \ell ({\theta }_t){\parallel }^2+\frac{{\eta }_t^{2}M(n-M)}{n^3}\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2\hfill \\ \hfill & +\frac{2L^2{\eta }_{t-1}^2{\sigma }^{2}M(n-M)}{n}+\frac{L^2{\eta }_t^{2}M(n-M){\sigma }^2}{2n}\hfill \\ \hfill & +\frac{{\eta }_t^2{(n+M)}^2{\sigma }^{2}L}{2n^2}.\hfill \end{array}$$

(32)

□

Proof of Theorem 2. 

From Lemmas 2 and 4, we have

$$\begin{array}{cc}\hfill & \mathbb{E}\ell ({\theta }_{t+1})\le \mathbb{E}\ell ({\theta }_t)-{\eta }_t\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2-\hfill \\ \hfill & \frac{M(n-M){\eta }_t}{n^2}\mathbb{E}\parallel \nabla \ell ({\theta }_t){\parallel }^2+\frac{{\eta }_t^{2}M(n-M)}{n^3}\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2\hfill \\ \hfill & +\frac{2L^2{\eta }_{t-1}^2{\sigma }^{2}M(n-M)}{n}+\frac{L^2{\eta }_t^{2}M(n-M){\sigma }^2}{2n}\hfill \\ \hfill & +\frac{{\eta }_t^2{(n+M)}^2{\sigma }^{2}L}{2n^2}+\frac{(n-M)(n+3M){\eta }_t^2{\sigma }^{2}L}{2M(n-1)n}.\hfill \end{array}$$

(33)

When the step size ${\eta }_t={\eta }_{t-1}=\frac{1}{L\sqrt{T}}$, it follows $\frac{M(n-M){\eta }_t}{n^2}\ge \frac{M(n-M){\eta }_t^2}{n^3}$ and we have

$$\begin{array}{cc}\hfill & \mathbb{E}\ell ({\theta }_{t+1})\le \mathbb{E}\ell ({\theta }_t)-{\eta }_t\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2+D{\eta }_t^{2}L.\hfill \end{array}$$

(34)

Summing Equation (34) over $t=0,\cdots ,T$ and rearranging the terms, we obtain

$$\begin{array}{cc}\hfill \sum _{t=0}^T{\eta }_t\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2& \le \ell ({\theta }_0)-\mathbb{E}\ell ({\theta }_{T+1})+D{\eta }_t^{2}LT\hfill \\ \hfill & \le \ell ({\theta }_0)-{\ell }^{*}+D{\eta }_t^{2}LT.\hfill \end{array}$$

(35)

We divide T for both sides of Equation (35), which leads to

$$\begin{array}{c}\hfill \frac{1}{T}\sum _{t=0}^T{\eta }_t\mathbb{E}{\parallel \nabla \ell ({\theta }_t)\parallel }^2\le \frac{\ell ({\theta }_0)-{\ell }^{*}}{T}+D{\eta }_t^{2}L.\end{array}$$

(36)

We can obtain the final result (23) by plugging in the step size ${\eta }_t=\frac{1}{L\sqrt{T}}$. □

Remark 3.

Theorem 2 demonstrates that FedUmf has a convergence rate of $O(1/\sqrt{T})$ for non-convex loss functions, which is as same as the conventional parallel SGD without quantization [33].

5. Experiments

5.1. Experimental Setup

5.1.1. Models and Datasets

In this experiment, we employ real-world datasets for standard image classification tasks, including the commonly used MNIST and CIFAR10. In Appendix A, we show more experimental results; the dataset is extended to MNIST, EMNIST, Fashion-MNIST, CIFAR10 and CIFAR100.

MNIST is a simple digit classification dataset; the training set contains 60,000 (28∗28) samples and the test set contains 10,000 samples. In addition, CIFAR10 is also intended for an image classification task with 10 classes, and its data set contains a total of 60,000 (32∗32) samples available for use. In particular, our network setup follows that described in the literature [2] on MNSIT, ResNet18 [34] on CIFAR10.

The experimental design mainly includes two mainstream balance settings: IID setting and non-IID setting. For the IID setup, we shuffle the dataset randomly; all clients receive the same number of samples, which are independently and equally distributed over the training data set. The non-IID setup has a very different setting than IID. We divide the data into blocks by category and each person extracts several blocks. According to the client settings, the client will hold categories ranging from 1 to n. In this case, we make it have at most two classes.

5.1.2. Hyperparameters

In this section, we describe in detail the meanings and settings of some of the hyperparameters used in the experiments. We set T as the communication rounds. B is the local batch size for training at each round and $C\in (0,1]$ is the proportion of clients authorized by the server each round. Let K represent the local training times of each client. We test multiple learning rate settings. The low learning rate $\eta$ is set as 0.01, while the high one is set as 0.05. In addition, the low client fraction C is set as 0.1, while the high one is set as 0.5. $Mo$ stands for the momentum choice of the optimizer. $\lambda$ stands for the weight decay of the optimizer, which is set to be 0.0005. For MNIST, the settings are $B=50$, $T=150$, $K=1$, and $Mo=0.5$. For CIFAR10, the settings are $B=50$, $T=300$, $K=1$, and $Mo=0.5$.

5.1.3. Criteria

All models are appraised at each epoch using the test accuracy, and we also record the number training rounds to arrive at a given test accuracy. The loss function is calculated using cross-entropy. In the main text, we use FedAvg as the baseline, and in the Appendix A, we compare more algorithms, such as FedProx, FedScaff, FedDyn, and FedDC (state of the art). All experiments are run using Tesla V100 with 125GB RAM. In addition to using a figure to show the test accuracy curve, we also use a table to show the communication rounds when the specified test accuracy is achieved.

5.2. MNIST Results

5.2.1. IID Setting

Table 1. Accuracy on MNIST dataset. IID partition.

Parameters, $\mathit{\alpha }=1$	Schemes	Accuracy
		92%	93%	94%	95%	96%	97%
$\eta =0.01,C=0.1$	FedAvg	23	34	48	69	103	*
	FedUmf	14	21	28	39	55	99
$\eta =0.01,C=0.5$	FedAvg	23	35	46	70	101	*
	FedUmf	17	24	32	47	66	110
$\eta =0.05,C=0.1$	FedAvg	6	9	11	15	23	38
	FedUmf	5	6	7	10	15	25
$\eta =0.05,C=0.5$	FedAvg	4	5	6	11	15	46
	FedUmf	4	5	6	9	15	29

‘*’ is used to denote that the model fails to achieve the target accuracy.

records the experimental results for the MNIST dataset with the IID partition for the case of $\alpha =1$, which means that the full SGD of the unselected clients in the previous round will be fused in this round. In the top two rows of the table, the learning rate is set as $\eta =0.01$ and C is set to be 0.1 and 0.5, respectively. In the bottom two rows of the table, we have $\eta =0.05$, and C is also set to be 0.1 and 0.5, respectively. We can see that the FedUmf outperforms FedAvg for all cases. For example, the number of rounds to reach the test accuracy of 98% is 34–48% smaller.

Subfigures (a) and (b) in Figure 3 and Figure 4 plot the number of communication rounds versus test accuracy for the two aforementioned scenarios. Subfigures (c) and (d) in Figure 3 and Figure 4 plot the number of communication rounds versus the corresponding training loss. For a given learning rate, a greater C leads to a smaller gap between FedUmf and FedAvg, because a larger C implies increasing the number of clients selected at each round, which results in a reduction of the number of unselected clients whose gradient can be leveraged. In addition, to illustrate the effect of the coefficient $\alpha$, we also add two curves for $\alpha =0.1$ and $\alpha =0.5$ as comparison. As $\alpha$ increases, performance becomes better, which means that adding the full gradient is the best choice for the current setting. When the learning rate increases from 0.1 to 0.5, a similar performance enhancement can be observed, which indicates the wide applicable range of our algorithm.

5.2.2. Non-IID Setting

Table 2. Accuracy on MNIST dataset, Non-IID partition.

Parameters, $\mathit{\alpha }=1$	Schemes	Accuracy
		91%	92%	93%	94%	95%	96%
$\eta =0.01,C=0.1$	FedAvg	24	34	44	71	92	141
	FedUmf	12	18	29	34	54	69
$\eta =0.01,C=0.5$	FedAvg	22	33	44	64	92	135
	FedUmf	15	23	32	44	62	87
$\eta =0.05,C=0.1$	FedAvg	7	8	11	14	22	31
	FedUmf	5	7	8	10	11	23
$\eta =0.05,C=0.5$	FedAvg	7	8	11	14	19	26
	FedUmf	5	6	8	10	14	21

records the experimental results for the MNIST dataset with the non-IID partition for the case of $\alpha =1$. Similar settings are adopted as in the IID case. We can see that the performance of FedUmf dominates FedAvg for all cases as well.

Subfigures (a) and (b) in Figure 5 and Figure 6 plot the number of communication rounds versus test accuracy for the two aforementioned scenarios, while subfigures (c) and (d) plot the corresponding training loss. We can still observe a clear performance boost for FedUmf compared to FedAvg. Similarly, it can be seen that a larger C implies a smaller gap between FedUmf and FedAvg, for the same reason as in the IID case.

5.3. CIFAR10 Result

5.3.1. IID Setting

We adopt the ResNet18 CNN model used in [34] with $\alpha =1$.

Table 3. Accuracy on CIFAR10 dataset, IID partition.

Parameters, $\mathit{\alpha }=1$	Schemes	Accuracy
		30%	40%	50%	55%	60%	65%	70%
$\eta =0.01,C=0.1$	FedAvg	6	25	82	130	207	*	*
	FedUmf	4	15	45	66	103	165	288
$\eta =0.01,C=0.5$	FedAvg	4	25	78	128	200	*	*
	FedUmf	3	17	52	85	129	206	*
$\eta =0.05,C=0.1$	FedAvg	4	11	33	53	76	108	157
	FedUmf	4	8	21	31	45	64	90
$\eta =0.05,C=0.5$	FedAvg	3	10	30	46	67	97	140
	FedUmf	3	9	22	34	49	70	101

reports the results. ‘*’ is used to denote that the model fails to achieve the target accuracy. In the top two rows of the table, the learning rate is set as $\eta =0.05$ and C is set to be 0.1 and 0.5, respectively. In the bottom two rows of the table, we have $\eta =0.1$ and C is also set to be 0.1 and 0.5, respectively. Similar to the experiment on MNIST dataset, we notice that FedUmf outperforms FedAvg significantly in all cases; e.g., the number of rounds to reach an accuracy of 70% is 42–50% less for all cases. When C increases, we can see that the benefits of our algorithm gradually diminish, which is because the chance of utilizing gradient fusions decreases.

Subfigures (a) and (b) in Figure 7 and Figure 8 plot the number of communication rounds versus the test accuracy for the two aforementioned scenarios. Subfigures (c) and (d) in Figure 7 and Figure 8 plot the number of communication rounds versus the corresponding training loss for these two scenarios. We have also simulated $\alpha =0.1$ and $\alpha =0.5$ cases. The results show a descending trend as $\alpha$ becomes smaller, similar to the MNIST dataset.

5.3.2. Non-IID Partition

Figure 9 and Figure 10 and

Table 4. Accuracy on CIFAR10 dataset, non-IID partition.

Parameters, $\mathit{\alpha }=0.5$	Schemes	Accuracy
		45%	50%	55%	60%	65%	70%
$\eta =0.01,C=0.1$	FedAvg	74	129	224	*	*	*
	FedUmf	43	65	103	146	230	*
$\eta =0.01,C=0.5$	FedAvg	69	124	194	*	*	*
	FedUmf	44	78	122	183	290	*
$\eta =0.05,C=0.1$	FedAvg	31	43	65	95	129	191
	FedUmf	17	25	39	54	74	108
$\eta =0.05,C=0.5$	FedAvg	24	37	57	82	116	167
	FedUmf	18	26	40	57	81	116

show the results for CIFAR10 with the non-IID partition. We set $\eta =0.01$ and simulate the cases with $C=0.1$ and $C=0.5$. In addition, we set $\eta =0.05$ and simulate the cases with $C=0.1$ and $C=0.5$. It can be seen that FedUmf still achieves a faster convergence rate than FedAvg.

In conclusion, by taking the advantage of previous unexploited client gradients, the rate of convergence can be greatly expedited with FedUmf compared to the vanilla FedAvg.

6. Conclusions

In this paper, we have proposed a federated learning algorithm—FedUmf—that allows unselected clients to train model update and fuses the resulting new model later when the clients receive authorization to upload. This design can avoid wasting computation capacity and expedite the convergence rate of FL. A rigorous convergence analysis was given for FedUmf, which proved a faster convergence rate than vanilla FedAvg. The simulation performance demonstrated that FedUmf performs better than the traditional FedAvg, where unselected clients are idle. It also shows satisfactory results in combination with the SOTA algorithms.