# A Distributed Online Newton Step Algorithm for Multi-Agent Systems

Authors: Xiaofei Chu
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Most of the current algorithms for solving distributed online optimization problems are based on the first-order method, which are simple in computation but slow in convergence. Newton’s algorithm with fast convergence speed needs to calculate the Hessian matrix and its inverse, leading to computationally complex. A distributed online optimization algorithm based on Newton’s step is proposed in this paper, which constructs a positive definite matrix by using the first-order information of the objective function to replace the inverse of the Hessian matrix in Newton’s method. The convergence of the algorithm is proved theoretically and the regret bound of the algorithm is obtained. Finally, numerical experiments are used to verify the feasibility and efficiency of the proposed algorithm. The experimental results show that the proposed algorithm has an efficient performance on practical problems, compared to several existing gradient descent algorithms.


---

## Body

## 1. Introduction

In recent years, with the development of computer network technology, distributed optimization algorithms [1–3] have been successfully applied to solve large-scale optimization problems, which are considered to be an effective method. Distributed optimization decomposes a large-scale optimization problem into multiple subproblems according to different agents in a multi-agent network. Different agents calculate their associated subproblems simultaneously and communicate information with their immediate neighbor agents. And, all the agents finally obtain a common optimal solution that can minimize the sum of their objective functions through the exchange of information along with their respective optimization iteration. Many problems in science and engineering can be modeled as problems, such as machine learning [4], signal tracking and location [5], sensor networks [6, 7], and smart grids [8].Distributed optimization assumes that the local objective function is known and invariant. However, many practical problems in diverse fields are affected by their environment and the corresponding objective function is changing all the time, which requires the optimization process of these problems in the online setting. In the distributed online optimization problem, each agent has a limited amount of information. Only when one agent makes a decision with the current information can it know the relevant information of its corresponding objective function, which leads to the inevitable outcome: the decision it makes is not the optimal and the difference, so-called regret, exists between make-decisions of all agents, respectively. Regret is one of the most straightforward measures of the performance of an online algorithm. Obviously, the smaller the regret, the better the performance of the algorithm. Since the implementation of the algorithm is completed after multiple iterations, we theoretically require that the regret generated by multiple iterations should gradually approach to zero along with the increasing of iterative number. That is, if the corresponding cumulative regret bound of the algorithm can be got, the regret bound should be sublinear convergence with respect to the number of iteration.Distributed online optimization and its applications in multi-agent systems have become a hot research area nowadays in the systems and control community. Inspired by the distributed dual average algorithm in [3], the authors in [9] proposed a distributed online weighted dual average algorithm for the distributed optimization problem on dynamic networks and obtained a square-root regret bound. Yan et al. [10] introduced a distributed online projected subgradient descent algorithm and achieved a square-root regret for convex locally cost functions and a logarithmic regret for strongly convex locally cost function. In [11], a distributed stochastic subgradient online optimization algorithm is proposed. In the case that the local objective function is convex and strongly convex, the convergence of the algorithm is proved, and the corresponding regret bounds are obtained respectively. For more references on distributed online algorithms, see [12–21].The distributed online optimization algorithm based on the first-order information is simple in a calculation but converges slowly in most cases. In the traditional optimization method, Newton’s method converges faster than the first-order information when it uses the second-order gradient information of the objective function. Some scholars have applied it to distributed optimization problems [22–24] to improve the convergence of distributed online optimization algorithm. However, these algorithms need to compute and store the Hessian matrix of the objective along with its inverse at each iteration, which will inevitably affect the efficiency. To overcome such inconvenience, inspired by the algorithm mentioned in reference [25], we propose a distributed online Newton step algorithm, which can achieve the effect of the Newton method by using the first information of the objective function.The major contributions of this article are as follows: (i) for the distributed online optimization problem, we propose a distributed online Newton step algorithm which can not only avoid the deficiencies of calculation and storage in the process of Newton method implementation but also achieve the effectiveness of Newton’s method. In the algorithm, the first-order gradient of the object function has been used to construct a positive definite matrix, which is similar to the inverse of the Hessian matrix in the Newton method. Moreover, the convergence of the proposed algorithm is proved theoretically, and the regret bound of the algorithm is obtained. (ii) We apply the proposed algorithm to a practical problem. The effectiveness and practicality of the algorithm is verified by numerical experiments. Meanwhile, we compare the proposed algorithm with several existing gradient descent algorithms, and the results show that the convergence rate of this algorithm is obviously faster than the gradient descent algorithms.The rest of this paper is organized as follows: in Section2, we discuss some closely related works about distributed Newton method. Some necessary mathematical preliminaries and assumptions which will be used in this paper are introduced in Section 3. Our algorithm is stated in Section 4, and the concrete proof of the convergence of the algorithm is presented in Section 5. The performance of the proposed algorithm is verified in comparison with several gradient descent algorithms over the practical problem in Section 6, and then the conclusion of this paper is included in Section 7.


