A Derivative-Incorporated Adaptive Gradient Method for Federated Learning

Abstract

As a new machine learning technique, federated learning has received more attention in recent years, which enables decentralized model training across data silos or edge intelligent devices in the Internet of Things without exchanging local raw data. All kinds of algorithms are proposed to solve the challenges in federated learning. However, most of these methods are based on stochastic gradient descent, which undergoes slow convergence and unstable performance during the training stage. In this paper, we propose a differential adaptive federated optimization method, which incorporates an adaptive learning rate and the gradient difference into the iteration rule of the global model. We further adopt the first-order moment estimation to compute the approximate value of the differential term so as to avoid amplifying the random noise from the input data sample. The theoretical convergence guarantee is established for our proposed method in a stochastic non-convex setting under full client participation and partial client participation cases. Experiments for the image classification task are performed on two standard datasets by training a neural network model, and experiment results on different baselines demonstrate the effectiveness of our proposed method.

1. Introduction

With huge amounts of data being generated at an increasing rate, the cost of collecting and handling data is becoming more expensive by a centralized data center. Therefore, collaborative learning [1,2] has gained more attention due to its ability to unite the collective power of devices distributed in different geographic locations. However, the exchange of information among devices may cause the risk of data leakage during the process of training. As a promising solution, federated learning [3,4,5] was proposed to train models across edge smart devices in the Internet of Things without exchanging local raw data, which can balance the need for data privacy and the benefits of collaborative machine learning in a distributed environment. In the federated learning setting, the central server coordinates multiple clients to jointly train a global model from amounts of dispersive local data on different clients with periodic model aggregation. Since there is no exchange and sharing of data between clients and the central server during the training process, federated learning protects the privacy of clients to some extent. Furthermore, the communication manner with the server after multiple local update steps reduces the communication frequency and saves the limited communication resources. Benefitting from the decentralized learning based on local data, federated learning has been widely applied in a mobile edge network [6], healthcare [7], vehicles [8], and other fields.

Federated Averaging (FedAvg) [4] is one of the most prevailing algorithms for federated learning where a subset of clients conduct multiple stochastic gradient update steps based on their local data, and then the updates are sent back to the centralized server and averaged. FedAvg degenerates into the local stochastic gradient descent algorithm [9] when the data on different clients follow the same distribution. Despite gaining lots of attention, the practical implementation of FedAvg faces many challenges. The algorithm suffers from model drift, which hinders it converging to the optimal value of the objective function. The work of [10] generalized FedAvg and proposed FedProx to tackle the statistical and systems heterogeneity problems. In [11], the authors introduced control variates to adjust the model bias across clients, which was caused by the non-identically distributed data, but this required clients to remain stateful, which is unpractical. In addition, several works introduced the momentum technique to improve the convergence performance of stochastic gradient-based methods, which used the accumulated gradient information of previous iterations in the current step. Liu et al. [12] proposed a momentum federated learning method in a deterministic setting. The literature [13] applied a discounted global momentum to embed local iterations so as to accelerate learning and control model drift. In fact, the accumulated stale information may slow down the response to changes toward the update direction, which leads to the models continuing to update in the wrong direction, even though the gradient in the current step is already pointing in the right direction. This phenomenon is called overshoot in the domain of control, which manifests as oscillation and consumes more training time and resources.

Proportional–integral–derivative (PID) control is one of the most widely used control methods in the field of industrial control. The basic idea of PID control is making use of the current, past, and future trend information between the actual system output and the desired output. In order to settle the overshoot problem based on the stochastic gradient method, the study [14] that originated from the PID method proposed an integral–derivative approach which introduces the derivative or difference of the gradient in the training process. And the study [15] proposed a complete PID optimizer to stabilize the training process. On the other hand, due to the advantages of less parameter adjustment and better convergence speed, adaptive-type methods and variants [16,17,18] have been used in federated learning settings and obtained good results. Inspired by these observations, we focus on both the descent direction and the learning rate for performance improvement in the design of an optimization algorithm based on stochastic gradient. We introduce the derivative information to the update rule of a federated model, which represents the future trend information of the gradient change. With reference to the ongoing debate on model-centric AI and data-centric AI, our work belongs to the category of model-centric AI, highlighting the significance of further developing model-centric approaches [19]. In a nutshell, the contributions are elaborated on as follows.

• We develop a federated optimization method, named FedDA, which utilizes the trend of gradient change and adaptive learning rate to update the federated global model.
• We provide the convergence analysis for the proposed algorithm. It achieves the convergence rate of $\mathcal{O}(1/\sqrt{nTH})$ for full client participation and $\mathcal{O}(1/\sqrt{T}\sqrt[3]{m})$ for partial client participation in a stochastic non-convex setting, where n, m represent the number of clients, H is the number of local updates and T denotes the number of communications.
• We conduct the image classification tasks on a standard dataset to compare FedDA and other basineline methods. The experiment results show the effectiveness of our proposed algorithm.

The rest of this paper is organized as follows. We review the related literature in Section 2. Next, the optimization problem and algorithm design are presented in Section 3. Then, the helpful assumptions and theoretical results are displayed in Section 4. The convergence guarantee is built in detailed in Section 5. We compare the proposed algorithm with several baseline methods by extensive experiments in Section 6. We conclude the article in Section 7.

$Notation.$ In this paper, we use $\left[n\right]$ to denote the set $\{1,2,∆,n\}$ for a positive integer n and $S_t$ is the clients set with size $\mid S_t\mid =m$ for $m\in (0,n]$ in the communication round t. We use ${\parallel ·\parallel }_1$ and $\parallel ·\parallel$ to represent the ${\ell }_1$ and ${\ell }_2$ norm, respectively. Let ${[·]}_{i,t}^h$ denote the model parameter of the h-th local update step of the t-th communication round for client i.

2. Related Work

Stochastic gradient descent (SGD) [20] has been extensively applied in training large-scale machine learning models because of only choosing a mini-batch data sample or even a sample for each update round for the past few years. In order to reduce the influence of noise on stochastic gradient, the momentum technique [21,22] was introduced to correct the gradient direction. The literature [23] trained deep recurrent neural networks with momentum and strong initialization. Although its advantages include its simplicity and ease of implementation, the stochastic gradient-type methods depend on the selection of hyperparameters and show a heavy-tailed behavior from empirical observations. Adaptive optimization methods and variants have been studied and applied for their good practical performance in neural network training, such as Adagrad [24], Adam [16] and AMSGrad [25]. Xie et al. [26] proposed a new variant of Adam by reformulating the Nesterov update schemes for accelerate deep neural network training. These methods generally utilize the adaptive learning rate and momentum technique, which adaptively adjust learning rates for each coordinate of model parameters and enjoy excellent convergence performance. Recently, Recht [27] has revealed the connection between PID feedback control and stochastic optimization algorithms, and the former can be viewed as an optimizer that encapsulates gradient and momentum. An et al. [14] proposed a PID controller approach to solve the overshoot problem, which added the gradient difference in the current update step to predict the change trend of the updating direction. The work of [15] proposed a complete PID algorithm by increasing the effect of current information to relieve the oscillations during the training stage. The idea of adaptive PID control [28] permeates into the stochastic optimization by taking advantage of the current, the past and predicted future information of the gradient throughout the training process. These methods are implemented in a centralized manner.

As the size of the data samples increases, distributed training has gained more attention. Despite the great advantage, it incurs privacy issues and a communication bottleneck caused by the bandwidth limits and network delays. FedAvg [4] was proposed by incorporating a local gradient update and model averaging periodically, significantly reducing the communication overhead. After that, many variants of FedAvg were developed and proposed. The convergent upper bound of FedAvg was established by [9] and improved later in [29] under different data distribution cases. Li et al. [10] introduced a proximal term and proposed the FedProx framework to solve the heterogeneity challenge. Karimireddy et al. [11] made use of the control variable to adjust the model bias across clients. Guo et al. [30] presented hybrid local SGD by means of dividing the clients into different groups to achieve a good balance between model accuracy and runtime. Most of these works used stochastic gradient descent to update local models. Some momentum-based approaches are extended to the federated learning setting. Nesterov momentum [31] was used to accelerate learning when the objective function is convex. The work of [32] added the momentum to both the server model aggregation and local model update in order to reduce high variance, which improved the iteration complexity of federated learning. More recently, the studies incorporating momentum and an adaptive technique have emerged in a federated learning setting. FedAdam [17] was first proposed as a federated version of the adaptive gradient-type method with satisfactory performance. Several adaptive gradients methods with calibrations were studied by [33]. Local AMSGrad [34] considers the adaptiveness in the local model, while FedCAMS [18] utilizes the adaptive gradient in the update of the global model. FedExP [35] was developed by using varying pseudo-gradients to adaptively decide the step size of the server. Inspired by the above studies, in this article, we introduce the gradient difference and adaptive learning rate to the server side during the update of the global model and analyze its convergence performance.

3. Problem Formulation and Algorithm Design

A typical federated learning system with n clients or devices is considered where a global model is jointly trained under the orchestration of a central server by decentralized data. The main goal for n devices in a federated learning system is to settle an optimization problem, which can be formulated as:

$$\begin{array}{cc}\hfill \underset{\mathbf{x}\in {\mathbb{R}}^d}{min}f\left(\mathbf{x}\right)& =\frac{1}{n}\sum _{i=1}^n{f}_i\left(\mathbf{x}\right),\hfill \end{array}$$

(1)

where $f_i\left(\mathbf{x}\right)\triangleq {\mathbb{E}}_{{\xi }_i\sim D_i}{f}_i(\mathbf{x};{\xi }_i)$ denotes the local cost function for the i-th client, which assesses the average discrepancy between the learning model and the ground truth associated with a random data sample ${\xi }_i$ that draws distribution $D_i$. n is the number of decentralized clients, and d denotes the dimensionality of the model parameters. In practice, the dataset belonging to each client is often generated based on its own local environment, which means the distribution $D_i,D_j$ could be different, i.e., $D_i\ne D_j$, when $i\ne j$.

