# Distributed Constrained Stochastic Subgradient Algorithms Based on Random Projection and Asynchronous Broadcast over Networks

Authors: Junlong Zhu; Ping Xie; Qingtao Wu; Mingchuan Zhang; Ruijuan Zheng; Jianfeng Guan; Changqiao Xu
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

We consider a distributed constrained optimization problem over a time-varying network, where each agent only knows its own cost functions and its constraint set. However, the local constraint set may not be known in advance or consists of huge number of components in some applications. To deal with such cases, we propose a distributed stochastic subgradient algorithm over time-varying networks, where the estimate of each agent projects onto its constraint set by using random projection technique and the implement of information exchange between agents by employing asynchronous broadcast communication protocol. We show that our proposed algorithm is convergent with probability 1 by choosing suitable learning rate. For constant learning rate, we obtain an error bound, which is defined as the expected distance between the estimates of agent and the optimal solution. We also establish an asymptotic upper bound between the global objective function value at the average of the estimates and the optimal value.


---

## Body

## 1. Introduction

Distributed optimization problems have received considerable interest from industry and academia since it arises in many applications, including distributed parameter estimation, detection and source localization [1–4], distributed learning and regression [5–7], resource allocation [8, 9], and distributed power control [10]. The goal of such problems is to minimize a global objective function which is a sum of local cost functions over a network. To achieve this goal, we need to design a distributed optimization algorithm over time-varying networks, where each local cost function and constraint set are private information. Moreover, each agent can exchange information with its neighbors across the time-varying networks. Hence, many distributed optimization algorithms are proposed to address the distributed optimization problems [11–15].However, each agent may not know the constraint setXi beforehand in some applications. Thus, the estimate of each agent i cannot be projected onto the constraint set Xi by the determinate projection operation, and the determinate projection-based distributed optimization algorithm [16–18] cannot be directly application in such optimization problems. To deal with this case, a random projection-based distributed optimization algorithm is studied in [19, 20]. Moreover, the determinate projection-based distributed optimization algorithm can be regarded as a special case of the random projection-based distributed optimization algorithm. Therefore, we consider the distributed random projection algorithm in this paper. Furthermore, the local constraint set Xi is assumed to have the form, Xi=⋂j∈ΘiXij, where Θi is the index set and Xij is a simple set.In addition, each agent needs to exchange information with its neighbors over time-varying networks. Hence, the design of communication protocol is a crucial role in the design of distributed optimization algorithm. In practice, gossip communication protocol [21] and broadcast communication protocol [22] are two frequently used communication protocols. An asynchronous distributed random projection algorithm based on gossip communication protocol has been proposed in [23]. However, the broadcast is a natural communication mode in wireless media. Moreover, compared with the gossip communication protocol, the broadcast communication protocol can improve communication in consensus algorithms. Since the consensus problem can be regarded as a special case of distributed optimization problem, the global objective function is a sum of local cost functions. Hence, the same improvement result can apply to the distributed optimization problem. Furthermore, due to bidirectional communications, the communication bottleneck is created in broadcast communication protocol. To remove this bottleneck, we use the random broadcast communication protocol to exchange information among agents over time-varying networks. Therefore, we propose an asynchronous distributed random subgradient algorithm by using random projection operation and random broadcast communication protocol. Further, we assume that the link can be randomly interrupted in our proposed algorithm. The broadcast-based consensus algorithm has been recently studied in [22, 24, 25]. Besides, [26] proposes an asynchronous distributed projection algorithm based on broadcast communication protocol, where the constraint set is available to every agent and the projection operation is a determinate projection. Unlike [26], we project the estimate of each agent onto its own constraint set by employing random projection operation. Furthermore, each agent only knows its own constraint set and does not know the constraint sets of other agents. Informally, the algorithm in [26] is a special case of our proposed algorithm.Our objective is to analyze the convergence properties of our proposed algorithm and establish some asymptotic error bounds. The main contributions of this paper are as follows:(i)
We propose an asynchronous distributed random subgradient algorithm based on random projection operation and randomized broadcast communication protocol, where we consider the case that the link failures are randomly occurring over time-varying networks. Moreover, we assume that each agent only knows its local cost function and its own constraint set.(ii)
We analyze the convergence properties of our proposed algorithm by appropriately chosen step sizes; we show that the estimates of all agents converge to an optimal solution with probability 1.(iii)
We also establish some asymptotic error bounds when the step sizes are constant.The remainder of this paper is organized as follows. We describe the optimization problem of our interest, present the algorithm, and give some assumptions in Section2. We state the main results of the paper in Section 3. In Section 4, the convergence rate of the algorithm and their proofs are provided. The analysis of error bounds is presented in Section 5. The conclusion of the paper is given in Section 6.Notation. In this paper, all vectors are column vectors. We use boldface to denote the vectors in Rd and use normal font to denote scalars or vectors of different dimensions. xT and AT denote the transpose operation of a vector x and a matrix A, respectively. We use x to denote the standard Euclidean norm of a vector x. The notations 1 and I denote a vector whose all entries are 1 and the identity matrix of size n×n, respectively. EX denotes the expectation of a random variable X.


## 2. Algorithm Description and Assumptions

