# A Privacy-Masking Learning Algorithm for Online Distributed Optimization over Time-Varying Unbalanced Digraphs

Authors: Rong Hu; Binru Zhang
Journal: Journal of Mathematics
 (2021)

---

## Abstract

This paper investigates a constrained distributed optimization problem enabled by differential privacy where the underlying network is time-changing with unbalanced digraphs. To solve such a problem, we first propose a differentially private online distributed algorithm by injecting adaptively adjustable Laplace noises. The proposed algorithm can not only protect the privacy of participants without compromising a trusted third party, but also be implemented on more general time-varying unbalanced digraphs. Under mild conditions, we then show that the proposed algorithm can achieve a sublinear expected bound of regret for general local convex objective functions. The result shows that there is a trade-off between the optimization accuracy and privacy level. Finally, numerical simulations are conducted to validate the efficiency of the proposed algorithm.


---

## Body

## 1. Introduction

Owing to high requirement of large scale and distributed data processing, distributed optimization (DO) is an attractive approach. The framework of DO permits multiple units to maintain their data unrevealed and optimize cooperatively a common optimization objective by local message exchanges and computations. As a consequence, DO helps to alleviate computational burden and strengthen both robustness to communication failures and scalability of data manipulation. In existing literature, distributed methods mainly include (sub)gradient-based approaches, dual averaging methods, primal-dual methods, and alternating direction method of multipliers (ADMM) based methods. We can refer to the recent survey and references therein [1].Compared with classical DO in which the local objective functions are usually time-invariant, online distributed optimization (ODO) is applicable to the circumstances where local objective functions possibly change over time in some uncertain and even adversarial environments. Various ODO approaches have been increasingly developed in recent years [3, 4]. In [2], Schwartz initially gave a review on the advancement of online convex optimization. In a static undirected graph, Yan et al. in [5] proposed a gradient-based online learning method for the ODO problem and established the regret bounds for convex cost functions. As an alternative, primal-dual-based method and its variants were further developed in [6, 7] for the ODO problems over undirected balanced networks. Very recently, Li et al. in [8] extended online mirror descent distributed algorithm [9] to a more general setup, in which a primal-dual mirror descent distributed method was proposed for solving the constrained ODO problems over a time-changing network with the requirement that the weight matrices are doubly stochastic.All the distributed methods mentioned above are highly dependent on the demand of double-stochastic weight matrices induced by undirected or directed balanced graphs, which are fairly narrow and even unapplicable in practice. For example, a sensor network is directionally operated, since individual sensors possess diverse communication ranges limited by power supplies, which leads to the information flows between sensors become directed. Under this circumstance, the communication graphs with double stochasticity may be hard to be constructed. Recently, Nedić and Olshevsky in [10] initially introduced extra computations and communications to overcome the imbalance of networks by learning a specific eigenvector and then developed a push-sum-based algorithm. By using both column-stochastic and row-stochastic weight matrices simultaneously, Pu et al. [11] proposed an AB algorithm without learning the eigenvector. There are a lot of efforts for addressing unbalanced digraphs including the surplus-based algorithm [12], the epigraph-based algorithm [13], etc. Nevertheless, all these methods mainly focused on solving the DO problems. Akbari et al. [14] generalized the push-sum scheme to the online setup for the ODO problem over digraphs requiring column stochasticity of weight matrices. However, it requires that each node must acquire its out-degree for restructuring outgoing weights, which is difficult to be completed in a distributed scenario, especially when broadcast-based networks are adopted. In comparison with column-stochastic weight matrices, row-stochastic weight matrices are more practicable and easier to be satisfied, since each node can allocate these weights on messages by itself when received [13, 15, 16].However, the interactions among nodes in a distributed way will possibly lead to the disclosure of sensitive data, e.g., healthcare and financial accounts. As a consequence, data privacy has naturally aroused high attention when employing sensitive information. In distributed machine learning, there is an urgent need for designing DO methods while taking privacy-preserving property into account [17, 18]. Recently, the work of [19] integrated homomorphic cryptography schemes into the DO method, resulting in strong privacy guarantees. However, the method encounters expensive computation and communication costs, which is inapplicable in large-scale networks. As a charming alternative, differential privacy (DP) has attracted considerable research interest due to its rigorous mathematical foundation and being executed easily. DP has become a well-known concept of privacy-preserving method and has found a lot of applications in practice [20]. The basic idea of DP methods is injecting artificial noises into true message, resulting in a balance between computation accuracy and privacy level. The recent work [21] proposed an ODO algorithm with DP over time-changing networks with weight-balancing digraphs. However, this method is only suitable for unconstrained problems, requiring that each node has the knowledge of its out-degrees.All the limitations mentioned above motivate us to further explore an approach that has a stronger adaptability to more general applications. In this paper, by introducing the Laplace noise, we design an ODO algorithm with DP for solving constrained ODO problems in time-changing digraphs with row-stochastic matrices while preserving certain privacy. The main contributions of this article are summarized as follows:(i)
We design a differentially private online distributed method by injecting Laplace noises for addressing a constrained ODO problem over time-varying unbalanced digraphs. In contrast to existing privacy-preserving methods in [22–24], our algorithm is suitable for more practical and general network topologies. More specifically, the network consists of time-varying unbalanced digraphs with row-stochastic matrices, which is much weaker than those in [22–24]. Furthermore, row stochasticity considered in this paper is more convenient and practical for each unit to allocate the weights on information it received than column stochasticity in [21, 25].(ii)
We establish a rigorous expected bound with a square-root regret for general convex local cost functions. The expected regret can achieve the same order ofOT as the methods in [15, 16] with no DP scheme, coinciding with best theoretical regrets obtained by state-of-the-art methods. Moreover, our analysis discloses a trade-off between optimization accuracy and privacy degree by adaptively adjusting the amount of Laplace noises injected.(iii)
In contrast to cloud-enabled distributed methods with differential privacy [26, 27], our algorithm is executed in a completely distributed fashion that individual node only communicates with its neighbors, without requiring a powerful cloud authority. Besides, our algorithm can overcome the infeasibility issue by introducing an additional projection step, whereas the algorithms proposed in [22, 23] possibly suffer from the issue.The remainder of the paper is organized as follows. The problem of interest is first presented in Section2. The algorithm is proposed in Section 3. The main results on DP and the regret bound are presented in Section 4. Section 5 provides numerical simulations. Finally, conclusions are given in Section 6.Notation. Use N=1,…,N to represent the set of integers for a positive integer N. x⊤ denotes the transpose of a vector x∈ℝd. Use ei=0,…,1i,…,0⊤∈ℝd to represent a base vector and 1d=1,…,1⊤∈ℝd to represent a vector with all the entry equal to 1. Aij stands for the i,j-th component of matrix A. A non-negative square matrix A is row (column)-stochastic if each row (column) of A sums up to 1. The matrix A is doubly stochastic if both each row and each column of A sum up to 1. The Euclidean projection operator is defined by ΠXx=argminy∈Xy−x for any x∈ℝd, where X is a convex set in ℝd. For a given parameter σ>0, we use Lapσ to represent the Laplace distribution. ℙx and Ex denote the probability distribution and expectation of a random variable x, respectively.


