# A Distributed Conjugate Gradient Online Learning Method over Networks

Authors: Cuixia Xu; Junlong Zhu; Youlin Shang; Qingtao Wu
Journal: Complexity
 (2020)

---

## Abstract

In a distributed online optimization problem with a convex constrained set over an undirected multiagent network, the local objective functions are convex and vary over time. Most of the existing methods used to solve this problem are based on the fastest gradient descent method. However, the convergence speed of these methods is decreased with an increase in the number of iterations. To accelerate the convergence speed of the algorithm, we present a distributed online conjugate gradient algorithm, different from a gradient method, in which the search directions are a set of vectors that are conjugated to each other and the step sizes are obtained through an accurate line search. We analyzed the convergence of the algorithm theoretically and obtained a regret bound ofOT, where T is the number of iterations. Finally, numerical experiments conducted on a sensor network demonstrate the performance of the proposed algorithm.


---

## Body

## 1. Introduction

Distributed optimization has received considerable interest in science and engineering, which can be applied in numerous fields such as distributed tracking and localization [1], multiagent coordination [2], distributed estimations using sensor networks [3–5], and machine learning [6]. Such problems can be modeled to minimize or maximize the summation of some of the local convex functions, and these local functions only use a local computation and communication in a distributed manner. With an increase in the network size and data volume, more effective distributed algorithms have become a hot research topic. In recent years, many scholars have proposed various distributed optimization algorithms to solve such problems [7–15].Most of the existing algorithms assume that the cost function at each agent is fixed. However, in practical problems, the environment of an agent is uncertain and the cost function of each agent changes over time, requiring us to solve such problems through an online setting. To be more precise, in a distributed online optimization, the cost function of each agent changes during each step, and witht iterations, before a decision is given, the cost function for each agent is unknown; only when we obtain a decision from a constrained set, we can obtain the information of the cost function. In addition, we also obtain a loss at the same time. Such loss reflects the error in the cost of the objective function between the current decision point and the best decision in hindsight, which we call regret. Regret is an important criterion in evaluating a distributed online algorithm. A well-performing distributed online optimization algorithm should decrease the average total regret approach to zero over time.Because an online distributed optimization algorithm is more consistent with that used for practical problems, many scholars have conducted numerous studies and some effective algorithms have been proposed [16–24]. Yan et al. [20] introduced a distributed autonomous online learning algorithm, namely, a subgradient descent method using a projection. When the local objective functions are strongly convex and convex, the regret bounds of the proposed algorithm are obtained, respectively. The authors in [22] introduced an online distributed push-sum algorithm in which the search direction is a negative subgradient in each iteration, which achieves regret O((log(T))2) when the local function is strongly convex. For a time-varying directed network problem, Zhu et al. [25, 26] proposed a distributed online optimization algorithm. During each iteration, the negative subgradient is randomly selected as the search direction. The authors in [27] presented a distributed online algorithm based on a primal-dual dynamic mirror descent for a problem with time-varying coupling inequality constraints and obtained a dynamic regret bound. The authors in [28] proposed a distributed online conditional gradient algorithm for a constrained distributed online optimization problem in the Internet of Things.The existing distributed online optimization algorithm based on the gradient method is simple to calculate and requires little storage; however, to ensure the convergence of the algorithm, the iterative step length usually needs to decrease with an increase in the number of iterations, which will lead to a zigzag path at the end of the algorithm. That is, the algorithm will carry out multiple iterations in the same direction or approximate direction, which greatly increases the computational time of the algorithm. The conjugate gradient algorithm also has the advantages of simple calculations and guaranteed convergence under certain conditions [29–31] but differs from the gradient method in that the search direction of the conjugate gradient algorithm is a group of conjugate or approximately conjugate vectors, and during the later stage of the algorithm, there are no additional repeated iterations in the same or approximate direction. Thus, the convergence of the conjugate gradient method is generally faster than that of the gradient descent method. In particular, for an objective functional quadratic, the conjugate gradient method has a quadratic termination. Based on these advantages, the conjugate gradient method has been used to solve numerous centralized offline optimization problems [32–35]. According to the existing literature, however, the conjugate gradient method has not been applied to distributed online optimization problems. To fill in this gap, herein, we present a distributed online conjugate gradient algorithm.There are two main contributions provided by the present study. First, a new algorithm for a distributed online constrained convex optimization problem, namely, a distributed online conjugate gradient algorithm, is proposed. In our algorithm, a set of conjugate directions is used to replace the gradient directions used in a traditional gradient descent method, and the step size is obtained through an accurate linear search, thus effectively avoiding the slow convergence speed of a traditional gradient descent algorithm during the later stage. Second, we provide a careful analysis of the convergence of the proposed algorithm and obtain the square root of the regret bound.The remainder of this paper is organized as follows: in Section2, we first briefly introduce the distributed online optimization model, followed by some necessary mathematical preliminaries and assumptions used in this study. We also provide a detailed statement of our algorithm in Section 3 and an analysis of the convergence of the algorithm in Section 4. The simulation results of our algorithm are then presented in Section 5. Finally, we provide some concluding remarks in Section 6. In addition, further detailed proofs of some of the lemmas applied can be found in the Appendix.