In this section, we present a differential adaptive federated optimization algorithm (FedDA) to solve problem (1), where the central server updates the global model by adopting the differential of the pseudo-gradient and an adaptive learning rate. The pseudo-code of FedDA is summarized in detailed in Algorithm 1. Specifically, at the beginning of communication round t, the centralized server randomly selects a subset $S_t$ of clients and sends the current global model ${\mathbf{x}}_t$ to each client i, $i\in S_t$. After conducting H stochastic gradient descent steps with the local learning rate as line 6 in Algorithm 1, each client i acquires the local model parameters ${\mathbf{x}}_{i,t}^H$ and sends its model update to the central server after computing the model difference ${\Gamma }_{i,t}$, i.e., ${\Gamma }_{i,t}={\mathbf{x}}_{i,t}^H-{\mathbf{x}}_t$, where ${\mathbf{x}}_t$ is the global model. In fact, by recursion on the local update rule in line 6, ${\Gamma }_{i,t}$ is the cumulative gradient for the client i. Hence, the aggregated difference ${\Gamma }_t$ as defined in line 10 of Algorithm 1 can be regarded as the pseudo-gradient to update the global model in the sever. Then, based on ${\Gamma }_t$, the central server computes the momentum term ${\mathbf{m}}_t$ and ${\mathbf{v}}_t$ following AMSGrad in [25] where ${\widehat{\mathbf{v}}}_t$ is designed to be non-decreasing, avoiding the divergence of adaptive methods, and ${\beta }_1$ and ${\beta }_1$ are momentum factors.

Algorithm 1 Federated Differential Adaptive Optimization Algorithm (FedDA)

Input: Initial point ${\mathbf{x}}_0$, learning rate ${\eta }_l$ and $\eta$, ${\mathbf{m}}_0=0$, ${\mathbf{v}}_0=0$, ${\mathbf{d}}_0=0$.   1: for $t=1,\dots ,T$ do   2:   for each client $i\in S_t$ in parallel do   3:   Set ${\mathbf{x}}_{i,t}^0={\mathbf{x}}_t$   4:   for $h=0,\dots ,H-1$ do   5:    Compute stochastic gradient ${\mathbf{g}}_{i,t}^h=\nabla F_i({\mathbf{x}}_{i,t}^h,{\xi }_{i,t}^h)$   6:    Local update: ${\mathbf{x}}_{i,t}^{h+1}={\mathbf{x}}_{i,t}^h-{\eta }_l{\mathbf{g}}_{i,t}^h$   7:   end for   8:   Let ${\Gamma }_{i,t}={\mathbf{x}}_{i,t}^H-{\mathbf{x}}_t$ and upload ${\Gamma }_{i,t}$ to the server   9:   end for 10:   Compute ${\Gamma }_t=\frac{1}{|S_t|}{\sum }_{i\in S_t}{\Gamma }_{i,t}$ in the server 11:   Update ${\mathbf{m}}_t={\beta }_1{\mathbf{m}}_{t-1}+(1-{\beta }_1){\Gamma }_t$ 12:   Update ${\mathbf{v}}_t={\beta }_2{\mathbf{v}}_{t-1}+(1-{\beta }_2){\Gamma }_t^2$ 13:   Let ${\widehat{\mathbf{v}}}_t=max\{{\widehat{\mathbf{v}}}_{t-1},{\mathbf{v}}_t\}$ and ${\widehat{\Gamma }}_t=\frac{{\Gamma }_t}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}$ 14:   Update ${\mathbf{d}}_t={\beta }_1{\mathbf{d}}_{t-1}+(1-{\beta }_1)({\widehat{\Gamma }}_t-{\widehat{\Gamma }}_{t-1})$ 15:   Update the global model in the server:   ${\mathbf{x}}_{t+1}={\mathbf{x}}_t+\eta \frac{{\mathbf{m}}_t}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}+\nu {\mathbf{d}}_t$ 16:   Broadcast ${\mathbf{x}}_{t+1}$ to each client 17: end for

In particular, we add the ${\mathbf{d}}_t$ term to the update rule of the global model. It denotes the changing trend of gradient and can be interpreted as the future information along the undate direction. To weaken the impact of noise caused by mini-batch data in each optimization step, we adopt moving average decay on the ${\mathbf{d}}_t$ term, which incorporates the history value on the current update and calculates a weighted average based on these values as shown in line 14 of Algorithm 1. In addition, we introduce ${\widehat{\Gamma }}_t={\Gamma }_t/(\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ)$ to reduce the interference of outliers and correct the gradient, because the model may be unstable and the difference in the gradient direction by random batch sampling can be large, especially in the initial stage of training. Note that the vector square and vector division throughout the paper are element-wise.

4. Main Theoretical Results

In this section, we provide the theoretical convergence results of our proposed algorithm FedDA. Before presenting the main results, we first make some assumptions required for the analytical proof.

Assumption 1.

(Smoothness) The cost function $f_i\left(\mathbf{x}\right)$ is L-smooth with the constant $L>0$; that is, for ∀$\mathbf{x},\mathbf{y}\in {\mathbb{R}}^d$ and $i\in \left[n\right]$, we have

$$\parallel \nabla f_i\left(\mathbf{x}\right)-\nabla f_i\left(\mathbf{y}\right)\parallel \le L\parallel \mathbf{x}-\mathbf{y}\parallel .$$

(2)

Note that Assumption 1 suggests the critical property, i.e., $f_i\left(\mathbf{x}\right)-f_i\left(\mathbf{y}\right)\le \langle \nabla f_i\left(\mathbf{y}\right),\mathbf{x}-\mathbf{y}\rangle +\frac{L}{2}{\parallel \mathbf{x}-\mathbf{y}\parallel }^2$. It is a commonly used assumption in theoretical analysis of stochastic non-convex optimization problems [25,36]. Similarly, it is also used in the algorithm analysis of federated learning, such as [18,34].

Assumption 2.

(Unbiased and bounded gradient) For $\forall i\in \left[n\right]$ and $t\in \left[T\right]$, the stochastic gradient ${\mathbf{g}}_{i,t}^h$ is unbiased, i.e., $\mathbb{E}\left[{\mathbf{g}}_{i,t}^h\right]=\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)$; each function $f_i\left(\mathbf{x}\right)$ has a B-bounded stochastic gradient, i.e., $\parallel {\mathbf{g}}_{i,t}^h\parallel \le B$.

Assumption 2 is a general assumption condition to give the upper bound of the gradient in adaptive gradient-type methods, such as in [17,34].

Assumption 3.

(Bounded variance) For $\forall i\in \left[n\right]$ and $t\in \left[T\right]$, the variance of each stochastic gradient for a local client is bounded, i.e., $\mathbb{E}\parallel {\mathbf{g}}_{i,t}^h-\nabla f_i\left({\mathbf{x}}_{i,t}^h\right){\parallel }^2\le {\delta }_l^2$; the deviations among each loss function $f_i\left(\mathbf{x}\right)$ are bounded, i.e., $\frac{1}{n}{\sum }_{i=1}^n{\parallel \nabla f_i\left(\mathbf{x}\right)-\nabla f\left(\mathbf{x}\right)\parallel }^2\le {\delta }_g^2$.

Note that the local bound ${\delta }_l$ in Assumption 3 quantifies the random variation of the gradient estimator for each client, and the global bound ${\delta }_g$ describes the deviation between each loss function $f_i\left(\mathbf{x}\right)$, which is mainly introduced by the heterogeneous data of each client. In particular, ${\delta }_g=0$ means that the data of all the clients follow the same distribution, i.e., the homogeneous data setting.

Based on these assumptions, we present the following convergence theorems for the proposed algorithm. The case in which all clients take part in the model training during each round is considered first, i.e., $|S_t| =n$, any $t\in \left[T\right]$.

Theorem 1.

(Full Client Participation) Suppose that Assumptions 1–3 hold. Let local learning rate ${\eta }_l$ satisfy ${\eta }_l\le min\{\frac{1}{8HL},\frac{ϵ}{3HL(HB+ϵ)(\eta {\beta }_1^2/{(1-{\beta }_1)}^2+\eta +{\nu }^2/{\eta }^2)}\}$. Under the full client participation case, the iterations of Algorithm 1 satisfy

$$\begin{array}{cc}\hfill & \frac{1}{T}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2\le 4({\eta }_{l}HB+ϵ)\left[\frac{f\left({\mathbf{x}}_0\right)-f^{\ast }}{\eta {\eta }_{l}HT}+\frac{C_1}{T}+C_2\right],\hfill \end{array}$$

(3)

where $C_1=\frac{{\beta }_1{B}^{2}d}{(1-{\beta }_1)ϵ}+\frac{\eta {\eta }_{l}H{B}^2{\beta }_1^{2}Ld}{{(1-{\beta }_1)}^2{ϵ}^2}$ and $C_2=\frac{5{\eta }_l^2{L}^{2}H}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)+\frac{3\eta {\eta }_l{\beta }_1^{2}L{\delta }_l^2}{2n{(1-{\beta }_1)}^2{ϵ}^2}+\frac{6{\eta }_{l}LH{B}^2{\nu }^2}{\eta {ϵ}^2}$, and $f^{\ast }$ represents the optimal function value.

Remark 1.

In Theorem 1, the expected squared gradient norm in the global model is used to measure the convergence in non-convex optimization. We find that the convergence upper bound of FedDA in (3) includes three terms: the first two terms relate to T and vanish to zero when T has a sufficiently large increase. The third term $C_2$ is independent of T, which depends on the local variance ${\delta }_l$ and the global variance ${\delta }_g$. We further divide $C_2$ into three parts. The first part in $C_2$ is the cumulative variance by conducting H local iteration steps which are greatly affected by the data heterogeneity. It will be smaller when each client follows the same data distribution, i.e., ${\delta }_g=0$. The local variance of the gradient computed by randomly sampling data points for each client contributes to the second part of $C_2$. It decreases at the rate $\frac{1}{n}$, which means more data samples from more clients, resulting in the decreasing of noise of stochastic gradients. The last part of $C_2$ depends on the number of local update H. This requires a sufficiently small ν to offset the influence of the gradient difference to make the last past in $C_2$ small.

With Theorem 1, we restate the above convergence result for the FedDA algorithm by choosing proper learning rates:

Corollary 1.

Let ${\eta }_l=\mathcal{O}\left(\frac{1}{\sqrt{T}H}\right)$, $\eta =\mathcal{O}\left(\sqrt{nH}\right)$. For $T\ge nH$, the convergence rate of the FedDA algorithm under the all client participation case is:

$$\begin{array}{c}\hfill \frac{1}{T}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2\le \mathcal{O}\left(\frac{1}{\sqrt{nTH}}\right).\end{array}$$

(4)

Remark 2.

From Corollary 1, we can see that the convergence rate of the proposed algorithm is $\mathcal{O}\left(\frac{1}{\sqrt{nTH}}\right)$ as long as $T\ge nH$. In [37], the generated FedAvg with local and global learning rates achieves a convergence rate of $\mathcal{O}(1/\sqrt{nKT})$, where K denotes the number of local update steps. For federated adaptive optimization, the convergence rate of FedAdam [17] is $\mathcal{O}(1/\sqrt{nKT})$, which is similar to FedYogi when the data are heterogeneous. Thus, the proposed FedDA matches the convergence result of a non-convex problem in federated learning [18].