## 2. Problem Formulation and Preliminaries

### 2.1. Graph Theory

Considering a network withN nodes, we introduce a directed graph G=N,E to model the network communication among nodes, where N is the node set and E⊆N×N is the link set. We use j,i∈E to represent a directed link, implying that node j directly transmits message to node i. Denote Ni+≔j|j,i∈Ε∪i and Ni−≔j|i,j∈Ε∪i by the collection of in-neighbors and out-neighbors for node i, respectively. A directed path is a sequence of directed links i1,i2,i2,i3,…,ik−1,ik. The directed graph G is strongly connected if there exists at least a directed path from i to j for any i,j∈N. A weight matrix A∈ℝN×N is associated with the graph G with elements Aij>0 if i,j∈E, Aij=0 otherwise. The graph G is said to be balanced if ∑j∈Ni+Aij=∑j∈Ni−Aji for all i∈V, and unbalanced, otherwise. If the links of G change over time, we use Gt=N,Et and At∈ℝN×N to denote the time-changing directed graphs and weight matrices, respectively.Now we need the following assumptions on the directed graph sequenceGtt≥1.Assumption 1.
(a) The sequence of unbalanced graphsGtt≥1 is uniformly jointly strongly connected, i.e., there exists a finite integer B>0 such that the graph Gk∪Gk+1∪⋯∪Gk+B−1 is strongly connected for any k≥0. (b) At each time t≥1, the weight matrix At is row-stochastic.


### 2.2. Differential Privacy

For two datasetsD≔dii∈N and D′≔di′i∈N, we say that D and D′ are adjacent if there is an i∈N satisfying di≠di′, and dj=dj′ for ∀j≠i. We use AdjD,D′to represent the adjacent relationship between D and D′, which means that D and D′ distinguish from one data point while all other data points are the same. For privacy concerns, we next introduce the concept of differential privacy.Definition 1 (ε-DP) (see [20]).
For a givenε>0, a randomized method ℳ preserves ε-differential privacy if for any adjacent datasets D and D′ and for any set of outputs Υ⊆Rℳ, the following relation holds:(1)ℙℳD∈Υ≤ℙℳD′∈Υ×expε×D⊕D′,where ⊕ denotes the symmetric difference, D⊕D′ stands for the number of different records in D and D′, and Rℳ is the output range of ℳ.By the concept ofε-DP, we can see that a small change of private dataset makes no remarkable difference on the output of ℳ. Hence, the adversary in the network obtains little information from participants. The parameter ε measures the privacy level of ℳ, i.e., smaller ε implies a higher degree of privacy-preserving property. Intuitively, ε should be kept small. However, this possibly sacrifices the accuracy of the method ℳ. Thus, we had to seek a balance between the desired privacy degree and computation accuracy by carefully choosing ε.For the sake of designing a differentially private mechanism, we hope to know the “sensitivity” of a randomized methodℳ. We now introduce the following definition of sensitivity, reflecting the supreme magnitude by which any single individual data changes the method ℳ in the worst case.Definition 2 (sensitivity) ( see [20]).
At timet, the sensitivity of a randomized method ℳ is defined by(2)Δt≔supDt,Dt′:AdjDt,Dt′ℳDt−ℳDt′1,where Dt and Dt′ are the corresponding input datasets at time t.


### 2.3. Problem Formulation

In what follows, we formulate the distributed online problem. At time constantt∈T, each node i∈N submits an action xi,t limited a common set X⊆ℝd, and then a local function fi,t:ℝd⟶ℝ is disclosed to this node and thereby incurred the cost fi,txi,t. In this setting, the goal is to cooperatively optimize the global cost function at time t∈T:(3)ftx≔∑i=1Nfi,tx,subject to x∈X. It should be emphasized here that each node is accessible to its local function fi,t and the global objective ft is unavailable for any single node. Thus, all the nodes in the network need to exchange with each other for minimizing the global objective ftx. Besides, each node’s local function is disclosed before the node submits its action.Due to the time-varying characteristics of cost functions, it is reburied to develop a method to decrease the gap between the cumulative payoff incurred by the method and the cost of the best fixed action in hindsight across a finite time periodT≥1. That is, the total cost should be as close as possible to the best fixed action if all the information of fi,tt=1T,i∈N is known beforehand. Considering privacy concerns, all the nodes of the network only share their noisy actions with neighboring nodes based on a randomized strategy to guard private messages. Denote ℱt by the σ-algebra produced by the history of a method until time t. The expected regret of node j∈N is used to assess the performance of the method(4)ERjT≔∑t=1TEftxj,t−∑t=1Tftx∗,where x∗≔argminx∈X∑t=1Tftx is the best fixed decision in hindsight. An online algorithm performs well if its regret is sublinear as a function of time period T.The goal of this paper is to design a privacy-masking algorithm to minimizeft over time-changing generally unbalanced digraphs requiring that each node asymptotically drives its regret to zero over time in a distributed and online way. To the end, we introduce the following assumptions.Assumption 2.
(a) The constraintX is a non-empty closed convex set. (b) For i∈N and t≥1, local cost functions fi,t are convex on X. (c) For i∈N and t≥1, the subgradient ∇fi,t of fi,t is bounded on X, that is, there is a constant Gi>0 satisfying ∇fi,tx≤Gi for all x∈X. Let G≔maxi∈NGi.


## 2.1. Graph Theory

Considering a network withN nodes, we introduce a directed graph G=N,E to model the network communication among nodes, where N is the node set and E⊆N×N is the link set. We use j,i∈E to represent a directed link, implying that node j directly transmits message to node i. Denote Ni+≔j|j,i∈Ε∪i and Ni−≔j|i,j∈Ε∪i by the collection of in-neighbors and out-neighbors for node i, respectively. A directed path is a sequence of directed links i1,i2,i2,i3,…,ik−1,ik. The directed graph G is strongly connected if there exists at least a directed path from i to j for any i,j∈N. A weight matrix A∈ℝN×N is associated with the graph G with elements Aij>0 if i,j∈E, Aij=0 otherwise. The graph G is said to be balanced if ∑j∈Ni+Aij=∑j∈Ni−Aji for all i∈V, and unbalanced, otherwise. If the links of G change over time, we use Gt=N,Et and At∈ℝN×N to denote the time-changing directed graphs and weight matrices, respectively.Now we need the following assumptions on the directed graph sequenceGtt≥1.Assumption 1.
(a) The sequence of unbalanced graphsGtt≥1 is uniformly jointly strongly connected, i.e., there exists a finite integer B>0 such that the graph Gk∪Gk+1∪⋯∪Gk+B−1 is strongly connected for any k≥0. (b) At each time t≥1, the weight matrix At is row-stochastic.


## 2.2. Differential Privacy

