# Distributed Stochastic Subgradient Projection Algorithms Based on Weight-Balancing over Time-Varying Directed Graphs

Authors: Junlong Zhu; Ping Xie; Mingchuan Zhang; Ruijuan Zheng; Ling Xing; Qingtao Wu
Journal: Complexity
 (2019)

---

## Abstract

We consider a distributed constrained optimization problem over graphs, where cost function of each agent is private. Moreover, we assume that the graphs are time-varying and directed. In order to address such problem, a fully decentralized stochastic subgradient projection algorithm is proposed over time-varying directed graphs. However, since the graphs are directed, the weight matrix may not be a doubly stochastic matrix. Therefore, we overcome this difficulty by using weight-balancing technique. By choosing appropriate step-sizes, we show that iterations of all agents asymptotically converge to some optimal solutions. Further, by our analysis, convergence rate of our proposed algorithm isO(lnΓ/Γ) under local strong convexity, where Γ is the number of iterations. In addition, under local convexity, we prove that our proposed algorithm can converge with rate O(lnΓ/Γ). In addition, we verify the theoretical results through simulations.


---

## Body

## 1. Introduction

In this paper, we focus on distributed constrained optimization problems, which have arisen in many applications. For instance, large-scale machine learning [1–4], resource allocation [5, 6], sensor networks [7–10], and multiagent systems [11]. To address such problems, the designs of distributed optimization algorithms are necessary. Moreover, the goal is to minimize the sum of cost functions of all agents over networks, where each agent only knows its own information and can receive the information from its neighbors.Distributed optimization algorithms are originally introduced in seminal work [12] and have a vast literature devoted to them in recent years [13–19]. In this literature, the distributed (sub)gradient methods are used over networks. Moreover, the performance limitations and convergence rates of these algorithms are well understood. In addition, the distributed Newton methods and other descent methods are used to solve the distributed optimization problems [20, 21], and their rates of convergence are also analyzed.However, these methods cited above assumed that information exchange among agents takes place over either fixed or undirected graphs. Nevertheless, in some communication networks such as mobile sensor networks, the communication between agents is unidirectional because different agents have different interference and noise patterns, the information are broadcasted at different power level, and the communication links between agents are directed in these networks [22–24]. Hence, the directed network topology is a natural assumption. In addition, the time-varying communication network topology is also a valid assumption in wireless networks, where each agent can move or the communication links may be destroyed randomly. For these reasons, we assume that these network topologies can be modeled as time-varying directed graphs. In this paper, we assume that each out-degree is known to each agent at each round, where the assumption cannot be removed [25]. To obtain knowledge of the out-degree, we can bidirectionally exchange “Hello” messages in a single communication process.In fact, the recent works [22, 23] provide subgradient-push distributed algorithms to minimize the cost function over time-varying directed network in discrete-time. Similarly, [24] proposes a distributed subgradient algorithm, which used weight-balancing in discrete-time. In addition, [26] considers a continuous-time optimization algorithm over underlying time-varying directed networks. Moreover, the distributed algorithms in [22, 24] converge with rate O(lnΓ/Γ), whereas in [23], their algorithm converges with rate O(lnΓ/Γ) by assuming that the local cost functions are differentiable and strongly convex. Nevertheless, these works consider the unconstrained optimization problem. In [27], the authors propose the D-DPS algorithm over a directed network with convergence rate O(lnΓ/Γ). However, we assume that the graph is time-varying and directed in this paper. To overcome the asymmetry caused by directed graphs, we employ the weight-balancing technique in the paper. Hence, a distributed stochastic subgradient projection algorithm is proposed, based on weight-balancing technique. Assume that each local cost function is strongly convex; even if all agents have access to their own noisy subgradient, our proposed algorithm is asymptotically convergent with rate O(lnΓ/Γ). Besides, our proposed algorithm also asymptotically converges with rate O(lnΓ/Γ) for generally convex cost functions. Compared with the best previous convergence rate of O(1/Γ), which is achieved in centralized way, where the local functions are strongly convex and differentiable, the variance of noisy subgradient is bounded [28, 29]. Thus, our convergence results are quite close to it. However, we need not assume that local cost functions are differentiable. In addition, we assume that local cost functions do not establish Lipschitz continuous gradients.Our goal is to design a distributed optimization algorithm and analyze the properties of the proposed algorithm, based on weight-balancing over time-varying directed networks. This work has the following contributions:(i)
We propose a distributed stochastic subgradient projection algorithm based on weight-balancing over time-varying directed networks. Furthermore, each local cost function is private information for other agents. Hence, each agent only utilizes its own private information. Moreover, noisy subgradientsi of local cost function gi is known to each agent i for i=1,…,N. In addition, the algorithm is implemented without any centralized control, and every agent need not to know network topology and only requires to know its out-degree at each round.(ii)
By some standard assumptions, we show that our proposed algorithm asymptotically converges to some optimal solutions.(iii)
For strongly convex cost functions, we prove that the convergence rate ofO(lnΓ/Γ) is achieved. In addition, we also show that the convergence rate is O(lnΓ/Γ) for locally convex cost functions.Organization. In Section 2, the constrained optimization problem is described, we also give some assumptions, and then a distributed stochastic subgradient projection algorithm is proposed over time-varying directed networks. We state the main results of this paper in Section 3. We provide the proofs of the main results in Section 4. In Section 5, simulations are also presented. The conclusion of the paper is provided in Section 6.Notation. We use lowercase boldface to denote the vectors in Rd and use lowercase normal font to denote scalars or vectors, which are not d-dimensional vectors. For instance, uiτ denotes a vector in Rd at agent i at round τ, while the notation yiτ is a scalar in R. The vector such as yτ in RN is obtained by stacking all scalars yiτ for i=1,…,N. In addition, we use the natation “T” to denote transpose operation. u is the Euclidean norm of u. Besides, the notation u1 is 1-norm of u. The notation 1 denotes a N-dimensional vector whose all elements are 1, and I is identity matrix, whose size is N×N. E· denotes the expectation operator. Besides, the notation ΠUu means that a vector u is projected onto the constraint set U. The notation ⊗ denotes Kronecker product operator.