## 2. Preliminaries

In this section, we provide a brief background on the distributed online optimization and the conjugate gradient method. At the same time, some constructs used in this study and some relevant assumptions regarding our analysis are provided.


### 2.1. Distributed Online Optimization

Consider a network system with multiple agents; in this network, each agenti is associated with a convex function ftix:ℝn⟶ℝ. All agents aim to solve the following general consensus problem cooperatively:(1)min∑i=1nftixsubject tox∈X.During each roundt ∈ {1, …, T}, the ith agent is required to generate a decision point xi(t) from a convex compact set X. Then, the adversary replies to each agent’s decision with a cost function ftix:X⟶ℝ, and each agent has a loss of fti(xi(t)) simultaneously. The communication between agents is specified by a graph G=V,ℰ, where V=1,…,n is the vertex set and ℰ⊂V×V is the edge set. Each agent i can only communicate with its immediate neighbors Ni=j∈Vu^i,j∈ℰ. The goal of the agents is to seek a sequence of decision points xit,i∈V such that the cumulative regret with respect to each agent i regarding any fixed decision x∗∈X in hindsight(2)RTxit,x∗=∑t=1Tftixit−ftix∗,is sublinear in T, that is, limT⟶∞RT/T = 0.


### 2.2. Conjugate Gradient Method

For the following optimization problem,(3)minx∈ℝnfx,where f(x) is a quadratic continuous differentiable. The iterative form of the conjugate gradient (CG) method is usually designed as(4)xk+1=xk+αkdk,k=0,1,2,…,where x(k) is the point from the kth iteration, αk > 0 is the step length, and the search direction dk is defined as(5)dk=−gk,k=0,−gk+βkdk−1,k≥1.in which, gk is the gradient of the objective function at the current iterate point x(k), βk∈ℝ is a scalar, and the different definitions of βk represent different methods of a conjugate gradient [27]. Well-known conjugate gradient methods include the Polak–Ribiere–Polyak (PRP) method and the Fletcher–Reeves (FR) method. In this study, we define the parameter βk using the PRP method, the specific form of which is as follows:(6)βkPRP=gk−gk−1Tgkgk−1Tgk−1,βk=max0,βkPRP.Gilbert and Nocedal [36] proved that if the parameter βk is appropriately bounded in magnitude, the CG method can converge globally. Therefore, the CG method satisfies the sufficient descent condition under this hypothesis.To analyze the convergence of our algorithm, we provide the bound of the conjugate gradient as follows.Lemma 1 (see [37]).
Letf(x) be a quadratic continuous difference convex function, and ∇2f(x) be a Hessian matrix of the function. For any x^∈ℝn, when x∈C=xfx≤fx^,x∈ℝn and y∈ℝn, there exist two positive numbers m and M such that(7)my2≤yT∇2fxy≤My2.Taking an initial pointx(1) ∈ C, where xk, dk, and βk are all defined using the PRP method,(8)gk≤dk≤m+Mmgk,in which gk=∇fxk.


### 2.3. Some Constructs and Assumptions

