# D-(DP)2SGD: Decentralized Parallel SGD with Differential Privacy in Dynamic Networks

Authors: Yuan Yuan; Zongrui Zou; Dong Li; Li Yan; Dongxiao Yu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Decentralized machine learning has been playing an essential role in improving training efficiency. It has been applied in many real-world scenarios, such as edge computing and IoT. However, in fact, networks are dynamic, and there is a risk of information leaking during the communication process. To address this problem, we propose a decentralized parallel stochastic gradient descent algorithm (D-(DP)2SGD) with differential privacy in dynamic networks. With rigorous analysis, we show that D-(DP)2SGD converges with a rate of O1/Kn while satisfying ε-DP, which achieves almost the same convergence rate as previous works without privacy concern. To the best of our knowledge, our algorithm is the first known decentralized parallel SGD algorithm that can implement in dynamic networks and take privacy-preserving into consideration.


---

## Body

## 1. Introduction

Decentralized machine learning, as a modeling mechanism that allocates training tasks and computes resources to achieve a balance between training speed and accuracy, has demonstrated strong potential in various areas, especially for training large models on large datasets [1–3], such as ImageNet [4]. Typically, assume that there are n workers where each worker has its local data, decentralized machine learning problem is aimed at solving an empirical risk minimization problem as follows:
(1)minx∈ℝdfx=1n∑i=1nfix,where fix is the local loss function at node i. The objective fx can be rephrased as a linear combination of the local loss function fix. This formulation can be expressed as many popular decentralized learning models including deep learning [5], linear regression [6], and logistic regression [7].In recent years, decentralized machine learning has attracted much attention to derive convergence solutions while reducing communication costs [8, 9]. Previous works mainly study decentralized collaborative learning in a static network assumption. For example, decentralized parallel stochastic gradient descent (D-PSGD) is one of the fundamental methods in solving large-scale machine learning tasks in static networks [1]. In D-PSGD, all nodes compute the stochastic gradient using their local dataset and exchange the results with their neighbors iteratively. However, in fact, dynamicity has been an important feature for networks, especially for large-scale networks, such as IoT [10] and V2V networks [11, 12], as nodes in the network can move around and join or leave the network at any time. On the other hand, in large-scale networks, it is hard or even impossible to ensure every node is reliable [13, 14]. Consequently, during the collaborative learning process, it is unavoidable to face the risk of information leaking. Hence, when designing decentralized machine learning algorithms, it has been to consider the impact of the dynamicity of network topology and the demand for privacy preservation. However, to the best of our knowledge, there is no existing work taking both factors simultaneously into consideration. In this work, we focus on this missing piece in decentralized learning.Specifically, based on differential privacy, we present a new dynamic decentralized stochastic gradient descent algorithm (D-(DP)2SGD), which offers a strong protection for local datasets of decentralized nodes. With rigorous analysis, we show that our proposed D-(DP)2SGD algorithm satisfies ε-DP and achieves the convergence rate of O1/Kn when K is large enough. Empirically, we conduct experiments on CIFAR-10 datasets to accomplish image classification tasks. We conduct extensive experiments to evaluate the performance of our proposed algorithms.The remainder of this paper is organized as follows. We present our survey on related work in Section2. We then introduce our model, problem, and some useful preliminary knowledge in Section 3. Our algorithm, main results, and analysis are presented in Section 4, Section 5, and Section 6, respectively. Experimental results are illustrated in Section 7. The whole paper is concluded in Section 8.


## 2. Related Work

In this section, we introduce some closed related work.


### 2.1. Decentralized Parallel Stochastic Gradient Algorithms

Most existing work on decentralized parallel stochastic gradient focus on static networks in both synchronous and asynchronous settings [1, 15–18]. Under the synchronous setting, Lian et al. [1] illustrated the advantage of decentralized algorithms over centralized ones and showed that the proposed D-PSGD converges with a rate of O1/Kn when K is large enough, where K is the number of iterations and n is the total number nodes in the network. Qureshi et al. [17] proposed an algorithm called S-ADDOPT, and it converges with a rate of O1/K.Feyzmahdavian et al.[19] and Agarwal et al. [20] considered decentralized SGD in the asynchronous setting. They allowed workers to use stale weights to compute gradients in S-PSGD. Asynchronous algorithms avoid idling any worker to reduce the communication overhead, and it is very robust because it can still work well when part of the computing workers are down. For asynchronous algorithms, Lian et al. [16] proposed the asynchronous decentralized parallel SGD algorithm for convex optimization and showed AD-PSGD converges at O1/K. Then, Lian et al. [21] proposed the asynchronous decentralized parallel stochastic gradient descent algorithm for nonconvex optimization and showed the ergodic convergence rate is O1/K. They proved that the linear speedup is achievable when the number of workers is bounded by K.


### 2.2. Differentially Privacy Decentralized Learning

Most existing work on differentially private decentralized learning focuses on the static network [22–25]. Our work combines decentralized learning and dynamic network in a DP setting. In contract, Lu et al. [24] proposed an asynchronous federated learning scheme with differential private for resource sharing in vehicular networks. Hsin-Pai et al. [26] proposed a new learning algorithm LEASGD (Leader-Follower Elastic Averaging Stochastic Gradient Descent), which is driven by a novel Leader-Follower topology and a differential privacy model. And they provide a theoretical analysis of the convergence rate and the trade-off between the performance and privacy in the private setting. Based on the research in [16], Xu et al. [2] designed an algorithm on asynchronous decentralized parallel stochastic gradient descent algorithm with differential privacy (A(DP)2SGD). They showed that A(DP)2SGD converges at O1/K. For all of these reviewed papers, the study of decentralized parallel SGD for differential privacy in dynamic networks is still an open problem.


## 2.1. Decentralized Parallel Stochastic Gradient Algorithms

Most existing work on decentralized parallel stochastic gradient focus on static networks in both synchronous and asynchronous settings [1, 15–18]. Under the synchronous setting, Lian et al. [1] illustrated the advantage of decentralized algorithms over centralized ones and showed that the proposed D-PSGD converges with a rate of O1/Kn when K is large enough, where K is the number of iterations and n is the total number nodes in the network. Qureshi et al. [17] proposed an algorithm called S-ADDOPT, and it converges with a rate of O1/K.Feyzmahdavian et al.[19] and Agarwal et al. [20] considered decentralized SGD in the asynchronous setting. They allowed workers to use stale weights to compute gradients in S-PSGD. Asynchronous algorithms avoid idling any worker to reduce the communication overhead, and it is very robust because it can still work well when part of the computing workers are down. For asynchronous algorithms, Lian et al. [16] proposed the asynchronous decentralized parallel SGD algorithm for convex optimization and showed AD-PSGD converges at O1/K. Then, Lian et al. [21] proposed the asynchronous decentralized parallel stochastic gradient descent algorithm for nonconvex optimization and showed the ergodic convergence rate is O1/K. They proved that the linear speedup is achievable when the number of workers is bounded by K.


## 2.2. Differentially Privacy Decentralized Learning

Most existing work on differentially private decentralized learning focuses on the static network [22–25]. Our work combines decentralized learning and dynamic network in a DP setting. In contract, Lu et al. [24] proposed an asynchronous federated learning scheme with differential private for resource sharing in vehicular networks. Hsin-Pai et al. [26] proposed a new learning algorithm LEASGD (Leader-Follower Elastic Averaging Stochastic Gradient Descent), which is driven by a novel Leader-Follower topology and a differential privacy model. And they provide a theoretical analysis of the convergence rate and the trade-off between the performance and privacy in the private setting. Based on the research in [16], Xu et al. [2] designed an algorithm on asynchronous decentralized parallel stochastic gradient descent algorithm with differential privacy (A(DP)2SGD). They showed that A(DP)2SGD converges at O1/K. For all of these reviewed papers, the study of decentralized parallel SGD for differential privacy in dynamic networks is still an open problem.


## 3. System Model and Problem Description