## 2. Problem Setup, Algorithm Description, and Assumptions

We use a graph to model a network, which consists ofN agents. Moreover, each agent represents a node. Further, we also consider the case that network topology is time-varying and directed. Hence, we use the notation Gτ=V,Eτ to denote network topology at each round τ, where V denotes the agent set and Eτ denotes the directed edge set. j,i∈Eτ means that agent j can send message to agent i at round τ. If two agents can directly exchange information, then we say the agents are neighboring. Furthermore, we use Njoutτ and Njinτ to represent the set of out-neighbors and the set of in-neighbors of agent j at round τ, respectively. Formally, Njoutτ=k∣j,k∈Eτ,k∈V and Njinτ=k∣k,j∈Eτ,k∈V, respectively. Besides, we denote the out-degree and in-degree by djoutτ=Njoutτ and djinτ=Njinτ, respectively.In this paper, the constrained optimization problem is described as follows:(1)minimizeugu=∑i=1Ngius.t.u∈U,where gi:Rd→R denotes local cost function of agent i and U⊆Rd denotes constraint set.Our goal is to solve problem (1) by cooperative and fully decentralized way over time-varying and directed networks. Further, each local cost function gi can be only known to each agent i and all agents know constraint set U. Moreover, each agent can share its own iteration with its out-neighbors.In this paper, we assume that the network topology is time-varying and directed. Note that the directed graph may cause the asymmetry. Thus, to overcome the asymmetry, we employ the weight-balancing technique in the paper. Following from [24], we give the definition of balancing weights over time-varying directed networks as follows.Definition 1 (balancing weights).
The weightwi,ϱ(τ) of agent i, i∈V, balances a time-varying directed network at round τ if, for any agent i, the agent weight wi,ϱ(τ) satisfies (2)wi,ϱτdioutτ=∑j∈Niinτwj,ϱτ,where ϱ(τ) is the index of relationships of neighbors at time τ.From Definition1, the total weight incoming from agent i (which is ∑j∈Niinτ‍wj,ϱ(τ)) is equal to the total outgoing weight of agent i (which is wi,ϱ(τ)dioutτ) at round τ over a time-varying directed network.In order to solve problem (1) over a time-varying directed graph Gτ, we first give some standard assumptions as follows.Assumption 2.
Assume that the time-varying directed network sequenceGτ is strongly connected at each round τ.Assumption2 ensures that each agent can receive information from the other agents at round τ in network Gτ.Assumption 3.
Let constraint setU⊆Rd be closed and convex. In addition, assuming that local cost function giu is convex with σi≥0, for all i∈V, i.e., for u,v∈U, each local cost function gi satisfies(3)giu-giv≥∇givTu-v+σi2u-v2,where ∇giv denotes a (sub)gradient of giu at u=v. If σi>0, giv is σi-strongly convex. Otherwise, giv is convex.Assumption3 ensures that the set of subgradients ∂gi is nonempty. Besides, the assumption on the subgradient is provided as follows. The similar assumption can be found in [13, 24, 27].Assumption 4.
We assume that the subgradient∇giu of giu is uniformly bounded over U for i∈V. Namely, ∇giu≤Li, for all u∈U.Next, we describe our proposed optimization algorithm which is executed over a time-varying directed network. Assume thatuiτ∈U is the iteration of agent i at round τ. Moreover, the iteration uiτ is updated as follows:(4)viτ=1-wiτdioutτuiτ+∑j∈Niinτwjτujτ,(5)uiτ+1=ΠUviτ-ατsiτ,for all i∈V, where ατ denotes a step-size sequence and we use siτ to abbreviate the notation siuiτ, which represents a noisy subgradient of giu at u=uiτ. Following from (4)-(5), each agent i first linearly fuses from its own estimate and the estimates of in-coming neighbor agents and updates the estimate in opposite direction of its own noisy subgradient. Finally, a new estimate of agent i is obtained by projecting the updated estimate onto the constraint set U. Moreover, the above update equations can be executed by simple broadcast communication.From (5), we need to make some assumptions about the noisy subgradient. Specifically, we describe the noisy subgradient siuiτ as follows:(6)siuiτ=∇giuiτ+ϵiτ,where ϵiτ∈U denotes a stochastic subgradient error and ∇giuiτ denotes a subgradient of giu at u=uiτ. Let Fτ denote all the information generated by the distributed stochastic subgradient projection algorithms (4)-(5) for all τ≥0. Hence, the assumption for stochastic subgradient error ϵiτ is as follows.Assumption 5.
For everyi, i=1,…,N, we assume that the stochastic subgradient error ϵiτ at round τ≥1 is a random variable with Eϵiτ∣Fτ-1=0. Moreover, assume that ϵiτ are independent of each other. Assume that the noise-norm ϵiτ at round τ≥1 is uniformly bounded, i.e., Eϵiτ∣Fτ-1≤νi, where νi is a positive scalar.In our proposed algorithm,wiτ is weight of agent i at round τ. As with [24], every agent i updates its weight wiτ over time-varying directed networks as follows:(7)wiτ+1=12wiτ+1dioutτ∑j∈Niinτ12wjτ.In this paper, let the optimal set of the proposed algorithms be nonempty, which can be defined as follows:(8)U∗≜u∣gu=g∗,u∈U,where g∗≜gu∗≜minu∈Ugu.First, we formally introduce the constrained optimization problem in this section, and then we also give some valid assumptions. Simultaneously, a distributed stochastic subgradient projection algorithm is proposed to solve constrained optimization problem (1) over time-varying directed networks. The main results of the paper are presented in the next section.


## 3. Main Results