The following assumptions are given throughout this paper:(i)
Each cost functionfti(x) is a convex and twice continuous differentiable L-Lipschitz on the convex set X.(ii)
The setX is compact and convex, and 0∈X, 0 denotes a vector with all entries equal to zero.(iii)
The Euclidean diameter ofX is bounded by R.As the Lipschitz condition in (i) implies, for anyx∈X and any gradient gi, we have the following:(9)gi∗≤L,Where ⋅∗:=supu≤1⋅,u denotes the dual norm.The next definition is used throughout this paper.Definition 1 (see [38]).
Letf(x) be a function difference on an open set C⊆ℝn, and let X be a convex subset of C. Then, f(x) is convex on X if and only if(10)fx≥fx0+∇fx0,x−x0,for all x0,x∈X×X.
Now, we give an important inequality in [39] that is often used in optimization problems.
Letf(x) be a first-order continuous differentiable function on the set ℝn, whose first derivative satisfies the Lipschitz condition, and thus ∀x,y∈ℝn,(11)fy−fx−f′x,y−x≤L2y−x2,where L is the Lipschitz constant and ∥⋅∥ denotes the European norm.


## 2.1. Distributed Online Optimization

Consider a network system with multiple agents; in this network, each agenti is associated with a convex function ftix:ℝn⟶ℝ. All agents aim to solve the following general consensus problem cooperatively:(1)min∑i=1nftixsubject tox∈X.During each roundt ∈ {1, …, T}, the ith agent is required to generate a decision point xi(t) from a convex compact set X. Then, the adversary replies to each agent’s decision with a cost function ftix:X⟶ℝ, and each agent has a loss of fti(xi(t)) simultaneously. The communication between agents is specified by a graph G=V,ℰ, where V=1,…,n is the vertex set and ℰ⊂V×V is the edge set. Each agent i can only communicate with its immediate neighbors Ni=j∈Vu^i,j∈ℰ. The goal of the agents is to seek a sequence of decision points xit,i∈V such that the cumulative regret with respect to each agent i regarding any fixed decision x∗∈X in hindsight(2)RTxit,x∗=∑t=1Tftixit−ftix∗,is sublinear in T, that is, limT⟶∞RT/T = 0.


## 2.2. Conjugate Gradient Method

For the following optimization problem,(3)minx∈ℝnfx,where f(x) is a quadratic continuous differentiable. The iterative form of the conjugate gradient (CG) method is usually designed as(4)xk+1=xk+αkdk,k=0,1,2,…,where x(k) is the point from the kth iteration, αk > 0 is the step length, and the search direction dk is defined as(5)dk=−gk,k=0,−gk+βkdk−1,k≥1.in which, gk is the gradient of the objective function at the current iterate point x(k), βk∈ℝ is a scalar, and the different definitions of βk represent different methods of a conjugate gradient [27]. Well-known conjugate gradient methods include the Polak–Ribiere–Polyak (PRP) method and the Fletcher–Reeves (FR) method. In this study, we define the parameter βk using the PRP method, the specific form of which is as follows:(6)βkPRP=gk−gk−1Tgkgk−1Tgk−1,βk=max0,βkPRP.Gilbert and Nocedal [36] proved that if the parameter βk is appropriately bounded in magnitude, the CG method can converge globally. Therefore, the CG method satisfies the sufficient descent condition under this hypothesis.To analyze the convergence of our algorithm, we provide the bound of the conjugate gradient as follows.Lemma 1 (see [37]).
Letf(x) be a quadratic continuous difference convex function, and ∇2f(x) be a Hessian matrix of the function. For any x^∈ℝn, when x∈C=xfx≤fx^,x∈ℝn and y∈ℝn, there exist two positive numbers m and M such that(7)my2≤yT∇2fxy≤My2.Taking an initial pointx(1) ∈ C, where xk, dk, and βk are all defined using the PRP method,(8)gk≤dk≤m+Mmgk,in which gk=∇fxk.


## 2.3. Some Constructs and Assumptions

The following assumptions are given throughout this paper:(i)
Each cost functionfti(x) is a convex and twice continuous differentiable L-Lipschitz on the convex set X.(ii)
The setX is compact and convex, and 0∈X, 0 denotes a vector with all entries equal to zero.(iii)
The Euclidean diameter ofX is bounded by R.As the Lipschitz condition in (i) implies, for anyx∈X and any gradient gi, we have the following:(9)gi∗≤L,Where ⋅∗:=supu≤1⋅,u denotes the dual norm.The next definition is used throughout this paper.Definition 1 (see [38]).
Letf(x) be a function difference on an open set C⊆ℝn, and let X be a convex subset of C. Then, f(x) is convex on X if and only if(10)fx≥fx0+∇fx0,x−x0,for all x0,x∈X×X.
Now, we give an important inequality in [39] that is often used in optimization problems.
Letf(x) be a first-order continuous differentiable function on the set ℝn, whose first derivative satisfies the Lipschitz condition, and thus ∀x,y∈ℝn,(11)fy−fx−f′x,y−x≤L2y−x2,where L is the Lipschitz constant and ∥⋅∥ denotes the European norm.