We consider a network consisting ofn computational nodes (could be a machine or a GPU). At each iterate k, the network topology is denoted by a network Gk=V,Ek, where V is the set of n computational nodes, V=1,2,⋯,n, and Ek⊂V×V is the set of communication edges at iterate k. If there exists an edge from node i to node j at iterate k, then i,j∈Ek. In a connected network, two nodes are neighbors if the node can be connected directly by an edge, i.e., the nodes can communicate with each other. The set of neighbors of node i at iterate k is denoted by Nki=j∣i,j∈Ek, and define Cki=Nki⋃i. We assume that the nodes keep unchanged, but the connection between nodes can be changed after every iteration. The network Gk is assumed to be strongly connected, i.e., for all nodes i,j∈V, there exists a path from i to j at each iterate k≥0. Some frequently used notations are summarized in Table 1.Table 1
Frequently used notations.
NotationDescription∥·∥The vectorℓ2 norm or the matrix spectral norm depending on the argument∥·∥FThe matrix Frobenius normf·The optimization function∇f·The gradient of a functionf1nThe column vector inℝn with 1 for all elementsf∗The optimal solution of problemλi·Theith largest eigenvalue of a matrixGkThe network topology at iteratekVThe set of nodesEkThe set of edges at iteratekKThe total number of iterationsNkiThe set of neighbors of nodei at iterate kxk,iThe local variable in nodei at iterate kx¯kThe average local variable with all nodes at iteratekξk,iThe sampled training data in nodei at iterate kx~k,iThe perturbed variable in nodei at iterate kηk,iThe Laplace noise drawn fromLapςXkThe concatenation of all local variablesX~kThe concatenation of all perturbed variablesηkThe concatenation of all Laplace noisesξkThe concatenation of all random samples∂FXk,ξkThe concatenation of all stochastic gradientsIn a decentralized network, the data is stored at nodes, and each node is associated with a local loss function(2)fix=Eξ~DiFix;ξ,where Di is a distribution associated with the local data at node i and ξ is a data sampled via Di.In this work, we consider the following optimization problem:(3)minx∈ℝdfx=Ei~Ifix=Ei~IEξ~DiFix;ξ,where I is a uniform distribution of nodes.Similarity, we gives anδ-approximation solution if
(4)K−1∑k=0K−1E∇fx¯k2≤δ,where x¯k is the average local variable with all nodes at iterate k and K is the maximum iterations.We next review the definition of differential privacy, which is originally proposed by Dwork [27].Definition 1 (see [27] (Differential Privacy)).
Given aε≥0, a randomized mechanism M with domain D preserves ε-differential privacy if for all S⊆RangeM and for any adjacent datasets (Given two datasets D=x1,x2,⋯,xn and D′=x′1,x′2,⋯,x′n, D and D′ are adjacent if there exist i∈n such that xi≠x′i and for j≠i, xj=x′j, i.e., ∥D−D′∥1=1.) D,D′∈D such that:
(5)ℙMD∈S≤expεℙMD′∈S,where RangeM is the output range of mechanism M.Informally, differential privacy means that the distributions over the outputs of the randomized algorithm should be nearly identical for two adjacent input datasets. The constantε measures the privacy level of the randomized mechanism M, i.e., a large ε implies a lower privacy level. Therefore, an appropriate constant ε should be chosen to balance the accuracy and the privacy level of the mechanism M.Then, we introduce the definition of sensitivity, which plays a key role in the design of differential privacy mechanisms.Definition 2 (see [28] (Sensitivity)).
The sensitivity of a functionf:D⟶ℝd is defined as follows:
(6)Δ=supD,D′:∥D−D′∥1=1∥fD−fD′∥1.The sensitivity of a mechanismM captures the magnitude by which a single individual’s data can change the mechanism M in the worse case. Moreover, we will introduce the Laplace mechanism.Definition 3 (see [27] (The Laplace mechanism).
Given any functionf:D⟶ℝd, the Laplace mechanism is defined as:
(7)MD,f·,ε=fD+ηk,i,where ηk,i are i.i.d. random variables drawn from Lapς. The variable of Laplace distribution is 2ς2, where ς=Δ/ε according to the property of differential privacy.Throughout the paper, we adopt the following commonly used assumptions:(1)
Lipschitzian gradient: all functionsfi·'s are L-Lipschitzian gradients.(2)
Unbiased estimation:(8)Eξ~Di∇Fix;ξ=∇fix,Ei~IEξ~Di∇Fix;ξ=∇fx.(3)
Bounded variance: assume the variance of stochastic gradient(9)Ei~IEξ~Di∥∇Fix;ξ−∇fx∥2,is bounded for any x with i sampled from the distribution I and ξ from the distribution Di. It implies there exist constants σ and ζ such that
(10)Eξ~Di∥∇Fix;ξ−∇fix∥2≤σ2,∀i,∀x,Ei~I∥∇fix−∇fx∥2≤ζ2,∀x.(4)
Bounded subgradient: assume that the subgradient∇Fix;ξ of Fix;ξ is Gi-bounded for all i∈V and x∈ℝd, i.e., ∇Fix;ξ≤Gi and G=maxi∈VGi.


## 4. Algorithm

The D-(DP)2SGD algorithm can be described as follows: each node maintains its own local variable xk,i and run the following steps.
(i)
Sample data: each node samples a training dataξk,i.(ii)
Compute gradient: each node computes the stochastic gradient∇Fixk,i,ξk,i using the current local variable xk,i and the data ξk,i, where i is the node index and k is the iterate number.(iii)
Add noise: random generate the Laplace noiseηk,i~Lapς and add noise to the variable xk,i, to get the perturbed variable x~k,i=xk,i+ηk,i.(iv)
Communication: send the perturbed variablex~k,i and the degree dk,i to its neighbors; receive x~k,j and dk,j from neighbors, where j∈Nki.(v)
Determine the matrixWk: determine the matrix Wk according to the local network topology, i.e.,(11)wk,ij=1maxdk,i,dk,jifi≠j,andj∈Nki,1−∑m∈Nkiwk,imifi=j,0otherwise.where wk,ij describes how much node j can affect node i at iterate k.
(vi)
Weighted average: compute the weighted average by obtaining perturbed variable from neighbors and the matrixWk: xk+1/2,i=∑j∈Ckiwk,ijx~k,j.(vii)
Gradient update: each node updates its local variable using the weighted average and the local stochastic gradientxk+1,i=xk+1/2,i−γ∇Fixk,i,ξk,i.From a global view, we define the concatenation of all local variables, perturbed variables, Laplace noises, random samples, and stochastic gradients by matrixXk∈ℝd×n, X~k∈ℝd×n, and ηk∈ℝd×n, vector ξk∈ℝn, and ∂FXk,ξk, respectively:
(12)Xk=xk,1,⋯,xk,n∈ℝd×n,ηk=ηk,1,⋯,ηk,n∈ℝd×n,X~k=x~k,1,⋯,x~k,n∈ℝd×n,ξk=ξk,1,⋯,ξk,n∈ℝn,∂FXk,ξk=∇F1xk,1;ξk,1∇F2xk,2;ξk,2⋯∇Fnxk,n;ξk,n∈ℝd×n.Then, thekth iterate of Algorithm 1 can be described as the following update
(13)Xk+1=X~kWk−γ∂FXk,ξk,i.e., Xk+1=Xk+ηkWk−γ∂FXk,ξk.Algorithm 1: D-(DP)2SGD: Dynamic Decentralized Parallel Stochastic Gradient Descent.
InitializationInitial pointx0,i=x0=0, step length γ, noise variance ς and number of iterations Kendfork=0,1,⋯,K−1in parallel for nodesi∈VdoSample a training dataξk,i;Compute the stochastic gradient∇Fixk,i,ξk,i using the current local variable xk,i and the data ξk,i;Randomly generate the Laplace noiseηk,i~Lapς and add noise to the variable xk,i, to get the perturbed variable x~k,i: x~k,i=xk,i+ηk,i;Send the perturbed variablex~k,i and its degree dk,i to its neighbors;Receivex~k,j and dk,j from its neighbors, j∈Nki;DetermineWk according to Equation (11);Compute the neighborhood weighted average by obtaining perturbed variables from neighbors:xk+1/2,i=∑j∈Ckiwk,ijx~k,j;Update its local variablexk+1,i=xk+1/2,i−γ∇Fixk,i,ξk,i;endOutput:1/n∑i=1nxK,i.


## 5. Main Results

In this section, we present the main results, which guarantees the privacy and the convergence rate of our proposed algorithm.Theorem 4.
Let assumptions hold. Ifηk,i’s are i.i.d. random variables drawn according to the Laplace distribution with parameter ς, such that ς=Δ/ε for all k∈0,⋯,K−1 and ε>0. Then, our proposed algorithm guarantees ε-differential private.Theorem 5.
LetB1=1/2−18γ2n−1L2/1−ρ2B2, B2=1−36γ2n−1L2/1−ρ2. Under the assumptions, we can get the convergence rate of Algorithm 1 as follows:
(14)1−γL/2∑k=0K−1E∂fXk1n/n2+B1∑k=0K−1E∇fXk1n/n2K≤f0−f∗γK+41+2LG2dγε2+γLnσ2+24n−1L2G2γ2ε21−ρ2B2+2γ2L2n−1σ21−ρB2+18γ2n−1L2ζ21−ρ2B2,where Xk1n/n=1/n∑i=1nxk,i=x¯k.This theorem characterizes the convergence of the average of all local optimization variablesxk,i. To take a closer look at this result, we choose an appropriate step length in Theorem 5 to obtain the following result:Corollary 6.
Under the same assumptions as in Theorem5, let G/ε≤f0−f∗+Lσ/41+2Ldn, by setting γ=1/2L+σK/n, we have the following convergence rate:
(15)∑k=0K−1E∇fXk1n/n2K≤8Lf0−f∗K+12f0−f∗+LσKn,if the total number of iterates K is sufficiently large,
(16)K≥max16n3n−12L4σ6f0−f∗+L212G2ε21−ρ2+σ21−ρ+9ζ21−ρ22,144nn−1L2σ21−ρ2.


## 6. Result Analysis

In this section, we will give the analysis for privacy preservation and convergence rate of D-(DP)2SGD.For convenience, we define(17)∂fXk=∇f1xk,1∇f2xk,2⋯∇fnxk,n∈ℝd×n,and
(18)Φk:s=WkWk−1⋯Ws,k≥s,I,s=k+1.


### 6.1. Privacy Analysis

Proof (Proof of Theorem4).
From the definition of sensitivity, we obtain(19)xk,i−xk,i′1≤Δ.
Note thatxk,i and x′k,i are in space ℝd. According to the definition of 1-norm, we have
(20)∑l=1dxk,il−x′k,il=xk,i−x′k,i1≤Δ,where xk,il and x′k,il are the lth component of xk,i and x′k,i, respectively.
Consider an output vectorsyk,i. Then, we follow from the property of Laplace distribution, we get
(21)ℙMDk∈S=∏l=1d12ςexp−∣yk,il−xk,il∣ς,ℙMDk′∈S=∏l=1d12ςexp−∣yk,il−x′k,il∣ς.
Then,(22)ℙMDk∈SℙMDk′∈S=∏l=1dexp−yk,il−xk,il−yk,il−x′k,ilς≤∏l=1dexpxk,il−x′k,ilς=expxk,i−x′k,i1ς≤expΔς,where the first inequality comes from the triangle inequality, and the last inequality follows from (19).
Therefore, we knowε=Δ/ς, we can obtain
(23)ℙMD∈SℙMD′∈S≤expε.


### 6.2. Convergence Rate Analysis

In order to obtain the result of convergence rate, we first give some lemmas.Lemma 7.
Wk is a symmetric doubly stochastic matrix.Proof.
From the definition of Equation (11), we can obtain that
(24)wk,ij∈0,1,∀i,j,(1)
wk,ij∈0,1, for all i,j;(2)
wk,ij=wk,ji, for all i,j;(3)
∑jwk,ij=1, for all i.
Therefore,Wk is a symmetric doubly stochastic matrix.Lemma 8.
DefineΦK−1,0=I, where I is the identity matrix. Assume that there exists aρ∈0,1 such that
(25)maxλ2EWsΤWs,λnEWsΤWs≤ρ,∀s.
Then(26)E1nn−ΦK−1,0ei2≤n−1nρK,∀K≥0.Proof.
Letys=1n/n−Φs−1,0ei. We prove this lemma by induction. For s=0, ∥y0∥2=∥1n/n−ei∥2=n−12/n2+∑i=1n−11/n2=n2−2n+1+n−1/n2=n−1/n.
We assume thats=K hold, i.e., EyK2≤n−1/nρK. Then, for s=K+1, note that yK+1=WKyK, then we have
(27)EyK+12=EWKyK2=EWKyK,WKyK=EyK,WKΤWKyK=EyK,EWKΤWKyK.
According to Lemma7, EWKΤWK is symmetric and doubly stochastic. Then, 1n is an eigenvector of EWKΤWK, and 1 is the eigenvalue. According to the spectral theorem of Hermitian matrices, we can construct a basis of ℝn composed by the eigenvectors of EWKΤWK starting from 1n. From Equation (25), the magnitude of all other eigenvectors’ associated eigenvalues should be smaller or equal to ρ. Note that yK is orthogonal to 1n, then we can find
(28)EyK+12≤ρEyK2.
By induction, we complete the proof.In Lemma9, we give the bound of the sensitivity of our proposed algorithm.Lemma 9.
Under assumption 4, the sensitivity of the algorithm can be bounded as(29)Δ≤2Gdγ,where G=maxi∈VGi and d is the dimensionality of vectors.Proof.
Assume thatDk and D′k are any two adjacent datasets at iterate k. Assume that xk,i and x′k,i be the executions for MDk and MD′k, respectively. Then, from our proposed algorithm, we have
(30)MDk−MDk′1=xk+1,i−x′k+1,i1=γ∇Fixk,i;ξk,i−∇Fixk,i;ξ′k,i1≤dγ∇Fixk,i;ξk,i−∇Fixk,i;ξk,i′≤dγ∇Fixk,i;ξk,i∥+∥∇Fixk,i;ξk,i′,where the first inequality comes from the norm inequality and the last inequality is from the triangle inequality. From assumption 4, we have
(31)∇Fixk,i;ξk,i≤Gi≤G.
Since we can choose the pair of adjacent datasetsDk, D′k arbitrarily, and we can obtain
(32)Δ≤2Gdγ.
The lemma is obtained.From Lemma9, we know that the learning rate γ, the dimensionality of vectors d, the maximal bound of subgradient G, and the privacy level ε have an effect on the magnitude of the added random noise. Based on Lemma 9, we next provide the bound of the noise.Lemma 10.
We give the following inequalities:(33)Eηs1nn2≤8G2dγ2ε2andEηs2≤8nG2dγ2ε2.Proof.
According to the property of the Laplace mechanismE∥ηs,i∥2≤2ς2 and ς=Δ/ε, we obtain a bound on ηs in the following:
(34)Eηs1nn2≤E∑i=1nηs,in2≤1n∑i=1nE∥ηs,i∥2≤1n·n·2ς2=2ς2≤1922Gdγε2=8G2dγ2ε2.
And we can get a bound onηs.
(35)Eηs2≤EηsF2≤∑i=1nEηs,i2≤n·2ς2≤2n2Gdγε2=8nG2dγ2ε2.Lemma 11 (see [1]).
Under assumption 1, the following inequality holds:(36)E∥∂fXs∥2≤∑h=1n3EL2∑i′=1nxs,i′n−xs,h2+3nζ2+3E∇fXs1nn1nΤ2,∀s∈K.The proof of this lemma can be found in the full version of [1]. And we define Disk,i as the squared distance of the local optimization variable on node i from the averaged local optimization variable on all nodes at iterate k, i.e., Disk,i=E∑i′=1nxk,i′/n−xk,i2. In the following, we will present the bound of Disk,i.Lemma 12.
Under the definition ofDisk,i, we can get:
(37)Disk,i≤48n−1G2dγ2ε21−ρ2+2γ22n−1σ21−ρ+18n−1ζ21−ρ2+6n−1n∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1+6n−1n∑s=0k−1∑h=1nEL2Diss,h2ρk−s−11−ρ+ρk−s−1.Proof.
According to the update method ofXk, we split Disk,i into two terms:
(38)Disk,i=E∑i′=1nxk,i′n−xk,i2=EXk1nn−Xkei2=EXk−1+ηk−1Wk−11n−γ∂FXk−1;ξk−11nn−Xk−1+ηk−1Wk−1ei−γ∂FXk−1;ξk−1ei2=EXk−11n+ηk−11n−γ∂FXk−1;ξk−11nn−Xk−1Wk−1ei+ηk−1Wk−1ei−γ∂FXk−1;ξk−1ei2=EX01nn+∑s=0k−1ηs1nn−∑s=0k−1γ∂FXs;ξs1nn−X0Φk−1,0ei+∑s=0k−1ηsΦk−1,sei−γ∂FXk−1,ξk−1ei−∑s=0k−2γ∂FXs;ξsΦk−1,s+1ei2=18EX01nn−Φk−1,0ei+∑s=0k−1ηs1nn−Φk−1,sei−γ∑s=0k−1∂FXs;ξs1nn−Φk−1,s+1ei2=E∑s=0k−1ηs1nn−Φk−1,sei−γ∑s=0k−1∂FXs;ξs1nn−Φk−1,s+1ei2=2E∑s=0k−1ηs1nn−Φk−1,sei2⏟A1+2γ2E∑s=0k−1∂FXs;ξs1nn−Φk−1,s+1ei2⏟A2,where the seventh equation comes from x0,i=x0=0 for ∀i.
Firstly, we splitA1 into two terms,
(39)A1=E∑s=0k−1ηs1nn−Φk−1,sei2=∑s=0k−1Eηs1nn−Φk−1,sei2⏟=A3+∑s≠s′k−1Eηs1nn−Φk−1,sei,ηs′1nn−Φk−1,s′ei⏟=A4.
To boundA1, we first boundA3 and A4:
(40)A3=∑s=0k−1Eηs1nn−Φk−1,sei2≤∑s=0k−1Eηs21nn−Φk−1,sei2≤33∑s=0k−18nG2dγ2ε2·n−1nρk−s≤8n−1G2dγ2ε211−ρ.
Moreover,A4 can be bound as follows:
(41)A4=∑s≠s′k−1Eηs1nn−Φk−1,sei,ηs′1nn−Φk−1,s′ei≤∑s≠s′k−1Eηs1nn−Φk−1,seiηs′1nn−Φk−1,s′ei≤∑s≠s′k−1Eηs1nn−Φk−1,seiηs′1nn−Φk−1,s′ei≤∑s≠s′k−1Eηs221nn−Φk−1,sei+∑s≠s′k−1ηs′221nn−Φk−1,s′ei≤26∑s≠s′k−1Eηs22+ηs′22n−1nρk−s+s′2=n−1n∑s≠s′k−1Eηs2ρk−s+s′/2≤332n−1n·8nG2dγ2ε2∑s=0k−1∑s′=s+1k−1ρk−s+s′/2≤2n−1n·8nG2dγ2ε2∑s=0k−1ρk−s+1/21−ρk+1/21−ρ≤16n−1G2dγ2ε21−ρk−1/2ρ−ρk+1/21−ρ2≤16n−1G2dγ2ε211−ρ2.
Then, pluggingA3 and A4 into A1,
(42)A1=8n−1G2dγ2ε211−ρ+16n−1G2dγ2ε211−ρ2=8n−1G2dγ2ε211−ρ+21−ρ2≤24n−1G2dγ2ε21−ρ2.where the last inequality comes from the fact that 1/1−ρ≤1/1−ρ2.
Moreover, we splitA2 into two terms:
(43)A2=E∑s=0k−1∂FXs;ξs1nn−Φk−1,s+1ei2≤2E∑s=0k−1∂FXs;ξs−∂fXs1nn−Φk−1,s+1ei2⏟=A5+2E∑s=0k−1∂fXs1nn−Φk−1,s+1ei2⏟=A6.
We give an upper boundA5 as follows:
(44)A5=E∑s=0k−1∂FXs;ξs−∂fXs1nn−Φk−1,s+1ei2=∑s=0k−1E∂FXs;ξs−∂fXs1nn−Φk−1,s+1ei2≤∑s=0k−1E∂FXs;ξs−∂fXs21nn−Φk−1,s+1ei2≤∑s=0k−1E∂FXs;ξs−∂fXsF21nn−Φk−1,s+1ei2≤nσ2∑s=0k−1n−1nρk−s−1=n−1σ21−ρ,where the last second inequality comes from Lemma 8 and assumption 3.
ForA6, we will give the following upper bound:
(45)A6=E∑s=0k−1∂fXs1nn−Φk−1,s+1ei2=∑s=0k−1E∂fXs1nn−Φk−1,s+1ei2⏟=A7+∑s≠s′k−1E∂fXs1nn−Φk−1,s+1ei,∂fXs′1nn−Φk−1,s+1ei⏟=A8.
To boundA6, we first bound A7 and A8, for A7:
(46)A7=∑s=0k−1E∂fXs1nn−Φk−1,s+1ei2≤∑s=0k−1E∂fXs21nn−Φk−1,s+1ei2≤3∑s=0k−1∑h=1nEL2Diss,h1nn−Φk−1,s+1ei2+3nζ2∑s=0k−1n−1nρk−s−1+3∑s=0k−1E∇fXs1nn1nΤ21nn−Φk−1,s+1ei2≤3n−1n∑s=0k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s−1+3n−1ζ21−ρ,where the last inequality comes from Lemmas 8 and 11.
Then, we boundA8 as follows:
(47)A8=∑s≠s′k−1E∂fXs1nn−Φk−1,s+1ei,∂fXs′1nn−Φk−1,s+1ei≤∑s≠s′k−1E∂fXs1nn−Φk−1,s+1ei∂fXs′1nn−Φk−1,s+1ei≤∑s≠s′k−1E∂fXs1nn−Φk−1,s+1ei∂fXs′1nn−Φk−1,s+1ei≤∑s≠s′k−1E∂fXs221nn−Φk−1,s+1ei+∑s≠s′k−1∂fXs′221nn−Φk−1,s+1ei≤26∑s≠s′k−1E∂fXs22+∂fXs′22n−1nρk−s+s′/2−1=n−1n∑s≠s′k−1E∂fXs2ρk−s+s′/2−1≤363n−1n∑s≠s′k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s+s′/2−1⏟=A9+∑s≠s′k−13n−1ζ2ρk−s+s′/2−1⏟=A10,where A10 can be bounded by ζ and ρ:
(48)A10=6n−1ζ2∑s>s′k−1ρk−s+s′/2−1=6n−1ζ2∑s=0k−1∑s′=s+1k−1ρk−s+s′/2−1=6n−1ζ2ρk/2−1ρk/2−ρρ−12ρ+1≤6n−1ζ211−ρ2,and we give a bound of A9:
(49)A9=3n−1n∑s≠s′k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s+s′/2−1=6n−1n∑s=0k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2∑s′=s+1k−1ρ2k−s+s′−2≤6n−1n∑s=0k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s−11−ρ.
Then, we plugA9, A10 into A8, plug A8, A7 into A6. We can yield the upper bound for A6.
(50)A6≤6n−1n∑s=0k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s−11−ρ+6n−1ζ21−ρ2+3n−1n∑s=0k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s−1+3n−1ζ21−ρ≤3n−1n∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1+3n−1n∑s=0k−1∑h=1nEL2Diss,h2ρk−s−11−ρ+ρk−s−1+9n−1ζ21−ρ2.
Then, we plugA5 and A6 into A2 yielding the upper bound of A2.
(51)A2≤2n−1σ21−ρ+6n−1n∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1+6n−1n∑s=0k−1∑h=1nEL2Diss,h2ρk−s−11−ρ+ρk−s−1+18n−1ζ21−ρ2.
Finally, we can describeDisk,i as follows:
(52)Disk,i=2A1+2γ2A2≤48n−1G2dγ2ε21−ρ2+2γ22n−1σ21−ρ+18n−1ζ21−ρ2+6n−1n∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1+6n−1n∑s=0k−1∑h=1nEL2Diss,h2ρk−s−11−ρ+ρk−s−1.
The lemma is obtained.Based on these lemmas above, we prove Theorem5 subsequently.Proof (Proof of Theorem5).
We start fromfXk+11n/n:
(53)EfXk+11nn=EfXk+ηkWk1nn−γ∂FXk;ξk1nn=EfXkWk1nn+ηkWk1nn−γ∂FXk;ξk1nn=Lemma7EfXk1nn+ηk1nn−γ∂FXk;ξk1nn≤EfXk1nn+E∇fXk1nn,ηk1nn−γ∂fXk1nn+L2Eηk1nn−γ∂FXk;ξk1nn2≤EfXk1nn+E∇fXk1nn,ηk1nn−E∇fXk1nn,γ∂fXk1nn+LE∑i=1nηk,in2+γ2LE∑i=1n∇Fixk,i;ξk,in2,where the last step comes from ∥a−b∥2≤2∥a∥2+2∥b∥2.
Then, we split the second term according to2a,b≤∥a∥2+∥b∥2,
(54)E∇fXk1nn,ηk1nn≤12E∇fXk1nn2+12Eηk1nn2=12E∇fXk1nn2+12E∑i=1nηk,in2.
We split the last term of (53) into two terms because of Eξk,i∇Fixk,i;ξk,i=∇fixk,i,
(55)E∑i=1n∇Fixk,i;ξk,in2=E∑i=1n∇Fixk,i;ξk,i−∑i=1n∇fixk,in2+E∑i=1n∇fixk,in2.
According to (54) and (55), (53) can be expressed as:
(56)EfXk+11nn≤EfXk1nn−γE∇fXk1nn,∂fXk1nn+12E∇fXk1nn2+1+2L2E∑i=1nηk,in2+γ2LE∑i=1n∇Fixk,i;ξk,i−∑i=1n∇fixk,in2+γ2LE∑i=1n∇fixk,in2.
We can bound the second last term usingσ:
(57)γ2LE∑i=1n∇Fixk,i;ξk,i−∑i=1n∇fixk,in2=γ2Ln2∑i=1nE∥∇Fixk,i;ξk,i−∇fixk,i∥2+2γ2Ln2∑i=1n∑i′=i+1nE∇Fixk,i;ξk,i−∇fixk,i,∇Fi′xk,i;ξk,i′−∇fi′xk,i′=γ2Ln2∑i=1nE∥∇Fixk,i;ξk,i−∇fixk,i∥2+2γ2Ln2∑i=1n∑i′=i+1nE∇Fixk,i;ξk,i−∇fixk,i,Eξk,i′∇Fi′xk,i;ξk,i′−∇fi′xk,i′=γ2Ln2∑i=1nE∥∇Fixk,i;ξk,i−∇fixk,i∥2≤γ2Lnσ2,where the last step is true because of assumption 3.
Then, it follows from (56):
(58)EfXk+11nn≤EfXk1nn−γE∇fXk1nn,∂fXk1nn+12E∇fXk1nn2+1+2L2E∑i=1nηk,in2+γ2Lnσ2+γ2LE∑i=1n∇fixk,in2≤33EfXk1nn−γ−2γ2L2E∂fXk1nn2−γ−12E∇fXk1nn2+41+2LG2dγ2ε2+γ2Lnσ2+γ2E∇fXk1nn−∂fXk1nn2⏟=X,where the last step comes from 2a,b=∥a∥2+∥b∥2−∥a−b∥2.
We then bound the equationX:
(59)X=E∇fXk1nn−∂fXk1nn2=E∑i=1n∇fi∑i′=1nxk,i′/nn−∑i=1n∇fixk,in2≤1n∑i=1nE∇fi∑i′=1nxk,i′n−∇fixk,i2≤Assumption1L2n∑i=1nE∑i′=1nxk,i′n−xk,i2⏟=Disk,i,where the first inequality comes from ∥∑i=1nai∥2≤n∑i=1n∥ai∥2.
According to Equation (37) in Lemma 12, we have the bound of Disk,i. Then, we will bound its average Mk on all nodes as follows:
(60)EMk=E∑i=1nDisk,in=48n−1G2dγ2ε21−ρ2+4γ2n−1σ21−ρ+36γ2n−1ζ21−ρ2+12n−1γ2L2∑s=0k−1EMk2ρk−s−11−ρ+ρk−s−1+12n−1nγ2∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1.
Summing it fromk=0 to K−1, we can get the following result:
(61)∑k=0K−1EMk≤48n−1G2dγ2Kε21−ρ2+4γ2n−1σ2K1−ρ+36γ2n−1ζ2K1−ρ2+12n−1γ2L2∑k=0K−1∑s=0k−1EMk2ρk−s−11−ρ+ρk−s−1+12n−1nγ2∑k=0K−1∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1≤48n−1G2dγ2Kε21−ρ2+4γ2n−1σ2K1−ρ+36γ2n−1ζ2K1−ρ2+12n−1γ2L2∑k=0K−1EMk11−ρ+21−ρ2+12n−1nγ2∑k=0K−1E∇fXs1nn1nΤ211−ρ+21−ρ2≤48n−1G2dγ2Kε21−ρ2+4γ2n−1σ2K1−ρ+36γ2n−1ζ2K1−ρ2+36n−1γ2L21−ρ2∑k=0K−1EMk+36γ2n−11−ρ2n∑k=0K−1E∇fXk1nn1nΤ2.
We then can get the bound of the summation ofEMk’s from k=0 to K−1:
(62)1−36γ2n−1L21−ρ2∑k=0K−1EMk≤48n−1G2dγ2Kε21−ρ2+4γ2n−1σ2K1−ρ+36γ2n−1ζ2K1−ρ2+36γ2n−11−ρ2n∑k=0K−1E∇fXk1nn1nΤ2.
Rearranging the term, it can be obtained that(63)∑k=0K−1EMk≤48n−1G2dγ2Kε21−ρ21−36γ2n−1L2/1−ρ2+4γ2n−1σ2K1−ρ1−36γ2n−1L2/1−ρ2+36γ2n−1ζ2K1−ρ21−36γ2n−1L2/1−ρ2+36γ2n−11−ρ2n1−36γ2n−1L2/1−ρ2∑k=0K−1E∇fXk1nn1nΤ2.
Plugging the bound ofMk into X:
(64)X≤L2n∑i=1nEDisk,i=L2EMk.
Then, we bound theEfXk+11n/n by the above bound,
(65)EfXk+11nn≤EfXk1nn−γ−2γ2L2E∂fXk1nn2−γ−12E∇fXk1nn2+41+2LG2dγ2ε2+γ2Lσ2n+γ2X≤EfXk1nn−γ−2γ2L2E∂fXk1nn2−γ−12E∇fXk1nn2+41+2LG2dγ2ε2+γ2Lσ2n+γ2L2EMk.
Summing fromk=0 to k=K−1:
(66)γ−2γ2L2∑k=0K−1E∂fXk1nn2+γ−12∑k=0K−1E∇fXk1nn2≤f0−f∗+41+2LG2dγ2Kε2+γ2KLσ2n+γ2L2∑k=0K−1EMk≤61f0−f∗+41+2LG2dγ2Kε2+γ2KLσ2n+γ2L248n−1G2dγ2Kε21−ρ21−36γ2n−1L2/1−ρ2+γ2L24γ2n−1σ2K1−ρ1−36γ2n−1L2/1−ρ2+γ2L236γ2n−1ζ2K1−ρ21−36γ2n−1L2/1−ρ2+γ2L236γ2n−11−ρ2n1−36γ2n−1L2/1−ρ2∑k=0K−1E∇fXk1nn1nΤ2=f0−f∗+41+2LG2dγ2Kε2+γ2KLσ2n+24n−1L2G2γ3Kε21−ρ21−36γ2n−1L2/1−ρ2+2γ3L2n−1σ21−ρ1−36γ2n−1L2/1−ρ2K+18γ3L2n−1ζ21−ρ21−36γ2n−1L2/1−ρ2K+18γ3L2n−11−ρ21−36γ2n−1L2/1−ρ2∑k=0K−1E∇fXk1nn2.
Rearranging the terms, we get the following result:(67)1−γL/2∑k=0K−1E∂fXk1n/n2+1/2−18γ2n−1L2/1−ρ21−36γ2n−1L2/1−ρ2∑k=0K−1E∇fXk1n/n2K≤f0−f∗γK+41+2LG2dγε2+γLnσ2+24n−1L2G2γ2ε21−ρ21−36γ2n−1L2/1−ρ2+2γ2L2n−1σ21−ρ1−36γ2n−1L2/1−ρ2+18γ2n−1L2ζ21−ρ21−36γ2n−1L2/1−ρ2.
This completes the proof.Proof (Proof of Corollary6).
Substitutingγ=1/2L+σK/n into the result of Theorem 5 and removing the first term of the RHS on the LHS, we can obtain that
(68)B1∑k=0K−1E∇fXk1n/n2K≤2L+σK/nf0−f∗K+41+2LG2d2L+σK/nε2+Lσ22nL+σKn+2n−1L22L+σK/n2B212G2ε21−ρ2+σ21−ρ+9ζ21−ρ2≤2Lf0−f∗K+f0−f∗σKn+41+2LG2dσK/nε2+Lσ2σKn+2n−1L2σK/n2B212G2ε21−ρ2+σ21−ρ+9ζ21−ρ2.
LetG/ε≤f0−f∗+Lσ/41+2Ldn, and we show B1 and B2 are approximately constants when (16) is satisfied.
(69)B1=12−18γ2n−1L21−ρ2B2,B2=1−36γ2n−1L21−ρ2.
Note that(70)γ2≤1−ρ272n−1L2⇒B2≥12,γ2≤1−ρ2144n−1L2⇒B1≥14.
Sinceγ2≤n/σ2K, as long as we have
(71)nσ2K≤1−ρ2144n−1L2,
B2≥1/2 and B1≥1/4 will be satisfied. Then, we can obtain K≥144nn−1L2/σ21−ρ2.
LetK≥16n3n−12L4/σ6f0−f∗+L212G2/ε21−ρ2+σ2/1−ρ+9ζ2/1−ρ22, then
(72)∑k=0K−1E∇fXk1n/n2K≤8Lf0−f∗K+12f0−f∗+LσKn.


## 6.1. Privacy Analysis

Proof (Proof of Theorem4).
From the definition of sensitivity, we obtain(19)xk,i−xk,i′1≤Δ.
Note thatxk,i and x′k,i are in space ℝd. According to the definition of 1-norm, we have
(20)∑l=1dxk,il−x′k,il=xk,i−x′k,i1≤Δ,where xk,il and x′k,il are the lth component of xk,i and x′k,i, respectively.
Consider an output vectorsyk,i. Then, we follow from the property of Laplace distribution, we get
(21)ℙMDk∈S=∏l=1d12ςexp−∣yk,il−xk,il∣ς,ℙMDk′∈S=∏l=1d12ςexp−∣yk,il−x′k,il∣ς.
Then,(22)ℙMDk∈SℙMDk′∈S=∏l=1dexp−yk,il−xk,il−yk,il−x′k,ilς≤∏l=1dexpxk,il−x′k,ilς=expxk,i−x′k,i1ς≤expΔς,where the first inequality comes from the triangle inequality, and the last inequality follows from (19).
Therefore, we knowε=Δ/ς, we can obtain
(23)ℙMD∈SℙMD′∈S≤expε.


## 6.2. Convergence Rate Analysis

In order to obtain the result of convergence rate, we first give some lemmas.Lemma 7.
Wk is a symmetric doubly stochastic matrix.Proof.
From the definition of Equation (11), we can obtain that
(24)wk,ij∈0,1,∀i,j,(1)
wk,ij∈0,1, for all i,j;(2)
wk,ij=wk,ji, for all i,j;(3)
∑jwk,ij=1, for all i.
Therefore,Wk is a symmetric doubly stochastic matrix.Lemma 8.
DefineΦK−1,0=I, where I is the identity matrix. Assume that there exists aρ∈0,1 such that
(25)maxλ2EWsΤWs,λnEWsΤWs≤ρ,∀s.
Then(26)E1nn−ΦK−1,0ei2≤n−1nρK,∀K≥0.Proof.
Letys=1n/n−Φs−1,0ei. We prove this lemma by induction. For s=0, ∥y0∥2=∥1n/n−ei∥2=n−12/n2+∑i=1n−11/n2=n2−2n+1+n−1/n2=n−1/n.
We assume thats=K hold, i.e., EyK2≤n−1/nρK. Then, for s=K+1, note that yK+1=WKyK, then we have
(27)EyK+12=EWKyK2=EWKyK,WKyK=EyK,WKΤWKyK=EyK,EWKΤWKyK.
According to Lemma7, EWKΤWK is symmetric and doubly stochastic. Then, 1n is an eigenvector of EWKΤWK, and 1 is the eigenvalue. According to the spectral theorem of Hermitian matrices, we can construct a basis of ℝn composed by the eigenvectors of EWKΤWK starting from 1n. From Equation (25), the magnitude of all other eigenvectors’ associated eigenvalues should be smaller or equal to ρ. Note that yK is orthogonal to 1n, then we can find
(28)EyK+12≤ρEyK2.
By induction, we complete the proof.In Lemma9, we give the bound of the sensitivity of our proposed algorithm.Lemma 9.
Under assumption 4, the sensitivity of the algorithm can be bounded as(29)Δ≤2Gdγ,where G=maxi∈VGi and d is the dimensionality of vectors.Proof.
Assume thatDk and D′k are any two adjacent datasets at iterate k. Assume that xk,i and x′k,i be the executions for MDk and MD′k, respectively. Then, from our proposed algorithm, we have
(30)MDk−MDk′1=xk+1,i−x′k+1,i1=γ∇Fixk,i;ξk,i−∇Fixk,i;ξ′k,i1≤dγ∇Fixk,i;ξk,i−∇Fixk,i;ξk,i′≤dγ∇Fixk,i;ξk,i∥+∥∇Fixk,i;ξk,i′,where the first inequality comes from the norm inequality and the last inequality is from the triangle inequality. From assumption 4, we have
(31)∇Fixk,i;ξk,i≤Gi≤G.
Since we can choose the pair of adjacent datasetsDk, D′k arbitrarily, and we can obtain
(32)Δ≤2Gdγ.
The lemma is obtained.From Lemma9, we know that the learning rate γ, the dimensionality of vectors d, the maximal bound of subgradient G, and the privacy level ε have an effect on the magnitude of the added random noise. Based on Lemma 9, we next provide the bound of the noise.Lemma 10.
We give the following inequalities:(33)Eηs1nn2≤8G2dγ2ε2andEηs2≤8nG2dγ2ε2.Proof.
According to the property of the Laplace mechanismE∥ηs,i∥2≤2ς2 and ς=Δ/ε, we obtain a bound on ηs in the following:
(34)Eηs1nn2≤E∑i=1nηs,in2≤1n∑i=1nE∥ηs,i∥2≤1n·n·2ς2=2ς2≤1922Gdγε2=8G2dγ2ε2.
And we can get a bound onηs.
(35)Eηs2≤EηsF2≤∑i=1nEηs,i2≤n·2ς2≤2n2Gdγε2=8nG2dγ2ε2.Lemma 11 (see [1]).
Under assumption 1, the following inequality holds:(36)E∥∂fXs∥2≤∑h=1n3EL2∑i′=1nxs,i′n−xs,h2+3nζ2+3E∇fXs1nn1nΤ2,∀s∈K.The proof of this lemma can be found in the full version of [1]. And we define Disk,i as the squared distance of the local optimization variable on node i from the averaged local optimization variable on all nodes at iterate k, i.e., Disk,i=E∑i′=1nxk,i′/n−xk,i2. In the following, we will present the bound of Disk,i.Lemma 12.
Under the definition ofDisk,i, we can get:
(37)Disk,i≤48n−1G2dγ2ε21−ρ2+2γ22n−1σ21−ρ+18n−1ζ21−ρ2+6n−1n∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1+6n−1n∑s=0k−1∑h=1nEL2Diss,h2ρk−s−11−ρ+ρk−s−1.Proof.
According to the update method ofXk, we split Disk,i into two terms:
(38)Disk,i=E∑i′=1nxk,i′n−xk,i2=EXk1nn−Xkei2=EXk−1+ηk−1Wk−11n−γ∂FXk−1;ξk−11nn−Xk−1+ηk−1Wk−1ei−γ∂FXk−1;ξk−1ei2=EXk−11n+ηk−11n−γ∂FXk−1;ξk−11nn−Xk−1Wk−1ei+ηk−1Wk−1ei−γ∂FXk−1;ξk−1ei2=EX01nn+∑s=0k−1ηs1nn−∑s=0k−1γ∂FXs;ξs1nn−X0Φk−1,0ei+∑s=0k−1ηsΦk−1,sei−γ∂FXk−1,ξk−1ei−∑s=0k−2γ∂FXs;ξsΦk−1,s+1ei2=18EX01nn−Φk−1,0ei+∑s=0k−1ηs1nn−Φk−1,sei−γ∑s=0k−1∂FXs;ξs1nn−Φk−1,s+1ei2=E∑s=0k−1ηs1nn−Φk−1,sei−γ∑s=0k−1∂FXs;ξs1nn−Φk−1,s+1ei2=2E∑s=0k−1ηs1nn−Φk−1,sei2⏟A1+2γ2E∑s=0k−1∂FXs;ξs1nn−Φk−1,s+1ei2⏟A2,where the seventh equation comes from x0,i=x0=0 for ∀i.
Firstly, we splitA1 into two terms,
(39)A1=E∑s=0k−1ηs1nn−Φk−1,sei2=∑s=0k−1Eηs1nn−Φk−1,sei2⏟=A3+∑s≠s′k−1Eηs1nn−Φk−1,sei,ηs′1nn−Φk−1,s′ei⏟=A4.
To boundA1, we first boundA3 and A4:
(40)A3=∑s=0k−1Eηs1nn−Φk−1,sei2≤∑s=0k−1Eηs21nn−Φk−1,sei2≤33∑s=0k−18nG2dγ2ε2·n−1nρk−s≤8n−1G2dγ2ε211−ρ.
Moreover,A4 can be bound as follows:
(41)A4=∑s≠s′k−1Eηs1nn−Φk−1,sei,ηs′1nn−Φk−1,s′ei≤∑s≠s′k−1Eηs1nn−Φk−1,seiηs′1nn−Φk−1,s′ei≤∑s≠s′k−1Eηs1nn−Φk−1,seiηs′1nn−Φk−1,s′ei≤∑s≠s′k−1Eηs221nn−Φk−1,sei+∑s≠s′k−1ηs′221nn−Φk−1,s′ei≤26∑s≠s′k−1Eηs22+ηs′22n−1nρk−s+s′2=n−1n∑s≠s′k−1Eηs2ρk−s+s′/2≤332n−1n·8nG2dγ2ε2∑s=0k−1∑s′=s+1k−1ρk−s+s′/2≤2n−1n·8nG2dγ2ε2∑s=0k−1ρk−s+1/21−ρk+1/21−ρ≤16n−1G2dγ2ε21−ρk−1/2ρ−ρk+1/21−ρ2≤16n−1G2dγ2ε211−ρ2.
Then, pluggingA3 and A4 into A1,
(42)A1=8n−1G2dγ2ε211−ρ+16n−1G2dγ2ε211−ρ2=8n−1G2dγ2ε211−ρ+21−ρ2≤24n−1G2dγ2ε21−ρ2.where the last inequality comes from the fact that 1/1−ρ≤1/1−ρ2.
Moreover, we splitA2 into two terms:
(43)A2=E∑s=0k−1∂FXs;ξs1nn−Φk−1,s+1ei2≤2E∑s=0k−1∂FXs;ξs−∂fXs1nn−Φk−1,s+1ei2⏟=A5+2E∑s=0k−1∂fXs1nn−Φk−1,s+1ei2⏟=A6.
We give an upper boundA5 as follows:
(44)A5=E∑s=0k−1∂FXs;ξs−∂fXs1nn−Φk−1,s+1ei2=∑s=0k−1E∂FXs;ξs−∂fXs1nn−Φk−1,s+1ei2≤∑s=0k−1E∂FXs;ξs−∂fXs21nn−Φk−1,s+1ei2≤∑s=0k−1E∂FXs;ξs−∂fXsF21nn−Φk−1,s+1ei2≤nσ2∑s=0k−1n−1nρk−s−1=n−1σ21−ρ,where the last second inequality comes from Lemma 8 and assumption 3.
ForA6, we will give the following upper bound:
(45)A6=E∑s=0k−1∂fXs1nn−Φk−1,s+1ei2=∑s=0k−1E∂fXs1nn−Φk−1,s+1ei2⏟=A7+∑s≠s′k−1E∂fXs1nn−Φk−1,s+1ei,∂fXs′1nn−Φk−1,s+1ei⏟=A8.
To boundA6, we first bound A7 and A8, for A7:
(46)A7=∑s=0k−1E∂fXs1nn−Φk−1,s+1ei2≤∑s=0k−1E∂fXs21nn−Φk−1,s+1ei2≤3∑s=0k−1∑h=1nEL2Diss,h1nn−Φk−1,s+1ei2+3nζ2∑s=0k−1n−1nρk−s−1+3∑s=0k−1E∇fXs1nn1nΤ21nn−Φk−1,s+1ei2≤3n−1n∑s=0k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s−1+3n−1ζ21−ρ,where the last inequality comes from Lemmas 8 and 11.
Then, we boundA8 as follows:
(47)A8=∑s≠s′k−1E∂fXs1nn−Φk−1,s+1ei,∂fXs′1nn−Φk−1,s+1ei≤∑s≠s′k−1E∂fXs1nn−Φk−1,s+1ei∂fXs′1nn−Φk−1,s+1ei≤∑s≠s′k−1E∂fXs1nn−Φk−1,s+1ei∂fXs′1nn−Φk−1,s+1ei≤∑s≠s′k−1E∂fXs221nn−Φk−1,s+1ei+∑s≠s′k−1∂fXs′221nn−Φk−1,s+1ei≤26∑s≠s′k−1E∂fXs22+∂fXs′22n−1nρk−s+s′/2−1=n−1n∑s≠s′k−1E∂fXs2ρk−s+s′/2−1≤363n−1n∑s≠s′k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s+s′/2−1⏟=A9+∑s≠s′k−13n−1ζ2ρk−s+s′/2−1⏟=A10,where A10 can be bounded by ζ and ρ:
(48)A10=6n−1ζ2∑s>s′k−1ρk−s+s′/2−1=6n−1ζ2∑s=0k−1∑s′=s+1k−1ρk−s+s′/2−1=6n−1ζ2ρk/2−1ρk/2−ρρ−12ρ+1≤6n−1ζ211−ρ2,and we give a bound of A9:
(49)A9=3n−1n∑s≠s′k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s+s′/2−1=6n−1n∑s=0k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2∑s′=s+1k−1ρ2k−s+s′−2≤6n−1n∑s=0k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s−11−ρ.
Then, we plugA9, A10 into A8, plug A8, A7 into A6. We can yield the upper bound for A6.
(50)A6≤6n−1n∑s=0k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s−11−ρ+6n−1ζ21−ρ2+3n−1n∑s=0k−1∑h=1nEL2Diss,h+E∇fXs1nn1nΤ2ρk−s−1+3n−1ζ21−ρ≤3n−1n∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1+3n−1n∑s=0k−1∑h=1nEL2Diss,h2ρk−s−11−ρ+ρk−s−1+9n−1ζ21−ρ2.
Then, we plugA5 and A6 into A2 yielding the upper bound of A2.
(51)A2≤2n−1σ21−ρ+6n−1n∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1+6n−1n∑s=0k−1∑h=1nEL2Diss,h2ρk−s−11−ρ+ρk−s−1+18n−1ζ21−ρ2.
Finally, we can describeDisk,i as follows:
(52)Disk,i=2A1+2γ2A2≤48n−1G2dγ2ε21−ρ2+2γ22n−1σ21−ρ+18n−1ζ21−ρ2+6n−1n∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1+6n−1n∑s=0k−1∑h=1nEL2Diss,h2ρk−s−11−ρ+ρk−s−1.
The lemma is obtained.Based on these lemmas above, we prove Theorem5 subsequently.Proof (Proof of Theorem5).
We start fromfXk+11n/n:
(53)EfXk+11nn=EfXk+ηkWk1nn−γ∂FXk;ξk1nn=EfXkWk1nn+ηkWk1nn−γ∂FXk;ξk1nn=Lemma7EfXk1nn+ηk1nn−γ∂FXk;ξk1nn≤EfXk1nn+E∇fXk1nn,ηk1nn−γ∂fXk1nn+L2Eηk1nn−γ∂FXk;ξk1nn2≤EfXk1nn+E∇fXk1nn,ηk1nn−E∇fXk1nn,γ∂fXk1nn+LE∑i=1nηk,in2+γ2LE∑i=1n∇Fixk,i;ξk,in2,where the last step comes from ∥a−b∥2≤2∥a∥2+2∥b∥2.
Then, we split the second term according to2a,b≤∥a∥2+∥b∥2,
(54)E∇fXk1nn,ηk1nn≤12E∇fXk1nn2+12Eηk1nn2=12E∇fXk1nn2+12E∑i=1nηk,in2.
We split the last term of (53) into two terms because of Eξk,i∇Fixk,i;ξk,i=∇fixk,i,
(55)E∑i=1n∇Fixk,i;ξk,in2=E∑i=1n∇Fixk,i;ξk,i−∑i=1n∇fixk,in2+E∑i=1n∇fixk,in2.
According to (54) and (55), (53) can be expressed as:
(56)EfXk+11nn≤EfXk1nn−γE∇fXk1nn,∂fXk1nn+12E∇fXk1nn2+1+2L2E∑i=1nηk,in2+γ2LE∑i=1n∇Fixk,i;ξk,i−∑i=1n∇fixk,in2+γ2LE∑i=1n∇fixk,in2.
We can bound the second last term usingσ:
(57)γ2LE∑i=1n∇Fixk,i;ξk,i−∑i=1n∇fixk,in2=γ2Ln2∑i=1nE∥∇Fixk,i;ξk,i−∇fixk,i∥2+2γ2Ln2∑i=1n∑i′=i+1nE∇Fixk,i;ξk,i−∇fixk,i,∇Fi′xk,i;ξk,i′−∇fi′xk,i′=γ2Ln2∑i=1nE∥∇Fixk,i;ξk,i−∇fixk,i∥2+2γ2Ln2∑i=1n∑i′=i+1nE∇Fixk,i;ξk,i−∇fixk,i,Eξk,i′∇Fi′xk,i;ξk,i′−∇fi′xk,i′=γ2Ln2∑i=1nE∥∇Fixk,i;ξk,i−∇fixk,i∥2≤γ2Lnσ2,where the last step is true because of assumption 3.
Then, it follows from (56):
(58)EfXk+11nn≤EfXk1nn−γE∇fXk1nn,∂fXk1nn+12E∇fXk1nn2+1+2L2E∑i=1nηk,in2+γ2Lnσ2+γ2LE∑i=1n∇fixk,in2≤33EfXk1nn−γ−2γ2L2E∂fXk1nn2−γ−12E∇fXk1nn2+41+2LG2dγ2ε2+γ2Lnσ2+γ2E∇fXk1nn−∂fXk1nn2⏟=X,where the last step comes from 2a,b=∥a∥2+∥b∥2−∥a−b∥2.
We then bound the equationX:
(59)X=E∇fXk1nn−∂fXk1nn2=E∑i=1n∇fi∑i′=1nxk,i′/nn−∑i=1n∇fixk,in2≤1n∑i=1nE∇fi∑i′=1nxk,i′n−∇fixk,i2≤Assumption1L2n∑i=1nE∑i′=1nxk,i′n−xk,i2⏟=Disk,i,where the first inequality comes from ∥∑i=1nai∥2≤n∑i=1n∥ai∥2.
According to Equation (37) in Lemma 12, we have the bound of Disk,i. Then, we will bound its average Mk on all nodes as follows:
(60)EMk=E∑i=1nDisk,in=48n−1G2dγ2ε21−ρ2+4γ2n−1σ21−ρ+36γ2n−1ζ21−ρ2+12n−1γ2L2∑s=0k−1EMk2ρk−s−11−ρ+ρk−s−1+12n−1nγ2∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1.
Summing it fromk=0 to K−1, we can get the following result:
(61)∑k=0K−1EMk≤48n−1G2dγ2Kε21−ρ2+4γ2n−1σ2K1−ρ+36γ2n−1ζ2K1−ρ2+12n−1γ2L2∑k=0K−1∑s=0k−1EMk2ρk−s−11−ρ+ρk−s−1+12n−1nγ2∑k=0K−1∑s=0k−1E∇fXs1nn1nΤ22ρk−s−11−ρ+ρk−s−1≤48n−1G2dγ2Kε21−ρ2+4γ2n−1σ2K1−ρ+36γ2n−1ζ2K1−ρ2+12n−1γ2L2∑k=0K−1EMk11−ρ+21−ρ2+12n−1nγ2∑k=0K−1E∇fXs1nn1nΤ211−ρ+21−ρ2≤48n−1G2dγ2Kε21−ρ2+4γ2n−1σ2K1−ρ+36γ2n−1ζ2K1−ρ2+36n−1γ2L21−ρ2∑k=0K−1EMk+36γ2n−11−ρ2n∑k=0K−1E∇fXk1nn1nΤ2.
We then can get the bound of the summation ofEMk’s from k=0 to K−1:
(62)1−36γ2n−1L21−ρ2∑k=0K−1EMk≤48n−1G2dγ2Kε21−ρ2+4γ2n−1σ2K1−ρ+36γ2n−1ζ2K1−ρ2+36γ2n−11−ρ2n∑k=0K−1E∇fXk1nn1nΤ2.
Rearranging the term, it can be obtained that(63)∑k=0K−1EMk≤48n−1G2dγ2Kε21−ρ21−36γ2n−1L2/1−ρ2+4γ2n−1σ2K1−ρ1−36γ2n−1L2/1−ρ2+36γ2n−1ζ2K1−ρ21−36γ2n−1L2/1−ρ2+36γ2n−11−ρ2n1−36γ2n−1L2/1−ρ2∑k=0K−1E∇fXk1nn1nΤ2.
Plugging the bound ofMk into X:
(64)X≤L2n∑i=1nEDisk,i=L2EMk.
Then, we bound theEfXk+11n/n by the above bound,
(65)EfXk+11nn≤EfXk1nn−γ−2γ2L2E∂fXk1nn2−γ−12E∇fXk1nn2+41+2LG2dγ2ε2+γ2Lσ2n+γ2X≤EfXk1nn−γ−2γ2L2E∂fXk1nn2−γ−12E∇fXk1nn2+41+2LG2dγ2ε2+γ2Lσ2n+γ2L2EMk.
Summing fromk=0 to k=K−1:
(66)γ−2γ2L2∑k=0K−1E∂fXk1nn2+γ−12∑k=0K−1E∇fXk1nn2≤f0−f∗+41+2LG2dγ2Kε2+γ2KLσ2n+γ2L2∑k=0K−1EMk≤61f0−f∗+41+2LG2dγ2Kε2+γ2KLσ2n+γ2L248n−1G2dγ2Kε21−ρ21−36γ2n−1L2/1−ρ2+γ2L24γ2n−1σ2K1−ρ1−36γ2n−1L2/1−ρ2+γ2L236γ2n−1ζ2K1−ρ21−36γ2n−1L2/1−ρ2+γ2L236γ2n−11−ρ2n1−36γ2n−1L2/1−ρ2∑k=0K−1E∇fXk1nn1nΤ2=f0−f∗+41+2LG2dγ2Kε2+γ2KLσ2n+24n−1L2G2γ3Kε21−ρ21−36γ2n−1L2/1−ρ2+2γ3L2n−1σ21−ρ1−36γ2n−1L2/1−ρ2K+18γ3L2n−1ζ21−ρ21−36γ2n−1L2/1−ρ2K+18γ3L2n−11−ρ21−36γ2n−1L2/1−ρ2∑k=0K−1E∇fXk1nn2.
Rearranging the terms, we get the following result:(67)1−γL/2∑k=0K−1E∂fXk1n/n2+1/2−18γ2n−1L2/1−ρ21−36γ2n−1L2/1−ρ2∑k=0K−1E∇fXk1n/n2K≤f0−f∗γK+41+2LG2dγε2+γLnσ2+24n−1L2G2γ2ε21−ρ21−36γ2n−1L2/1−ρ2+2γ2L2n−1σ21−ρ1−36γ2n−1L2/1−ρ2+18γ2n−1L2ζ21−ρ21−36γ2n−1L2/1−ρ2.
This completes the proof.Proof (Proof of Corollary6).
Substitutingγ=1/2L+σK/n into the result of Theorem 5 and removing the first term of the RHS on the LHS, we can obtain that
(68)B1∑k=0K−1E∇fXk1n/n2K≤2L+σK/nf0−f∗K+41+2LG2d2L+σK/nε2+Lσ22nL+σKn+2n−1L22L+σK/n2B212G2ε21−ρ2+σ21−ρ+9ζ21−ρ2≤2Lf0−f∗K+f0−f∗σKn+41+2LG2dσK/nε2+Lσ2σKn+2n−1L2σK/n2B212G2ε21−ρ2+σ21−ρ+9ζ21−ρ2.
LetG/ε≤f0−f∗+Lσ/41+2Ldn, and we show B1 and B2 are approximately constants when (16) is satisfied.
(69)B1=12−18γ2n−1L21−ρ2B2,B2=1−36γ2n−1L21−ρ2.
Note that(70)γ2≤1−ρ272n−1L2⇒B2≥12,γ2≤1−ρ2144n−1L2⇒B1≥14.
Sinceγ2≤n/σ2K, as long as we have
(71)nσ2K≤1−ρ2144n−1L2,
B2≥1/2 and B1≥1/4 will be satisfied. Then, we can obtain K≥144nn−1L2/σ21−ρ2.
LetK≥16n3n−12L4/σ6f0−f∗+L212G2/ε21−ρ2+σ2/1−ρ+9ζ2/1−ρ22, then
(72)∑k=0K−1E∇fXk1n/n2K≤8Lf0−f∗K+12f0−f∗+LσKn.


## 7. Experiments

In this section, we perform extensive simulations to evaluate our proposed algorithm. In particular, we compare the convergence rate of our proposed algorithm with the best-known D-PSGD algorithm give in [1], in the settings of different privacy budgets, different number of nodes and different extents of dynamicity.In our experiments, we evaluate our proposed algorithm on image classification tasks. We train ResNet model on CIFAR-10 dataset. Moreover, we use MPI to implement the communication scheme. We run our experiments on a CPU server cluster. Each server has 32 cores, which is an Intel Xeon E5-2620 v4 @ 2.10GHz cluster. Each server is equipped with 128G memory.


### 7.1. Impact of Privacy Budgets

We evaluate the import of privacy budget on the convergence of our proposed algorithm in a dynamic network. Here, we run our algorithm in a dynamic network with different number of nodes under different privacy budgets. The results are illustrated in Figure1, where the privacy budget ε is set to 10−1,10−2, and 10−3, respectively. It can be seen that the smaller ε is, the slower the learning converges. This is because a smaller privacy budget means more noise are added, which affects the convergence speed of the algorithm.Figure 1
The convergence rate with different privacy budgets.
(a)
n=4(b)
n=8


### 7.2. Impact of Dynamicity

We compare our algorithm with the best-known D-PSGD algorithm (with privacy protection) in a static network. Due to D-PSGD is applied to a ring structure, we set the expected degree in the dynamic network as 2. Here, the privacy budget is set to10−1, and the number of nodes is 4 and 8. From Figure 2, we can find that our proposed algorithm can reach the same convergence rate in dynamic networks as the D-PSGD algorithm (with privacy protection) in static networks.Figure 2
Comparison between dynamic networks and static networks.
(a)
n=4(b)
n=8


## 7.1. Impact of Privacy Budgets

We evaluate the import of privacy budget on the convergence of our proposed algorithm in a dynamic network. Here, we run our algorithm in a dynamic network with different number of nodes under different privacy budgets. The results are illustrated in Figure1, where the privacy budget ε is set to 10−1,10−2, and 10−3, respectively. It can be seen that the smaller ε is, the slower the learning converges. This is because a smaller privacy budget means more noise are added, which affects the convergence speed of the algorithm.Figure 1
The convergence rate with different privacy budgets.
(a)
n=4(b)
n=8


## 7.2. Impact of Dynamicity

We compare our algorithm with the best-known D-PSGD algorithm (with privacy protection) in a static network. Due to D-PSGD is applied to a ring structure, we set the expected degree in the dynamic network as 2. Here, the privacy budget is set to10−1, and the number of nodes is 4 and 8. From Figure 2, we can find that our proposed algorithm can reach the same convergence rate in dynamic networks as the D-PSGD algorithm (with privacy protection) in static networks.Figure 2
Comparison between dynamic networks and static networks.
(a)
n=4(b)
n=8


## 8. Conclusion

We presented D-(DP)2SGD, a decentralized parallel stochastic gradient descent algorithm with privacy preservation in dynamic networks. With theoretical analysis and extensive experiments, it shows that our proposed algorithm can achieve the same convergence rate as the best know previous work in static networks without considering privacy issue. Based on this work, it is meaningful to further devise privacy-preserving algorithms in an asynchronous dynamic environment.



---

*Source: 6679453-2021-03-24.xml*