We consider a network which consists ofn agents (or nodes), indexed by 1,…,n. At each time t, the network topology is denoted by an undirected graph Gt=V,Et, where V=1,…,n denotes the set of agents and E⊂V×V denotes the set of edges. We assume that the undirected graph is simple. If there exists a directed edge from agent i to j at time t, then i,j∈Et. In a connected network, two agents are said to be neighbor of if the agents may be connected directly by an edge; that is, the agents can share information with each other. At time t, we denote the set of neighbors of agent i by Ni; that is, Ni=j∈V∣i,j∈Et. We also assume that communication links may be interrupted at random times.We consider an optimization problem as follows:(1)minimizeϕx≜∑i=1nϕixsubject  tox∈X≜⋂i=1nXi,where ϕi:Rd↦R denotes the convex objective function of agent i and Xi denotes constraint set of agent i.To solve problem (1), we propose an asynchronous distributed subgradient random projection algorithm based on randomized broadcast communication protocol. In this paper, we employ the asynchronous time model as in [21] and the randomized broadcast model as in [22].


### 2.1. Algorithm Description

In asynchronous model, each agent has a virtual clock, and the virtual clock ticks is a Poisson process with raten. We assume that one agent is waked up at a time. Thus, if an agent is waked up at time t, we use It to denote the index of the agent. Since the link can be randomly interrupted, we also use Jt to denote the subset of the neighbors of the agent It. Hence, the agent j∈Jt receives the broadcast information with probability pij; that is, if i,j∈Et, then pij>0. Each agent i∈Jt hears the broadcast information from agent It at time t. Hence, if i∉Jt, then(2)xit=xit-1,where xit denotes the estimate of agent i at time t. If i∈Jt, then the estimate of agent i is updated as follows:(3)zit=βxIkt-1+1-βxit-1xit=PXiωitzit-αit∇ϕizit+ϵit,where β∈0,1 is a mixing parameter, αit denotes the stepsize of agent i at time t, ωit denotes a random variable, ∇ϕizit denotes subgradient of function at x=zit, and ϵit is a stochastic subgradient error of agent i at time t. Moreover, let ωit be independent of each other and be independent from the random broadcast process. Note that ωit is drawn from the index set Θi. PXiωit denotes the Euclidean projection operation on the constraint set Xiωit.In order to analyze conveniently, we first define the following matrix:(4)Qt=I-β∑j∈JtejejT-ejeItT,where I is the identity matrix of size n×n and ej∈Rn denotes a vector with jth entry being 1 and the other entries being 0. From Lemma  2 in [26], each random matrix Qt is not doubly stochastic, but the expectation of matrix Qt is doubly stochastic. Let Dt≜Qt-1/n11TQt. We note that the matrices Dt are i.i.d. and λ≜λ1EDtTDt<1, where λ1A denotes the largest eigenvalue of a symmetric matrix A. Hence, by (4), relations (2)-(3) can be rewritten as follows:(5)zit=∑j=1nQtijxjt-1xit=zit-zitχi∈Jt+PXiωitzit-αit∇ϕizit+ϵitχi∈Jt,where χi∈Jt=1 if i∈Jt occurs, or else χi∈Jt=0.


### 2.2. Assumptions

In order to analyze the convergence properties of algorithm (5), we need to give some standard assumptions as follows.Assumption 1.
The network topologyGt=V,Et is connected and without self-loops at time t. If i,j∈Et, then pij>0. If i,j∉Et, then pij=0. Furthermore, the link failure process is independent and identically distribution.Assumption 2.
We assume that the constraint setsXij are nonempty closed and convex for all i∈V. We also assume that the cost function ϕi:Rd→R is convex. Moreover, we assume that the subgradient ∇ϕix of ϕix is uniformly bounded over X for every i∈V; namely, ∇ϕix≤Lmax for all x∈X.Assumption 3.
For any random variableωit∈Θi, i∈V, and for all x∈Rd, we assume that the following relation hold:(6)ρ2x,X≤ciEρ2x,Xiωit,where ci is a positive constant and ρx,X denotes the distance between a point x and a set X.In Assumption3, random variable ωit obeys a positive probability distribution. Moreover, if the set X has a nonempty interior, then Assumption 3 can be seen to hold [27].LetFt denote all the information generated by the entire history of algorithm (5). Next, we give the assumption for stochastic subgradient error ϵit as follows.Assumption 4.
For each agenti at time t, we assume that the error ϵit satisfies(7)Eϵit∣Ft-1,It,Jt=0,Eϵit∣Ft-1,It,Jt≤νwith probability 1, where ν is a positive constant.In this section, we propose an asynchronous distributed subgradient projection algorithm based on random projection operation and randomized broadcast communication protocol. Moreover, we also provide some standard assumptions to analyze the convergence properties of the algorithm. We will present main results of this paper in Section3.


## 2.1. Algorithm Description