## 3. Distributed Online Conjugate Gradient Algorithm

For the distributed online optimization problem (1), each locally cost function fti(x) satisfies the assumptions in Section 2. The network topology relationship among agents is specified by an undirected graph G=V,ℰ, that is, if i,j∈ℰ, it implies that j,i∈ℰ. Each agent i can only communicate with its immediate neighbors. The adjacency matrix of the undirected graph is a doubly stochastic symmetric P=pijn×n, such that pij ≥ 0 only if i,j∈ℰ; otherwise, pij = 0 and ∑j∈Nipij=∑j=1npij=1 for all i∈V and ∑i∈Njpij=∑i=1npij=1 for all j∈V.To solve (1), we present a distributed online conjugate gradient algorithm. After giving a decision xit∈X based on the current information, we can obtain the cost function fti(x) and compute the gradient git=∇ftixt. We can then calculate the value of βi(t) using the gradients in the current iteration point xi(t) and the previous iteration point xi(t − 1). If βi(t) > 0, a new search direction di(t), computed using a Gram–Schmidt conjugate of the gradients in the current iteration point xi(t) and the previous search direction di(t − 1), can be constructed. If the parameter is βi(t) ≤ 0, we then obtain the new search direction dit=−git, which is equivalent to restarting the distributed online conjugate gradient algorithm in the direction of the steepest descent. The iteration step length αi(t) can be obtained through an exact line search, and the next iteration point xi(t + 1) can be obtained using the conjugate direction vector di(t) and step αi(t). The specific algorithm is summarized in Algorithm 1.Algorithm 1:Distributed Online Conjugate Gradient Algorithm (D-OCG).
(1)
Input: convex setX, maximum round number T
(2)
Initialize:xi1∈X,zi1=0, ∀i ∈ V
(3)
for
i = 1, …, Tdo
(4)
The adversary revealsfti, ∀i ∈ V
(5)
Compute the gradientsgit ∈ ∂fti(xi(t)), ∀i ∈ V
(6)
Compute:
βitPRP=gitTgit−git−1/git−12,
βi(t) = max{0, βi(t)PRP},
dit=−gi1,t=1−git+βitdit−1,t>1
(7)
λit=argminλ≥0ftixit+1/2tλdit
αit=λit/t, ∀i ∈ V
(8)
for each i ∈ Vdo
(9)
zit+1=∑j=1npijzjt−dit
(10)
xit+1=∏Xφx−zit+1,αit
(11)
end for
(12)
end forHere, we define the projection function used in this algorithm as follows:(12)∏Xφxu,αt=argminx∈Xu,x+1αtφx.


## 4. Regret Bound Analysis