## 2. Related Work

Newton and Quasi-Newton methods are recognized as a class of effective algorithms in solving optimization problems. The iterative formula of Newton method is as follows:(1)xk+1=xk−αkHk−1gk,where Hk−1 is the inverse of Hessian matrix ∇2fxk. Newton’s method needs to calculate the second derivative of the objective function and the Hessian matrix obtained may not be positive definite. In order to overcome these shortcomings, some scholars put forward the Quasi-Newton method. The basic idea of the Quasi-Newton method is to structure an approximate matrix without the second derivative of the objective function to instead of the inverse of the Hessian matrix in the Newton method. Different methods of constructing approximate matrix represent different Quasi-Newtonian methods.Although the Quasi-Newton method is recognized as a more efficient algorithm, it is seldom used in a distributed environment because the distribution approximation of Newton steps is difficult to design. Mark Eisen et al. [26] proposed a decentralized Quasi-Newton Method. In this method, the idea of determining the Newton direction is to utilize the inverse of the Hessian matrix to approximate the curvature of the cost function of the agent and its neighbor agents. This method has good convergence but faces storage and computational deficiencies for large data sets (The approach involves the power of matrices of sizes np×np with n being the total number of nodes and p being the number of features). Aryan Mokhtari, Qing Ling, and Alejandro Ribeiro in [27] proposed a Network Newton method. In this method, a distributed computing matrix is constructed by equivalent transformation of the original problem, which can replace the original Hessian matrix, so as to realize the distributed solution of the problem. The authors proved that the algorithm can converge to the approximate value of the optimal parameter at least at the linear rate. They further demonstrated the convergence rate of the algorithm and analyzed several practical implementation matters in the literature [28]. Rasul Tutunov et al. [29] proposed a distributed Newton optimization algorithm based on consensus. By using the sparsity of the dual Hessian matrix, they reconstructed the calculation of Newton steps into the method of solving diagonally dominant linear equations and realized the distributed calculation of Newton’s method. They also theoretically proved that the algorithm has superlinear convergence similar to centralized Newton’s algorithm in the field of the optimal solution. Although these algorithms realize the distributed computation of the Newton method, they need to calculate the inverse of the Hessian, which is expensive for the algorithm.Motivated by these observations, for the online setting, we propose a distributed Newton-step algorithm which can achieve a convergence rate approximate to Newton’s method on the basis of distributed computing, and the inverse of the approximate Hessian matrix can be easily calculated. Numerical experimental results show that our algorithm can run significantly faster than the algorithms in [9, 10, 19] with a lower computational cost in preiteration.


## 3. Preliminaries

In this section, some notational conventions and basic notions are introduced first. Then, we provide a brief description distributed online optimization problem. At the same time, some concepts will be used and relevant assumptions are represented in this paper.


### 3.1. Some Conceptions and Assumptions

Then-dimension Euclidean space is denoted by ℝn, X is a subset of ℝn, and ⋅ represents the Euclidean norm. Strongly convex functions are defined as follows:Definition 1.
[30] Let fx be a differentiable function on ℝn, ∇fx be the gradient of function fx at x, and X∈ℝn be a convex subset. Then fx is strictly convex on X if and only if(2)fx>fx0+∇fx0,x−x0,for all x0,x∈X×X.Lemma 1 (see [25]).
Functionfx:X⟶ℝ is differentiable on the set X with a diameter D, and α>0 is a constant. For ∀x∈X,∇fx≤L and exp−αfx is concave, then when β≤min1/4LD,α, for any x,y∈X, the following inequation holds:(3)fx≥fy+∇fyTx−y+β2x−yT∇fy∇fyTx−y.Some notations about matrices are given to be used in our proof of the convergence of the algorithm. Denote the space of alln×n matrices by ℝn×n. For a matrix A=aijn×n∈ℝn×n, aij represents the entry of A at the ith row and the jth column. AT=ajin×n is the transpose of A. A denotes the determinant of A, and λi is the ith eigenvalue of the matrix A. Then, the next equations are set up: A=∏i=1nλi, trA=∑i=1naii=∑i=1nλi. In addition, for any vector x,y,z∈ℝn, equation xTAz+yTAz=x+yTAz is set up.Definition 2.
[31] Matrix A∈ℝn×n is positive definite, if and only if for any x∈ℝn and x≠0 (0 denotes an n-dimensional vector where all the entries are 0), xTAx>0.


### 3.2. Distributed Online Optimization Problem