For two datasetsD≔dii∈N and D′≔di′i∈N, we say that D and D′ are adjacent if there is an i∈N satisfying di≠di′, and dj=dj′ for ∀j≠i. We use AdjD,D′to represent the adjacent relationship between D and D′, which means that D and D′ distinguish from one data point while all other data points are the same. For privacy concerns, we next introduce the concept of differential privacy.Definition 1 (ε-DP) (see [20]).
For a givenε>0, a randomized method ℳ preserves ε-differential privacy if for any adjacent datasets D and D′ and for any set of outputs Υ⊆Rℳ, the following relation holds:(1)ℙℳD∈Υ≤ℙℳD′∈Υ×expε×D⊕D′,where ⊕ denotes the symmetric difference, D⊕D′ stands for the number of different records in D and D′, and Rℳ is the output range of ℳ.By the concept ofε-DP, we can see that a small change of private dataset makes no remarkable difference on the output of ℳ. Hence, the adversary in the network obtains little information from participants. The parameter ε measures the privacy level of ℳ, i.e., smaller ε implies a higher degree of privacy-preserving property. Intuitively, ε should be kept small. However, this possibly sacrifices the accuracy of the method ℳ. Thus, we had to seek a balance between the desired privacy degree and computation accuracy by carefully choosing ε.For the sake of designing a differentially private mechanism, we hope to know the “sensitivity” of a randomized methodℳ. We now introduce the following definition of sensitivity, reflecting the supreme magnitude by which any single individual data changes the method ℳ in the worst case.Definition 2 (sensitivity) ( see [20]).
At timet, the sensitivity of a randomized method ℳ is defined by(2)Δt≔supDt,Dt′:AdjDt,Dt′ℳDt−ℳDt′1,where Dt and Dt′ are the corresponding input datasets at time t.


## 2.3. Problem Formulation

In what follows, we formulate the distributed online problem. At time constantt∈T, each node i∈N submits an action xi,t limited a common set X⊆ℝd, and then a local function fi,t:ℝd⟶ℝ is disclosed to this node and thereby incurred the cost fi,txi,t. In this setting, the goal is to cooperatively optimize the global cost function at time t∈T:(3)ftx≔∑i=1Nfi,tx,subject to x∈X. It should be emphasized here that each node is accessible to its local function fi,t and the global objective ft is unavailable for any single node. Thus, all the nodes in the network need to exchange with each other for minimizing the global objective ftx. Besides, each node’s local function is disclosed before the node submits its action.Due to the time-varying characteristics of cost functions, it is reburied to develop a method to decrease the gap between the cumulative payoff incurred by the method and the cost of the best fixed action in hindsight across a finite time periodT≥1. That is, the total cost should be as close as possible to the best fixed action if all the information of fi,tt=1T,i∈N is known beforehand. Considering privacy concerns, all the nodes of the network only share their noisy actions with neighboring nodes based on a randomized strategy to guard private messages. Denote ℱt by the σ-algebra produced by the history of a method until time t. The expected regret of node j∈N is used to assess the performance of the method(4)ERjT≔∑t=1TEftxj,t−∑t=1Tftx∗,where x∗≔argminx∈X∑t=1Tftx is the best fixed decision in hindsight. An online algorithm performs well if its regret is sublinear as a function of time period T.The goal of this paper is to design a privacy-masking algorithm to minimizeft over time-changing generally unbalanced digraphs requiring that each node asymptotically drives its regret to zero over time in a distributed and online way. To the end, we introduce the following assumptions.Assumption 2.
(a) The constraintX is a non-empty closed convex set. (b) For i∈N and t≥1, local cost functions fi,t are convex on X. (c) For i∈N and t≥1, the subgradient ∇fi,t of fi,t is bounded on X, that is, there is a constant Gi>0 satisfying ∇fi,tx≤Gi for all x∈X. Let G≔maxi∈NGi.


## 3. Differentially Private Distributed Online Algorithm

Now we present our algorithm. At timet, each node i hold two variables xi,t∈ℝd and wi,t∈ℝn. Firstly, node i generates an artificially noise vector ni,t, which is independent and identically distributed (i.i.d.) and drawn from the Laplace distribution LapMt with parameter Mt, and then the local action xi,t is perturbed by ni,t as follows:(5)yi,t=xi,t+ni,t.After that, nodei shares the noisy version of its action with its out-neighbors Ni,t− by(6)zi,t=ΠX∑j∈Ni,t−Atijyj,t,and then updates its action via an Euclidean projection using a stochastic subgradient g˜i,t re-scaled by a number wii,t as follows:(7)xi,t+1=ΠXzi,t−ηtg˜i,twii,t,where g˜i,t=∇fi,tzi,t+δi,t is the stochastic subgradient of fi,t at zi,t, δi,t is a random variable, and ηt>0 is the stepsize. Here wii,t is the i-th entry of the auxiliary variable wi,t, which is useful to balance the stochastic subgradient g˜i,t due to the influence of unbalancedness of the network. The auxiliary variable wi,t is updated by(8)wi,t+1=∑j∈Ni,t−Atijwj,t.Notice that making the projection ontoX in (6) is to maintain the point zi,t staying in X, since the function ∇fi,t is well defined on X.Now we summarize the above updates as in Algorithm1.Algorithm 1: Differentially private distributed online algorithm using time-varying row-stochastic weight matrix.
(1)
Input: set wi,1=ei∈ℝn, xi,1∈X⊆ℝd for all i∈N and stepsize parameter ηt for all t∈T(2)
fort=1 to Tdo(3)
fori=1 to Ndo(4)
Computeyi,t via (1) by adding noise ni,t∼LapMt to xi,t(5)
Broadcastyi,t and wi,t to out-neighbors j∈Ni,t−(6)
Compute local actionxi,t+1 via (3) and (2)(7)
Compute auxiliary variablewi,t via (4).(8)
end for(9)
end for(10)
Output:xi,Ti=1N.Remark 1.
When compared with existing algorithms, Algorithm1 has the following features.(i)
The proposed algorithm is applicable to more general time-changing digraphs with row-stochastic weight matrices, whereas the algorithms are restrictive to a static undirected graph with doubly stochastic matrix [22, 23] or time-varying digraphs with column-stochastic matrices [25]. Our algorithm extends the method with a static digraph in [24] to time-varying digraphs with row-stochastic matrices; meanwhile, the choice of stepsize for our algorithm is adaptive, without knowing the time horizon T in advance.(ii)
The algorithms proposed in [22, 23] possibly suffer from the infeasibility when using the subgradient ∇fi,t to update, since large noise that provides high privacy guarantees can get the consensus update ∑j∈Ni,t−Atijyj,t out of the convex domain X. Our algorithm can overcome this difficulty by introducing an additional projection step (see (2)).(iii)
By injecting an artificial and controllable noiseni,t to the accurate state xi,t at each iteration, the proposed algorithm can guard privacy. It can be viewed as an extension of distributed methods [15, 16] to the scenario that privacy concerns and online learning are simultaneously considered.(iv)
In contrast to cloud-enabled distributed methods with differential privacy [26, 27], our algorithm is executed in a completely distributed fashion that individual node only communicates with its neighbors, without requiring a powerful cloud authority.Next we present a lemma that displays several properties ofAt and the auxiliary variable wii,t, which are useful to analyze the performance analysis of Algorithm 1.Lemma 1 (see [13, 16]).
Suppose Assumption1 holds. Let At:s≔As−1…At for s≥t, where Ak:k=I and At:sij represents the element of At:s. Then, for any t≥1, there is a normalized vector πt1N⊤πt=1 such that(a)
The relationAt:sij−πj,t≤Γγs−t holds for all s≥t≥1 and i,j∈N, with some constants Γ>0 and γ∈0,1.(b)
The relationω−1≤πi,t≤1 holds for all i∈N, with a constant ω>0.(c)
πt⊤=πt+1⊤At.Due to introducing the noisy subgradients, we need some standard assumptions on the noiseδi,t.Assumption 3.
The stochastic noiseδi,t,i∈N,t∈T is independent and satisfies that Eδi,t|ℱt−1=0 and Eδi,t|ℱt−1≤νi for a constant νi>0.Note that, under Assumptions2 and 3, it holds that Eg˜i,t|ℱt−1=∇fi,tzi,t and Eg˜i,t|ℱt−1≤Gi+νi. The stochastic noise δi,t,i∈N,t∈T is also considered in [10, 11, 21, 25].