To analyze the regret bound for D-OCG, we provide some preliminary remarks and a few definitions. Using Algorithm1, we can determine the following:(13)zit+1=∑j=1npijzjt−dit,xit+1=∏Xφx−zit+1,αit.Now, we define(14)z¯t=1n∑i=1nzit,d¯t=1n∑i=1ndit,yt=∏Xφx−z¯t+1,αt,and from the evolution of zi(t + 1), we can obtain(15)z¯t+1=z¯t−d¯t.Now, the main results in our paper can be stated.Theorem 1.
The sequences ofxi(t) and zi(t) generated by Algorithm 1 are given for all i∈V, where φx=1/2x2, φx∗≤R2, and αit=1/tλit, and we thus have the cumulative regret owing to the action of agent i,s(16)RTx∗,xit=∑t=1Tftxit−ftx∗≤n+2M+mm1−σ2Pn+b+1M+m22m2λL2T+1λb+1R2T+bD,where λ = max1≤i≤n, 1≤t≤T{λi(t)}, b and D are two nonnegative constants, M and m are as defined in Lemma 1, n is the number of agents, and σ2(P) is the second largest eigenvalue of the adjacency matrix P.From Theorem1, we obtain a regret bound of the proposed algorithm under the local convexity, which is sublinear to T, i.e., the regret bound of the D-OCG algorithm can approach zero as the value of T increases, where T is the number of iterations. It is evident that the value of the regret bound is related to the upper bound L of the gradient of the local objective functions and the diameter R of the constraint set X. By Lemma 1, we know that the regret bound is also related to the Hessian matrix of the local objective functions. Moreover, the value of the regret bound is also related to the scale and topology of the network.To prove Theorem1, we now present the following lemmas.Lemma 2.
For anyi∈V and x∗∈X, we can obtain the following inequality:(17)∑t=1Tftxit−ftx∗≤L+Ln∑t=1Txit−yt+∑t=1T1n∑i=1nftxit−ftx∗.Proof.
Based on assumption (i), the functionft(xi(t)) is L-Lipschitz continuous on the convex set X, that is,(18)ftxit−ftyt≤Lxit−yt,and thus(19)∑t=1Tftxit−ftx∗=∑t=1Tftxit−ftyt+ftyt−ftx∗≤L∑t=1Txit−yt+∑t=1Tftyt−ftx∗.
By contrast,(20)∑t=1Tftyt−ftx∗=∑t=1T1n∑i=1nftyt−ftxit+ftxit−ftx∗≤Ln∑t=1T∑i=1nxit−yt+∑t=1T1n∑i=1nftxit−ftx∗.
Combining equations (19) and (20), the proof of Lemma 2 is completed.
Now, we prove that the last term of inequality (20) has a particular bound.Lemma 3.
For anyi∈V and x∗∈X,(21)∑t=1T1n∑i=1nftxit−ftx∗≤Ln∑t=1T∑i=1nxit−yt+∑t=1T1n∑i=1ngit,yt−x∗.Proof.
Becausegit=∇ftxit is a gradient of ft(x) at xi(t), using the convexity for function ft(x), we have(22)ftxit−ftx∗≤git,xit−x∗.
Then, based on assumption (i), we know thatgit≤L. We can then obtain the following:(23)git,xit−x∗=git,xit−yt+git,yt−x∗≤Lxit−yt+git,yt−x∗.
Summing fort = 1, …, T for the average of git,xit−x∗, the following is obtained:(24)∑t=1T1n∑i=1ngit,xit−x∗=∑t=1T1n∑i=1ngit,xit−yt+yt−x∗≤Ln∑t=1T∑i=1nxit−yt+∑t=1T1n∑i=1ngit,yt−x∗.
The proof of Lemma3 is completed.
Now, we turn our attention to the following term:(25)∑t=1T1n∑i=1ngit,yt−x∗.
According to the definition of the conjugate gradient, we give the bound of equation (25) in Lemma 4.Lemma 4.
For anyi∈V and βi(t) ≤ b (where b is a nonnegative constant), the following bound holds:(26)∑t=1T1n∑i=1ngit,yt−x∗≤b+112∑t=1Tαt−1d¯t−1∗2+1αTφx∗+bφαT∗z¯T.Proof.
Based on the definitions ofdi(t) and d¯t, the left-hand side of the above inequality can be split into two:(27)∑t=1T1n∑i=1ngit,yt−x∗=∑t=1T1n∑i=1n−dit+βitdit−1,yt−x∗=∑t=1T1n∑i=1n−dit,yt−x∗+∑t=1T1n∑i=1nβitdit−1,yt−x∗=∑t=1T−d¯t,yt−x∗+∑t=1T1n∑i=1nβitdit−1,yt−x∗.
Thus, we prove that the first term in equation (27) has a bound. For any function f(x), we know that(28)fx≤supx∈domffx,where dom f is the domain of the function f(x). Therefore, for the function(29)Gx=∑t=1Td¯t,x−1αTφx,x∈X,we can obtain for any x∗∈X,(30)Gx∗≤supx∈XGx,that is,(31)∑t=1Td¯t,x∗−1αTφx∗≤supx∈X∑t=1Td¯t,x−1αTφx,so(32)∑t=1Td¯t,x∗≤supx∈X∑t=1Td¯t,x−1αTφx+1αTφx∗.
Based on the definition of the conjugate function [40] and the updates for z¯t, we have the following:(33)∑t=1Td¯t,x∗≤φαT∗∑t=1Td¯t+1αTφx∗≤φαT∗−z¯T+1+1αTφx∗.
Becauseα(t) is a nonincreasing sequence, based on the definition of the conjugate function φα∗z, we can obtain for all z∈ℝd,(34)φαt∗z≤φαt−1∗z,and thus we obtain the following:(35)φαt∗−z¯t+1≤φαt−1∗−z¯t+d¯t.
According to the inequality (11), we know that(36)φαt−1∗−z¯t+d¯t≤φαt−1∗−z¯t+d¯t,x+12αt−1d¯t∗2.
A detailed proof of equation (36) is provided in Appendix A. The following inequality is then established:(37)−d¯t,x≤φαt−1∗−z¯t−φαt∗−z¯t+1+12αt−1d¯t∗2.
Summing both sides of the above inequation fromt = 1 to T, we obtain the following:(38)∑t=1T−d¯t,x≤∑t=1Tφαt−1∗−z¯t−φαt∗−z¯t+1+12∑t=1Tαt−1d¯t∗2.
Through equations (33) and (38), we can write the following:(39)∑t=1T1n∑i=1n−dit,yt−x∗=∑t=1T−d¯t,yt−x∗=∑t=1T−d¯t,yt+∑t=1Td¯t,x∗≤∑t=1Tφαt−1∗−z¯t−φαt∗−z¯t+1+12∑t=1Tαt−1d¯t∗2+φαT∗−z¯T+1+1αTφx∗≤12∑t=1Tαt−1d¯t∗2+1αTφx∗.
We then analyze the bound on the second term in inequality (27). Because βi(t) = max1≤i≤n{0, βi(t)PRP}, and βi(t) ≤ b, we then analyze the following two situations.Case 1.
If(40)1n∑i=1nβitdit−1,yt−x∗≤0,then,(41)∑t=1T1n∑i=1nβitdit−1,yt−x∗≤0.
The conclusion therefore clearly holds.Case 2.
If(42)1n∑i=1nβitdit−1,yt−x∗>0,without loss of generality, we assume that for all i∈V,(43)dit−1,yt−x∗>0,so(44)1n∑i=1nβitdit−1,yt−x∗≤1n∑i=1nbdit−1,yt−x∗≤b1n∑i=1ndit−1,yt−x∗.
That is,(45)1n∑i=1nβitdit−1,yt−x∗≤bd¯t−1,yt−x∗.
Summing fort = 1, 2, …, T,(46)∑t=1T1n∑i=1nβitdit−1,yt−x∗≤b∑t=1Td¯t−1,yt−x∗.
Next, we give the bound of∑t=1Td¯t−1,yt−x∗.
Because(47)∑t=1Td¯t−1,yt−x∗=∑t=1Td¯t−1,yt+∑t=1T−d¯t−1,x∗,similar to the proof of inequality (33), we can obtain the following:(48)∑t=1T−d¯t−1,x∗≤φαT∗z¯T+1αTφx∗.
Through inequality (11), we obtain the following:(49)d¯t−1,x≤φαt−1∗−z¯t−φαt−1∗−z¯t−1+α2d¯t−1∗2.
In addition to the definition of functionφαt−1∗z, when z = 0,(50)φαt−1∗0=supx∈X−1αt−1φx=supx−1αt−1φx−δx∈X.
The definition of the projection shows that the supremum of the above equation is uniquely attained through∏Xφ0,αt−1. In addition, for all fixed z, when x = 0, z,x−1/αt−1φx−δx∈X=0, and thus we can obtain the supremum of φαt−1∗0 to the set.(51)x1αt−1φx+δx∈X−z,x≤0=X∩x1αt−1φx−z,x≤0.
Because the setX is closed and φ(x) is strongly convex (for the definition of strongly convex, see [40]), the set described above is compact. By contrast, we know that 〈z, x〉 is differentiable in z, and the supremum is unique, and thus we can obtain the following: ∇φαt−1∗0=∏Xφ0,αt−1=argminx∈X1/αt−1φx.
Then, we derive the next two equations through Taylor expansion:(52)φαt−1∗−z¯t≈φαt−1∗0+∇φαt−1∗0−z¯t,φαt−1∗−z¯t−1≈φαt−1∗0+∇φαt−1∗0−z¯t−1,and thus(53)φαt−1∗−z¯t−φαt−1∗−z¯t−1=∇φαt−1∗0−z¯t−−z¯t−1≤∇φαt−1∗0−z¯t+z¯t−1≤argminx∈χ1αt−1φxz¯t−z¯t−1.
Because0∈X, φx=1/2x2,(54)argminx∈X1αt−1φx=0,and therefore(55)φαt−1∗−z¯t−φαt−1∗−z¯t−1≤0.
Thus,(56)d¯t−1,x≤φαt−1∗−z¯t−φαt−1∗−z¯t−1+αt−12d¯t−1∗2≤α2d¯t−1∗2.
Summing both sides of the above inequation fromt = 1 to T, we obtain(57)∑t=1Td¯t−1,x≤12∑t=1Tαt−1d¯t−1∗2,and combining equations (46)–(57), we obtain the following:(58)∑t=1T1n∑i=1nβitdit−1,yt−x∗≤b2∑t=1Tαt−1d¯t−1∗2+bφαT∗z¯T+bαTφx∗.
Through equations (27), (39), and (58), we finalize the proof of Lemma 4.
Mark:(1)
The definition of the conjugate function for1/αTφx is as follows:(59)φαT∗z=supx∈χz,x−1αTφx.(2)
Through inequality (15) and step 2 in Algorithm 1, for all i∈V, z¯1=1/n∑i=1nzi1=0, we can obtain the following:(60)z¯T+1=z¯T−d¯T=⋯=z¯1−∑t=1Td¯t=−∑t=1Td¯t.
Next, we provide an important inequality, which will be used in the proof of Lemma6.Lemma 5.
(α-Lipschitz continuity of the projections). For any pair u,v∈ℝn,αt=max1≤i≤nαit, we have the following:(61)∏Xφu,αit−∏Xφv,αt≤αtu−v.A detailed proof of this Lemma can be seen in AppendixB.Now, we focus on an analysis of a key result concerning regret, i.e., ∥xi(t) − y(t)∥ in Lemma 6.Lemma 6.
For alli∈V and t ∈{0, …, T}, the following inequality is true:(62)xit−yt≤m+MnLm1−σ2Pαt−1.Proof.
Becausexi(t) and y(t) are the projections of zi(t) and z¯t onto the set X, through Lemma 5, we have the following:(63)xit−yt=∏Xφx−zit,αit−1−∏Xφx−z¯t,αt−1≤αt−1zit−z¯t.
Now, considering the evolution of sequence {zi(t)} in Algorithm 1, we obtain the following:(64)zit=∑j=1npijzjt−1−dit−1=∑j=1npij∑j=1npijzjt−2−dit−2−dit−1=⋯=−∑r=1t−1∑j=1npijt−r−1djr.
Becausepij is an element of a doubly stochastic matrix, ∑i=1npij=1, then we have(65)z¯t+1=1n∑i=1nzit+1=1n∑i=1n∑j=1npijzjt−dit=1n∑j=1n∑i=1npijzjt−1n∑i=1ndit=1n∑j=1nzjt−1n∑i=1ndit=z¯t−d¯t.
Based on Algorithm1 and the definition of z¯t, we can determine that z¯1=0, and thus(66)z¯t+1=z¯t−d¯t=z¯t−1−d¯t−1−d¯t=⋯=−∑r=1td¯r.
In addition, we can obtain(67)z˜t=−∑r=1t−1d¯r=−1n∑r=1t−1∑j=1ndjr,and based on the definition for the 1 norm of the vector (see [41]),(68)zit−z¯t=∑r=1t−1∑j=1npijt−r−1−1ndjr≤∑r=1t−1∑j=1npijt−r−1−1ndjr≤m+MmL∑r=1t−1Pit−r−1−1n1=m+MmL∑r=1t−1Pt−r−1ei−1n1.
To obtain a more specific bound of equation (46), we introduce a useful property of a stochastic matrix as follows [12]:(69)Pt−r−1ei−1n1≤σ2Pt−r−1n,where Pt−r−1 denotes the (t − r − 1)-th power of matrix P, ei is the ith basis coordinate of an n-dimensional space ℝn, 1 denotes a vector with all entries equal to 1, and σ2(P) is the second largest eigenvalue of stochastic matrices P and σ2(P) ≤ 1, through which we obtain the following inequality:(70)m+MmL∑r=1t−1Pt−r−1ei−1n1≤m+MmL∑r=1t−1σ2Pt−r−1n≤m+MnL1−σ2Pm.
Combining equations (63), (68), and (70) yields the following:(71)xit−yt≤m+MnLm1−σ2Pαt−1.
Thus, we complete the proof of Lemma6
Now, we can provide a brief proof of Theorem1.Proof of Theorem 1.
Combining lemmata2–6 yields the following regret bound:(72)RTx∗,xit=∑t=1Tft,ixit−ftx∗≤L+Ln∑t=1Txit−yt+Ln∑t=1T∑i=1nxit−yt+b+112∑t=1Tαt−1d¯t−1∗2+1αTφx∗+bφαT∗z¯T.
By equation (71) and based on αt=λ/t, φx∗≤R2, φαT∗z¯T≤D,andd¯t−1∗2≤M+m2/m2L2, we can obtain the conclusion to Theorem 1.