We consider a multiagent network system with multiple agents, each agenti is associated with a strictly convex function (with bounded first and second derivatives) ft,ix:ℝn⟶ℝ, and the function ft,ix is varying over time. All the agents cooperate to solve the following general convex consensus problem:(4)min∑i=1nft,ix,subject tox∈X.At each roundt=1,…,T, the ith agent is required to generate a decision point xit∈X according to its current local information as well as the information received from its immediate neighbors. Then, the adversary responds to each agent′s decision with a loss function ft,ix:X⟶ℝ and each agent gets the loss ft,ixit. The communication between agents is specified by an undirected graph G=V,E, where V=1,…,n is a vertex set, and E⊂V×V denotes an edge set. Undirected means if i,j∈E then j,i∈E. Each agent i can only communicate directly with its immediate neighbors Ni=j∈V|i,j∈E. The goal of the agents is to seek a sequence of decision points xit∈X,i∈V, so that the regret with respect to each agent i regarding any fixed decision x∗∈X in hindsight(5)RTxit,x=∑t=1T∑i=1nft,ixit−ft,ix∗,is sublinear in T.Throughout this paper, we make the following assumptions:(i)
each cost functionft,ix is strictly convex and twice continuous differentiable and L-Lipschitz on the convex set X(ii)
X is compact and the Euclidean diameter of X is bounded by D(iii)
exp−αftix is concave in the set X for all t and iBy assumption (i), the functionftix is convex in the set X, and with some reasonable assumptions over the domains of the value of α and x, exp−αftix is concave in the set X. In addition, the Lipschitz condition (i) implies that for any x∈X and any gradient gi, we have the following equation:(6)gi≤L.


## 3.1. Some Conceptions and Assumptions

Then-dimension Euclidean space is denoted by ℝn, X is a subset of ℝn, and ⋅ represents the Euclidean norm. Strongly convex functions are defined as follows:Definition 1.
[30] Let fx be a differentiable function on ℝn, ∇fx be the gradient of function fx at x, and X∈ℝn be a convex subset. Then fx is strictly convex on X if and only if(2)fx>fx0+∇fx0,x−x0,for all x0,x∈X×X.Lemma 1 (see [25]).
Functionfx:X⟶ℝ is differentiable on the set X with a diameter D, and α>0 is a constant. For ∀x∈X,∇fx≤L and exp−αfx is concave, then when β≤min1/4LD,α, for any x,y∈X, the following inequation holds:(3)fx≥fy+∇fyTx−y+β2x−yT∇fy∇fyTx−y.Some notations about matrices are given to be used in our proof of the convergence of the algorithm. Denote the space of alln×n matrices by ℝn×n. For a matrix A=aijn×n∈ℝn×n, aij represents the entry of A at the ith row and the jth column. AT=ajin×n is the transpose of A. A denotes the determinant of A, and λi is the ith eigenvalue of the matrix A. Then, the next equations are set up: A=∏i=1nλi, trA=∑i=1naii=∑i=1nλi. In addition, for any vector x,y,z∈ℝn, equation xTAz+yTAz=x+yTAz is set up.Definition 2.
[31] Matrix A∈ℝn×n is positive definite, if and only if for any x∈ℝn and x≠0 (0 denotes an n-dimensional vector where all the entries are 0), xTAx>0.


## 3.2. Distributed Online Optimization Problem

We consider a multiagent network system with multiple agents, each agenti is associated with a strictly convex function (with bounded first and second derivatives) ft,ix:ℝn⟶ℝ, and the function ft,ix is varying over time. All the agents cooperate to solve the following general convex consensus problem:(4)min∑i=1nft,ix,subject tox∈X.At each roundt=1,…,T, the ith agent is required to generate a decision point xit∈X according to its current local information as well as the information received from its immediate neighbors. Then, the adversary responds to each agent′s decision with a loss function ft,ix:X⟶ℝ and each agent gets the loss ft,ixit. The communication between agents is specified by an undirected graph G=V,E, where V=1,…,n is a vertex set, and E⊂V×V denotes an edge set. Undirected means if i,j∈E then j,i∈E. Each agent i can only communicate directly with its immediate neighbors Ni=j∈V|i,j∈E. The goal of the agents is to seek a sequence of decision points xit∈X,i∈V, so that the regret with respect to each agent i regarding any fixed decision x∗∈X in hindsight(5)RTxit,x=∑t=1T∑i=1nft,ixit−ft,ix∗,is sublinear in T.Throughout this paper, we make the following assumptions:(i)
each cost functionft,ix is strictly convex and twice continuous differentiable and L-Lipschitz on the convex set X(ii)
X is compact and the Euclidean diameter of X is bounded by D(iii)
exp−αftix is concave in the set X for all t and iBy assumption (i), the functionftix is convex in the set X, and with some reasonable assumptions over the domains of the value of α and x, exp−αftix is concave in the set X. In addition, the Lipschitz condition (i) implies that for any x∈X and any gradient gi, we have the following equation:(6)gi≤L.


## 4. Distributed Online Newton Step Algorithm