## 4. Main Results

In this section, we now give the main results including theε-DP of Algorithm 1 and its expected regret bounds.


### 4.1. Differential Privacy Analysis

By Definition2, the sensitivity Δt grasps the magnitude of the worst output of an algorithm caused by the change of any single data. Hence, it is necessary to bound Δt to derive the condition on noises for preserving ε-DP. Let Dt be the input of Algorithm 1 at time t that contains sensitive data required to be protected and each local cost function fi,t,∀i∈N, depends on Dt. Let xi,ti=1N,i∈N be the output sequence of Algorithm 1 at time t. We give a bound of Δt,∀t∈T for Algorithm 1 in the following lemma.Lemma 2.
Let Assumptions1–3 hold. For all t≥1, the sensitivity of Algorithm 1 is bounded as follows:(9)Δt≤2dωG^ηt,where d is the problem’s dimension and G^≔maxi∈NGi+νi.Proof.
LetDt and Dt′ be two adjacent datasets at time t and xi,t+1 and xi,t+1′ be the executions for Algorithm 1, respectively. Note that the adversary observes the output sequences kept the same, i.e., zi,t=zi,t′. By Algorithm 1 and Definition 2, we get(10)ℳtD−ℳtD′1=xi,t+1−xi,t+1′1=ΠXzi,t−ηtg˜i,tzi,twii,t−ΠXzi,t′−ηtg˜i,tzi,t′wii,t1≤ηtwii,tg˜i,tzi,t−g˜i,tzi,t′1≤dηtwii,tg˜i,tzi,t−g˜i,tzi,t′≤ωdηtg˜i,tzi,t+g˜i,tzi,t′,where the first inequality uses the non-expansive property of the Euclidean projection ΠX. From Assumptions 2 and 3, it yields that(11)Eg˜i,t|ℱt−1≤Gi+νi≤G^.
From Definition2, we further obtain(12)Δt≤Exi,t+1−xi,t+1′1|ℱt≤2ωdG^ηt,which implies the desired result.Theorem 1.
Under Assumptions1–3, if we take the parameter Mt=Δt/ε for all t≥1 when executing Algorithm 1, then Algorithm 1 can ensure ε-differential privacy at the t-th iteration.Proof.
Letxt=x1,t,…,xN,t⊤ and xt′=x1,t′,…,xN,t′⊤. By Lemma 2, we have(13)∑i=1N∑l=1dxi,tl−xi,t′l=xt−xt′1≤Δt.
Therefore, using the property of Laplace distribution, we obtain(14)∏i=1N∏l=1dℙzi,tl−xi,tlℙzi,t′l−xi,t′l=∏i=1N∏l=1dexp−zi,tl−xi,tl/Mtexp−zi,t′l−xi,t′l/Mt≤∏i=1N∏l=1dexpzi,t′l−xi,t′l−zi,tl+xi,tlMt=expxt−xt′1Mt≤expΔtMt,where the triangle inequality is used in the first inequality and Lemma 2 is used in the last inequality. By Definition 1, we have(15)ℙℳD∈Υ=∏t=1TℙℳDt∈Υ.
From the preceding relations, we obtain(16)∏t=1TℙℳDt∈Υ≤∏t=1TℙℳDt′∈Υ×∏t=1TexpΔtMt×Dt⊕Dt′=∏t=1TℙℳDt′∈Υ×expΔtMt×|Dt⊕Dt′|.
Using the choice of the parameterMt and Definition 1, the proof is completed.
Theorem1 shows that Algorithm 1 can guarantee ε-DP at each step by injecting a carefully designed Laplace noise. But it can only guard ε-DP at each single step. From the composition argument in [20], the privacy guarantee degrades after T-fold composition. The following corollary discloses the worst privacy guarantee after T steps, which is at most the sum of the DP guarantee of each single step.Corollary 1.
Under the conditions of Theorem1, Algorithm 1 can ensure Tε-DP after T iterations.


### 4.2. Regret Analysis