We first present an asymptotic convergence of the distributed stochastic subgradient projection algorithms (4)-(5) with appropriately chosen step-sizes. Specifically, the result is described as follows.Theorem 6.
Under Assumptions2–5, let the optimal set U∗ be nonempty. Moreover, for the positive step-size ατ, which satisfies decay conditions (26), let sequences uiτ, i=1,…,N, be generated by algorithms (4)-(5). Then, each sequence uiτ converges to some optimal solutions u∗ in U∗ with probability 1 for all i∈V. Namely, for all i∈V, limτ→∞uiτ=u∗ holds with probability 1.By Theorem6, the iterations asymptotically converge to some optimal solutions over time-varying directed networks. Namely, by our proposed algorithm, we can obtain some optimal solutions with probability 1.We now state convergence rate of our proposed algorithm. Under different assumptions about local cost functionsgi, we establish the different convergence rate. To this end, we first introduce the weighted average of the estimate sequence uiττ≥0, which is defined as [23](9)u^iτ=∑t=1τt-1uitττ-1/2,for all τ≥2. Hence, for all τ≥1, we have the following recursive relation:(10)u^iτ+1=τuiτ+1+Sτu^iτSτ+1,for all i∈V, where Sτ=ττ-1/2, for all τ≥2, and u^i1=ui0.Theorem 7.
Under Assumptions2–5, let ατ=μ/τ+1, where the positive constant μ satisfies(11)μ∑i=1NσiN≥4.Then, we obtain(12)Egu^iΓ-gu∗+∑j=1NσjujΓ-u∗≤10LCΓλ1-λ∑j=1Nuj01+μ1-λ∑i=1NdLi+νi1+lnΓ-1+8μΓ∑i=1NLi+νi2,for all i∈V, where Li, νi, and C are positive constants, λ∈0,1, L=∑i=1N‍Li, σi>0, and Γ denotes the number of iterations.From Theorem7, we establish the convergence rate when local cost functions are strongly convex. Moreover, gu^iΓ converges to gu∗ for any agent i with probability 1. Further, following from (12), the numerator has an lnΓ or a constant and the denominator has a Γ. Therefore, our algorithm converges to some optimal solutions with probability 1 at rate of OlnΓ/Γ.Theorem 8.
Under Assumptions2–5, let ατ=1/τ+1 for τ≥0. Then, for all i=1,…,N, we obtain that with probability 1(13)Egu~iΓ-gu∗≤3LC∑j=1Nuj011-λΓ+1+9LClnΓ+11-λΓ+1∑j=1N2dLj+νj+21+lnΓ+1Γ+1∑i=1NLi+νi2+N2Γ+1u¯0-u∗2,where u~iΓ is defined as (101), Li, νi, and C are positive constants, λ∈0,1, L=∑i=1N‍Li, and Γ denotes the number of iterations.Theorem8 gives the convergence rate of our proposed algorithm for local convex functions, which is O(lnΓ/Γ). Further, by Theorems 7 and 8, we can see that the time-varying and directed network topology does not affect the convergence rate.In this section, we show that our proposed algorithm is asymptotically convergent. For strongly convex functions, we derive a convergence rateO(lnΓ/Γ) for our algorithm over time-varying directed networks. Furthermore, we also present that our algorithm converges with rate O(lnΓ/Γ) under general convexity. In the next section, we will give the detailed proofs of main results.


## 4. Analysis of Convergence Results