For problem (4), we assume that information can be exchanged among each agent in a timely manner, that is, the network topology graph between n agents is a complete graph. The communication between agents in our algorithm is modeled by a doubly stochastic symmetric P, so that 1>pij>0 only if i,j∈E, else pij=0, and ∑j=1npij=∑j∈Nipij=1 for all i∈V, ∑i=1npij=∑i∈Njpij=1 for all j∈V.


### 4.1. Algorithm

The distributed online Newton step algorithm is presented in Algorithm1.Algorithm 1: The Distributed Online Newton Step Algorithm (D-ONS).
(1)
Input: convex setχ, maximum round number T.(2)
β=1/2min1/4LD,α.(3)
Initialize:xi1∈χ, ∀i∈V.(4)
fort=1,⋯⋯,Tdo(5)
The adversary revealsft,i,∀i∈V.(6)
Compute gradientsgit∈∂ft,ixit, ∀i∈V.(7)
ComputeHit=∑r=1tgirgirT+ϵIn, ∀i∈V.(8)
for each i∈Vdo(9)
zit+1=∑j=1nPijxjt−1/βHit−1git(10)
xit+1=∏χHitzit+1(11)
end for(12)
end forThe projection function used in this algorithm is defined as follows:(7)∏XAy=argminx∈Xy−xTAy−x,where A is a positive definite matrix.


### 4.2. Algorithm Analysis

In this algorithm, when a decisionxit is made by the agent i with the current information, the corresponding cost function ft,ix can be obtained. So we can get the gradient git=∇ft,ixit. Construct a symmetric positive definite matrix Hit=∑r=1tgirgirT+ϵIn, then the direction of iteration is constructed by utilizing Hit−1 which always exists to replace the inverse of the Hessian matrix in Newton’s method. Take the linear combination of the current iteration point of agent i and the current iteration point of its neighbor agent as the starting point of the new iteration along with the size 1/β, and the projection operation is used to get the next iteration point xit+1.The calculation ofHit and its inverse Hit−1 in the algorithm can be seen from Step 7, Hit=∑r=1tgirgirT+ϵIn=∑r=1t−1girgirT+ϵIn+gitgitT=Hit−1+gitgitT, which shows that Hit can be computed via using the previous approximation matrix Hit−1 as well as the gradient git at step t. Therefore, we do not have to store all the gradients from the previous t-step iteration, at the same time, as shown by the following equation (32): (8)A+uvT−1=A−1−A−1uvTA−11+vTA−1u.LetHit−1=A,u=v=git, and Hi0=ϵIn, then Hi0−1=1/ϵIn, the inverse of Hit can be got simply. It is the same thing as solving for Hit, we just use the information from the current and the previous step.


## 4.1. Algorithm

The distributed online Newton step algorithm is presented in Algorithm1.Algorithm 1: The Distributed Online Newton Step Algorithm (D-ONS).
(1)
Input: convex setχ, maximum round number T.(2)
β=1/2min1/4LD,α.(3)
Initialize:xi1∈χ, ∀i∈V.(4)
fort=1,⋯⋯,Tdo(5)
The adversary revealsft,i,∀i∈V.(6)
Compute gradientsgit∈∂ft,ixit, ∀i∈V.(7)
ComputeHit=∑r=1tgirgirT+ϵIn, ∀i∈V.(8)
for each i∈Vdo(9)
zit+1=∑j=1nPijxjt−1/βHit−1git(10)
xit+1=∏χHitzit+1(11)
end for(12)
end forThe projection function used in this algorithm is defined as follows:(7)∏XAy=argminx∈Xy−xTAy−x,where A is a positive definite matrix.


## 4.2. Algorithm Analysis

In this algorithm, when a decisionxit is made by the agent i with the current information, the corresponding cost function ft,ix can be obtained. So we can get the gradient git=∇ft,ixit. Construct a symmetric positive definite matrix Hit=∑r=1tgirgirT+ϵIn, then the direction of iteration is constructed by utilizing Hit−1 which always exists to replace the inverse of the Hessian matrix in Newton’s method. Take the linear combination of the current iteration point of agent i and the current iteration point of its neighbor agent as the starting point of the new iteration along with the size 1/β, and the projection operation is used to get the next iteration point xit+1.The calculation ofHit and its inverse Hit−1 in the algorithm can be seen from Step 7, Hit=∑r=1tgirgirT+ϵIn=∑r=1t−1girgirT+ϵIn+gitgitT=Hit−1+gitgitT, which shows that Hit can be computed via using the previous approximation matrix Hit−1 as well as the gradient git at step t. Therefore, we do not have to store all the gradients from the previous t-step iteration, at the same time, as shown by the following equation (32): (8)A+uvT−1=A−1−A−1uvTA−11+vTA−1u.LetHit−1=A,u=v=git, and Hi0=ϵIn, then Hi0−1=1/ϵIn, the inverse of Hit can be got simply. It is the same thing as solving for Hit, we just use the information from the current and the previous step.


## 5. Convergence Analysis