## 5. Simulation Experiments

To verify the performance of the D-OCG, we consider a problem of a distributed sensor network [18], which has n sensors and aims at the estimation of a random vector x∈X=x∈ℝdx22≤xmax2. In this network, at each time t ∈ {1, 2, …, T}, each sensor i receives an observation vector vti:ℝd⟶ℝm, in which the vector vti is time-varying owing to the effect of the observed noise. Assume that each sensor i has a linear model ϕi(x) = Aix, where Ai is the observation matrix of sensor i, and Ai∈ℝm×d and ∥Ai∥1 ≤ ϕmax. The local cost function in sensor i is defined as ftix^=1/2vti−Aix^22, where vti = Aix + ηti, in which ηti is white noise. The mathematical model of this problem is(73)minfx^∑t=1T∑i=1n12vti−Aix^22subject tox^∈X.In an offline case, the cost function in each sensori is fixed, and because we can know all information of the cost function in advance, the centralized optimal estimate for this problem can be obtained by(74)x∗=1T∑t=1T∑i=1nAiTAi−1∑i=1nAivti.In a practical problem, the characteristics of the white noise may be unknown, or some sensors might not work properly for a particular reason, and we therefore need to find an estimate for vectorx using a distributed online algorithm. Here, we set d = 1 and Ai=1/2, and sensor i observes vti = atix + bti, where ati ∼U(0, 1) and bti∼U−1/4,1/4 (in which x ∼ U(a, b) indicates a random vector x uniformly distributed on (0, 1)). Then, the cost function for sensor i at each time t is given by fti:ℝ⟶ℝ, where fti=1/2vti−Aix^2 and Ai∈ℝ.We verified the performance of the proposed algorithm based on the following three aspects:(1)
First, we determined how the number of nodes in the network affects the performance of the D-OCG. We can see from Figure1 that the average regret decreases slowly when we increase the number of nodes, and the algorithm is convergent on different scaled networks. When n = 1, the problem is equivalent to a centralized optimization problem, and our distributed optimization algorithm can reach the same effect as the centralized algorithm.(2)
We then checked how the network topology influences the performance of the D-OCG. We implemented the algorithm on three types of graphs with nine nodes. In a complete graph, each node is connected to the remaining nodes, that is, all nodes can exchange information with each other. In a cycle graph, each node is only connected to two nodes directly adjacent to it. The connectivity of a Watts–Strogatz graph is between the complete graph and the cycle graph. From Figure2, it can be seen that a better connectivity can lead to a slightly faster convergence.(3)
We next compared our algorithm with the class algorithm D-OGD in [20]. The parameters used in these two algorithms are based on their theoretical proofs. The network topology relationship among nodes is complete, whereas for nodes n = 9, the step size is αt=1/t. As shown in Figure 3, the convergence speed of the two algorithms is initially close, but with an increase in the number of iterations, the D-OCG converges faster than the D-OGD, which fully reflects the excellent performance of the proposed algorithm.Figure 1
The performance of our algorithm with different numbers of nodes.Figure 2
The performance of our algorithm with different topologies.Figure 3
Comparison of D-OCG and D-OGD with nine nodes.


## 6. Conclusion

We proposed a distributed online conjugate gradient algorithm to solve the distributed optimization problem with a convex constraint in a network. With this algorithm, the conjugate gradient is used to replace the gradient or subgradient in a traditional gradient decent method. Because the search direction is mutually conjugated throughout the entire algorithm iteration process, we can remove the disadvantage that a slow convergence has in the later stage of a gradient decent. We also presented a detailed analysis of the convergence for the proposed algorithm and obtained a regret bound for the optimization problem. The regret bound has a sublinear convergence. We applied the proposed algorithm (D-OCG) to a distributed sensor estimation problem. The numerical results show that our algorithm is feasible and effective, and under the same assumptions, the D-OCG has a better convergence rate than the traditional D-OGD gradient method.



---

*Source: 1390963-2020-03-11.xml*