We give relevant proof for our main results, namely, Theorems6, 7, and 8. For this purpose, a basic iterate relation is established. Then, we use the basic relation to prove our main results.For the sake of analysis, we first describe the scalar version of (4)-(5), where the variables uiτ and viτ are scalar variables, for all i∈V. Thus, the estimate uiτ of agent i is updated by(14)viτ=1-wiτdioutτuiτ+∑j∈Niinτwjτujτ,(15)uiτ+1=ΠUviτ-ατsiτ,for τ≥0 and all i∈V, where sik=∇giuiτ+ϵiτ and U⊆R denotes a constraint set.To facilitate analysis, we can rewrite algorithms (14)-(15) in a compact form, namely,(16)vτ=Wτuτ,(17)uτ+1=ΠUvτ-ατsτ,where the matrix Wτ is defined as follows: for any i and j∈Niinτ, Wτij=wjτ, Wτii=1-wiτdioutτ at each round τ. Moreover, we also define the following variables uτ and sτ: (18)uτ≜u1τ,…,uNτT,sτ≜s1τ,…,sNτT.To analyze our proposed algorithm, we rewrite algorithms (16)-(17) as follows:(19)vτ=Wτuτ,uτ+1=vτ-ατsτ+δτ,(20)δτ=ΠUvτ-ατgτ-vτ-ατsτ.Hence, letrτ=δτ-ατsτ, which can be referred as the perturbation. Then, following from (19)-(20), we have(21)uτ+1=WτWτ-1⋯W0u0+∑t=0τ-1Wτ⋯Wt+1rt+rτfor any t and τ with τ≥t. Furthermore, we introduce the following matrix: (22)Δτ:t≜Wt⋯Wτfor any t and τ with τ≥t, and Δτ,τ=Wτ. Hence, from (21), we have(23)uτ+1=Δτ:0u0+∑t=0τΔτ:t+1rtfor any t and τ with τ≥t. Moreover, let Δτ:τ+1=I for convenience.Moreover, sinceWτ is a sequence of column stochastic, which is proved in Lemma 9, we have 1TWτ=1T. Hence, following from (23), we have(24)1Tuτ+1=1Tu0+∑t=0τ1Trtfor  allτ≥0.Since the matricesWτ and Δτ:t are crucial in convergence analysis of our proposed algorithm, we first provide some proprieties of these matrices.Lemma 9.
We assume that Assumption2 holds. Then, for any τ≥0, the matrix Wτ is column stochastic. Moreover, for all i,j∈V, there exist some positive constants C and λ∈0,1, and the matrix Δτ:t satisfies(25)Δτ:tij-1N≤Cλτ-t+1for any t and τ with τ≥t.According to [24] (the proofs of Lemma 3 and Proposition  1 in [24]), we immediately obtain this lemma.In addition, we also give the properties of the projection operatorΠU·. Following from [14], we have the following.Lemma 10.
Assume that constraint setU is closed and convex in Rd. Furthermore, we assume that U is nonempty. Thus, we conclude that for any u∈Rd,(1)ΠUu-uTv-ΠUu≥0, for all v∈U(2)ΠUu-ΠUv≤u-v for any v∈Rd(3)ΠUu-uTu-v≤-ΠUu-u2, for all v∈U(4)ΠUu-v2+ΠUu-u2≤u-v2, for all v∈U.Besides, we present some auxiliary results as follows, which are used to prove the relative conclusions.Lemma 11 (see [30]).
We assume thatρn is a scalar for all positive integer n.(i) Iflimn→∞ρn=ρ, then we have limn→∞∑m=0nθn-mρm=ρ/1-θ for any θ∈(0,1).(ii) If∑n=0∞‍ρn<∞ and ρn≥0, then, for θ∈(0,1), we have ∑n=0∞‍∑m=0n‍θn-mρm<∞.In order to obtain a convergence result of algorithms (16)-(17), we first establish the following lemma.Lemma 12.
We assume that Assumptions2–3 hold. Let estimate sequence uiτ, i∈V, be generated by (16)-(17). Moreover, for τ>t≥1, the positive sequence ατ satisfies the following decay conditions:(26)∑τ=1∞ατ=∞,∑τ=1∞α2τ<∞,ατ≤αt.(a) Fori=1,…,N, we conclude that(27)uiτ-1TuτN≤Cλτu01+∑t=0τ-1λτ-t-1rt1.(b) Iflimτ→∞riτ=0 for i=1,…,N, we obtain(28)limτ→∞uiτ-1TuτN=0.(c) If∑τ=1∞ατriτ<∞, then, we obtain(29)∑τ=1∞ατuiτ-1TuτN<∞,for all i=1,…,N.Proof.
(a) From (23) and (24), we have(30)uiτ-1TuτN=Δτ-1:0u0i-∑t=0τ-1Δτ-1:t+1rti-1N1Tu0+1N∑t=0τ-11Trt≤maxjΔτ-1:0ij-1N×u01+∑t=0τ-1rt1maxjΔτ-1:t+1ij-1N≤Cλτu01+∑t=0τ-1Cλτ-t-1rt1,where we use Ho¨lder’s inequality to obtain the first inequality, and we also obtain the last inequality by Lemma 9. Hence, this conclusion of part (a) is obtained.
(b) Sinceλ∈0,1, following from preceding relation (a) and letting τ→∞, thus(31)limτ→∞uiτ-1TuτN≤limτ→∞∑t=0τ-1Cλτ-t-1rt1.Since riτ→0 for i∈V, so rτ1→0 as τ→∞. Hence, by Lemma 11(i), we obtain(32)limτ→∞∑t=0τ-1Cλτ-t-1rt1=0.Thus, we conclude the statement of (b).
(c) By the decay conditions ofατ, we obtain that(33)ατuiτ-1TuτN≤Cα1λτu01+∑t=0τ-1αtλτ-t-1rt1.Since λ∈0,1, we can see that ∑τ=0∞‍λτ is finite. Hence, following from Lemma 11(ii), the sum ∑τ=1∞‍∑t=0τ-1‍λτ-t-1αtrt1 is finite. Hence, the relation in part (c) is obtained.Informally, the distributed stochastic subgradient algorithm based on weight-balancing ensures that alluiτ track the running average 1Tuτ/N with a geometric rate λ.Following from the similar arguments as (19)-(20), we rewrite algorithms (4)-(5) as(34)vτ=Wτuτ,uτ+1=vτ-ατsτ+δτ,(35)δiτ=ΠUviτ-ατsiτ-viτ-ατsiτ,where Wτ=Wτ⊗Id and (36)uτ≜u1τT,…,uNτTT,vτ≜v1τT,…,vNτTT,sτ≜s1τT,…,sNτTT,δτ≜δ1τT,…,δNτTT.Moreover, let riτ=δiτ-ατsiτ, for all i=1,…,N, which is referred as perturbation vector. Hence, we introduce the following vector: (37)rτ≜r1τT,…,rNτTT.Note that the vectors uτ, vτ, sτ, δτ, and rτ are in RNd. Besides, the following corollary is obtained immediately from Lemma 12(a).Corollary 13.
For every agenti, i∈V, the vector variables uiτ and siτ in Rd are given in (4)-(5); then, we have(38)uiτ-∑j=1NujτN≤Cλτ∑j=1Nuj01+∑t=0τ-1λτ-t-1∑j=1Nrjt1.For any vector, 1-norm is greater than or equal to standard Euclidean norm. Therefore, from Lemma 12(a), which is applied to each coordinate of Rd, Corollary 13 holds immediately.In Lemma12 and Corollary 13, the perturbation term is a crucial role. Therefore, we bound the perturbation term in the following lemma.Lemma 14.
Under Assumptions2–5, the perturbations vectors riτ∈Rd, for all i∈V, satisfy(39)Eriτ1≤2dατLi+νi.Proof.
Following from Lemma10(4), we have(40)uiτ+1-viτ2≤viτ-ατsiτ-viτ2-uiτ+1-viτ-ατsiτ2.Furthermore, by Assumptions 4 and 5, we have(41)Euiτ+1-viτ2∣Fτ≤α2τLi+νi2-Eδiτ2,for all i∈V. Hence, we obtain with probability 1(42)Eδiτ2≤α2τLi+νi2.Further, following from the inequality Eu≤Eu2, then(43)Eδiτ≤ατLi+νi.According to the definition of perturbations vector riτ, we have(44)Eriτ1≤dEriτ≤dEδiτ+ατEsiτ≤2dατLi+νi.Therefore, this lemma is proved completely.To establish the convergence properties of our algorithm, an auxiliary variable is first defined, for allτ≥0, as follows:(45)u¯τ=1N∑i=1Nuiτ.We now establish the recurrence relation foru¯τ. Hence, for all i∈V and l∈D, where D=1,…,d, we introduce a vector ulτ∈RN such that ulτi=uiτl. Following from algorithms (4)-(5), we obtain for l∈D(46)ulτ+1=Wτulτ+rlτ,where rlτ is a vector in RN, which is defined as rlτi=riτl, for all i∈V and l∈D.Since the matrixWτ is column stochastic, we have, for all l∈D,(47)1N∑i=1Nulτ+1i=1N∑i=1Nulτi+1N∑i=1Nrlτi.We follow from the definition of ulτi; then,(48)u¯τ+1=u¯τ+1N∑i=1Nriτ.We also establish the following lemma, which is crucial in our proofs.Lemma 15 (basic iteration relation).
Let the estimate sequenceuiτ, i∈V, be generated by (4)-(5). Under Assumptions 2–5, for all vectors w∈U and τ≥0, then we obtain with probability 1(49)Eu¯τ+1-w2∣Fτ≤u¯τ-w2+4ατN∑i=1NLiuiτ-u¯τ+2N∑i=1NδiτTu¯τ-w+4α2τN∑i=1NLi+νi2-2ατNgu¯τ-gw-ατN∑i=1Nσiuiτ-w2,where Li and νi are defined as Assumptions 2–3, respectively. The constant σi is defined in (3).Proof.
By (48), we have(50)u¯τ+1-w2=u¯τ+1N∑i=1Nriτ-w2=u¯τ-w2+2N∑i=1NriτTu¯τ-w+1N2∑i=1Nriτ2=u¯τ-w2-2ατN∑i=1NsiτTu¯τ-w+2N∑i=1NδiτTu¯τ-w+1N2∑i=1Nriτ2.By taking expectation on the both sides of (50) with respect to Fτ, furthermore, we follow from (6) and the fact (51)Eϵiτ∣Fτ=0,and we have that(52)Eu¯τ+1-w2∣Fτ≤u¯τ-w2+2N∑i=1NδiτTu¯τ-w+1N2E∑i=1Nriτ2-2ατN∑i=1N∇giuiτTu¯τ-w.Next, we bound the term E∑i=1Nriτ2 in (52) as follows:(53)E∑i=1Nriτ2≤N∑i=1NEriτ2,where we use the inequality (∑i=1N‍ai)2≤N∑i=1N‍ai2 to obtain the above relation. In order to obtain the upper bound of E[∑i=1N‍riτ2], we need to bound the term E[riτ2] in (53). Following from the similar arguments as Lemma 14, we have(54)Eriτ2≤4α2τLi+νi2,for all i∈V. Hence, combining (53) and (54), we obtain(55)E∑i=1Nriτ2≤4Nα2τ∑i=1NLi+νi2.Substituting (55) into (52), we have(56)Eu¯τ+1-w2∣Fτ≤u¯τ-w2+2N∑i=1NδiτTu¯τ-w+4α2τN∑i=1NLi+νi2-2ατN∑i=1N∇giuiτTu¯τ-w.We next estimate the term ∇giuiτTu¯τ-w in (56). By (3) in Assumption 3, we have that(57)∇giuiτTu¯τ-w=∇giuiτTu¯τ-uiτ+∇giuiτTuiτ-w≥∇giuiτTu¯τ-uiτ+giuiτ-giw+σi2uiτ-w2.Further, we also obtain (58)∇giuiτTu¯τ-uiτ≥-Liu¯τ-uiτ,where we use Cauchy-Schwarz inequality to obtain the last inequality. Moreover, the term giuiτ-giw in (57) can be rewritten as(59)giuiτ-giw=giu¯τ-giw+giuiτ-giu¯τ. By using Assumptions 3 and 4, we have that(60)giuiτ-giw≥giu¯τ-giw+∇giu¯τTuiτ-u¯τ≥-Liuiτ-u¯τ+giu¯τ-giw.Hence, combining (57), (58), and (60), we obtain(61)∇giuiτTu¯τ-w≥giu¯τ-giw+σi2uiτ-w2-2Liuiτ-u¯τ.Substituting (61) into (56), we have(62)Eu¯τ+1-w2∣Fτ≤u¯τ-w2+4ατN∑i=1NLiuiτ-u¯τ+2N∑i=1NδiτTu¯τ-w+4α2τN∑i=1NLi+νi2-2ατN∑i=1Ngiu¯τ-giw-2ατN∑i=1Nσi2uiτ-w2.Following from the definition of the global cost function gu, and then using (62), the lemma is completely proved.To prove Theorem6, we employ the following lemma, which is given by [31].Lemma 16.
We assume that{vτ}, {uτ}, {aτ}, and {bτ} are random sequences. Moreover, we further suppose that elements of these sequences are nonnegative random variables and with probability 1 satisfy the following relation: (63)Evτ+1∣Fτ≤1+aτvτ-ut+bτfor τ≥0. Further, if ∑τ=0∞‍aτ<∞ and ∑τ=0∞‍bτ<∞ hold, then, vτ asymptotically converges to v, where v is a nonnegative random variable, i.e., limτ→∞vτ=v. Moreover, we also have ∑τ=0∞‍uτ<∞ with probability 1.Using the conclusion of Lemma16, we have the following lemma.Lemma 17.
Consider an optimization problemminu∈Rnhu. Assume that the set S∗ be nonempty, where S∗ is the optimal set. Let the function h:Rn→R be continuous. Suppose that uτ, aτ, and bτ are random sequences with nonnegative elements. Moreover, these sequences satisfy the following relation:(64)Euτ+1-u2∣Fτ≤1+aτuτ-u2-κτhuτ-hu+bτfor all u∈S∗ and τ≥0 with probability 1, where κτ≥0 for all τ≥0. Further, we assume that ∑τ=0∞‍bτ<∞ and ∑τ=0∞‍κτ=∞ hold. Then, the random sequence uτ converges to some optimal solutions u∗∈S∗ with probability 1.Proof.
Letu=u∗ and h∗=minu∈Rnhu; then, we have(65)Euτ+1-u∗2∣Fτ≤1+aτuτ-u∗2-κτhuτ-h∗+bτ.Thus, we satisfy the conditions of Lemma 16. Hence, the sequence {uτ+1-u∗2} is convergent, and we have(66)∑τ=0∞κτhuτ-h∗<∞.Since ∑τ=0∞‍κτ=∞, with probability 1 we have(67)liminfτ→∞huτ=h∗.Since the sequence {uτ+1-u∗2} is convergent for τ≥0, the sequence uτ is bounded. Therefore, there exists a convergent subsequence uτj of the sequence uτ that converges to some u~. Moreover, the subsequence uτj satisfies(68)limj→∞huτj=liminfτ→∞huτ=h∗.By using continuity of h, we have (69)limj→∞huτj=hu~.Following from (68), we can see that the random sequence uτ asymptotically converges to some u~∈S∗. Therefore, the random sequence uτ converges to u∗ by setting u∗=u~.We now start to prove Theorem6 by using the conclusions of Lemmas 15 and 17.Proof of Theorem6.
Sinceατ→0 as τ→∞, we obtain(70)limτ→∞ulτ+1i-1TulτN=0,which follows from Lemma 10(2). Therefore, using (70), we have(71)limτ→∞uiτ-u¯τ=0.We also have (72)Erlτi≤Erlτ∞≤maxi⁡Eriτ,where Assumptions 2 and 3 are used. Thus, following from the decay conditions of ατ, we have(73)∑τ=1∞ατriτ≤maxi⁡2Li+νi∑τ=1∞α2τ<∞for i∈V. Following from Lemma 10(3), we obtain(74)∑τ=1∞ατulτi-1TulτN<∞.Hence, we obtain(75)∑τ=1∞ατuiτ-u¯τ<∞.
Letw=u∗ for u∗∈U∗ in Lemma 15, and we have(76)Eu¯τ+1-u∗2∣Fτ≤u¯τ-u∗2+4ατN∑i=1NLiuiτ-u¯τ+2N∑i=1NδiτTu¯τ-u∗+4α2τN∑i=1NLi+νi2-2ατNgu¯τ-gu∗.According to the conclusion of Lemma 10(1), we obtain (77)δiτTu¯τ-u∗≤0.Hence, we have with probability one(78)Eu¯τ+1-u∗2∣Fτ≤u¯τ-u∗2+4ατN∑i=1NLiuiτ-u¯τ+4α2τN∑i=1NLi+νi2-2ατNgu¯τ-gu∗.By using (75), we have(79)∑τ=1∞4ατN∑i=1NLiuiτ-u¯τ<∞.Since ∑τ=1∞‍ατ=∞ and ∑τ=1∞‍α2τ<∞ hold by the assumption of ατ, the conditions of Lemma 17 hold. Following from Lemma 17, we can see that u¯τ asymptotically converges to u∗. Further, following from (71), uiτ also asymptotically converges to u∗ for all i∈V, i.e.,(80)limτ→∞uiτ=u∗with the notion that probability 1 holds. Therefore, Theorem 6 is proved completely.Now, we establish the following lemma, which is an important relation for the proof of the Theorem7.Lemma 18.
Let the estimate sequenceuiτ, i∈V, be generated by (4)-(5), and ατ=μ/τ+1, where the constant μ satisfies (52). Under Assumptions 2–5, then we obtain with probability 1(81)E∑τ=1Γ-1uiτ-∑j=1NujτN≤Cλ1-λ∑j=1Nuj01+μ1-λ∑i=1N2dLi+νi1+lnΓ-1for all i∈V and Γ≥2.Proof.
Following from Corollary13, we obtain(82)∑τ=1Γ-1uiτ-∑j=1NujτN≤C∑τ=1Γ-1λτ∑j=1Nuj01+C∑τ=1Γ-1∑t=0τ-1λτ-t-1∑j=1Nrjt1.Using (82) and the result of Lemma 14, we obtain(83)E∑τ=1Γ-1uiτ-∑j=1NujτN≤C∑j=1Nuj01∑τ=1Γ-1λτ+∑i=1N2dLi+νi∑τ=1Γ-1∑t=0τ-1αtλτ-t-1.For λ∈0,1, we have ∑τ=1Γ-1‍λτ≤λ/1-λ. Hence, the first term in (83) is bounded as follows:(84)∑τ=1Γ-1λτ∑j=1Nuj01≤λ1-λ∑j=1Nuj01.Next, we estimate the second term in (83). From the expression ατ=μ/τ+1, we have(85)∑τ=1Γ-1∑t=0τ-1αtλτ-t-1=∑τ=1Γ-1∑t=0τ-1μt+1λτ-t-1=∑τ=1Γ-1∑t=1τμtλτ-t=∑t=1Γ-1∑τ=tΓ-1μtλτ-t≤μ1-λ∑t=1Γ-11t=μ1-λ1+∑t=2Γ-11t≤μ1-λ1+∫1Γ-11tdt=μ1-λ1+lnΓ-1for Γ≥2. Therefore, combining (83), (84), and (85), the result of this lemma is obtained.Next, we start to prove Theorem7 by using the results of Lemmas 15 and 18.Proof of Theorem7.
We assume thatσi is a positive constant for all i∈V. Hence, for each agent i∈V, local cost function gi is a σi-strongly convex function. Moreover, the function gu=∑i=1N‍giu has a unique global minimization solution u∗. Hence, let w=u∗ in Lemma 15, and we have(86)Eu¯τ+1-u∗2∣Fτ≤u¯τ-u∗2+4ατN∑i=1NLiuiτ-u¯τ+4α2τN∑i=1NLi+νi2-2ατNgu¯τ-gu∗-ατN∑i=1Nσiuiτ-u∗2,where we employ inequality δiτTu¯τ-u∗≤0. Next, we first bound the term gu¯τ-gu∗ in (86). By using the fact that the function gi is σi-strongly convex and ∇giu∗=0, we have(87)gu¯τ-gu∗≥12∑i=1Nσiu¯τ-u∗2.In addition, note that g is the strongly convex function. Hence, by using the boundedness of subgradient ∇gu, we also have that(88)gu¯τ-gu∗=gu¯τ-guiτ+guiτ-gu∗≥-Luiτ-u¯τ+guiτ-gu∗,where L≜∑i=1N‍Li. Therefore, following from (87) and (88), we obtain(89)2gu¯τ-gu∗≥12∑i=1Nσiu¯τ-u∗2-Luiτ-u¯τ+guiτ-gu∗.Therefore, substituting (89) into (86), we obtain with probability 1(90)Eu¯τ+1-u∗2∣Fτ≤u¯τ-u∗2+ατNLuiτ-u¯τ-ατN∑i=1Nσiuiτ-u∗2+4ατN∑i=1NLiuiτ-u¯τ+4α2τN∑i=1NLi+νi2-ατ2N∑i=1Nσiu¯τ-u∗2-ατNguiτ-gu∗.Following from the expression of ατ=μ/τ+1, where μ is given by (11), we have that(91)Eu¯τ+1-u∗2∣Fτ≤1-2τ+1u¯τ-u∗2-μNτ+1guiτ-gu∗+∑i=1Nσiuiτ-u∗2+μLNτ+1uiτ-u¯τ+4μ2Nτ+12∑i=1NLi+νi2+4μNτ+1∑i=1NLiuiτ-u¯τ.Multiplying the both sides of (91) by ττ+1, we have(92)τ+1τEu¯τ+1-u∗2∣Fτ≤4μ2τ∑i=1NLi+νi2Nτ+1-μτNguiτ-gu∗+∑i=1Nσiuiτ-u∗2+μLτNuiτ-u¯τ+4μτN∑i=1NLiuiτ-u¯τ+ττ-1u¯τ-u∗2.By iterating the expression of (92), we obtain(93)ΓΓ-1Eu¯Γ-u∗2≤-μN∑τ=1Γ-1τEguiτ-gu∗+μLN∑τ=1Γ-1τEuiτ-u¯τ-μN∑τ=1Γ-1τ∑i=1NσiEuiτ-u∗2+4μN∑τ=1Γ-1τ∑i=1NLiEuiτ-u¯τ+4μ2N∑i=1NLi+νi2∑τ=1Γ-1ττ+1for all i∈V and Γ≥2. Due to τ≤Γ-1, so the relations(94)∑τ=1Γ-1τEuiτ-u¯τ≤Γ-1∑τ=1Γ-1Euiτ-u¯τand(95)∑τ=1Γ-1τ∑i=1NLiEuiτ-u¯τ≤Γ-1∑i=1NLi∑τ=1Γ-1Euiτ-u¯τhold.
Hence, following from the conclusion of Lemma18, we obtain(96)ΓΓ-1Eu¯Γ-u∗2≤-μN∑τ=1Γ-1τEguiτ-gu∗-μN∑τ=1Γ-1τ∑i=1NσiEuiτ-u∗2+μLΓ-1NCλ1-λ∑j=1Nuj01+μ1-λ∑i=1N2dLi+νi1+lnΓ-1+4μΓ-1N∑i=1NLiCλ1-λ∑j=1Nuj01+μ1-λ∑i=1NdLi+νi1+lnΓ-1+4μ2N∑i=1NLi+νi2∑τ=1Γ-1ττ+1.Dividing both sides of (96) by ΓΓ-1, then we have that(97)μNΓΓ-1∑τ=1Γ-1τEguiτ-gu∗+∑i=1NσiEuiτ-u∗2≤μLCNΓλ1-λ∑j=1Nuj01+μ1-λ∑i=1NdLi+νi1+lnΓ-1+4μCNΓ∑i=1NLiλ1-λ∑j=1Nuj01+μ1-λ∑i=1NdLi+νi1+lnΓ-1+4μ2NΓ∑i=1NLi+νi2,where we use the relation ∑τ=1Γ-1‍τ/τ+1≤Γ-1 for Γ≥2. Hence, by a few algebraic operators, we obtain(98)1ΓΓ-1∑τ=1Γ-1τEguiτ-gu∗+∑i=1NσiEuiτ-u∗2≤5LCΓλ1-λ∑j=1Nuj01+μ1-λ∑i=1NdLi+νi1+lnΓ-1+4μΓ∑i=1NLi+νi2.
Due to convexity of the functiong, using the definition of u^iΓ and convexity of norm function, we obtain(99)gu^iΓ-gu∗+∑j=1NσjujΓ-u∗≤∑τ=1Γ-1τguiτ-gu∗+∑j=1Nσjujτ-u∗ΓΓ-1/2.Taking expectation in both sides of (99), then(100)Egu^iΓ-gu∗+∑j=1NσjEujΓ-u∗≤2∑τ=1Γ-1τEguiτ-gu∗+∑j=1NσjEujτ-u∗ΓΓ-1.Therefore, substituting (98) into (100) and by a few algebraic operators, we derive the desired result.Next, we give the proof of Theorem8, where we assume that the functions gi are generally convex for all i∈V.Proof of Theorem8.
Letσi=0 for all i=1,…,N in Assumption 3. Moreover, we introduce the following variable, which is the ergodic average of the estimates uiτ:(101)u~iΓ=1∑τ=0Γατ∑τ=0Γατuiτ.According to (86), we have(102)Eu¯τ+1-u∗2∣Fτ≤u¯τ-u∗2+4ατN∑i=1NLiuiτ-u¯τ+4α2τN∑i=1NLi+νi2-2ατNEgu¯τ-gu∗.Combining (88) with (102), and after some elementary algebra operations, we obtain(103)2ατNEguiτ-gu∗≤u¯τ-u∗2+4α2τN∑i=1NLi+νi2+2ατNLuiτ-u¯τ+4ατN∑i=1NLiuiτ-u¯τ-Eu¯τ+1-u∗2∣Fτ.By summing the preceding inequality and dividing by 2/NΦΓ, where ΦΓ=∑τ=0Γ‍ατ, we obtain(104)∑τ=0ΓατEguiτ-gu∗ΦΓ≤N2ΦΓu¯0-u∗2+LΦΓ∑τ=0Γατuiτ-u¯τ+2ΦΓ∑τ=0Γατ∑i=1NLiuiτ-u¯τ+2ΦΓ∑τ=0Γα2τ∑i=1NLi+νi2.Since ατ=1/τ+1, we have(105)ΦΓ=∑τ=0Γ1τ+1≥∫0Γ+1dγγ+1=2Γ+2-1≥Γ+1for all Γ≥1. Moreover, we also have(106)∑τ=0Γα2τ=∑τ=0Γ1τ+1=∑γ=1Γ+11γ≤1+∫1Γ+1dγγ=1+lnΓ+1.In addition, using the result of Corollary 13, we have(107)∑τ=0Γατuiτ-u¯τ≤∑τ=0ΓατCλτ∑j=1Nuj01+∑j=1N2dLj+νj∑t=0τ-1Cλτ-t-1αt,where the inequality follows from Lemma 14. Since ατ=1/τ+1≤1, so we obtain(108)∑τ=0Γατλτ≤11-λ.Further, we also have(109)∑τ=0Γ∑t=0τ-1λτ-t-1αtατ=1+∑ϑ=1Γλϑ-1∑ι=1Γ-ϑ+11ιϑ+ι≤1+∑ϑ=1Γλϑ-1∫0Γ-ϑ+1dγγγ+ϑ≤1+2∑ϑ=1Γλϑ-1lnΓ-ϑ+1+Γ+1≤1+21-λln2+12lnΓ+1≤41-λlnΓ+1.Combining (107), (108), and (109), we obtain(110)∑τ=0Γατuiτ-u¯τ≤C1-λ∑j=1Nuj01+4ClnΓ+11-λ∑j=1N2dLj+νj.Thus, following from the preceding relation, we obtain(111)∑τ=0Γατ∑i=1NLiuiτ-u¯τ=∑i=1NLi∑τ=0Γατuiτ-u¯τ≤LC1-λ∑j=1Nuj01+4LClnΓ+11-λ∑j=1N2dLj+νj.Substituting (105), (106), (110), and (111) into (104), we have(112)∑τ=0ΓατEguiτ-gu∗ΦΓ≤3LC∑j=1Nuj011-λΓ+1+9LClnΓ+11-λΓ+1∑j=1N2dLj+νj+21+lnΓ+1Γ+1∑i=1NLi+νi2+N2Γ+1u¯0-u∗2.
Besides, by convexity of functiong, and then following from the definition of u~iΓ in (101), then we conclude that(113)Egu~iΓ-gu∗≤∑τ=0ΓατEguiτ-gu∗ΦΓfor all i∈V and Γ≥1. Therefore, combining (112) with (113), the conclusion of this theorem is obtained completely.In this section, we prove our main results, which are presented in Section3. If step-sizes ατ are positive and satisfy decay conditions (26), our proposed algorithm is asymptotically convergent by appropriately choosing step-sizes ατ. Further, our algorithm converges with rate O(lnΓ/Γ) under strong convexity and with rate O(lnΓ/Γ) under general convexity.