Now, the main result of this paper is stated in the following.Theorem 1.
Give the sequence ofxit and zit generated by Algorithm 1 for all i∈V, x∗=argminx∈X∑i=1nft,ix, and the regret with respect to agent i′s action is(9)RTx∗,xit=∑t=1Tftixit−ftix∗,≤ϵD2β2+n2βlnTL2ϵ+1+C+C3lnTL^2+ϵL^2+ϵ,where C=C1+C2, C1=βη2n2D21−2lnη​L2/lnη2−1/lnη, C2=n3DLM+m2η/Mmϵ1−η2, C3=n4L2M+m4/8βM2m21−η2L^2, η=max1≤i,j≤npij,andM,m,L^are constants, and L^≤1/t∑r=1tgir2.From Theorem 1, the regret bound of Algorithm1 is sublinear convergence with respect to iterative number T, that is, limT⟶∞RTx∗,xit/T=0. Note that, the regret bound is related to the scale of the network. Specifically, as the network grows in size, the regret bound value also increases. In addition, the value of the regret bound is also influenced by the values of parameter ϵ and the diameter of the convex set X. The value of η indirectly reflects the connectivity of the network implying that the smaller the value of η , the smaller the regret bound of the algorithm.To prove the conclusion of Theorem 1, we first give some lemmas and their proofs.Lemma 2.
For any fixedi∈V, let ftix=ftx, then ∇ftixit=∇ftxit=git, and the following bound holds for any j∈V and x∈X(10)∑t=1Tftxit−ftx∗≤∑t=1TgitTxit−x∗−β2∑t=1Txit−x∗TgitgitTxit−x∗,where β=1/2min1/4LD,α.Proof.
According to the assumption that the functionftx is strictly convex and continuous differentiable in convex set X, and xit∈X,x∗∈X, by Lemma 1 we can obtain(11)ftxit−ftx∗≤gitTxit−x∗−β2xit−x∗TgitgitTxit−x∗.
Summing up overt=1,2,…,T can get the conclusion of Lemma 2. ■
From Lemma2, if the upper bound of the right side of the inequality can be obtained, the upper bound of the left side can be obtained, too. Therefore, we are committed to solving the upper bound of the right side of the above equation.Lemma 3.
Letyit=∑j=1npijxjt−xit, and the following bound holds for any j∈V and any x∈X,(12)∑t=1TgitTxit−x∗−β2∑t=1Txit−x∗TgitgitTxit−x∗≤β2ϵD2−∑t=1TgitTyit+β∑t=1TyitTHitxit−x∗+β2∑t=1TyitTHityit+12β∑t=1TgitTHit−1git.Proof.
according to Algorithm1, we have the following equation:(13)zit+1=∑j=1npijxjt−1βHit−1git,so(14)zit+1−x∗=∑j=1npijxjt−1βHit−1git−x∗,=xit−x∗+∑j=1npijxjt−xit−1βHit−1git,=xit−x∗+yit−1βHit−1git,then we can obtain the following next equation:(15)zit+1−x∗THitzit+1−x∗,=xit−x∗THitxit−x∗+yit−1βHit−1gitTHitxit−x∗,+xit−x∗THityit−1βHit−1git,+yit−1βHit−1gitTHityit−1βHit−1git,=xit−x∗THitxit−x∗+2yitTHitxit−x∗,−2βgitTxit−x∗−2βgitTyit+yitTHityit+1β2gitTHit−1git.
Sincexit+1 is the projection of zit+1 in the norm induced by Hit, it is a well known fact that (see [25] section 3.5 Lemma 3.9)(16)xit+1−x∗THitxit+1−x∗≤zit+1−x∗THitzit+1−x∗.
This fact together with (15) gives(17)xit+1−x∗THitxit+1−x∗≤xit−x∗THitxit−x∗+2yitTHitxit−x∗−2βgitTxit−x∗−2βgitTyit+yitTHityit+1β2gitTHit−1git.
Summing both sides of (17) from t=1 to T, we obtain the following equation:(18)∑t=1Txit+1−x∗THitxit+1−x∗≤∑t=1Txit−x∗THitxit−x∗−2β∑t=1TgitTyit−2β∑t=1TgitTxit−x∗+2∑t=1TyitTHitxit−x∗+∑t=1TyitTHityit+1β2∑t=1TgitTHit−1git,that is(19)−∑t=1Txit−x∗THit+1−Hitxit−x∗≤xi1−x∗THi1−gi1gi1Txi1−x∗−2β∑t=1TgitTyit−2β∑t=1TgitTxit−x∗−xiT+1−x∗THiTxiT+1−x∗+∑t=1TyitTHityit+2∑t=1TyitTHitxit−x∗+1β2∑t=1TgitTHit−1git.
According to Algorithm1, Hit+1−Hit=gitgitT, then(20)∑t=1Txit−x∗THit+1−Hitxit−x∗=∑t=1Txit−x∗TgitgitTxit−x∗,thus we obtain(21)∑t=1TgitTxit−x∗−β2∑t=1Txit−x∗TgitgitTxit−x∗≤β2xi1−x∗THi1−gi1gi1Txi1−x∗−∑t=1TgitTyit+β∑t=1TyitTHitxit−x∗−β2xiT+1−x∗THiTxiT+1−x∗+β2∑t=1TyitTHityit+12β∑t=1TgitTHit−1git.
Due toHi1−gi1gi1T=ϵIn, then(22)xi1−x∗THi1−gi1gi1Txi1−x∗,=ϵxi1−x∗Txi1−x∗=ϵxi1−x∗2≤ϵD2.
And, sinceHiT is positive definite, and β>0, so −β/2xiT+1−x∗THiTxiT+1−x∗≤0. Combining (21) and (22), we can state(23)∑t=1TgitTxit−x∗−β2∑t=1Txit−x∗TgitgitTxit−x∗≤β2ϵD2−∑t=1TyitTgit+β∑t=1TyitTHitxit−x∗+β2∑t=1TyitTHityit+12β∑t=1TgitTHit−1git.
Thus, the proof of Lemma3 is completed. ■
Next, we consider the last term of (23).Lemma 4.
For anyi∈V, we can get the following bound holding:(24)12β∑t=1TgitTHit−1git≤n2βlogTL2ϵ+1.Proof.
Note that,(25)gitTHit−1git=Hit−1•gitgitT=Hit−1•Hit−Hit−1,where for matrices A,B∈ℝn×n, we denote by A•B=∑i=1n∑j=1naijbij the inner product of these matrices as vectors in ℝn2. For real numbers a,b∈ℝ+ and the logarithm function y=lnx, the Taylor expansion of y in a is y=logx=loga+1/ax−a+Rnx. So logb≤loga+1/ab−a, implying a−1a−b≤loga/b. An analogous fact holds for the positive definite matrices, i.e., A−1•A−B≤logA/B, where A,B denote the determinant of the matrix A,B (see the detailed proof in [25]). This fact gives us (for convenience we denote Hi0=ϵIn)(26)∑t=1TgitTHit−1git=∑t=1THit−1•Hit−Hit−1,≤∑t=1TlogHitHit−1=logHiTHi0.
SinceHiT=∑t=1TgitgitT+ϵIn and git≤L, from the properties of matrices and determinants, we know that the largest eigenvalue of HiT is TL2+ϵ at most. Hence HiT≤TL2+ϵn and Hi0=ϵn, then(27)∑t=1TgitTHit−1git≤logHiTHi0≤nlogTL2ϵ+1.
Combining the above factors, we obtain the following equation:(28)12β∑t=1TgitTHit−1git≤n2βlogTL2ϵ+1.
The proof of Lemma4 is completed. ■
According to Algorithm1, zit+1=∑j=1npijxjt−1/βHit−1git, where −Hit−1git is the direction of iteration. Using the knowledge of matrix analysis, we have the following conclusions.Lemma 5.
For anyi∈V,1≤t≤T,(29)Hit−1git≤M+m2n2L4Mm∑r=1tgir2+ϵ,where m=minλ1,λ2,…,λn, M=maxλ1,λ2,…,λn, 0<m≤M, and λii=1,…,n is the i th eigenvalue of Hit.This conclusion gives us that when the number of iterations increases,Hit−1git converges to zero, which ensures the consistency of the algorithm. The detailed proof can be seen in Appendix A.Now, we consider the norm of vectoryit, zit+1−x∗ and get the following inequation.Lemma 6.
For any1≤i≤n,1≤t≤T, let η=max1≤i,j≤npij, 0<η<1, then(30)zit+1−x∗≤nDηt+M+m2n2L4βMm∑r=1tgir2+ϵ1−η,and(31)yit≤2nDηt+M+m2n2L4βMm∑r=1tgir2+ϵ1−η,where n is the size of the network, T is the total number of iterations. The specific proof is represented in Appendix B.Next, we turn our attention to the bound of the following termβ∑t=1TyitTHitxit−x∗−∑t=1TyitTgit+β/2∑t=1TyitTHityit. By combining the knowledge of vectors and matrices, we get Lemma 7.Lemma 7.
For anyi∈V, the following inequality holds(32)β∑t=1TyitTHitxit−x∗−∑t=1TyitTgitβ2∑t=1TyitTHityit≤2β∑t=1T∑r=1tgir2+ϵnD+M+m2n2L4βMm∑r=1tgir2+ϵ1−η2,≤C+C3lnTL^2+ϵL^2+ϵ,where C1=βη2n2D21−2lnηL2/lnη2−1/lnη, C2=n3DLM+m2η/Mmϵ1−η2, C3=n4L2M+m4/8βM2m21−η2L^2,andC=C1+C2.Proof.
According to Algorithm1, we can state(33)zit+1=∑j=1npijxjt−1βHit−1git,where β is a positive constant, and Hit−1 is the inverse of matrix Hit. We obtain the following equation:(34)git=βHit∑j=1npijxjt−zit+1.
Now, by multiplying both sides of this equation by the vectoryitT, we can obtain the following equation:(35)yitTgit=βyitTHit∑j=1npijxjt−zit+1,then the left of (32) can be written as follows:(36)∑t=1TyitTHitxit−x∗+β2∑t=1TyitTHityit−∑t=1TyitTgit=β∑t=1TyitTHitxit−x∗+β2∑t=1TyitTHityit−β∑t=1TyitTHit∑j=1npijxjt−zit+1.
The matrixHit is symmetric and positive definite, which means that yitTHityit≥0, therefore we can obtain the following equation:(37)β∑t=1TyitTHitxit−x∗+β2∑t=1TyitTHityit−β∑t=1T∑j=1npijxjt−zit+1THityit≤β∑t=1TyitTHitxit−x∗+β∑t=1TyitTHityit−β∑t=1TyitTHit∑j=1npijxjt−zit+1≤β∑t=1TyitTHitzit+1−x∗≤β∑t=1TyitTHitzit+1−x∗≤β∑t=1TyitHit2zit+1−x∗Hit2.
Here, we apply the Cauchy–Schwarz inequation:xTAy2≤xA2yA2, where A is a n×n Hermite matrix and A is positive semidefinite.
Next, we consider the super bound ofyitHit2 and zit+1−x∗Hit2. According to the Step 7 of Algorithm 1, Hit=∑r=1tgirgirT+ϵIn=Hit−1+gitgitT, so(38)yitHit2=yitTHityit=yitTHit−1+gitgitTyit,=yitHit−1+yitTgit2≤yitHit−1+yit2git2,≤yitHi0+yit2gi12+⋯+yit2git2,≤ϵyit2+∑r=1tyit2gir2≤ϵ+∑r=1tgir2yit2.
Similarly, we have the following equation:(39)zit+1−x∗Hit2≤ϵ+∑r=1tgir2zit+1−x∗2.
Combining the results of Lemmas5 and 6, we have the following equation:(40)yitHit2zit+1−x∗Hit2≤4ϵ+∑r=1tgir22nDηt+M+m2n2L4βMm∑r=1tgir2+ϵ1−η4,then(41)β∑t=1TyitTHitxit−x∗+β2∑t=1TyitTHityit−β∑t=1T∑j=1npijxjt−zit+1THityit≤β∑t=1TyitTHitzit+1−x∗≤β∑t=1TyitHit2zit+1−x∗Hit2,≤2β∑t=1Tϵ+∑r=1tgir2nDηt+M+m2n2L4βMm∑r=1tgir2+ϵ1−η2.
Thus, we complete the proof of Lemma7. ■
Putting all these together, Theorem1 can be proved as follows.Proof of Theorem 1.
According to the assumptions,fx is strictly convex, and the function exp−αfx is concave in X when the value of α is sufficiently small. Setting β=min1/4LD,α, combined with axioms 2–7, we can obtain the regret bound(42)RTx∗,xit=∑t=1Tftixitftix∗≤ϵD2β2+n2βlogTL2ϵ+1+C+C3logTL^2+ϵL^2+ϵ.
The values of the parameters in equation (15) are the same as Theorem 1. ■