We analyze theoretically the regret bound of Algorithm1. The following lemma provides the network disagreement error.Lemma 3.
Under Assumptions1–3, the sequence xi,t is generated by Algorithm 1 taking Mt=Δt/ε. Then,(17)Exi,t+1−x¯t+1|ℱt≤Γγt∑j=1Nx˜j,1+2ωNΓG^∑s=1t−1γt−sηs+2ωG^ηt+22dNΓ∑s=1t−1γt−sMs+22dMt,where x¯t≔∑i=1Nπi,txi,t and constants Γ and γ are given in Lemma 1.Proof.
Letxt=x1,t,…,xN,t⊤, ut=u1,t,…,uN,t⊤ and vt=v1,t,…,vN,t⊤, where(18)ui,t=ΠXzi,t−ηtg˜i,twii,t−zi,t,vi,t=ΠX∑j=1NAtijyj,t−∑j=1NAtijxj,t,i∈N.
Letx¯t=πt⊤xt, u¯t=πt+1⊤ut, v¯t=πt+1⊤vt. From (7) and (6), it gives rise to(19)xt+1=Atxt+vt+ut.
Then, multiplying both sides of (19) by 1Nπt+1⊤ and making use of πt⊤=πt+1⊤At from Lemma 1, we get(20)1Nx¯t+1=1Nπt⊤xt+1Nv¯t+1Nu¯t.
Combining (19) and (20), we get(21)xt+1−1Nx¯t+1=At−1Nπt⊤xt+vt−1Nv¯t+ut−1Nu¯t.
Lettingx˜t+1=xt+1−1Nx¯t+1, A˜t=At−1Nπt⊤, v˜t=vt−1Nv¯t, and u˜t=ut−1Nu¯t and noting that At−1Nπt⊤1Nx¯t=At1N−1Nπt⊤1Nx¯t=0 due to row stochasticity of At, it follows from (21) that(22)x˜t+1=A˜tx˜t+v˜t+u˜t=∏s=1tA˜sx˜1+∑s=2t∏k=stA˜kv˜s−1+v˜t+∑s=2t∏k=stA˜ku˜s−1+u˜t.
By mathematical induction, it gives rise to∏k=stA˜k=At+1:s−1Nπs⊤. Thus, relation (9) can be written as(23)x˜t+1=At+1:1−1Nπ1⊤x˜1+∑s=2tAt+1:s−1Nπs⊤v˜s−1+v˜t+∑s=2tAt+1:s−1Nπs⊤u˜s−1+u˜t.
From the preceding relation, we can obtain(24)x˜i,t+1=∑j=1NAt+1:1ij−πj,1x˜j,1+∑s=2t∑j=1NAt+1:sij−πj,sv˜j,s−1+v˜i,t+∑s=2t∑j=1NAt+1:sij−πj,su˜j,s−1+u˜i,t.
Taking the norm on both sides of the above equality, we have(25)xi,t+1−x¯t+1=x˜i,t+1≤∑j=1NAt+1:1ij−πj,1x˜j,1+∑s=2t∑j=1NAt+1:sij−πj,sv˜j,s−1+v˜i,t+∑s=2t∑j=1NAt+1:sij−πj,su˜j,s−1+u˜i,t.
Using the non-expansivity ofΠX and (18), we have(26)ui,t≤ωηtg˜i,t,vi,t≤∑j=1NAtijnj,t.
From the definition ofu˜i,t and v˜i,t, we further obtain that Eu˜i,t≤2ωG^ηt and(27)Ev˜i,t≤∑j=1NAtijEnj,t+∑i=1Nπi,tEni,t.
Using Lemma1, Assumption 2, (24), and (27), we can get(28)Exi,t+1−x˜t+1≤Γγt∑j=1Nx˜j,1+2Γ∑s=2t∑j=1Nγt−s+1∑i=1NAs−1ijEni,s−1+∑j=1NAtijEnj,t+∑i=1Nπi,tEni,t+2NωΓG^∑s=2tγt−s+1ηs−1+2ωG^ηt.
Sinceni,t∼LapMt and each entry of ni,t∈ℝd is independent, we obtain Eni,tl2=2Mt2, where ni,tl is the l-th entry of ni,t. Moreover, we have(29)Eni,t2=∑l=1dEni,tk2≤2dMt2,(30)Eni,t≤Eni,t2=2dMt.
Thus, by taking the expectation condition onℱt for (28), the desired result can be obtained.Lemma 4.
Under Assumptions1–3, the sequence xi,t is generated by Algorithm 1 with Mt=Δt/ε. Then, we have(31)∑i=1Nπi,t+1Exi,t+1−x∗2|ℱt≤∑i=1Nπi,tExi,t−x∗2+2dMt2+G^2ω2ηt2−B0ηtEftx¯t−ftx∗+22dωGMtηt+2Gωηt∑i=1Nπi,tExi,t−x¯t,where B0=2inft≥1πi,t+1/wii,t.Proof.
By (3) and the non-expansibility of ΠX, we obtain(32)Exi,t+1−x∗2|ℱt=EΠXzi,t−ηtg˜i,twii,t−x∗2|ℱt≤Ezi,t−ηtg˜i,twii,t−x∗2=Ezi,t−x∗2−2ηtwii,tEg˜i,t,zi,t−x∗+ηt2wii,t2Eg˜i,t2.
Using the relationπt⊤=πt+1⊤At from Lemma 1, it follows that(33)∑i=1Nπi,t+1Ezi,t−x∗2=∑i=1Nπi,t+1EΠX∑j=1NAtijxj,t+nj,t−x∗2≤∑i=1Nπi,t+1E∑j=1NAtijxj,t+nj,t−x∗2≤∑i=1Nπi,tExi,t+ni,t−x∗2=∑i=1Nπi,tExi,t−x∗2+∑i=1Nπi,tEni,t2≤∑i=1Nπi,tExi,t−x∗2+2dMt2.
Combining (32) and (33) with Lemma 1, we obtain(34)∑i=1Nπi,t+1Exi,t+1−x∗2≤∑i=1Nπi,tExi,t−x∗2+2dMt2+G^2ω2ηt2−∑i=1Nπi,t+12ηtwii,tEg˜i,t,zi,t−x∗.
Note that(35)g˜i,t,zi,t−x∗=∇fi,tzi,t,zi,t−x∗+g˜i,t−∇fi,tzi,t,zi,t−x∗,(36)−∇fi,tzi,t,zi,t−x∗≤fi,tx∗−fi,tzi,t≤fi,tx∗−fi,txt+Gzi,t−x¯t≤fi,tx∗−fi,tx¯t+G∑j=1NAtijxj,t+nj,t−x¯t≤fi,tx∗−fi,tx¯t+G∑j=1NAtijxj,t+nj,t−x¯t.
Using (35) and (36) and the fact that Eg˜i,t−∇fi,tzi,t,zi,t−x∗=0, we can estimate the third term in RHS of (34):(37)−2ηt∑i=1Nπi,t+1wii,tEg˜i,t,zi,t−x∗≤−2ηt∑i=1Nπi,t+1wii,tEfi,tx¯t−fi,tx∗+2Gηt∑i=1Nπi,t+1wii,t∑j=1NAtijExj,t+nj,t−x¯t.
By lettingB0=2inft≥1πi,t+1/wii,t, the first term of RHS in (37) can be bounded as follows:(38)−2ηt∑i=1Nπi,t+1wii,tEfi,tx¯t−fi,tx∗≤−B0ηt∑i=1NEfi,tx¯t−fi,tx∗.
For the second item in RHS of (37), we have(39)2Gηt∑i=1Nπi,t+1wii,t∑j=1NAtijExj,t+nj,t−x¯t≤2Gωηt∑i=1Nπi,tExi,t−x¯t+ni,t.
By substituting (38) and (39) into (37), it yields that(40)≤−B0ηt∑i=1NEfi,tx¯t−fi,tx∗−2ηt∑i=1Nπi,t+1wii,tEg˜i,t,zi,t−x∗+2Gωηt∑i=1Nπi,tExi,t−x¯t+Eni,t.
Finally, combining (34), (40), and (30), the desired result can be obtained.
Now we give the main result on convergence rate of Algorithm1.Theorem 2.
Under Assumptions1–3, the sequence xi,t is generated by Algorithm 1 with Mt=Δt/ε. If we take the stepsize as ηt=1/t for all t≥1, then(41)ERiT≤B1+B2εT,where B1=ΓG/1−γN+2ω/B0∑j=1Nx˜j,1 and B2ε=ND2/B0+2G^ω2/B08d2G^/ε2+G^+42dG/ε+4GG^N+2ω/B0ω+NΓγ/1−γω+22d/ε.Proof.
From the boundedness of subgradients offi,t, we have(42)ftxi,t−ftx∗=ftxi,t−ftx¯t+ftx¯t−ftx∗≤G∑i=1Nxi,t−x¯t+ftx¯t−ftx∗.
Summing up overt=1,…,T for the preceding inequality and then taking the expectation, we get(43)∑t=1TEftxi,t−ftx∗≤G∑t=1T∑i=1NExi,t−x¯t+∑t=1TEftx¯t−ftx∗.
Rearranging the terms in (31) and then summing up from t=1 to T, it yields that(44)∑t=1TEftx¯t−ftx∗≤∑t=1T1B0ηt∑i=1Nπi,tExi,t−x∗2−∑i=1Nπi,t+1Exi,t+1−x∗2+2B0∑t=1TMt2ηt+G^2ω2B0∑t=1Tηt+22dωGB0∑t=1TMt+2GωB0∑t=1T∑i=1Nπi,tExi,t−x¯t.
LetP0 be the first term of RHS in (44). Now we estimate P0 as follows:(45)P0≤1B0η1∑i=1NExi,1−x∗2+∑t=2T1B0ηt−1B0ηt−1∑i=1NExi,t−x∗2≤ND2B0ηT,where we use the relation 0≤πi,t≤1 in the first inequality and D2=:supx,y∈X‖x−y‖2 in the last inequality, respectively.
Combining (43)–(45) and Lemma 3, we have(46)∑t=1TEftxi,t−ftx∗≤ND2B0ηT+2B0∑t=1TMt2ηt+G^2ω2B0∑t=1Tηt+22dωGB0∑t=1TMt+ΓG1−γN+2ωB0∑j=1Nx˜j,1+2NωΓGG^N+2ωB0∑t=1T∑s=1t−2γt−s−1ηs+2ωGG^N+2ωB0∑t=1Tηt−1+22dNΓGN+2ωB0∑t=1T∑s=1t−2γt−s−1Ms+22dGN+2ωB0∑t=1TMt−1.
Note that the choice ofηt=1/t and Mt=Δt/ε≤2dG^ω/εηt, and due to Lemma 2, it follows from (46) that(47)∑t=1TEftxi,t−ftx∗≤ΓG1−γN+2ωB0∑j=1Nx˜j,1+ND2B0T+2G^ω2B08d2G^ε2+G^+42dGεT+4GG^N+2ωB0ω+NΓγ1−γω+22dεT,where we use the relation that ∑t=1T1/t≤2T. This completes the proof.Remark 2.
From Theorem1, the expected bound of regret for Algorithm 1 can be arrived at a square-root regret for convex cost functions. Notice that the expected regret has the same order of OT as [15, 16] (with no differential privacy scheme) for a fixed ε even when the Laplace noise is infused. In addition, the bound of regret is dependent on the connectivity of the network γ, the network size N, and the dimension d of the underlying problem.
For a fixedT, the expected regret will increase (large enough) when the parameter ε of privacy level becomes small. As seen from Theorem 2, the expected regret is of order O1/ε2 for any ε∈0,1. Thus, the results of Theorem 2 tell us that there is a comprehensive balance between the privacy degree and desired accuracy of algorithm.