## 5. Simulations

In this section, we consider the multiclass classification problem in machine learning. In the problem, each agenti∈V generates a decision matrix Uit=[u1T;…;ucT]T∈Rc×d through a data example eit∈Rd that is one of the classes C={1,…,c}. The decision is used to predict the class label via argmaxl∈CulTeit. The loss function of each agent i∈V is defined as (114)giUit=ln1+∑l≠yitexpulTeit-uyitTeit, where yit denotes the true class label. In this problem, the domain U is given by U={U∈Rc×d∣Utr≤ζ}, in which Utr represents the nuclear norm of U.In our simulations, we setN=10, the step-size is set as ατ=1/τ. Moreover, we use a multiclass dataset, which is called news20 (http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/.). This dataset has 62,061 features, 20 classes, and 15,935 instances. The testing size of news20 is 3,993. In addition, the time-varying graph at round τ is shown in Figure 1. We use the following quantity to measure the performance of the algorithms: (115)rt=1N∑i=1Ngiuit-giu∗.Figure 1
The strongly connected time-varying graph.In the first simulation experiment, we compare the performances of the algorithm with communication and without communication. As shown in Figure2, we can see that the performance with communication is better than that without communication.Figure 2
The performance of our algorithm with communication and without communication.In the second simulation experiment, we compare the convergence performances with D-DPS [27]. As shown in Figure 3, for the similar setting, these algorithms have similar convergence rates. However, our algorithm considers the noisy subgradient. Moreover, the cost functions may be nondifferentiable and we consider the case that the graph is time-varying. Therefore, our algorithm has better applicability to real environments.Figure 3
Comparison of D-DPS and the proposed algorithm.


## 6. Conclusion

We have proposed a fully decentralized stochastic subgradient projection algorithm to solve distributed constrained optimization problem over time-varying directed networks. We employ weight-balancing technique to overcome the influence of directed graphs and assume that every agent knows its own out-degree at each time epoch in our algorithm. Moreover, all agents have access to their own noisy subgradient. We have proved that our proposed algorithm is asymptotically convergent with suitable chosen step-sizesατ over time-varying directed networks. Furthermore, for local strongly convex functions, we have proved that our algorithm converges with the rate OlnΓ/Γ. Meanwhile, for generally convex functions, we have also showed that the convergence rate O(lnΓ/Γ) is achieved. Additionally, the performance of the proposed algorithm has also been evaluated by simulations.



---

*Source: 8030792-2019-08-20.xml*