Next, a partial client participation case is considered, which is more practical in a federated learning setting for each communication round. $S_t$ denotes the set of clients who participate in the training of the local model and communicate with the central server in round t, and the size of $S_t$ is m, i.e., $|S_t|=m$, $0<m\le n$, $\forall t\in \left[T\right]$. We adopt the random sampling strategy without replacement. There is a random selection of clients in addition to the stochastic gradient. Here, $\mathbb{E}[·]$ is still used to express the expectations for these two kinds of randomness.

Theorem 2.

(Partial Client Participation) Suppose that Assumptions 1–3 hold. Let local learning rate ${\eta }_l$ satisfy ${\eta }_l\le min\{\frac{1}{8HL},\frac{m(n-1){ϵ}^2}{nHL(m-1)(2{\eta }^2+3{\nu }^2+1+3{\eta }^2{\beta }_1^2/{(1-{\beta }_1)}^2)(HB+ϵ)}\}$. Under the partial client participation case, the iterations of Algorithm 1 satisfy

$$\begin{array}{cc}\hfill & \frac{1}{T}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2\le 4({\eta }_{l}HB+ϵ)\left[\frac{f\left({\mathbf{x}}_0\right)-f^{\ast }}{\eta {\eta }_{l}HT}+\frac{C_1}{T}+C_4\right],\hfill \end{array}$$

(5)

where $C_1=\frac{{\beta }_1{B}^{2}d}{(1-{\beta }_1)ϵ}+\frac{\eta {\eta }_l{\beta }_1^{2}LH{B}^{2}d}{{(1-{\beta }_1)}^2{ϵ}^2}$, $C_4=\frac{5{\eta }_l^2{L}^{2}H}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)+\frac{6{\eta }_{l}LH{B}^2{\nu }^2}{{ϵ}^2}+C_{3}L\left[\frac{{\eta }_l{\delta }_l^2}{m}+\frac{{\eta }_l(n-m)}{m(n-1)}·\left(15H^2{L}^2{\eta }_l^2({\delta }_l^2+6H{\delta }_g^2)+3H{\delta }_g^2\right)\right]$ and $C_3=\frac{2\eta +3{\nu }^2+1}{2{ϵ}^2}+\frac{3{\eta }^2{\beta }_1^2}{2{(1-{\beta }_1)}^2{ϵ}^2}$, and $f^{\ast }$ represents the optimal function value.

Remark 3.

In Theorem 2, the similar convergence upper bound is obtained for partial client participation but with a larger bias term $C_4$, which suggests that the convergence of FedDA has not changed fundamentally except introducing extra variance because of low client participation and the use of a difference term, which can be controlled by choosing a small ν.

From Theorem 2, we restate the above result by choosing a specific learning rate:

Corollary 2.

If we choose ${\eta }_l=\mathcal{O}\left(\frac{1}{\sqrt{T}H}\right)$, $\eta =\mathcal{O}\left(\sqrt[3]{m}\right)$, the convergence rate of the FedDA algorithm under the partial client participation case is:

$$\begin{array}{c}\hfill \frac{1}{T}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2\le \mathcal{O}\left(\frac{1}{\sqrt{T}\sqrt[3]{m}}\right).\end{array}$$

(6)

From Corollary 2, we find that partial client participation does not have changes in convergence in the sense of order. It implies that a larger number of m can help convergence. In addition, when choosing $m\le H^3$, we have a slightly small convergence bound compared to [18].

5. Performance Analysis

This section first gives useful lemmas and builds a theoretical convergence guarantee for the proposed algorithm FedDA. Here, we define ${\mathbf{x}}_0={\mathbf{x}}_1$, ${\Gamma }_0=0$; for $t\ge 1$, a virtual sequence ${\mathbf{y}}_t$ is introduced as follows:

$$\begin{array}{c}\hfill {\mathbf{y}}_t={\mathbf{x}}_t+\frac{{\beta }_1}{1-{\beta }_1}({\mathbf{x}}_t-{\mathbf{x}}_{t-1})-\nu {\widehat{\Gamma }}_{t-1},\end{array}$$

(7)

and we obtain the following property for the difference of ${\mathbf{y}}_t$,

$$\begin{array}{cc}\hfill {\mathbf{y}}_{t+1}-{\mathbf{y}}_t& =\frac{1}{1-{\beta }_1}({\mathbf{x}}_{t+1}-{\mathbf{x}}_t)-\frac{{\beta }_1}{1-{\beta }_1}({\mathbf{x}}_t-{\mathbf{x}}_{t-1})-\nu ({\widehat{\Gamma }}_t-{\widehat{\Gamma }}_{t-1})\hfill \\ \hfill & =\frac{1}{1-{\beta }_1}\left(\frac{\eta {\mathbf{m}}_t}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}+\nu {\mathbf{d}}_t\right)-\nu ({\widehat{\Gamma }}_t-{\widehat{\Gamma }}_{t-1})-\frac{{\beta }_1}{1-{\beta }_1}\left(\frac{\eta {\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}+\nu {\mathbf{d}}_{t-1}\right)\hfill \\ \hfill & =\frac{\eta {\beta }_1}{1-{\beta }_1}\left(\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}\right)\odot {\mathbf{m}}_{t-1}+\frac{\eta }{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\odot {\Gamma }_t.\hfill \end{array}$$

(8)

Lemma 1.

Under Assumption 2 and Algorithm 1, we have $\parallel \nabla f\left(\mathbf{x}\right)\parallel \le B$, $\parallel {\Gamma }_t\parallel \le {\eta }_{l}HB$, $\parallel {\mathbf{m}}_t\parallel \le {\eta }_{l}HB$, $\parallel {\mathbf{v}}_t\parallel \le {\eta }_l^2{H}^2{B}^2$ and $\parallel {\mathbf{d}}_t\parallel \le \frac{2(1-{\beta }_1)}{{\beta }_1}\frac{{\eta }_{l}HB}{ϵ}$.

Proof of Lemma 1. 

Because of the bounded stochastic gradient by Assumption 2, we have

$$\begin{array}{cc}\hfill \parallel \nabla f\left(\mathbf{x}\right)\parallel & =\parallel {\mathbb{E}}_{\xi }\nabla f(\mathbf{x},\xi )\parallel \le {\mathbb{E}}_{\xi }\parallel \nabla f(\mathbf{x},\xi )\parallel \le B.\hfill \end{array}$$

(9)

By the definition of ${\Gamma }_t$ in Algorithm 1, the following relation holds regardless of full participation or partial participation cases,

$$\begin{array}{cc}\hfill \parallel {\Gamma }_t\parallel & =∥\frac{1}{|{\mathcal{S}}_t|}\sum _{i\in {\mathcal{S}}_t}{\Gamma }_{i,t}∥=∥\frac{1}{|{\mathcal{S}}_t|}\sum _{i\in {\mathcal{S}}_t}\left(-{\eta }_l\sum _{h=0}^{H-1}{g}_{i,t}^h\right)∥\le \frac{{\eta }_l}{|{\mathcal{S}}_t|}\sum _{i\in {\mathcal{S}}_t}\sum _{h=0}^{H-1}∥g_{i,t}^h∥\le {\eta }_{l}HB.\hfill \end{array}$$

(10)

Hence, we can estimate the upper bound for ${\mathbf{m}}_t$ and ${\mathbf{v}}_t$ based on (10),

$$\begin{array}{c}\hfill \parallel {\mathbf{m}}_t\parallel \le (1-{\beta }_1)\sum _{j=1}^t{\beta }_1^{t-j}∥{\Gamma }_j∥\le {\eta }_{l}HB,\end{array}$$

(11)

$$\begin{array}{c}\hfill \parallel {\mathbf{v}}_t\parallel \le (1-{\beta }_2)\sum _{j=1}^t{\beta }_2^{t-j}{∥{\Gamma }_j∥}^2\le {\eta }_l^2{H}^2{B}^2.\end{array}$$

(12)

In addition, we expand ${\mathbf{d}}_t$ and note ${\widehat{\Gamma }}_0=0$:

$$\begin{array}{cc}\hfill \parallel {\mathbf{d}}_t\parallel & =∥\frac{1-{\beta }_1}{{\beta }_1}\left({\widehat{\Gamma }}_t-(1-{\beta }_1)\sum _{j=1}^t{\beta }_1^{t-j}{\widehat{\Gamma }}_j\right)∥\hfill \\ \hfill & \le \frac{1-{\beta }_1}{{\beta }_1}\left(∥{\widehat{\Gamma }}_j∥+(1-{\beta }_1)\sum _{j=1}^t{\beta }_1^{t-j}∥{\widehat{\Gamma }}_j∥\right)\hfill \\ \hfill & \le \frac{2(1-{\beta }_1)}{{\beta }_1}\frac{{\eta }_{l}HB}{ϵ},\hfill \end{array}$$

(13)

where the last inequality holds by $\parallel {\widehat{\Gamma }}_t\parallel \le \frac{{\eta }_{l}HB}{ϵ}$. □

Lemma 2.

Under Algorithm 1, for the difference sequence of $\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}$, we have ${\sum }_{t=1}^T{∥\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}∥}_1\le \frac{d}{ϵ}$ and ${\sum }_{t=1}^T∥\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}∥\le \frac{d}{{ϵ}^2}$.

Proof of Lemma 2. 

From the definition of ${\widehat{\mathbf{v}}}_t=max\{{\widehat{\mathbf{v}}}_{t-1},{\mathbf{v}}_t\}$, we have

$$\begin{array}{cc}\hfill \sum _{t=1}^T{∥\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}∥}_1& =\sum _{t=1}^T{∥\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}∥}_1-{∥\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}∥}_1\hfill \\ \hfill & ={∥\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_0}+ϵ}∥}_1-{∥\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_T}+ϵ}∥}_1\hfill \\ \hfill & \le \frac{d}{ϵ}.\hfill \end{array}$$

(14)

Similarly, according to the definition of the ${\ell }_2$ norm, we have

$$\begin{array}{cc}\hfill \sum _{t=1}^T{∥\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}∥}^2& =\sum _{t=1}^T\sum _{j=1}^d{\left(\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right)}_j^2\hfill \\ \hfill & \le \sum _{t=1}^T\sum _{j=1}^d\frac{1}{ϵ}{\left(\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right)}_j\hfill \\ \hfill & \le \sum _{j=1}^d\frac{1}{ϵ}{\left(\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_0}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_T}+ϵ}\right)}_j\hfill \\ \hfill & \le \frac{d}{{ϵ}^2},\hfill \end{array}$$