## 4.1. Differential Privacy Analysis

By Definition2, the sensitivity Δt grasps the magnitude of the worst output of an algorithm caused by the change of any single data. Hence, it is necessary to bound Δt to derive the condition on noises for preserving ε-DP. Let Dt be the input of Algorithm 1 at time t that contains sensitive data required to be protected and each local cost function fi,t,∀i∈N, depends on Dt. Let xi,ti=1N,i∈N be the output sequence of Algorithm 1 at time t. We give a bound of Δt,∀t∈T for Algorithm 1 in the following lemma.Lemma 2.
Let Assumptions1–3 hold. For all t≥1, the sensitivity of Algorithm 1 is bounded as follows:(9)Δt≤2dωG^ηt,where d is the problem’s dimension and G^≔maxi∈NGi+νi.Proof.
LetDt and Dt′ be two adjacent datasets at time t and xi,t+1 and xi,t+1′ be the executions for Algorithm 1, respectively. Note that the adversary observes the output sequences kept the same, i.e., zi,t=zi,t′. By Algorithm 1 and Definition 2, we get(10)ℳtD−ℳtD′1=xi,t+1−xi,t+1′1=ΠXzi,t−ηtg˜i,tzi,twii,t−ΠXzi,t′−ηtg˜i,tzi,t′wii,t1≤ηtwii,tg˜i,tzi,t−g˜i,tzi,t′1≤dηtwii,tg˜i,tzi,t−g˜i,tzi,t′≤ωdηtg˜i,tzi,t+g˜i,tzi,t′,where the first inequality uses the non-expansive property of the Euclidean projection ΠX. From Assumptions 2 and 3, it yields that(11)Eg˜i,t|ℱt−1≤Gi+νi≤G^.
From Definition2, we further obtain(12)Δt≤Exi,t+1−xi,t+1′1|ℱt≤2ωdG^ηt,which implies the desired result.Theorem 1.
Under Assumptions1–3, if we take the parameter Mt=Δt/ε for all t≥1 when executing Algorithm 1, then Algorithm 1 can ensure ε-differential privacy at the t-th iteration.Proof.
Letxt=x1,t,…,xN,t⊤ and xt′=x1,t′,…,xN,t′⊤. By Lemma 2, we have(13)∑i=1N∑l=1dxi,tl−xi,t′l=xt−xt′1≤Δt.
Therefore, using the property of Laplace distribution, we obtain(14)∏i=1N∏l=1dℙzi,tl−xi,tlℙzi,t′l−xi,t′l=∏i=1N∏l=1dexp−zi,tl−xi,tl/Mtexp−zi,t′l−xi,t′l/Mt≤∏i=1N∏l=1dexpzi,t′l−xi,t′l−zi,tl+xi,tlMt=expxt−xt′1Mt≤expΔtMt,where the triangle inequality is used in the first inequality and Lemma 2 is used in the last inequality. By Definition 1, we have(15)ℙℳD∈Υ=∏t=1TℙℳDt∈Υ.
From the preceding relations, we obtain(16)∏t=1TℙℳDt∈Υ≤∏t=1TℙℳDt′∈Υ×∏t=1TexpΔtMt×Dt⊕Dt′=∏t=1TℙℳDt′∈Υ×expΔtMt×|Dt⊕Dt′|.
Using the choice of the parameterMt and Definition 1, the proof is completed.
Theorem1 shows that Algorithm 1 can guarantee ε-DP at each step by injecting a carefully designed Laplace noise. But it can only guard ε-DP at each single step. From the composition argument in [20], the privacy guarantee degrades after T-fold composition. The following corollary discloses the worst privacy guarantee after T steps, which is at most the sum of the DP guarantee of each single step.Corollary 1.
Under the conditions of Theorem1, Algorithm 1 can ensure Tε-DP after T iterations.


## 4.2. Regret Analysis