## 6. Numerical Experiment

In order to verify the performance of our proposed algorithm, we conducted a numerical experiment on an online estimation over a distributed sensor network which is mentioned in reference [9]. In a distributed sensor network, there are n sensors (See Figure 1 in [9]). Each sensor is connected to one or more sensors. It is assumed that each sensor is connected to a processing unit. Finally, the processing units are integrated to obtain the best evaluation of the environment. The specific model is as follows: given a closed convex set X=x∈ℝn|x2≤xmax, the observation vector yt,i:ℝn⟶ℝd represents the i th sensor measurement at time t which is uncertain and time-varying due to the sensor’s susceptibility to unknown environmental factors such as jamming. The sensor is assumed (not necessarily accurately) to have a linear model of the form hix=Hix, where Hi∈ℝn×d is the observation matrix of sensor i and Hi1≤hmax for all i. The objective is to find the argument x^∈X that minimizes the cost function fx^=1/n∑i=1nft,ix^, namely,(43)min1n∑i=1nft,ix^,subject tox^∈X,where the cost function associated with sensor i is ft,ix^=1/2yt,ix−Hix^22. Since the observed value yt,i changes with time t, only when we calculate the value of x^it can we get the local error of the i th sensor at time t. In other words, due to modeling errors and uncertainties in the environment, the local error functions are allowed to change over time.Figure 1
Comparisonn = 1, n = 10, n = 100.In an offline setting, each sensori has a noisy observation yt,i=Hix+vt,i=Hix+v1,i for all t=1,2,…,T, where vt,i is generally assumed to be (independent) white noise at time t. In this case, the centralized optimal estimate for problem (37) is(44)x^∗=∑i=1nHiTHi−1∑i=1nHiTy1,ix.While in an online setting, the white noisevt,i varies with time t (see [9]). We assume vt,i∼U−1/4,1/4 (The white noise vt,i is uniformly distributed on the interval −1/4,1/4). In the proposed distributed online algorithm, each sensor i calculate x^it∈X based on the local information available to it and then an “oracle” reveals the cost ft,ix^ at time step t.The performance of the proposed algorithm is discussed based on the following aspects:


### 6.1. The Analysis of the Algorithm Performance

The numerical experiments consist of two parts: the impact of network size on the performance of the D-ONS and the effect of network connectivity on the effectiveness of the algorithm iterations.We carried out numerical experiments atn = 1, n = 2 and n = 100, respectively. Figure 1 depicts the convergence curves of the algorithm for different network sizes. According to Figure 1, it is obvious that the average regret decreases fast and the algorithm can converge on different scaled networks as the number of the agent in the network increase. Especially, 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.According to Theorem1, the effectiveness of the algorithm is directly affected by the connectivity of the network, so we verify the algorithm under different network topology. (i) Complete graph. All the agents are connected to each other. (ii) Cycle graph. Each agent is only connected to its two immediate neighbors. (iii) Watts–Strogatz. The connectivity of random graphs is related to the average degree and connection probability. Here, let the average degree of the graph is 3 and the probability of connection is 0.6. As shown in Figure 2, D-ONS can lead to a significantly faster convergence on a complete graph than a cycle graph and has the similar convergence on Watts–Strogatz. The experimental result is consistent with the theoretical analysis results in this paper.Figure 2
Comparison under different topology.


### 6.2. Performance Comparison of Algorithms

To verify the performance of the proposed algorithm, we compared the proposed algorithm with the class algorithms D-OGD in [10], D-ODA in [9] and the algorithm in [19]. The parameters in these algorithms are based on their theoretical proofs. The network topology relationship among agents is complete, and the size of the network is the same n=10. As shown in Figure 3, the presented algorithm D-ONS displays better performance with faster convergence and higher accuracy than D-ODA, D-OGD, and the algorithm in [19].Figure 3
The convergence curves of compared algorithms.