(15)

where the last inequality has the non-decreasing nature of ${\widehat{\mathbf{v}}}_t$. We finish the proof. □

Lemma 3.

Under the scheme of randomly sampling without replacement, the average of partial model difference ${\Gamma }_t$ is an unbiased estimator of ${\overline{\Gamma }}_t$, i.e.,

$${\mathbb{E}}_{S_t}\left[{\Gamma }_t\right]={\overline{\Gamma }}_t,$$

(16)

where ${\overline{\Gamma }}_t=\frac{1}{n}{\sum }_{i=1}^n{\Gamma }_{i,t}$.

Proof of Lemma 3. 

For a partial client participation case, let $S_t=\{l_1,∆,l_m\}$ with $|S_t|=m$; because the sampling distribution of each round is identical, we have

$$\begin{array}{cc}\hfill {\mathbb{E}}_{S_t}[{\Gamma }_t]& =\frac{1}{m}{\mathbb{E}}_{S_t}[\sum _{l_i\in S_t}{\Gamma }_{l_i,t}]=\frac{1}{m}{\mathbb{E}}_{S_t}[\sum _{i=1}^m{\Gamma }_{l_i,t}]={\mathbb{E}}_{S_t}[{\Gamma }_{l_1,t}]=\frac{1}{n}\sum _{i=1}^n{\Gamma }_{i,t}={\overline{\Gamma }}_t.\hfill \end{array}$$

(17)

□

Lemma 4.

Under Assumptions 1–3 and Algorithm 1, when all clients participate in communication with the server in each round, the following upper bound holds for the average of the aggregated model difference ${\Gamma }_t$

$$\begin{array}{c}\hfill \mathbb{E}\parallel {\Gamma }_t{\parallel }^2\le \frac{{\eta }_l^{2}H{\delta }_l^2}{n}+\frac{{\eta }_l^2}{n^2}\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2,\end{array}$$

(18)

and for a partial participation case, we have

$$\begin{array}{cc}\hfill \mathbb{E}\parallel {\Gamma }_t{\parallel }^2& \le \frac{{\eta }_l^{2}H{\delta }_l^2}{m}+\frac{{\eta }_l^2(n-m)}{m(n-1)}\left[15H^3{L}^2{\eta }_l^2({\delta }_l^2+6H{\delta }_g^2)+3H^2{\delta }_g^2\right.\hfill \\ \hfill & \phantom{=}\left.+(90H^4{L}^2{\eta }_l^2+3H^2){\parallel \nabla f\left({\mathbf{x}}_t\right)\parallel }^2\right]+\frac{{\eta }_l^2(m-1)}{mn(n-1)}\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2.\hfill \end{array}$$

(19)

Proof of Lemma 4. 

When $|S_t|=n$, we have

$$\begin{array}{cc}\hfill \mathbb{E}\parallel {\Gamma }_t{\parallel }^2& =\mathbb{E}{∥\frac{1}{n}\sum _{i=1}^n{\Gamma }_{i,t}∥}^2\hfill \\ \hfill & =\mathbb{E}{∥-\frac{{\eta }_l}{n}\sum _{i=1}^n\sum _{h=0}^{H-1}{\mathbf{g}}_{i,t}^h∥}^2\hfill \\ \hfill & =\frac{{\eta }_l^2}{n^2}\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\left({\mathbf{g}}_{i,t}^h-\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)\right)∥}^2+\frac{{\eta }_l^2}{n^2}\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\hfill \\ \hfill & \le \frac{{\eta }_l^{2}H{\delta }_l^2}{n}+\frac{{\eta }_l^2}{n^2}\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2,\hfill \end{array}$$

(20)

where the third equation holds by ${\mathbb{E}\parallel \mathbf{z}\parallel }^2={\mathbb{E}\parallel \mathbf{z}-\mathbb{E}\mathbf{z}\parallel }^2+{\parallel \mathbb{E}\mathbf{z}\parallel }^2$, and the last inequality holds by Assumption 3 and $\mathbb{E}\parallel {\sum }_{=1}^n{\mathbf{z}}_i{\parallel }^2={\sum }_{=1}^n\mathbb{E}{\parallel {\mathbf{z}}_i\parallel }^2$ when ${\mathbf{z}}_i$ is an independent random variable with zero mean.

When $|S_t| =m$, and $m\in (0,n]$, we introduce the indicator function for convenience as follows