In asynchronous model, each agent has a virtual clock, and the virtual clock ticks is a Poisson process with raten. We assume that one agent is waked up at a time. Thus, if an agent is waked up at time t, we use It to denote the index of the agent. Since the link can be randomly interrupted, we also use Jt to denote the subset of the neighbors of the agent It. Hence, the agent j∈Jt receives the broadcast information with probability pij; that is, if i,j∈Et, then pij>0. Each agent i∈Jt hears the broadcast information from agent It at time t. Hence, if i∉Jt, then(2)xit=xit-1,where xit denotes the estimate of agent i at time t. If i∈Jt, then the estimate of agent i is updated as follows:(3)zit=βxIkt-1+1-βxit-1xit=PXiωitzit-αit∇ϕizit+ϵit,where β∈0,1 is a mixing parameter, αit denotes the stepsize of agent i at time t, ωit denotes a random variable, ∇ϕizit denotes subgradient of function at x=zit, and ϵit is a stochastic subgradient error of agent i at time t. Moreover, let ωit be independent of each other and be independent from the random broadcast process. Note that ωit is drawn from the index set Θi. PXiωit denotes the Euclidean projection operation on the constraint set Xiωit.In order to analyze conveniently, we first define the following matrix:(4)Qt=I-β∑j∈JtejejT-ejeItT,where I is the identity matrix of size n×n and ej∈Rn denotes a vector with jth entry being 1 and the other entries being 0. From Lemma  2 in [26], each random matrix Qt is not doubly stochastic, but the expectation of matrix Qt is doubly stochastic. Let Dt≜Qt-1/n11TQt. We note that the matrices Dt are i.i.d. and λ≜λ1EDtTDt<1, where λ1A denotes the largest eigenvalue of a symmetric matrix A. Hence, by (4), relations (2)-(3) can be rewritten as follows:(5)zit=∑j=1nQtijxjt-1xit=zit-zitχi∈Jt+PXiωitzit-αit∇ϕizit+ϵitχi∈Jt,where χi∈Jt=1 if i∈Jt occurs, or else χi∈Jt=0.


## 2.2. Assumptions

In order to analyze the convergence properties of algorithm (5), we need to give some standard assumptions as follows.Assumption 1.
The network topologyGt=V,Et is connected and without self-loops at time t. If i,j∈Et, then pij>0. If i,j∉Et, then pij=0. Furthermore, the link failure process is independent and identically distribution.Assumption 2.
We assume that the constraint setsXij are nonempty closed and convex for all i∈V. We also assume that the cost function ϕi:Rd→R is convex. Moreover, we assume that the subgradient ∇ϕix of ϕix is uniformly bounded over X for every i∈V; namely, ∇ϕix≤Lmax for all x∈X.Assumption 3.
For any random variableωit∈Θi, i∈V, and for all x∈Rd, we assume that the following relation hold:(6)ρ2x,X≤ciEρ2x,Xiωit,where ci is a positive constant and ρx,X denotes the distance between a point x and a set X.In Assumption3, random variable ωit obeys a positive probability distribution. Moreover, if the set X has a nonempty interior, then Assumption 3 can be seen to hold [27].LetFt denote all the information generated by the entire history of algorithm (5). Next, we give the assumption for stochastic subgradient error ϵit as follows.Assumption 4.
For each agenti at time t, we assume that the error ϵit satisfies(7)Eϵit∣Ft-1,It,Jt=0,Eϵit∣Ft-1,It,Jt≤νwith probability 1, where ν is a positive constant.In this section, we propose an asynchronous distributed subgradient projection algorithm based on random projection operation and randomized broadcast communication protocol. Moreover, we also provide some standard assumptions to analyze the convergence properties of the algorithm. We will present main results of this paper in Section3.


## 3. Main Results

In this section, we provide the convergence properties of algorithm (5). The detailed proofs of main results are given in next section.We first define the optimal value and optimal solutions set of problem (1) as follows: (8)ϕ∗=minx∈X⁡ϕx,X∗=x∈X∣ϕx=ϕ∗.The first result states that our proposed algorithm is convergent with probability 1.Theorem 5.
Under Assumptions1–4, let the set of optimal point X∗ be nonempty. Let estimate sequence xit, i=1,…,n, be generated by algorithm (5) with positive stepsize αit=1/Φit, where Φit is the update number of agent i until time t. Then, the estimates of all agents converge to some optimal points x∗∈X∗ with probability 1.Theorem5 shows that the iterations of all agents asymptotic converge to some optimal points over time-varying networks; that is, for all i∈V, limt→∞xit=x∗ with probability 1.We also establish asymptotic error bound between some optimal points in the optimal set and the estimates of algorithm (5).Theorem 6.
Under Assumptions1–4, let estimate sequence xit, i=1,…,n, be generated by algorithm (5) and let αit=αi for t≥1. Moreover, assume that each function ϕix is δi-strongly convex, where the constant δi satisfies 0<2αiδi<1. Furthermore, let the set X be compact. Then, one has with probability 1
(a)(9)lim⁡supt→∞⁡1n∑i=1nExit-x∗2≤ΔγαLmaxLX+21+cγmaxαmax2Lmax2mini⁡γiδiαi+γmaxαmax2Lmax1-λmini⁡γiδiαi×2dLmax+ν2+81+cγmaxLmax2mini⁡γiδiαi,
(b)(10)lim⁡supt→∞⁡Eϕx~iT-ϕ∗⁡≤nγmaxαmax2Lmax1-λmini⁡γiαi×2dLmax+ν2+81+cγmaxLmax2mini⁡γiδiαi+nΔγαLmaxLX+2n1+cγmaxαmax2Lmax2mini⁡γiαi,where x~iT=1/T∑t=1T‍xit, d is dimension of vector, γi=1/n∑j∈Nit‍pij for all i∈V, γmax=maxiγi, αmax=maxiαi, LX=maxx,yx-y, and Δγα=maxiγiαi-miniγiαi.Theorem6 establishes asymptotic error bound, which is defined as the average of expected distances between some optimal points x∗∈X∗ and the estimates of algorithm (5). The asymptotic error is defined as the difference between the global cost function at x~iT and the global cost function at optimal point x∗.In this section, we provide the main results of this paper. The detailed proofs of main results are given in Sections4 and 5.