We analyze theoretically the regret bound of Algorithm1. The following lemma provides the network disagreement error.Lemma 3.
Under Assumptions1–3, the sequence xi,t is generated by Algorithm 1 taking Mt=Δt/ε. Then,(17)Exi,t+1−x¯t+1|ℱt≤Γγt∑j=1Nx˜j,1+2ωNΓG^∑s=1t−1γt−sηs+2ωG^ηt+22dNΓ∑s=1t−1γt−sMs+22dMt,where x¯t≔∑i=1Nπi,txi,t and constants Γ and γ are given in Lemma 1.Proof.
Letxt=x1,t,…,xN,t⊤, ut=u1,t,…,uN,t⊤ and vt=v1,t,…,vN,t⊤, where(18)ui,t=ΠXzi,t−ηtg˜i,twii,t−zi,t,vi,t=ΠX∑j=1NAtijyj,t−∑j=1NAtijxj,t,i∈N.
Letx¯t=πt⊤xt, u¯t=πt+1⊤ut, v¯t=πt+1⊤vt. From (7) and (6), it gives rise to(19)xt+1=Atxt+vt+ut.
Then, multiplying both sides of (19) by 1Nπt+1⊤ and making use of πt⊤=πt+1⊤At from Lemma 1, we get(20)1Nx¯t+1=1Nπt⊤xt+1Nv¯t+1Nu¯t.
Combining (19) and (20), we get(21)xt+1−1Nx¯t+1=At−1Nπt⊤xt+vt−1Nv¯t+ut−1Nu¯t.
Lettingx˜t+1=xt+1−1Nx¯t+1, A˜t=At−1Nπt⊤, v˜t=vt−1Nv¯t, and u˜t=ut−1Nu¯t and noting that At−1Nπt⊤1Nx¯t=At1N−1Nπt⊤1Nx¯t=0 due to row stochasticity of At, it follows from (21) that(22)x˜t+1=A˜tx˜t+v˜t+u˜t=∏s=1tA˜sx˜1+∑s=2t∏k=stA˜kv˜s−1+v˜t+∑s=2t∏k=stA˜ku˜s−1+u˜t.
By mathematical induction, it gives rise to∏k=stA˜k=At+1:s−1Nπs⊤. Thus, relation (9) can be written as(23)x˜t+1=At+1:1−1Nπ1⊤x˜1+∑s=2tAt+1:s−1Nπs⊤v˜s−1+v˜t+∑s=2tAt+1:s−1Nπs⊤u˜s−1+u˜t.
From the preceding relation, we can obtain(24)x˜i,t+1=∑j=1NAt+1:1ij−πj,1x˜j,1+∑s=2t∑j=1NAt+1:sij−πj,sv˜j,s−1+v˜i,t+∑s=2t∑j=1NAt+1:sij−πj,su˜j,s−1+u˜i,t.
Taking the norm on both sides of the above equality, we have(25)xi,t+1−x¯t+1=x˜i,t+1≤∑j=1NAt+1:1ij−πj,1x˜j,1+∑s=2t∑j=1NAt+1:sij−πj,sv˜j,s−1+v˜i,t+∑s=2t∑j=1NAt+1:sij−πj,su˜j,s−1+u˜i,t.
Using the non-expansivity ofΠX and (18), we have(26)ui,t≤ωηtg˜i,t,vi,t≤∑j=1NAtijnj,t.
From the definition ofu˜i,t and v˜i,t, we further obtain that Eu˜i,t≤2ωG^ηt and(27)Ev˜i,t≤∑j=1NAtijEnj,t+∑i=1Nπi,tEni,t.
Using Lemma1, Assumption 2, (24), and (27), we can get(28)Exi,t+1−x˜t+1≤Γγt∑j=1Nx˜j,1+2Γ∑s=2t∑j=1Nγt−s+1∑i=1NAs−1ijEni,s−1+∑j=1NAtijEnj,t+∑i=1Nπi,tEni,t+2NωΓG^∑s=2tγt−s+1ηs−1+2ωG^ηt.
Sinceni,t∼LapMt and each entry of ni,t∈ℝd is independent, we obtain Eni,tl2=2Mt2, where ni,tl is the l-th entry of ni,t. Moreover, we have(29)Eni,t2=∑l=1dEni,tk2≤2dMt2,(30)Eni,t≤Eni,t2=2dMt.
Thus, by taking the expectation condition onℱt for (28), the desired result can be obtained.Lemma 4.
Under Assumptions1–3, the sequence xi,t is generated by Algorithm 1 with Mt=Δt/ε. Then, we have(31)∑i=1Nπi,t+1Exi,t+1−x∗2|ℱt≤∑i=1Nπi,tExi,t−x∗2+2dMt2+G^2ω2ηt2−B0ηtEftx¯t−ftx∗+22dωGMtηt+2Gωηt∑i=1Nπi,tExi,t−x¯t,where B0=2inft≥1πi,t+1/wii,t.Proof.
By (3) and the non-expansibility of ΠX, we obtain(32)Exi,t+1−x∗2|ℱt=EΠXzi,t−ηtg˜i,twii,t−x∗2|ℱt≤Ezi,t−ηtg˜i,twii,t−x∗2=Ezi,t−x∗2−2ηtwii,tEg˜i,t,zi,t−x∗+ηt2wii,t2Eg˜i,t2.
Using the relationπt⊤=πt+1⊤At from Lemma 1, it follows that(33)∑i=1Nπi,t+1Ezi,t−x∗2=∑i=1Nπi,t+1EΠX∑j=1NAtijxj,t+nj,t−x∗2≤∑i=1Nπi,t+1E∑j=1NAtijxj,t+nj,t−x∗2≤∑i=1Nπi,tExi,t+ni,t−x∗2=∑i=1Nπi,tExi,t−x∗2+∑i=1Nπi,tEni,t2≤∑i=1Nπi,tExi,t−x∗2+2dMt2.
Combining (32) and (33) with Lemma 1, we obtain(34)∑i=1Nπi,t+1Exi,t+1−x∗2≤∑i=1Nπi,tExi,t−x∗2+2dMt2+G^2ω2ηt2−∑i=1Nπi,t+12ηtwii,tEg˜i,t,zi,t−x∗.
Note that(35)g˜i,t,zi,t−x∗=∇fi,tzi,t,zi,t−x∗+g˜i,t−∇fi,tzi,t,zi,t−x∗,(36)−∇fi,tzi,t,zi,t−x∗≤fi,tx∗−fi,tzi,t≤fi,tx∗−fi,txt+Gzi,t−x¯t≤fi,tx∗−fi,tx¯t+G∑j=1NAtijxj,t+nj,t−x¯t≤fi,tx∗−fi,tx¯t+G∑j=1NAtijxj,t+nj,t−x¯t.
Using (35) and (36) and the fact that Eg˜i,t−∇fi,tzi,t,zi,t−x∗=0, we can estimate the third term in RHS of (34):(37)−2ηt∑i=1Nπi,t+1wii,tEg˜i,t,zi,t−x∗≤−2ηt∑i=1Nπi,t+1wii,tEfi,tx¯t−fi,tx∗+2Gηt∑i=1Nπi,t+1wii,t∑j=1NAtijExj,t+nj,t−x¯t.
By lettingB0=2inft≥1πi,t+1/wii,t, the first term of RHS in (37) can be bounded as follows:(38)−2ηt∑i=1Nπi,t+1wii,tEfi,tx¯t−fi,tx∗≤−B0ηt∑i=1NEfi,tx¯t−fi,tx∗.
For the second item in RHS of (37), we have(39)2Gηt∑i=1Nπi,t+1wii,t∑j=1NAtijExj,t+nj,t−x¯t≤2Gωηt∑i=1Nπi,tExi,t−x¯t+ni,t.
By substituting (38) and (39) into (37), it yields that(40)≤−B0ηt∑i=1NEfi,tx¯t−fi,tx∗−2ηt∑i=1Nπi,t+1wii,tEg˜i,t,zi,t−x∗+2Gωηt∑i=1Nπi,tExi,t−x¯t+Eni,t.
Finally, combining (34), (40), and (30), the desired result can be obtained.
Now we give the main result on convergence rate of Algorithm1.Theorem 2.
Under Assumptions1–3, the sequence xi,t is generated by Algorithm 1 with Mt=Δt/ε. If we take the stepsize as ηt=1/t for all t≥1, then(41)ERiT≤B1+B2εT,where B1=ΓG/1−γN+2ω/B0∑j=1Nx˜j,1 and B2ε=ND2/B0+2G^ω2/B08d2G^/ε2+G^+42dG/ε+4GG^N+2ω/B0ω+NΓγ/1−γω+22d/ε.Proof.
From the boundedness of subgradients offi,t, we have(42)ftxi,t−ftx∗=ftxi,t−ftx¯t+ftx¯t−ftx∗≤G∑i=1Nxi,t−x¯t+ftx¯t−ftx∗.
Summing up overt=1,…,T for the preceding inequality and then taking the expectation, we get(43)∑t=1TEftxi,t−ftx∗≤G∑t=1T∑i=1NExi,t−x¯t+∑t=1TEftx¯t−ftx∗.
Rearranging the terms in (31) and then summing up from t=1 to T, it yields that(44)∑t=1TEftx¯t−ftx∗≤∑t=1T1B0ηt∑i=1Nπi,tExi,t−x∗2−∑i=1Nπi,t+1Exi,t+1−x∗2+2B0∑t=1TMt2ηt+G^2ω2B0∑t=1Tηt+22dωGB0∑t=1TMt+2GωB0∑t=1T∑i=1Nπi,tExi,t−x¯t.
LetP0 be the first term of RHS in (44). Now we estimate P0 as follows:(45)P0≤1B0η1∑i=1NExi,1−x∗2+∑t=2T1B0ηt−1B0ηt−1∑i=1NExi,t−x∗2≤ND2B0ηT,where we use the relation 0≤πi,t≤1 in the first inequality and D2=:supx,y∈X‖x−y‖2 in the last inequality, respectively.
Combining (43)–(45) and Lemma 3, we have(46)∑t=1TEftxi,t−ftx∗≤ND2B0ηT+2B0∑t=1TMt2ηt+G^2ω2B0∑t=1Tηt+22dωGB0∑t=1TMt+ΓG1−γN+2ωB0∑j=1Nx˜j,1+2NωΓGG^N+2ωB0∑t=1T∑s=1t−2γt−s−1ηs+2ωGG^N+2ωB0∑t=1Tηt−1+22dNΓGN+2ωB0∑t=1T∑s=1t−2γt−s−1Ms+22dGN+2ωB0∑t=1TMt−1.
Note that the choice ofηt=1/t and Mt=Δt/ε≤2dG^ω/εηt, and due to Lemma 2, it follows from (46) that(47)∑t=1TEftxi,t−ftx∗≤ΓG1−γN+2ωB0∑j=1Nx˜j,1+ND2B0T+2G^ω2B08d2G^ε2+G^+42dGεT+4GG^N+2ωB0ω+NΓγ1−γω+22dεT,where we use the relation that ∑t=1T1/t≤2T. This completes the proof.Remark 2.
From Theorem1, the expected bound of regret for Algorithm 1 can be arrived at a square-root regret for convex cost functions. Notice that the expected regret has the same order of OT as [15, 16] (with no differential privacy scheme) for a fixed ε even when the Laplace noise is infused. In addition, the bound of regret is dependent on the connectivity of the network γ, the network size N, and the dimension d of the underlying problem.
For a fixedT, the expected regret will increase (large enough) when the parameter ε of privacy level becomes small. As seen from Theorem 2, the expected regret is of order O1/ε2 for any ε∈0,1. Thus, the results of Theorem 2 tell us that there is a comprehensive balance between the privacy degree and desired accuracy of algorithm.