$$\begin{array}{cc}\hfill \mathbb{E}\parallel {\Gamma }_t{\parallel }^2& =\mathbb{E}{∥\frac{1}{m}\sum _{i\in S_t}{\Gamma }_{i,t}∥}^2\hfill \\ \hfill & =\frac{1}{m^2}\mathbb{E}{∥\sum _{i=1}^n{\mathbb{I}}_{\{i\in S_t\}}{\Gamma }_{i,t}∥}^2\hfill \\ \hfill & =\frac{{\eta }_l^2}{m^2}\mathbb{E}\left[{∥\sum _{i=1}^n{\mathbb{I}}_{\{i\in S_t\}}\sum _{h=0}^{H-1}\left({\mathbf{g}}_{i,t}^h-\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)\right)∥}^2+{∥\sum _{i=1}^n{\mathbb{I}}_{\{i\in S_t\}}\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\right]\hfill \\ \hfill & =\frac{{\eta }_l^2}{m^2}\mathbb{E}\left[{∥\sum _{i=1}^n\mathbb{P}\{i\in S_t\}\sum _{h=0}^{H-1}\left({\mathbf{g}}_{i,t}^h-\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)\right)∥}^2+{∥\sum _{i=1}^n\mathbb{P}\{i\in S_t\}\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\right]\hfill \\ \hfill & =\frac{{\eta }_l^2}{nm}\mathbb{E}\left[\sum _{i=1}^n\sum _{h=0}^{H-1}{∥{\mathbf{g}}_{i,t}^h-\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\right]+\frac{{\eta }_l^2}{m^2}\mathbb{E}\left[{∥\sum _{i=1}^n\mathbb{P}\{i\in S_t\}\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\right]\hfill \\ \hfill & \le \frac{{\eta }_l^{2}H{\delta }_l^2}{m}+\frac{{\eta }_l^2}{m^2}\mathbb{E}{∥\sum _{i=1}^n\mathbb{P}\{i\in S_t\}\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2,\hfill \end{array}$$

(21)

where the third equation follows by the definition of variance, i.e., ${\mathbb{E}\parallel \mathbf{z}\parallel }^2={\mathbb{E}\parallel \mathbf{z}-\mathbb{E}\mathbf{z}\parallel }^2+{\parallel \mathbb{E}\mathbf{z}\parallel }^2$, the fifth equation holds by the fact that $\mathbb{E}\parallel {\sum }_{=1}^n{\mathbf{z}}_i{\parallel }^2={\sum }_{=1}^n\mathbb{E}{\parallel {\mathbf{z}}_i\parallel }^2$ when ${\mathbf{z}}_i$ is an independent random variable with zero mean, and $\mathbb{P}\{i\in S_t\}=\frac{m}{n}$. The last one is due to the bounded variance in Assumption 3.

Recalling the equation $\parallel {\sum }_{=1}^n{\mathbf{z}}_i{\parallel }^2=n{\sum }_{=1}^n\parallel {\mathbf{z}}_i{\parallel }^2-\frac{1}{2}{\sum }_{i\ne j}{\parallel {\mathbf{z}}_i-{\mathbf{z}}_j\parallel }^2$, for the last term in (21), we have

$$\begin{array}{cc}\hfill & \mathbb{E}{∥\sum _{i=1}^n\mathbb{P}\{i\in S_t\}\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\hfill \\ \hfill & =\sum _{i\ne j}\mathbb{P}\{i,j\in S_t\}〈\nabla f_i\left({\mathbf{x}}_{i,t}^h\right),\nabla f_j\left({\mathbf{x}}_{j,t}^h\right)〉+\sum _{i=1}^n\mathbb{P}\{i\in S_t\}{∥\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\hfill \\ \hfill & =\frac{m}{n}\sum _{i=1}^n{∥\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2+\frac{m(m-1)}{n(n-1)}\sum _{i\ne j}〈\nabla f_i\left({\mathbf{x}}_{i,t}^h\right),\nabla f_j\left({\mathbf{x}}_{j,t}^h\right)〉\hfill \\ \hfill & =-\frac{m(m-1)}{2n(n-1)}\sum _{i\ne j}{∥\sum _{h=0}^{H-1}\left(\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)-\nabla f_j\left({\mathbf{x}}_{j,t}^h\right)\right)∥}^2+\frac{m^2}{n}\sum _{i=1}^n{∥\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\hfill \\ \hfill & =\frac{m(n-m)}{n(n-1)}\sum _{i=1}^n{∥\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2+\frac{m(m-1)}{n(n-1)}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2,\hfill \end{array}$$

(22)

where the second equation holds by $\mathbb{P}\{i\in S_t\}=\frac{m}{n}$ and $\mathbb{P}\{i,j\in S_t\}=\frac{m(m-1)}{n(n-1)}$, while the third one and last one hold by $\parallel {\sum }_{=1}^n{\mathbf{z}}_i{\parallel }^2=n{\sum }_{=1}^n\parallel {\mathbf{z}}_i{\parallel }^2-\frac{1}{2}{\sum }_{i\ne j}{\parallel {\mathbf{z}}_i-{\mathbf{z}}_j\parallel }^2$ and $\langle {\mathbf{z}}_1,{\mathbf{z}}_2\rangle =\frac{1}{2}[\parallel {\mathbf{z}}_1{\parallel }^2+\parallel {\mathbf{z}}_2{\parallel }^2-\parallel {\mathbf{z}}_1-{\mathbf{z}}_1{\parallel }^2]$, respectively. In addition, by plugging $\mp \nabla f_i\left({\mathbf{x}}_t\right)\pm \nabla f\left({\mathbf{x}}_t\right)$ into the first term of (22), we obtain

$$\begin{array}{cc}\hfill & \sum _{i=1}^n{∥\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\hfill \\ \hfill & =\sum _{i=1}^n\mathbb{E}\parallel \sum _{h=0}^{H-1}\left[\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)-\nabla f_i\left({\mathbf{x}}_t\right)+\nabla f_i\left({\mathbf{x}}_t\right)-\nabla f\left({\mathbf{x}}_t\right)+\nabla f\left({\mathbf{x}}_t\right)\right]{\parallel }^2\hfill \\ \hfill & \le 3H{L}^2\sum _{i=1}^n\sum _{h=0}^{H-1}\mathbb{E}{∥{\mathbf{x}}_{i,t}^h-{\mathbf{x}}_t∥}^2+3n{H}^2({\delta }_g^2+\parallel \nabla f\left({\mathbf{x}}_t\right){\parallel }^2)\hfill \\ \hfill & \le (90n{H}^4{L}^2{\eta }_l^2+3n{H}^2){\parallel \nabla f\left({\mathbf{x}}_t\right)\parallel }^2+3n{H}^2{\delta }_g^2+15n{H}^3{L}^2{\eta }_l^2({\delta }_l^2+6H{\delta }_g^2),\hfill \end{array}$$

(23)

where the first inequality follows by Assumptions 1, 3 and $\parallel {\sum }_{i=1}^n{\mathbf{z}}_i{\parallel }^2\le n{\sum }_{i=1}^n{\parallel {\mathbf{z}}_i\parallel }^2$, and the last one follows Lemma 3 in [17]. Substituting (22), (23) into (21), we obtain (19), which finishes the proof. □

Lemma 5.

Under Assumptions 1–3 and Algorithm 1, for the full participation case, we have

$$\begin{array}{c}\hfill \sum _{t=1}^T\mathbb{E}{\parallel {\mathbf{m}}_t\parallel }^2\le \frac{TH{\eta }_l^2{\delta }_l^2}{n}+\frac{{\eta }_l^2}{n^2}\sum _{t=1}^T\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2,\end{array}$$

(24)

and for the partial participation case, we have

$$\begin{array}{cc}\hfill \sum _{t=1}^T\mathbb{E}{\parallel {\mathbf{m}}_t\parallel }^2& \le \frac{T{\eta }_l^{2}H{\delta }_l^2}{m}+\frac{{\eta }_l^2(n-m)}{m(n-1)}[15T{H}^3{L}^2{\eta }_l^2({\delta }_l^2+6H{\delta }_g^2)+3T{H}^2{\delta }_g^2+(90H^4{L}^2{\eta }_l^2+3H^2)·\hfill \\ \hfill & \phantom{=}\sum _{t=1}^T{\parallel \nabla f\left({\mathbf{x}}_t\right)\parallel }^2]+\frac{{\eta }_l^2(m-1)}{mn(n-1)}\sum _{t=1}^T\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2.\hfill \end{array}$$

(25)

Proof. 

For the full client participation scheme, i.e., $|S_t| =n$, according to Algorithm 1, we have

$$\begin{array}{cc}\hfill \mathbb{E}\parallel {\mathbf{m}}_t{\parallel }^2& =\mathbb{E}\parallel (1-{\beta }_1)\sum _{j=1}^t{\beta }_1^{t-j}{\Gamma }_j{\parallel }^2\hfill \\ \hfill & \le {(1-{\beta }_1)}^2\sum _{\tau =1}^d\mathbb{E}\left[{\left(\sum _{j=1}^t{\beta }_1^{t-j}{\Gamma }_{j,\tau }\right)}^2\right]\hfill \\ \hfill & \le {(1-{\beta }_1)}^2\sum _{\tau =1}^d\mathbb{E}\left[\left(\sum _{j=1}^t{\beta }_1^{t-j}\right)\left(\sum _{j=1}^t{\beta }_1^{t-j}{\Gamma }_{j,\tau }^2\right)\right]\hfill \\ \hfill & \le (1-{\beta }_1)\sum _{\tau =1}^d\mathbb{E}\left(\sum _{j=1}^t{\beta }_1^{t-j}{\Gamma }_{j,\tau }^2\right)\hfill \\ \hfill & =(1-{\beta }_1)\sum _{j=1}^t{\beta }_1^{t-j}\mathbb{E}{\parallel {\Gamma }_j\parallel }^2\hfill \\ \hfill & \le \frac{{\eta }_l^{2}H{\delta }_l^2}{n}+\frac{{\eta }_l^2}{n^2}\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2,\hfill \end{array}$$

(26)

where the first inequality and second equation hold by the definition of the ${\ell }_2$ norm, and the second inequality follows by Cauchy–Schwarz inequality ${\left({\sum }_{k=1}^n{\mathbf{a}}_k{\mathbf{b}}_k\right)}^2\le {\sum }_{k=1}^n{\mathbf{a}}_k^2{\sum }_{k=1}^n{\mathbf{b}}_k^2$. The last inequality is due to (18) in Lemma 4 and ${\beta }_1<1$. Taking summation over t from 1 to T for (26), we obtain the desired results (24).

For the partial client participation scheme, i.e., $|S_t| =m$, the main difference is using (19) instead of (18) in Lemma 4 when bound to $\mathbb{E}\parallel {\mathbf{m}}_t{\parallel }^2$. Following a similar proof above, we can obtain the result (25). □

Finally, with the previous lemmas, we return to prove Theorem 1.

Proof of Theorem 1. 

Due to the smoothness of f, we have

$$\begin{array}{cc}\hfill & \mathbb{E}f\left({\mathbf{y}}_{t+1}\right)-\mathbb{E}f\left({\mathbf{y}}_t\right)\hfill \\ \hfill & \le \mathbb{E}〈\nabla f\left({\mathbf{y}}_t\right),{\mathbf{y}}_{t+1}-{\mathbf{y}}_t〉+\frac{L}{2}\mathbb{E}{∥{\mathbf{y}}_{t+1}-{\mathbf{y}}_t∥}^2\hfill \\ \hfill & =\underset{A_1}{\underbrace{\mathbb{E}〈\nabla f\left({\mathbf{x}}_t\right),\frac{\eta }{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\odot {\Gamma }_t〉}}-\underset{A_2}{\underbrace{\frac{\eta {\beta }_1}{1-{\beta }_1}\mathbb{E}〈\nabla f\left({\mathbf{y}}_t\right),\left(\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right){\mathbf{m}}_{t-1}〉}}\hfill \\ \hfill & \phantom{=}+\underset{A_3}{\underbrace{\frac{{\eta }^{2}L}{2}{∥\frac{{\Gamma }_t}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}-\frac{{\beta }_1}{1-{\beta }_1}\left(\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right){\mathbf{m}}_{t-1}∥}^2}}\hfill \\ \hfill & \phantom{=}+\underset{A_4}{\underbrace{\mathbb{E}〈\nabla f\left({\mathbf{y}}_t\right)-\nabla f\left({\mathbf{x}}_t\right),\frac{\eta }{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\odot {\Gamma }_t〉}}.\hfill \end{array}$$

(27)

We first bound $A_1$ as following:

$$\begin{array}{cc}\hfill A_1& =\mathbb{E}〈\nabla f\left({\mathbf{x}}_t\right),\frac{\eta }{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\odot {\Gamma }_t〉\hfill \\ \hfill & =\eta \mathbb{E}〈\frac{\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ},{\Gamma }_t+{\eta }_{l}H\nabla f\left({\mathbf{x}}_t\right)-{\eta }_{l}H\nabla f\left({\mathbf{x}}_t\right)〉\hfill \\ \hfill & =\eta \mathbb{E}〈\frac{\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ},-\frac{{\eta }_l}{n}\sum _{i=1}^n\sum _{h=0}^{H-1}{g}_{i,t}^h+\frac{{\eta }_{l}H}{n}\sum _{i=1}^n\nabla f_i\left({\mathbf{x}}_t\right)〉-\eta {\eta }_{l}H\mathbb{E}{∥\frac{\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2.\hfill \end{array}$$

(28)

Note that the first term of (28) can be further estimated:

$$\begin{array}{cc}\hfill & \eta \mathbb{E}〈\frac{\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ},-\frac{{\eta }_l}{n}\sum _{i=1}^n\sum _{h=0}^{H-1}{g}_{i,t}^h+\frac{{\eta }_{l}H}{n}\sum _{i=1}^n\nabla f_i\left({\mathbf{x}}_t\right)〉\hfill \\ \hfill & =\eta \mathbb{E}〈\frac{\sqrt{{\eta }_{l}H}\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}},-\frac{\sqrt{{\eta }_{l}H}}{Hn\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}\sum _{i=1}^n\sum _{h=0}^{H-1}\left(\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)-\nabla f_i\left({\mathbf{x}}_t\right)\right)〉\hfill \\ \hfill & =\frac{\eta {\eta }_l}{2H{n}^2}\mathbb{E}{∥\frac{{\sum }_{i=1}^n{\sum }_{h=0}^{H-1}\left(\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)-\nabla f_i\left({\mathbf{x}}_t\right)\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2-\frac{\eta {\eta }_l}{2H{n}^2}\mathbb{E}{∥\frac{{\sum }_{i=1}^n{\sum }_{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2\hfill \\ \hfill & \phantom{=}+\frac{\eta {\eta }_{l}H}{2}\mathbb{E}{∥\frac{\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2\hfill \\ \hfill & \le \frac{\eta {\eta }_l{L}^2}{2n}\sum _{i=1}^n\sum _{h=0}^{H-1}\mathbb{E}{∥\frac{{\mathbf{x}}_{i,t}^h-{\mathbf{x}}_t}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2+\frac{\eta {\eta }_{l}H}{2}\mathbb{E}{∥\frac{\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2-\frac{\eta {\eta }_l}{2H{n}^2}\mathbb{E}{∥\frac{{\sum }_{i=1}^n{\sum }_{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2\hfill \\ \hfill & \le \frac{3\eta {\eta }_{l}H}{4}\mathbb{E}{∥\frac{\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2+\frac{5\eta {\eta }_l^3{L}^2{H}^2}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)-\frac{\eta {\eta }_l}{2H{n}^2}\mathbb{E}{∥\frac{{\sum }_{i=1}^n{\sum }_{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2,\hfill \end{array}$$

(29)

where the second equation is from the equality $\langle \mathbf{a},\mathbf{b}\rangle =\frac{1}{2}{(\parallel \mathbf{a}\parallel }^2+{\parallel \mathbf{b}\parallel }^2{-\parallel \mathbf{a}-\mathbf{b}\parallel }^2)$, the first inequality follows the fact that $\parallel {\sum }_{i=1}^n{\mathbf{a}}_i{\parallel }^2\le n{\sum }_{i=1}^n{\parallel {\mathbf{a}}_i\parallel }^2$ and the smoothness of function $f_i$. Lemma 3 in [17] and ${\eta }_l\le \frac{1}{8HL}$ result in the last inequality.

Plugging (29) into (28), we have

$$\begin{array}{cc}\hfill A_1& \le -\frac{\eta {\eta }_{l}H}{4}\mathbb{E}{∥\frac{\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2+\frac{5\eta {\eta }_l^3{L}^2{H}^2}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)\hfill \\ \hfill & \phantom{=}-\frac{\eta {\eta }_l}{2H{n}^2}\mathbb{E}{∥\frac{{\sum }_{i=1}^n{\sum }_{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}}∥}^2.\hfill \end{array}$$

(30)

We further estimate the term $A_2$.

$$\begin{array}{cc}\hfill A_2& =-\frac{\eta {\beta }_1}{1-{\beta }_1}\mathbb{E}〈\nabla f\left({\mathbf{y}}_t\right),\left(\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right)〉\hfill \\ \hfill & \le \frac{\eta {\beta }_1}{1-{\beta }_1}\parallel \nabla f\left({\mathbf{y}}_t\right)\parallel ∥\left(\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right)∥\hfill \\ \hfill & \le \frac{{\eta }_l\eta {\beta }_{1}H{B}^2}{1-{\beta }_1}{∥\left(\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right)∥}_1,\hfill \end{array}$$

(31)

where the first inequality is from $\langle a,b\rangle \le \parallel a\parallel \parallel b\parallel$, and the second one holds by Lemma 1.

For the term $A_3$ in (27), applying the inequality ${\parallel a+b\parallel }^2\le {2(\parallel a\parallel }^2+{\parallel b\parallel }^2)$ and (11) in Lemma 1 yields

$$\begin{array}{cc}\hfill A_3& =\frac{{\eta }^{2}L}{2}{∥-\frac{{\beta }_1}{1-{\beta }_1}\left(\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right)+\frac{{\Gamma }_t}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}∥}^2\hfill \\ \hfill & \le \frac{{\eta }^2{\beta }_1^{2}L}{{(1-{\beta }_1)}^2}{∥\left(\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right)∥}^2+L\parallel \frac{\eta {\Gamma }_t}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}{\parallel }^2\hfill \\ \hfill & \le \frac{{\eta }^2{\eta }_l^2{H}^2{B}^2{\beta }_1^{2}L}{{(1-{\beta }_1)}^2}\parallel \frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}{\parallel }^2+L\parallel \frac{\eta {\Gamma }_t}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}{\parallel }^2.\hfill \end{array}$$

(32)

Using similar techniques to bound the term $T_4$, we have

$$\begin{array}{cc}\hfill A_4& =\mathbb{E}〈\nabla f\left({\mathbf{y}}_t\right)-\nabla f\left({\mathbf{x}}_t\right),\frac{\eta }{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\odot {\Gamma }_t〉\hfill \\ \hfill & \le \mathbb{E}\parallel \nabla f\left({\mathbf{y}}_t\right)-\nabla f\left({\mathbf{x}}_t\right)\parallel \parallel \frac{\eta }{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\odot {\Gamma }_t\parallel \hfill \\ \hfill & \le L\mathbb{E}∥{\mathbf{y}}_t-{\mathbf{x}}_t∥∥\frac{\eta }{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\odot {\Gamma }_t∥\hfill \\ \hfill & \le \frac{L}{2}\parallel \frac{{\beta }_1}{1-{\beta }_1}\left(\frac{\eta {\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}+\nu {\mathbf{d}}_{t-1}\right)-\frac{\nu {\Gamma }_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}{\parallel }^2+\frac{L{\eta }^2}{2}\parallel \frac{{\Gamma }_t}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}{\parallel }^2\hfill \\ \hfill & \le \frac{3{\eta }^{2}L}{2}\frac{{\beta }_1^2}{{(1-{\beta }_1)}^2}\parallel \frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}{\parallel }^2+\frac{3L{\nu }^2}{2}\frac{{\beta }_1^2}{{(1-{\beta }_1)}^2}{∥{\mathbf{d}}_{t-1}∥}^2+\frac{L{\eta }^2}{2}\parallel \frac{{\Gamma }_t}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}{\parallel }^2\hfill \\ \hfill & \phantom{=}+\frac{3L{\nu }^2}{2}\parallel \frac{{\Gamma }_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}{\parallel }^2\hfill \\ \hfill & \le \frac{3{\eta }^{2}L}{2{ϵ}^2}\frac{{\beta }_1^2}{{(1-{\beta }_1)}^2}{∥{\mathbf{m}}_{t-1}∥}^2+\frac{3L{\nu }^2}{2{ϵ}^2}\parallel {\Gamma }_{t-1}{\parallel }^2+\frac{{\eta }^{2}L}{2{ϵ}^2}{\parallel {\Gamma }_t\parallel }^2+\frac{6L{\eta }_l^2{H}^2{B}^2{\nu }^2}{{ϵ}^2}.\hfill \end{array}$$

(33)

Summing from $t=1,∆,T$ and using the inequality in (24) of ${\sum }_{t=1}^T{\parallel {\mathbf{m}}_t\parallel }^2$, we have

$$\begin{array}{cc}\hfill \sum _{t=1}^T{T}_4& \le \frac{3{\eta }^{2}L}{2{ϵ}^2}\frac{{\beta }_1^2}{{(1-{\beta }_1)}^2}\frac{T{\eta }_l^{2}H{\delta }_l^2}{n}+\frac{L({\eta }^2+3{\nu }^2)}{2{ϵ}^2}\sum _{t=1}^T\mathbb{E}{\parallel {\Gamma }_t\parallel }^2+\frac{6TL{\eta }_l^2{H}^2{B}^2{\nu }^2}{{ϵ}^2}\hfill \\ \hfill & \phantom{=}+\frac{3{\eta }^{2}L}{2{ϵ}^2}\frac{{\beta }_1^2}{{(1-{\beta }_1)}^2}\frac{{\eta }_l^2}{n^2}\sum _{t=1}^T\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2.\hfill \end{array}$$

(34)

Plugging (30)–(34) into (27) and summing over t from 1 to T, we have

$$\begin{array}{cc}\hfill & \mathbb{E}f\left({\mathbf{y}}_{T+1}\right)-\mathbb{E}f\left({\mathbf{y}}_1\right)\hfill \\ \hfill & \le -\frac{\eta {\eta }_{l}H}{4}\sum _{t=1}^T\mathbb{E}{∥\frac{\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2-\frac{\eta {\eta }_l}{2H{n}^2}\sum _{t=1}^T\mathbb{E}{∥\frac{{\sum }_{i=1}^N{\sum }_{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2\hfill \\ \hfill & \phantom{=}+\frac{\eta {\eta }_l{\beta }_{1}H{B}^2}{1-{\beta }_1}\sum _{t=1}^T{∥\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}∥}_1+\frac{{\eta }^2{\eta }_l^2{H}^2{B}^2{\beta }_1^{2}L}{{(1-{\beta }_1)}^2}\sum _{t=1}^T\parallel \frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}{\parallel }^2\hfill \\ \hfill & \phantom{=}\hfill \\ \hfill & \phantom{=}+\frac{(2ϵ+1)L{\eta }^2+3L{\nu }^2}{2{ϵ}^2}\sum _{t=1}^T\mathbb{E}{\parallel {\Gamma }_t\parallel }^2+\frac{3{\eta }^2{\eta }_l^2{\beta }_1^{2}LHT{\delta }_l^2}{2n{(1-{\beta }_1)}^2{ϵ}^2}+\frac{5\eta {\eta }_l^3{L}^2{H}^{2}T}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)\hfill \\ \hfill & \phantom{=}+\frac{3{\eta }^{2}L}{2{ϵ}^2}\frac{{\beta }_1^2}{{(1-{\beta }_1)}^2}\frac{{\eta }_l^2}{n^2}\sum _{t=1}^T\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2+\frac{6T{\eta }_l^{2}L{H}^2{B}^2{\nu }^2}{{ϵ}^2}.\hfill \end{array}$$

(35)

By using Lemma 2 and rearranging the terms, we have

$$\begin{array}{cc}\hfill & \mathbb{E}f\left({\mathbf{y}}_{T+1}\right)-\mathbb{E}f\left({\mathbf{y}}_1\right)\hfill \\ \hfill & \le -\frac{\eta {\eta }_{l}H}{4({\eta }_{l}HB+ϵ)}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2+\frac{\eta {\eta }_l{\beta }_{1}H{B}^{2}d}{(1-{\beta }_1)ϵ}+\frac{3{\eta }^2{\eta }_l^2{\beta }_1^{2}LHT{\delta }_l^2}{2n{(1-{\beta }_1)}^2{ϵ}^2}+\frac{6T{\eta }_l^{2}L{H}^2{B}^2{\nu }^2}{{ϵ}^2}\hfill \\ \hfill & \phantom{=}-\left(\frac{\eta {\eta }_l}{2H{n}^2(HB+ϵ)}-\frac{3{\eta }^2{\eta }_l^2{\beta }_1^{2}L}{2n^2{(1-{\beta }_1)}^2{ϵ}^2}-\frac{3L({\eta }^2+{\nu }^2){\eta }_l^2}{2n^2{ϵ}^2}\right)\sum _{t=1}^T\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\hfill \\ \hfill & \phantom{=}+\frac{5\eta {\eta }_l^3{L}^2{H}^{2}T}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)+\frac{{\eta }^2{\eta }_l^2{H}^2{B}^2{\beta }_1^{2}Ld}{{(1-{\beta }_1)}^2{ϵ}^2}\hfill \\ \hfill & \le -\frac{\eta {\eta }_{l}H}{4({\eta }_{l}HB+ϵ)}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2+\frac{\eta {\eta }_l{\beta }_{1}H{B}^{2}d}{(1-{\beta }_1)ϵ}+\frac{5\eta {\eta }_l^3{L}^2{H}^{2}T}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)\hfill \\ \hfill & \phantom{=}+\frac{3{\eta }^2{\eta }_l^2{\beta }_1^{2}LHT{\delta }_l^2}{2n{(1-{\beta }_1)}^2{ϵ}^2}+\frac{{\eta }^2{\eta }_l^2{H}^2{B}^2{\beta }_1^{2}Ld}{{(1-{\beta }_1)}^2{ϵ}^2}+\frac{6T{\eta }_l^{2}L{H}^2{B}^2{\nu }^2}{{ϵ}^2},\hfill \end{array}$$

(36)

where the first inequality follows by $\frac{1}{{\eta }_{l}HB+ϵ}\ge \frac{1}{HB+ϵ}$ and $ϵ\le 1$, and the last one holds by the fact that $\frac{\eta {\eta }_l}{2H{n}^2(HB+ϵ)}-\frac{3{\eta }^2{\eta }_l^2{\beta }_1^{2}L}{2n^2{(1-{\beta }_1)}^2{ϵ}^2}-\frac{3L({\eta }^2+{\nu }^2){\eta }_l^2}{2n^2{ϵ}^2}\ge 0$; that is, ${\eta }_l\le \frac{\eta {ϵ}^2}{3HL(HB+ϵ)({\eta }^2{\beta }_1^2/{(1-{\beta }_1)}^2+{\eta }^2+{\nu }^2)}$.

Dividing by T both sides of (36), we obtain

$$\begin{array}{cc}\hfill \frac{\eta {\eta }_{l}H}{4({\eta }_{l}HB+ϵ)T}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2& \le \frac{f\left({\mathbf{y}}_1\right)-\mathbb{E}f\left({\mathbf{y}}_{T+1}\right)}{T}+\frac{\eta {\eta }_l{\beta }_{1}H{B}^{2}d}{T(1-{\beta }_1)ϵ}+\frac{{\eta }^2{\eta }_l^2{H}^2{B}^2{\beta }_1^{2}Ld}{T{(1-{\beta }_1)}^2{ϵ}^2}\hfill \\ \hfill & \phantom{=}+\frac{3{\eta }^2{\eta }_l^2{\beta }_1^{2}LH{\delta }_l^2}{2n{(1-{\beta }_1)}^2{ϵ}^2}+\frac{5\eta {\eta }_l^3{L}^2{H}^2}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)\hfill \\ \hfill & \phantom{=}+\frac{6{\eta }_l^{2}L{H}^2{B}^2{\nu }^2}{{ϵ}^2}.\hfill \end{array}$$

(37)

Therefore,

$$\begin{array}{cc}\hfill \frac{1}{T}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2& \le 4({\eta }_{l}HB+ϵ)\left[\frac{f\left({\mathbf{y}}_1\right)-f^{\ast }}{\eta {\eta }_{l}HT}+\frac{{\beta }_1{B}^{2}d}{T(1-{\beta }_1)ϵ}\right.+\frac{3\eta {\eta }_l{\beta }_1^{2}L{\delta }_l^2}{2n{(1-{\beta }_1)}^2{ϵ}^2}\hfill \\ \hfill & \phantom{=}+\frac{5{\eta }_l^2{L}^{2}H}{2ϵ}({\sigma }_l^2+6H{\sigma }_g^2)\left.+\frac{6{\eta }_{l}LH{B}^2{\nu }^2}{\eta {ϵ}^2}\right].\hfill & \hfill \phantom{=}\end{array}$$

(38)

When using $C_1=\frac{{\beta }_1{B}^{2}d}{T(1-{\beta }_1)ϵ}+\frac{\eta {\eta }_{l}H{B}^2{\beta }_1^{2}Ld}{T{(1-{\beta }_1)}^2{ϵ}^2}$ and $C_2=\frac{5{\eta }_l^2{L}^{2}H}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)+\frac{3\eta {\eta }_l{\beta }_1^{2}L{\delta }_l^2}{2n{(1-{\beta }_1)}^2{ϵ}^2}+\frac{6{\eta }_{l}LH{B}^2{\nu }^2}{\eta {ϵ}^2}$, (38) can be expressed as follows

$$\begin{array}{c}\hfill \frac{1}{T}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2\le 4({\eta }_{l}HB+ϵ)\left[\frac{f\left({\mathbf{y}}_1\right)-f^{\ast }}{\eta {\eta }_{l}HT}+\frac{C_1}{T}+C_2\right].\end{array}$$

(39)

The proof of Theorem 1 is finished. □

Next, we consider the case of partial client participation. Different from full client participation, the aggregated model difference ${\Gamma }_t$ over the subset $S_t$ is $\frac{1}{m}{\sum }_{i\in S_t}{\Gamma }_{i,t}$ in round t. For convenience and the consistency of notations, we denote ${\overline{\Gamma }}_t$ as the average of the aggregated global model difference hereafter, i.e., ${\overline{\Gamma }}_t=\frac{1}{n}{\sum }_{i=1}^n{\Gamma }_{i,t}$. In fact, ${\Gamma }_t$ is an unbiased estimate of ${\overline{\Gamma }}_t$ by Lemma 3.

Proof of Theorem 2. 

According to Assumption 1 and taking expectation over the randomness in round t, we have

$$\begin{array}{cc}\hfill & \mathbb{E}f\left({\mathbf{y}}_{t+1}\right)-\mathbb{E}f\left({\mathbf{y}}_t\right)\hfill \\ \hfill & \le \mathbb{E}〈\nabla f\left({\mathbf{y}}_t\right),{\mathbf{y}}_{t+1}-{\mathbf{y}}_t〉+\frac{L}{2}\mathbb{E}{∥{\mathbf{y}}_{t+1}-{\mathbf{y}}_t∥}^2\hfill \\ \hfill & =\underset{A_1^{\prime }}{\underbrace{\mathbb{E}〈\nabla f\left({\mathbf{x}}_t\right),\frac{\eta }{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\odot {\Gamma }_t〉}}-\underset{A_2^{\prime }}{\underbrace{\frac{\eta {\beta }_1}{1-{\beta }_1}\mathbb{E}〈\nabla f\left({\mathbf{y}}_t\right),\left(\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right)〉}}\hfill \\ \hfill & \phantom{=}+\underset{A_3^{\prime }}{\underbrace{\frac{{\eta }^{2}L}{2}{∥\frac{{\Gamma }_t}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}-\frac{{\beta }_1}{1-{\beta }_1}\left(\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{{\mathbf{m}}_{t-1}}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\right)∥}^2}}\hfill \\ \hfill & \phantom{=}+\underset{A_4^{\prime }}{\underbrace{\mathbb{E}〈\nabla f\left({\mathbf{y}}_t\right)-\nabla f\left({\mathbf{x}}_t\right),\frac{\eta }{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}\odot {\Gamma }_t〉}}.\hfill \end{array}$$

(40)

Since ${\mathbb{E}}_{S_t}\left[{\Gamma }_t\right]={\overline{\Gamma }}_t$ by Lemma 3, the term $A_1^{\prime }$ can be estimated by the same upper bound as in (30). Similar to (31) and (32), we obtain the estimator for $A_2^{\prime }$ and $A_3^{\prime }$, respectively.

$$\begin{array}{cc}\hfill \sum _{t=1}^T{A}_2^{\prime }& \le \frac{\eta {\eta }_l{\beta }_{1}H{B}^2}{1-{\beta }_1}\sum _{t=1}^T\mathbb{E}∥\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}∥,\hfill \end{array}$$

(41)

and

$$\begin{array}{c}\hfill \sum _{t=1}^T{A}_3^{\prime }\le \frac{{\eta }^2{\eta }_l^2{H}^2{B}^2{\beta }_1^{2}L}{{(1-{\beta }_1)}^2}\sum _{t=1}^T\parallel \frac{1}{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}-\frac{1}{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}{\parallel }^2+\frac{{\eta }^{2}L}{{ϵ}^2}\sum _{t=1}^T\mathbb{E}{\parallel {\Gamma }_t\parallel }^2,\end{array}$$

(42)

and

$$\begin{array}{c}\hfill \sum _{t=1}^T{A}_4^{\prime }\le \frac{3{\eta }^{3}L}{2{ϵ}^2}\frac{{\beta }_1^2}{{(1-{\beta }_1)}^2}\sum _{t=1}^T\mathbb{E}{∥{\mathbf{m}}_t∥}^2+\frac{6TL{\eta }_l^2\eta H^2{B}^2{\nu }^2}{{ϵ}^2}+\frac{L\eta (1+3{\nu }^2)}{2{ϵ}^2}\sum _{t=1}^T\mathbb{E}{\parallel {\Gamma }_t\parallel }^2.\end{array}$$

(43)

Summing over t from 1 to T for (40) and plugging (30), (41)–(43), we have

$$\begin{array}{cc}\hfill & \mathbb{E}f\left({\mathbf{y}}_{T+1}\right)-\mathbb{E}f\left({\mathbf{y}}_1\right)\hfill \\ \hfill & \le \sum _{t=1}^T(A_1^{\prime }+A_2^{\prime }+A_3^{\prime }+A_4^{\prime })\hfill \\ \hfill & \le -\frac{\eta {\eta }_{l}H}{4}\sum _{t=1}^T\mathbb{E}{∥\frac{\nabla f\left({\mathbf{x}}_t\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_t}+ϵ}}∥}^2+\frac{5\eta {\eta }_l^3{L}^2{H}^{2}T}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)+\frac{\eta {\eta }_l{\beta }_{1}H{B}^{2}d}{(1-{\beta }_1)ϵ}\hfill \\ \hfill & \phantom{=}-\frac{\eta {\eta }_l}{2H{n}^2}\sum _{t=1}^T\mathbb{E}{∥\frac{{\sum }_{i=1}^n{\sum }_{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)}{\sqrt{\sqrt{{\widehat{\mathbf{v}}}_{t-1}}+ϵ}}∥}^2+\frac{2L{\eta }^2+(3{\nu }^2+1)L\eta }{2{ϵ}^2}\sum _{t=1}^T\mathbb{E}{\parallel {\Gamma }_t\parallel }^2\hfill \\ \hfill & \phantom{=}+\frac{{\eta }^2{\eta }_l^2{H}^2{B}^2{\beta }_1^{2}Ld}{{(1-{\beta }_1)}^2{ϵ}^2}+\frac{3{\eta }^3{\beta }_1^{2}L}{2{(1-{\beta }_1)}^2{ϵ}^2}\sum _{t=1}^T\mathbb{E}{\parallel {\mathbf{m}}_t\parallel }^2+\frac{6TL{\eta }_l^2\eta H^2{B}^2{\nu }^2}{{ϵ}^2},\hfill \end{array}$$

(44)

where the inequality results from Lemma 2. Applying (19) and (25), we obtain

$$\begin{array}{cc}\hfill & \mathbb{E}f\left({\mathbf{y}}_{T+1}\right)-\mathbb{E}f\left({\mathbf{y}}_1\right)\hfill \\ \hfill & \le -\frac{\eta {\eta }_{l}H}{4({\eta }_{l}HB+ϵ)}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2+\frac{5\eta {\eta }_l^3{L}^2{H}^{2}T}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)+\frac{\eta {\eta }_l{\beta }_{1}H{B}^{2}d}{(1-{\beta }_1)ϵ}\hfill \\ \hfill & \phantom{=}-\left[\frac{\eta {\eta }_l}{2H{n}^2(HB+ϵ)}-\frac{C_3{\eta }_l^2\eta L(m-1)}{mn(n-1)}\right]\sum _{t=1}^T\mathbb{E}{∥\sum _{i=1}^n\sum _{h=0}^{H-1}\nabla f_i\left({\mathbf{x}}_{i,t}^h\right)∥}^2\hfill \\ \hfill & \phantom{=}+C_3\eta LT\left[\frac{{\eta }_l^{2}H{\delta }_l^2}{m}+\frac{{\eta }_l^2(n-m)}{m(n-1)}(15H^3{L}^2{\eta }_l^2({\delta }_l^2+6H{\delta }_g^2)+3H^2{\delta }_g^2)\right]\hfill \\ \hfill & \phantom{=}+\frac{C_3{\eta }_l^2\eta L(n-m)}{m(n-1)}(90H^4{L}^2{\eta }_l^2+3H^2)\sum _{t=1}^T{\parallel \nabla f\left({\mathbf{x}}_t\right)\parallel }^2+\frac{{\eta }^2{\eta }_l^2{\beta }_1^2{H}^2{B}^{2}Ld}{{(1-{\beta }_1)}^2{ϵ}^2}\hfill \\ \hfill & \phantom{=}+\frac{6TL{\eta }_l^2\eta H^2{B}^2{\nu }^2}{{ϵ}^2},\hfill \end{array}$$

(45)

where $C_3=\frac{2\eta +3{\nu }^2+1}{2{ϵ}^2}+\frac{3{\eta }^2{\beta }_1^2}{2{(1-{\beta }_1)}^2{ϵ}^2}$. We rearrange the terms and let ${\eta }_l$ satisfy the condition $\frac{\eta {\eta }_l}{2H{n}^2(HB+ϵ)}-\frac{C_3{\eta }_l^2\eta L(m-1)}{mn(n-1)}\ge 0$, that is ${\eta }_l\le \frac{m(n-1){ϵ}^2}{nHL(m-1)(2{\eta }^2+3{\nu }^2+1+3{\eta }^2{\beta }_1^2/{(1-{\beta }_1)}^2)(HB+ϵ)}$. In addition, ${\eta }_l$ also satisfies $\frac{\eta {\eta }_{l}H}{4({\eta }_{l}HB+ϵ)}-\frac{C_3{\eta }_l^2\eta L(n-m)}{m(n-1)}(90H^4{L}^2{\eta }_l^2+3H^2)\ge \frac{\eta {\eta }_{l}H}{8({\eta }_{l}HB+ϵ)}$. Thus, from (45), we have

$$\begin{array}{cc}\hfill & \frac{\eta {\eta }_{l}H}{8T({\eta }_{l}HB+ϵ)}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2\hfill \\ \hfill & \le \frac{f\left({\mathbf{y}}_1\right)-\mathbb{E}f\left({\mathbf{y}}_{T+1}\right)}{T}+\frac{5\eta {\eta }_l^3{L}^2{H}^2}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)+\frac{\eta {\eta }_l{\beta }_{1}H{B}^{2}d}{T(1-{\beta }_1)ϵ}\hfill \\ \hfill & \phantom{=}+C_3\eta L\left[\frac{{\eta }_l^{2}H{\delta }_l^2}{m}+\frac{{\eta }_l^2(n-m)}{m(n-1)}(15H^3{L}^2{\eta }_l^2({\delta }_l^2+6H{\delta }_g^2)+3H^2{\delta }_g^2)\right]\hfill \\ \hfill & \phantom{=}+\frac{6L{\eta }_l^2\eta H^2{B}^2{\nu }^2}{{ϵ}^2}+\frac{{\eta }^2{\eta }_l^2{\beta }_1^{2}L{H}^2{B}^{2}Ld}{T{(1-{\beta }_1)}^2{ϵ}^2}.\hfill \end{array}$$

(46)

Therefore,

$$\begin{array}{c}\hfill \frac{1}{T}\sum _{t=1}^T\mathbb{E}{∥\nabla f\left({\mathbf{x}}_t\right)∥}^2\le 8({\eta }_{l}HB+ϵ)\left[\frac{f\left({\mathbf{y}}_1\right)-f^{\ast }}{\eta {\eta }_{l}HT}+\frac{C_1}{T}+C_4\right],\end{array}$$

(47)

where $C_1=\frac{{\beta }_1{B}^{2}d}{(1-{\beta }_1)ϵ}+\frac{\eta {\eta }_l{\beta }_1^{2}LH{B}^{2}d}{{(1-{\beta }_1)}^2{ϵ}^2}$ and $C_4=\frac{5{\eta }_l^2{L}^{2}H}{2ϵ}({\delta }_l^2+6H{\delta }_g^2)+\frac{6{\eta }_{l}LH{B}^2{\nu }^2}{{ϵ}^2}+C_{3}L\left[\frac{{\eta }_l{\delta }_l^2}{m}+\frac{{\eta }_l(n-m)}{m(n-1)}(15H^2{L}^2{\eta }_l^2({\delta }_l^2+6H{\delta }_g^2)+3H{\delta }_g^2)\right]$.

The proof of Theorem 2 is finished. □

6. Experiments

In this section, the experiment for the image classification task is performed to evaluate the performance of the proposed algorithm. We first give the performance comparison between the proposed algorithm and other baseline algorithms. Then, we explore the effect of the number of local epochs and the number of clients on the algorithm performance.

We evaluate the performance of the proposed algorithm by conducting multi-class image classification tasks on the CIFAR-10 and CIFAR-100 datasets [38] with the convolutional neural network model RestNet-18 [39], respectively. The CIFAR-10 dataset consists of 60,000 32 × 32 pixels color pictures, which include 50,000 training images and 10,000 test images in a total of 10 categories with 6000 images in each category. The CIFAR-100 dataset has the same number of training samples and test samples with CIFAR-10, except it has 100 categories with 500 training images and 100 images test images per category. We first divide the training samples and test samples randomly and evenly among multiple clients. Based on the training set of each client, a local model is trained by an optimizer and sent to the centralized server. Then, the aggregated model is evaluated on a test set, which implies the generalization ability of the aggregated model. In the experiment, all the federated optimization algorithms including our proposed algorithm are implemented on a workstation equipped with two Intel(R) Xeon(R) Silver 4114 CPUs and two NVIDIA GeForce GTX 1080 Ti GPUs. The experiment environment is based on PyTorch 1.11.0. We consider a federated learning system with 100 clients in all and 0.1 as the ratio of client participation, which means 10 clients out of 100 are selected for training in each communication round. Specifically, each client randomly selected by the centralized server uses the same SGD optimizer and conducts 3 local epoch steps, and the local batch size is set to 20. The local learning rate and global learning rate are set to $0.01$ and 1 by grid searching for the best performance. The parameter $\nu$ is searched from $\{{10}^{-2},{10}^{-6},{10}^{-8},{10}^{-10},{10}^{-12}\}$ for the best performance. In addition, momentum factors ${\beta }_1,{\beta }_2$ are set to $0.9$ and $0.99$ by default, which follows the adaptive algorithms [16,18]. We compare the proposed algorithm with the classic federated average algorithm (FedAvg) [4] and federated adaptive-type algorithms [17] including FedAdam, FedYogi and FedAMS [18] as baselines. The experimental results are demonstrated in following figures.

Figure 1 and Figure 2 provide the convergence results for FedDA and other baselines on the CIFAR-10 dataset and CIFAR-100 dataset with the RestNet-18 model in terms of training loss and test accuracy. In order to show the difference between different curves clearly, we zoom in on the last few rounds as subgraphs and place them in the blank space of the figure. For the CIFAR-10 dataset, from the convergence curve of training loss against the communication rounds in Figure 1, we find that FedDA goes down faster with the increase of communication rounds, which suggests faster convergence than other baselines. Specifically, FedDA has similar performance with FedYogi and FedAMS in the middle of training, while it works slightly better in training loss and has the highest test accuracy among all the baseline algorithms in the end. These results empirically demonstrate the effectiveness of the proposed algorithm. The similar experiment results are obtained from Figure 2 for the CIFAR-100 dataset. As shown, the proposed FedDA converges slightly faster at the beginning and final stages of training, and it achieves a higher test accuracy, which suggests that FedDA behaves well.

As shown in Figure 3, the training loss and test accuracy of different client numbers are compared while other parameters remain the same. In this setting, we explore the impact of the client number n involved in training on the performance of FedDA by choosing different parameters n from $\{5,10,20,50\}$. From the left figure of Figure 3, we observe that the convergence curve with $n=50$ has the fastest convergence rate. On the other hand, a smaller n requires more communication rounds to achieve the same target accuracy, as shown in the right figure of Figure 2.

In Figure 4, we investigate the impact of local epoch number H on the performance of FedDA by training the RestNet-18 model on the CIFAR-10 dataset while keeping the other parameters the same. We choose different H values from $\{1,3,5,10\}$. From the learning curve of training loss against the communication round in Figure 4, we can find that the local training with a larger H can help accelerate the convergence. From the right figure of Figure 4, we observe that to achieve the same target accuracy, a larger local epoch H requires a smaller communication round.

7. Conclusions

In this paper, motivated by the idea of PID, we introduce the gradient difference to the stochastic optimization method and propose a differential adaptive method for federated learning, which aims to improve the performance while training the neural network by correcting the decent direction and adaptively updatingthe model parameters. We then analyze the convergence performance for our algorithm under full client participation and partial client participation cases in a stochastic non-convex optimization setting, where the convergence rate of $\mathcal{O}(1/\sqrt{T})$ is achieved. Experiments are conducted on the CIFAR-10 dataset and CIFAR-100 dataset with the RestNet-18 model, respectively. The experiment results demonstrate that the proposed method FedDA and federated adaptive methods (FedYogi, FedAMS) have a better performance than FedAvg. FedDA surpasses the other baselines in terms of initial and final training loss, and it achieves the highest test accuracy in the end. Compared to other baselines, the proposed algorithm does not incur additional communication cost, while these performance gains are attained by increasing the computational cost of the difference terms. Thus, it is important to achieve a good trade-off between model performance and algorithm efficiency. In addition, the risk of information leakage exists when uploading model differences from clients to the centralized server. Hence, methods of privacy protection could be combined in the local training at the clients’ side. The balance between privacy levels and model accuracy can be considered as future research work.