## 4. Analysis of Convergence Results

In this section, we provide the proof of Theorem5. For this purpose, we first establish a basic iterate relation for the estimates of algorithm (5).Lemma 7.
Under Assumptions1–4, the estimate sequence xit, i∈V, is generated by algorithm (5). Let αit=1/Φit and γi=1/n∑j∈Nitpij for all i∈V. Then, for any constant q∈0,1/2 and all vectors u∈X, one has with probability 1(11)Exit-u2∣Ft-1≤-2Eϕiyit-ϕiu∣Ft-1t-γiEρ2zit,X∣Ft-12c+2γiEyit-u2∣Ft-1t3/2-qpmin2+Ezit-u2∣Ft-1+2Lmax2t3/2-qpmin2+16n21+cLmax2t2pmin2for t≥t^, where yit=PXzit, pmin=min(i,j)⁡pij, and t^ is a sufficiently large positive constant.Proof.
Letu∈X. Following from the nonexpansive property [16], we have(12)xit-u2≤zit-u2-xit-zit2-2αit∇ϕizit+ϵit,zit-u+2αit∇ϕizit+ϵit,zit-xit.Further, from the definition of inner product and Cauchy-Schwarz inequality, we obtain(13)2αit∇ϕizit,zit-xit=2αit∇ϕizitTzit-xit≤2αit∇ϕizitzit-xit=22αit∇ϕizitzit-xit2≤4αi2t∇ϕizit2+zit-xit24≤4αi2tLmax2+14zit-xit2,where the second inequality follows from the inequality 2ab≤a2+b2. Hence, following from relations (12) and (13), we obtain(14)xit-u2≤zit-u2-2αitϕizit-ϕiu-34xit-zit2+4αi2tLmax2+2αitϵitTzit-xit-2αitϵitTzit-u.In addition, we also have(15)-2αitϕizit-ϕiu≤2αitLmaxzit-yit-2αitϕiyit-ϕiu≤4ηαi2tLmax2+14ηzit-yit2-2αitϕiyit-ϕiu,where the last inequality follows from the inequality 2ab≤τa2+b2/τ for some τ>0 by letting a=Lmaxαit, b=zit-yit, and τ=4η(η>0). Hence, combining relations (14) and (15), we obtain(16)xit-u2≤zit-u2-2αitϕiyit-ϕiu-34xit-zit2+14ηzit-yit2+4αi2t1+ηLmax2-2αitϵitTzit-u+2αitϵitTzit-xit.Next, we consider the term 2αitϕiyit-ϕiu in (16), which can be rewritten as follows:(17)2αitϕiyit-ϕiu=2tγiϕiyit-ϕiu+2αitϕiyit-ϕiu-2tγiϕiyit-ϕiu≥2tγiϕiyit-ϕiu-2αit-1tγiϕiyit-ϕiu.Thus, according to Lemma 3 of [26], there exists a sufficient large positive constant t^, for any t≥t^, we have(18)2αitϕiyit-ϕiu≥2tγiϕiyit-ϕiu-22t3/2-qpmin2Lmaxyit-u≥2tγiϕiyit-ϕiu-2t3/2-qpmin2Lmax2+yit-u2,where we use the Cauchy-Schwarz inequality. Then, from (16) and (18), we obtain(19)xit-u2≤zit-u2-2tγiϕiyit-ϕiu-34xit-zit2+2t3/2-qpmin2yit-u2+14ηzit-yit2+2αitϵitTzit-xit-2αitϵitTzit-u+2t3/2-qpmin2+16n2t2pmin21+ηLmax2.Note that zit-yit=ρzit,X; we have(20)xit-zit≥PXiωitzit-zit=ρzit,Xiωit.Hence, taking conditional expectation in both sides of (19) and using the fact that the mean of stochastic errors ϵit is zero, we obtain that with probability 1 for all t≥t^ and i∈Jt(21)Exit-u2∣Ft-1,It,Jt≤zit-u2-2tγiϕiyit-ϕiu-34Eρ2zit,Xiωit∣zit+2t3/2-qpmin2yit-u2+14ηρ2zit,X+2t3/2-qpmin2+16n2t2pmin21+ηLmax2.By Assumption 3, we have (22)Eρ2zit,Xiωit∣zit≥1cρ2zit,X,where c=maxi⁡ci. Let η=c. For all t≥t^, we obtain with probability 1(23)Exit-u2∣Ft-1,It,Jt≤zit-u2-2tγiϕiyit-ϕiu-12cρ2zit,X+2t3/2-qpmin2yit-u2+2t3/2-qpmin2+16n2t2pmin21+cLmax2.Note that xit=zit if i∉Jt. Besides, if i∈Jt, then the agent i updates its estimate with probability γi and does not update its estimate with probability 1-γi. Hence, following from (23), the desired result is obtained completely.We next consider the errorseit for all i∈V, which are caused by the random projection operation. The errors are defined as follows: eit=xit-zit for all i∈V. Moreover, we have the following lemma.Lemma 8.
Under Assumptions1–4, for t≥1 and all i∈1,…,n, the relations limt→∞ρzit,X=0 and ∑t=1∞Eρ2zit,X∣Ft-1<∞ hold with probability 1. Furthermore, for all i∈1,…,n, one has that limt→∞⁡ρzit,X=0 with probability 1.Proof.
Letu=yit=PXzit in Lemma 7. For all i∈1,…,n, we obtain with probability 1(24)Exit-PXzit2∣Ft-1=1+2t3/2-qpmin2Eρ2zit,X∣Ft-1-γi2cEρ2zit,X∣Ft-1+2t3/2-qpmin2+16n2t2pmin21+cLmax2,where t≥t^ with large enough t^ and q∈0,1/2. Since the function ρx,X is convex [28], we have(25)∑i=1nEρ2zit,X∣Ft-1≤∑j=1nρ2xjt-1,X.Combining (24), (25), and the definition of projection operation, we obtain for all t≥t^ with probability 1(26)∑i=1nExit-PXzit2∣Ft-1=1+2t3/2-qpmin2∑j=1nρ2xjt-1,X-γmin2c∑i=1nEρ2zit,X∣Ft-1+nLmax22t3/2-qpmin2+16n2t2pmin21+c,where γmin=mini⁡γi. Hence, following from the Supermartingale Convergence Theorem, which is stated in [29], we obtain ∑t=1∞Eρ2zit,X∣Ft-1<∞. Further, taking expectation on Ft in (26), we have that ∑t=1∞Eρ2zit,X<∞ for all i=1,…,n. By Monotone Convergence Theorem [30], we obtain i∈1,…,n; the relations limt→∞⁡ρzit,X=0.
Further, for alli∈Jt, following from the definition of error eit, we have(27)eit≤xit-yit+yit-zit=PXiωitzit-αit∇ϕizit+ϵit-yit+yit-zit.Moreover, note that yit∈Xiωit. Hence, we have(28)eit≤zit-αit∇ϕizit+ϵit-yit+yit-zit≤2zit-yit+αit∇ϕizit+ϵit=2ρzit,X+αit∇ϕizit+ϵit,where we use the nonexpansive property of the projection. Furthermore, following from the inequality a+b2≤2a2+b2, we obtain(29)eit2≤8ρ2zit,X+2αi2t∇ϕizit+ϵit2≤8ρ2zit,X+8n2t2pmin2∇ϕizit+ϵit2,where the last inequality follows from Lemma  3 in [26]. Taking the conditional expectation on both sides of (29), we have(30)Eeit2∣Ft-1≤8γiEρ2zit,X∣Ft-1+8γin2t2pmin2E∇ϕizit+ϵit2∣Ft-1≤8γiEρ2zit,X∣Ft-1+8γin2t2pmin2Lmax+ν2.Following from the fact that ∑t=1∞Eρ2zit,X∣Ft-1<∞ and ∑t=1∞1/t2<∞, we obtain with probability 1 ∑t=1∞Eeit2∣Ft-1<∞ for all i=1,…,n. Further, we also have limt→∞⁡eit=0 with probability 1. Therefore, the conclusions of this lemma are proved completely.We also establish the following lemma to prove the main results of this paper.Lemma 9.
Under Assumptions1–4, let αit=1/Φit. Assume that zit are generated by algorithm (5). Then, one finds ∑t=1∞1/tEzit-z¯t∣Ft-1<∞ with probability 1 for i=1,…,n, where z¯t=1/n∑i=1nzit.Proof.
We define the vectorvlt in Rn for l=1,…,d such that vlti=xitl for i=1,…,n. According to algorithm (5), we obtain(31)vlt=Qtvlt-1+ξltfort≥1,l=1,…,d,where ξlti=0 for i∉Jt, and if i∈Jt, then ξlti=PXiωitzit-αit∇ϕizit+ϵit-zitl. Further, note that x¯tl=1/n1Tvlt. Thus, by fixing arbitrary index l=1,…,d, we obtain(32)vlt-x¯tl1=Qt-1n11TQtvlt-1+I-1n11Tξlt.Since Qt1=1, Qt-1/n11TQt1=0. Thus, we have(33)vlt-x¯tl1=Dtvlt-1-x¯t-1l1+Hξlt,where H=I-1/n11T and we use the fact that Qt-1/n11TQtx¯t-1l1=0. Following from (33), we obtain with probability 1(34)Evlt-x¯tl1∣Ft-1≤EHξlt∣Ft-1+EDtvlt-1-x¯t-1l1∣Ft-1.We first compute the second term in right side of (34). According to the property of stochastic matrix Qt, we have(35)EDtvlt-1-x¯t-1l12∣Ft-1≤λvlt-1-x¯t-1l12.By using the inequality Ex≤Ex2, we have for t≥1(36)EDtvlt-1-x¯t-1l1∣Ft-1≤λvlt-1-x¯t-1l1.In addition, we have Hξlt2≤ξlt2 by using H2=I-1/n11T2=1. Hence, we obtain that(37)Hξlt2≤∑i=1nPXiωitzit-αit∇ϕizit+ϵit-zit2.Furthermore, from the nonexpansive property and αi2t≤4n2/t2pmin for t≥t^ with large enough t^, we find(38)Hξlt2≤∑i=1n8ρ2zit,X+8n2t2pmin2∇ϕizit+ϵit2.Thus, from (38), we have with probability 1(39)EHξlt∣Ft-1≤8n3t2pmin2Lmax+ν2+8∑i=1nEρ2zit,X∣Ft-1.Hence, from inequalities (36) and (39), we obtain(40)Evlt-x¯tl1∣Ft-1≤λvlt-1-x¯t-1l1+8n3t2pmin2Lmax+ν2+8∑i=1nEρ2zit,X∣Ft-1.Further, we obtain for t≥t^(41)1tEvlt-x¯tl1∣Ft-1≤1t-1vlt-1-x¯t-1l1-1-λtvlt-1-x¯t-1l1+1t8n3t2pmin2Lmax+ν2+8∑i=1nEρ2zit,X∣Ft-1.According to Lemma 8, the first term in (41) is convergent with probability 1. Moreover, since 1-λ>0 and then following from Supermartingale Convergence Theorem [29], we have(42)∑i=1n1tEvlt-x¯tl1∣Ft-1<∞.From the definition of vlt, we obtain for i∈V(43)∑i=1n1tExit-x¯t∣Ft-1<∞.From the convexity of norm and the definition of z¯t, we have(44)∑i=1nEzit-z¯t∣Ft-1≤∑j=1nxjt-1-x¯t-1.Thus, following from (43) and (44), we can see that(45)∑t=1∞1tEzit-z¯t∣Ft-1<∞for all i∈V with probability 1. Therefore, the lemma is proved completely.By using Lemmas7, 8, and 9, we start to prove Theorem 5.Proof of Theorem5.
From Lemma7, we obtain(46)∑i=1nExit-u2∣Ft-1≤1+2t3/2-qpmin2∑j=1nxjt-1-u2-2t∑i=1nEϕiyit-ϕiu∣Ft-1+nLmax22t3/2-qpmin2+16n2t2pmin21+c.Letting y¯t≜1/n∑i=1nyit, then y¯t∈X. Therefore, we have(47)∑i=1nϕiyit-ϕiu=∑i=1nϕiyit-ϕiy¯t+ϕy¯t-ϕu.By the convexity of each function ϕi and the boundedness of each subgradient norm ∇ϕi, we have(48)∑i=1nϕiyit-ϕiy¯t≥∑i=1n∇ϕiy¯tyit-y¯t≥-∑i=1n∇ϕiy¯tyit-y¯t≥-Lmax∑i=1nyit-y¯t.Furthermore, according to the convexity of squared-norm, we obtain(49)yit-y¯t=1n∑k=1nyit-ykt≤1n∑k=1nyit-ykt≤1n∑k=1nzit-zkt,where the last inequality uses the nonexpansive property.
Letz¯t=1/n∑i=1nzit. Moreover, we also have(50)zit-zkt≤zit-z¯t+zkt-z¯t.Hence, combining inequalities (49) and (50) and then summing over i from 1 to n, we have(51)∑i=1nyit-y¯t≤2∑i=1nzit-z¯t.Thus, from (47), (48), and (51), we obtain(52)∑i=1nϕiyit-ϕiu≥-2Lmax∑i=1nzit-z¯t+ϕy¯t-ϕu.Let u=x∗. Following from inequalities (46) and (52), we have with probability 1(53)∑i=1nExit-x∗2∣Ft-1≤1+2t3/2-qpmin2∑j=1nxjt-1-x∗2-2tEϕy¯t-ϕ∗∣Ft-1+4Lmaxt∑i=1nEzit-z¯t∣Ft-1+nLmax22t3/2-qpmin2+16n2t2pmin21+c.Moreover, note that ϕy¯t-ϕ∗≥0. Hence, by using Supermartingale Convergence Theorem [29] and Lemma 9, for all i∈V, we find that xit-x∗2 is convergent with probability 1. Moreover, ∑t=1∞1/tϕy¯t-ϕ∗<∞ hold with probability 1. Further, noting that ∑t=1∞1/t=∞, we have with probability 1(54)lim⁡inft→∞⁡ϕy¯t-ϕ∗=0.Hence, from the definition of yit and Lemma 8, we obtain with probability 1(55)limt→∞⁡zit-yit=0∀i∈Jt.Since xit-x∗ is convergent with probability 1, zit-x∗ and yit-x∗ are also convergent by using (5) and (55). Therefore, z¯t-x∗ and y¯t-x∗ are convergent with probability 1. According to (54), we obtain with probability 1 limt→∞y¯t=x∗. We further have limt→∞z¯t-y¯t⩽1/n∑k=1n‍limt→∞zkt-ykt=0. Hence, we obtain with probability 1 limt→∞z¯t=x∗. Following from Lemma 9, we have with probability 1 liminft→∞zit-z¯t=0. Therefore, we obtain limt→∞zit-x∗=0 with probability 1. Moreover, according to Lemma 9, the statement of this theorem is obtained completely.In this section, we have given a proof of Theorem5. From this theorem, we can see that the proposed algorithm is almost sure convergent. In next section, we will analyze the error bounds of the proposed algorithm.