## 5. Numerical Simulations

In this section, we present some numerical experiments to assess the performance of Algorithm1.We consider a network localization problem [25] with N participating units. All the units in the network are used to coordinately detect a common vector w∈ℝd. At each time slot t∈T, unit i has to access an observation vector hi,t∈Rdi, which changes over time with unknown noise due to environmental uncertainty. Assume that each unit i has a linear model in a form as hiw=Hiw, where Hi∈ℝdi×d is a given observation matrix, and Hiw=0 if and only if w=0. The goal is to cooperatively seek the vector w^∈W⊆ℝd by minimizing the global cost function(48)fw^=∑t=1T∑i=1Nfi,tw^,where fi,tw^=1/2hi,t−Hiw^2 is the local cost function of unit i. Here hi,t is the observation vector of unit i, modelled by hi,t=Hiw+θi,t, where θi,t denotes observation noise. Notice that each fi,t is time-varying and individual unit may be unwilling to share its private data with other units. Thus, it requires to design an online distributed algorithm to commonly estimate a best vector w while preserving the privacy of participants.In simulations, we setN=10 and d=1. At time t, local cost function of unit i is given by fi,tw^=1/2hi,t−Hiw^2, where hi,t=αi,tw+βi,t and Hi∈ℝ. We set the constraint set W=−5,5 and let the coefficients αi,t and βi,t randomly and uniformly draw from (0, 2] and [−1,1] at each time t, respectively. Let Hi be randomly generated from 0,2 for each unit i and set the stepsize ηt=2/t0.5. The communications among units are described in Figure 1. Note that any single graph is not strongly connected, but their jointed graphs are strongly connected. To satisfy Assumption 1, for each graph, we set the corresponding weight matrix by(49)Aij=1Niin,j∈Niin,0,otherwise,where Niin can be numbered directly from Figure 1. In the iteration process, we then randomly select a graph from the generated two graphs.Figure 1
Two unbalanced directed graphs.
(a)(b)We use Algorithm1 to estimate the vector w^. The trajectories of ten units are illustrated in Figure 2 over earlier 500 iterations. It can be observed that the estimate of each unit xi,t can gradually arrive at the same value.Figure 2
State trajectories of ten units.To study the effects of DP, we execute Algorithm1 over the unbalanced digraphs described above with the stepsize ηt=1/t0.5 for three different levels of DP: ε=10, ε=1, and ε=0.1. The results are displayed in Figure 3, which show that our algorithm can achieve a sublinear regret and the parameter ε determines a trade-off between the privacy level and the optimization accuracy. From this figure, we can observe that better privacy guarantees means worse accuracy of the algorithm.Figure 3
Evolutions ofRiT/T under different levels of privacy.Now we compare some numerical results between Algorithm1 with DP by setting ε=1 and the proposed algorithm in [16] that does not consider DP. Figure 4 demonstrates the time-averaging individual regret RjT/T vs. iteration T for two cases: one is the maximum time-averaging individual regret maxjRjT/T and the other one is the minimum time-averaging individual regret minjRjT/T. As seen in this figure, both maximum and minimum time-averaging individual regret is going to zero as the iteration T grows up for both algorithms. Meanwhile, the maximum time-averaging individual regret is very closely the minimum one for both algorithms.Figure 4
Comparisons between Algorithm1 with DP and the algorithm without DP in [16].


## 6. Conclusion

This paper has investigated a private distributed online constrained optimization in the setting that the unbalanced digraphs are time-varying requiring row stochasticity of weight matrices. By adopting the Laplace mechanism to protect sensitive data of participants, a differential privacy distributed online method was proposed. Under the convexity condition, the expected regret bounds of the proposed algorithm were derived. Finally, the trade-off between the privacy level and the algorithm accuracy is shown by numerical simulations.



---

*Source: 6115451-2021-10-28.xml*