## 6.1. The Analysis of the Algorithm Performance

The numerical experiments consist of two parts: the impact of network size on the performance of the D-ONS and the effect of network connectivity on the effectiveness of the algorithm iterations.We carried out numerical experiments atn = 1, n = 2 and n = 100, respectively. Figure 1 depicts the convergence curves of the algorithm for different network sizes. According to Figure 1, it is obvious that the average regret decreases fast and the algorithm can converge on different scaled networks as the number of the agent in the network increase. Especially, 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.According to Theorem1, the effectiveness of the algorithm is directly affected by the connectivity of the network, so we verify the algorithm under different network topology. (i) Complete graph. All the agents are connected to each other. (ii) Cycle graph. Each agent is only connected to its two immediate neighbors. (iii) Watts–Strogatz. The connectivity of random graphs is related to the average degree and connection probability. Here, let the average degree of the graph is 3 and the probability of connection is 0.6. As shown in Figure 2, D-ONS can lead to a significantly faster convergence on a complete graph than a cycle graph and has the similar convergence on Watts–Strogatz. The experimental result is consistent with the theoretical analysis results in this paper.Figure 2
Comparison under different topology.


## 6.2. Performance Comparison of Algorithms

To verify the performance of the proposed algorithm, we compared the proposed algorithm with the class algorithms D-OGD in [10], D-ODA in [9] and the algorithm in [19]. The parameters in these algorithms are based on their theoretical proofs. The network topology relationship among agents is complete, and the size of the network is the same n=10. As shown in Figure 3, the presented algorithm D-ONS displays better performance with faster convergence and higher accuracy than D-ODA, D-OGD, and the algorithm in [19].Figure 3
The convergence curves of compared algorithms.


## 7. Conclusion and Discussion

A distributed online optimization algorithm based on Newton step is proposed for a multiagent distributed online optimization problem, where the local objective function is strictly convex and quadratic continuously differentiable. In each iteration, the gradient of the current iteration point is used to construct a positive definite matrix, and then the direction of the next iteration is constructed by substituting this positive matrix for the inverse of the Hessian matrix in Newton’s method. Through theoretical analysis, the regret bound of the algorithm is obtained, and the regret bound converges sublinear with respect to the number of iterations. Numerical examples also demonstrate the feasibility and effectiveness of the proposed algorithm. Simulation results indicate significant convergence rate improvement of our algorithm relative to the existing distributed online algorithms based on first-order methods.



---

*Source: 1007032-2022-10-28.xml*