## 5. Error Bounds Analysis

In this section, we give the proof of Theorem6, where we assume that the cost function ϕi is strongly convex with constant δi and the stepsize αit is constant for all i∈V; that is, αit=αi. To prove Theorem 6, we first establish a basic iterate relation for a constant stepsize as follows.Lemma 10.
Under Assumptions1–4, let the estimate sequence xit, i∈V, be generated by algorithm (5). Moreover, αit=αi for all i=1,…,n, assuming that each function ϕix is δi-strongly convex, where the constant δi satisfies 0<2αiδi<1. Then, with probability 1, the following relation holds for all i∈Jt and t≥1:(56)Exit-u2∣Ft-1,It,Jt≤1-2δiαizit-u2-2αi∇ϕiuTyit-u+41+cαi2Lmax2.Proof.
Sincexit∈Xiωit, we have(57)Exit-u2∣Ft-1,It,Jt≤zit-u2-34Eρ2zit,Xiωit∣zit-2αi∇ϕizitTzit-u+4αi2Lmax2.Moreover, we also have(58)∇ϕizitTzit-u≥∇ϕiuTzit-u+δizit-u2,where the inequality follows from the fact that the function ϕi is strongly convex. Further, by using Assumption 2, we obtain(59)∇ϕiuTzit-u≥∇ϕiuTyit-u-Lmaxzit-yit.Combining (57), (58), and (59), we obtain(60)Exit-u2∣Ft-1,It,Jt≤1-2δiαizit-u2-34Eρ2zit,Xiωit∣zit+4αi2Lmax2-2αi∇ϕiuTyit-u+2αiLmaxρzit,X≤1-2δiαizit-u2-2αi∇ϕiuTyit-u-34Eρ2zit,Xiωit∣zit+4αi2Lmax2+4cαi2Lmax2+14cρ2zit,X.By Assumption 3, we see that(61)ρ2zit,X≤cEρ2zit,Xiωit∣Ft-1,It,JtFollowing from inequality (61), we have(62)-34Eρ2zit,Xiωit∣zit+14cρ2zit,X≤-12cρ2zit,X≤0.From (60) and (62), the conclusion of this lemma is obtained.Further, we also establish the following lemma.Lemma 11.
Under Assumptions1–4, let the estimate sequence xit, i∈V, be generated by algorithm (5). Let αit=αi and assume that each function ϕi is δi-strongly convex, where the constant δi satisfies 0<2αiδi<1. Then, we have with probability 1 (a)
(63)lim⁡supt→∞⁡∑i=1nEρ2xit,X∣Ft-1≤21+cnLmax2maxi⁡γiαi2mini⁡γiδiαi.(b)
(64)lim⁡supt→∞⁡∑i=1nExit-x¯t2≤2αmax2nd1-λ2Lmax+ν2+81+cγmaxLmax2mini⁡γiδiαi,where d is the dimension of vector xit, αmax=maxiαi, and γmax=maxiγi.Proof.
Lettingu=yit=PXzit in Lemma 10 and then following from the fact that ρxit,X≤xit-yit, for t≥1 and all i∈Jt, we have(65)Eρ2xit,X∣Ft-1,It,Jt≤1-2δiαiρ2zit,X+41+cαi2Lmax2.Note that the communication mode employs asynchronous broadcast protocol. Hence, we obtain with probability 1(66)Eρ2xit,X∣Ft-1≤1-2γiδiαiρ2zit,X+41+cγiαi2Lmax2.Summing (66) over i from 1 to n and then following from (25), we obtain(67)∑i=1nEρ2xit,X∣Ft-1≤41+cnLmax2maxi⁡γiαi2+1-2mini⁡γiδiαi∑j=1nρ2xjt-1,X.Therefore, from Lemma 6 in [26], the desired result is obtained.
(b) Summing (34) over l from 1 to d, we obtain(68)∑l=1dEvlt-x¯tl12≤∑l=1dEDtvlt-1-x¯t-1l12+∑l=1dEHξlt22,where the inequality follows from Hölder’s inequality. From the definitions of Dt and H and then from (35), we have(69)∑l=1dEDtvlt-1-x¯t-1l12≤λ∑l=1dvlt-1-x¯t-1l12.In addition, we also have(70)∑l=1dEHξlt2≤8d∑i=1nEρ2zit,X+2αmax2ndLmax+ν2.Letting κt=∑l=1dEvlt-x¯tl12 and then following from (68), (69), and (70), we obtain(71)κt=λκt-1+2αmax2ndLmax+ν2+8d∑i=1nEρ2zit,X.Following from Lemma 6 in [26], we have(72)lim⁡supt→∞⁡κt≤11-λ×lim⁡supt→∞⁡2αmax2ndLmax+ν2+8d∑i=1nEρ2zit,X.Therefore, we have(73)lim⁡supt→∞⁡κ2t≤2αmax2ndLmax+ν21-λ2+lim⁡supt→∞⁡8d∑j=1nEρ2xjt-1,X1-λ2.Besides, we have κ2t=∑i=1nExit-x¯t2. Therefore, by inequality (73) and part (a) of this lemma, part (b) is obtained.We now start to prove Theorem6.Proof of Theorem6.
(a) Letu=x∗ in Lemma 10. Moreover, we have(74)∇ϕix∗Tyit-x∗≥∇ϕix∗Ty¯t-x∗-Lmaxyit-y¯t.Thus, from Lemma 10 and (74), for all i∈Jt, we obtain(75)Exit-x∗2∣Ft-1,It,Jt≤1-2δiαizit-x∗2-2αiE∇ϕix∗Ty¯t-x∗∣Ft-1+41+cαi2Lmax2+2αiLmaxyit-y¯t,where we use the fact that the communication mode employs asynchronous broadcast protocol. Further, we obtain(76)Exit-x∗2∣Ft-1≤1-2γiδiαiEzit-x∗2∣Ft-1-2miniγiαiE∇ϕix∗Ty¯t-x∗∣Ft-1+2ΔγαE∇ϕix∗y¯t-x∗∣Ft-1+2γiαiLmaxEyit-y¯t∣Ft-1+41+cγiαi2Lmax2,where Δγα=maxiγiαi-miniγiαi. Moreover, we also have(77)∇ϕix∗y¯t-x∗≤LmaxLX,where LX=maxx,yx-y. Hence, summing (76) over i, we have(78)∑i=1nExit-x∗2∣Ft-1≤1-2mini⁡γiδiαi∑j=1nExjt-1-x∗2∣Ft-1+2γmaxαmaxLmax∑i=1nEyit-y¯t∣Ft-1+2nΔγαLmaxLX+41+cnγmaxαmax2Lmax2.Thus, from (78), we have(79)lim⁡supt→∞⁡1n∑i=1nExit-x∗2≤ΔγαLmaxLX+21+cγmaxαmax2Lmax2mini⁡γiδiαi+γmaxαmaxLmaxnmini⁡γiδiαilim⁡supt→∞⁡∑i=1nEyit-y¯t.Besides, we also obtain(80)∑i=1nEyit-y¯t≤n∑i=1nEyit-y¯t2≤n∑i=1nEzit-z¯t2≤n∑j=1nExjt-1-x¯t-12.Hence, combining (80) and Lemma 11(b), we have(81)lim⁡supt→∞⁡∑i=1nEyit-y¯t≤αmaxn1-λ2dLmax+ν2+81+cγmaxLmax2mini⁡γiδiαi.Therefore, the conclusion of part (a) is proved.
(b) From (76) and (77), we have(82)Exit-x∗2∣Ft-1≤1-2γiδiαiEzit-x∗2∣Ft-1-2mini⁡γiαiϕiy¯t-ϕix∗+2γmaxαmaxLmaxEyit-y¯t∣Ft-1+2ΔγαLmaxLX+41+cγmaxαmax2Lmax2.Due to (83)∑i=1nEzit-x∗2∣Ft-1≤∑j=1nxit-1-x∗2,by using the above relation and by some algebraic operations, we obtain with probability 1(84)Eϕxit-1-ϕ∗≤1-2γiδiαi2mini⁡γiαi×∑j=1nExjt-1-x∗2-∑i=1nExit-x∗2+γmaxαmaxLmaxmini⁡γiαi∑i=1nEyit-y¯t+nΔγαLmaxLX+2n1+cγmaxαmax2Lmax2mini⁡γiαi+Lmaxmini⁡γiαi∑i=1nExit-1-y¯t-1,where we use the following relation:(85)ϕxit-1-ϕ∗≤ϕy¯t-1-ϕ∗+Lmax∑j=1nxjt-1-y¯t-1.Hence, summing (84) over t from 1 to T and then taking the average, we have(86)1T∑t=1TEϕxit-1-ϕ∗≤1-2γiδiαi2Tmini⁡γiαi∑j=1nExj0-x∗2+γmaxαmaxLmaxmini⁡γiαi1T∑t=1T∑i=1nEyit-y¯t+nΔγαLmaxLX+2n1+cγmaxαmax2Lmax2mini⁡γiαi+Lmaxmini⁡γiαi1T∑t=1T∑i=1nExit-1-y¯t-1.Letting T→∞, we obtain(87)lim⁡supT→∞⁡1T∑t=1TEϕxit-1-ϕ∗≤γmaxαmaxLmaxmini⁡γiαilim⁡supt→∞⁡∑i=1nEyit-y¯t+Lmaxmini⁡γiαilim⁡supt→∞⁡∑i=1nExit-1-y¯t-1+nΔγαLmaxLX+2n1+cγmaxαmax2Lmax2mini⁡γiαi,where the inequality follows from inequality limsupT→∞1/T∑t=1T‍θt=limsupt→∞θt. Next, we compute the term limsupt→∞∑i=1nEyit-y¯t. From triangle inequality, we have(88)∑i=1nExit-y¯t≤∑i=1nExit-zit+zit-y¯t.Further, from the definition of y¯t and then by the convexity of norm, we obtain(89)∑i=1nEzit-y¯t≤∑i=1nEzit-yit=∑i=1nEρzit,X.Hence, according to Lemma 8, we have for all i∈V(90)lim⁡supt→∞⁡∑i=1nExit-y¯t=0.Following from (81) and (90), with probability 1 we have for all i∈V and t≥1(91)lim⁡supT→∞⁡1T∑t=1TEϕxit-1-ϕ∗≤nΔγαLmaxLX+2n1+cγmaxαmax2Lmax2mini⁡γiαi+nγmaxαmax2Lmax1-λmini⁡γiαi×2dLmax+ν2+81+cγmaxLmax2mini⁡γiσiαi.Therefore, by the convexity of global cost function ϕ, part (b) is obtained.


## 6. Conclusion

In this paper, we have considered a constrained distributed optimization problem. Moreover, the global cost function is a sum of local convex function and each agent only knows its own cost function and has access to noisy subgradient of its own objective function. However, each agent does not know constraint set in advance. To solve this problem, we proposed a distributed optimization algorithm over a time-varying network. The algorithm employs random projection method and the communication protocol uses broadcast communication protocol in an asynchronous way. We have showed that the proposed algorithm is convergent with probability 1 by choosing suitable stepsizes. We have also established two asymptotic error bounds with appropriately chosen stepsizes.



---

*Source: 1793291-2017-09-28.xml*