# Asynchronous Gossip-Based Gradient-Free Method for Multiagent Optimization

Authors: Deming Yuan
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

This paper considers the constrained multiagent optimization problem.
The objective function of the problem is a sum of convex functions,
each of which is known by a specific agent only.
For solving this problem, we propose an asynchronous distributed method
that is based on gradient-free oracles and gossip algorithm.
In contrast to the existing work, we do not require that agents be capable of
computing the subgradients of their objective functions and coordinating their step size values as well.
We prove that with probability 1 the iterates of all agents converge to the
same optimal point of the problem, for a diminishing step size.


---

## Body

## 1. Introduction

In recent years, the problem of solving convex optimization problems over a network has attracted a lot of research attention; see [1–18]. The objective function of the problem is a sum of convex functions, each of which is known by a specific agent only. Such problems arise in many real applications including distributed finite-time optimal rendezvous [2] and distributed regression over sensor networks [5]. The methods that are designed for solving these optimization problems need to be fully distributed; that is, there does not exist a central coordinator.In this paper, we propose an asynchronous gossip-based gradient-free method for solving the convex optimization problem over a multiagent network. The method is based on the gossip algorithm [19] and the gradient-free oracles [20]. The method is asynchronous in the sense that only one agent communicates at a given time, in contrast to the synchronous methods where all agents communicate simultaneously. Moreover, the method does not rely on the assumption that the information of the subgradients of the objective function is available. As is well known that for a variety of reasons there have been many instances where derivatives of the objective functions are unavailable or computationally expensive to calculate [20, 21].Literature Review. In [3], the authors study the problem of minimizing a sum of multiple convex functions, each of which is known to one specific agent only. The authors use the average consensus algorithm in the literature on multiagent systems (see, e.g., [19, 22–26]) as a mechanism to develop a distributed subgradient method for solving the optimization problem; the convergence of the method is also given for a constant step size. The authors in [7] further take the global equality and inequality constraints into consideration. The work in [2] proposes a variant of the distributed subgradient method in [3], in which at each iteration several consensus steps are executed, which simplifies the proof of the convergence of the method. Inspired by the work in [2], the authors in [6] further incorporate the global inequality constraints. The aforementioned methods are synchronous because they require that all agents in the network update at the same time. To overcome this limitation, the work in [14] develops an asynchronous distributed algorithm, based on the gossip algorithm. The algorithm is asynchronous in the sense that only one agent communicates at a given time. Moreover, all agents use different step size values and they do not require any coordination of the agents. In [5], the author further removes the need for bidirectional communications of the asynchronous algorithm in [14]; the convergence of the algorithm is also established. The aforementioned methods or algorithms, however, rely on the assumption that the subgradients of the objective functions are available to each agent, respectively.By comparison to previous work, the main contributions of this paper are twofold: (i) different from the methods or algorithms considered in existing papers, which rely on computing the subgradients of each agent’s objective function, we propose the derivative-free method which is based on utilizing the random gradient-free oracles; (ii) the proposed method is asynchronous, in the sense that all agents use different step size values that do not require any coordination of the agents. We prove that with probability 1 the iterates of all agents converge to the same optimal point of the problem, for a diminishing step size.Notation and Terminology. Let ℝd be the d-dimensional vector space. We denote the standard inner product on ℝd by 〈a,b〉=∑i=1d‍aibi, for a,b∈ℝd. We write ∥x∥ to denote the Euclidean norm of a vector x and Π𝒳[x] to denote the Euclidean projection of a vector x on 𝒳. We use xT to denote the transpose of x. For a matrix P, [P]ij represents the element in the ith row and jth column of P, and PT represents its transpose. We use 𝔼[x] to denote the expected value of a random variable x. For a function f, its gradient at a point x is represented by ∇f(x).


## 2. Problem Formulation

In this section, we start by describing the constrained multiagent optimization problem. Then, we provide some preliminary results on the gossip algorithm that we use in developing the method.


### 2.1. Constrained Multiagent Optimization

We consider the following constrained multiagent optimization problem:(1)min⁡x∈𝒳f(x)≜∑i=1N‍fi(x),
where x∈ℝd is a decision vector; fi:ℝd→ℝ is the convex objective function of agent i known only by agent i, and we assume that fi is Lipschitz continuous over 𝒳 with Lipschitz constant L(fi); 𝒳⊆ℝd is a nonempty closed convex set. We denote the optimal set of problem (1) by 𝒳*, and we assume that it is nonempty. Note that in problem (1), each function fi need not be differentiable.


### 2.2. Gossip Algorithm

The underlying network topology of problem (1) is denoted by G=(V,E), where V={1,…,N} is the node set and E is the set of links {i,j} with i≠j and {i,j}∈E only if there is a link between agents i and j. We assume that the network G is fixed, undirected, and connected.In the paper, we utilize gossip algorithm as a mechanism to design the method. To be specific, at each time instant, agenti is chosen with probability 1/N, and then with some positive probability, agent i communicates with one of its neighbors agent j. The iterations evolve as follows: for k≥0,
(2)xk+1i=xk+1j=12xki+12xkj
and for agents s that do not belong to {i,j}, update
(3)xk+1s=xks.


## 2.1. Constrained Multiagent Optimization

We consider the following constrained multiagent optimization problem:(1)min⁡x∈𝒳f(x)≜∑i=1N‍fi(x),
where x∈ℝd is a decision vector; fi:ℝd→ℝ is the convex objective function of agent i known only by agent i, and we assume that fi is Lipschitz continuous over 𝒳 with Lipschitz constant L(fi); 𝒳⊆ℝd is a nonempty closed convex set. We denote the optimal set of problem (1) by 𝒳*, and we assume that it is nonempty. Note that in problem (1), each function fi need not be differentiable.


## 2.2. Gossip Algorithm

The underlying network topology of problem (1) is denoted by G=(V,E), where V={1,…,N} is the node set and E is the set of links {i,j} with i≠j and {i,j}∈E only if there is a link between agents i and j. We assume that the network G is fixed, undirected, and connected.In the paper, we utilize gossip algorithm as a mechanism to design the method. To be specific, at each time instant, agenti is chosen with probability 1/N, and then with some positive probability, agent i communicates with one of its neighbors agent j. The iterations evolve as follows: for k≥0,
(2)xk+1i=xk+1j=12xki+12xkj
and for agents s that do not belong to {i,j}, update
(3)xk+1s=xks.


## 3. Gossip-Based Gradient-Free Method

In this section, motivated by the random gradient-free method in [20] and the gossip algorithm in [19], we present an asynchronous gossip-based gradient-free method for solving problem (1). We use Ik+1 to denote the index of the agent that is chosen to update at time k+1 and Jk+1 the index of the agent communicating with agent Ik+1. The method is given as follows.Gossip-Based Gradient-Free Method with a Diminishing Step SizeInitialize: choose random x0i∈𝒳, ∀i∈V.Iteration
(
k
≥
0
):(i)
fori∈{Ik+1,Jk+1}:(1)
computeφk+1i=(1/2)xkIk+1+(1/2)xkJk+1;(2)
computexk+1i=Π𝒳[φk+1i-σkiGμki(xki)], where σki=(Σki)-1, and Σki denotes the number of updates that agent i has performed until time k, inclusively, and Gμi(xki) is the random gradient-free oracle, given by
(4)Gμki(xki)=fi(xki+μkiνki)-fi(xki)μkiνki,whereμki=μσki, and μ is a positive constant; νki is a random variable generated locally according to the Gaussian distribution.(ii)
Fori∉{Ik+1,Jk+1}: xk+1i=xki.We useℱk to denote the σ-field generated by the entire history of the random variables to iteration k; that is,
(5)ℱk={x0i,i∈V}∪{Is+1,Js+1,νsIs+1,νsJs+1;0≤s≤k-1},
where ℱ0={x0i,i∈V}.The method can be presented in a more compact form, by defining the following weight matrix:(6)Wk+1=I-12(eIk+1-eJk+1)(eIk+1-eJk+1)T,k≥0,
where I is the identity matrix and ei∈ℝN denotes the ith standard basis vector. It is easy to see that Wk+1∈ℝN×N is doubly stochastic.Now we can write the method as follows: for allk≥0 and any i∈V,
(7)φk+1i=∑j=1N‍[Wk+1]ijxkj,xk+1i=φk+1i+[Π𝒳[φk+1i-σkiGμki(xki)]-φk+1i]×1{i∈{Ik+1,Jk+1}},
where 1{i∈{Ik+1,Jk+1}} is the indicator function of the event {i∈{Ik+1,Jk+1}}. For the gradient-free oracle Gμki(xki), we have the following lemma, which is adopted from [20].Lemma 1.
For eachi∈{Ik+1,Jk+1} and all k≥0, one has the following: (a)
𝔼[Gμki(xki)∣ℱk,Ik+1,Jk+1]=∇fμkii(xki), where fμkii(x)=(1/κ)∫ℝd‍fi(x+μkiξ)e-(1/2)∥ξ∥2dξ with κ=∫ℝd‍e-(1/2)∥ξ∥2dξ=(2π)d/2, and it satisfies:
(8)fi(x)≤fμkii(x)≤fi(x)+μkidL(fi).(b)
𝔼[∥Gμki(xki)∥2∣ℱk,Ik+1,Jk+1]≤(d+4)2L2(fi).Remark 2.
Note that method (7) is asynchronous, in the sense that to implement the method, each agent need not coordinate its step size with the step sizes of its neighbors; the time-varying parameters μki(k≥0,i∈V) share the same feature. In addition, to implement the method (7), the information of subgradients of the objective functions is not needed; however, each agent only needs to make two function evaluations per iteration to get the gradient-free oracle.Letℰki={i∈{Ik,Jk}} be the event that agent i updates at time k and πi the probability of event ℰki. It is easy to see that
(9)πi=1N+1N∑j∈Ni‍πji,
where Ni denotes the set that contains all agents that are neighboring to agent i and πji>0 denotes the probability that agent i is chosen by its neighbor j to communicate. In the paper, we denote πˇ=min⁡i∈Vπi and π^=max⁡i∈Vπi, respectively. There is an interesting link between the step size σki=(Σki)-1 and the probability πi that agent i updates.Lemma 3 (see [17]).
Letπmin⁡=min⁡{i,j}∈E⁡πij. Let σki=(Σki)-1 for all k≥1 and i∈V, and also let e be a scalar such that 0<e<1/2. Then, there exists a large enough k~=k~(e,N) such that with probability 1 for all k≥k~ and i∈V, (a)
σki≤2/kπi;(b)
(σki)2≤4N2/k2(1+πmin⁡)2;(c)
|σki-(1/kπi)|≤2/k3/2-e(1+πmin⁡)2.To establish the convergence of method (7), we also make use of the following lemma.Lemma 4 (see [5]).
Let{uk}, {vk}, {ak}, and {wk} be nonnegative random sequences such that for all k≥1, 𝔼[uk+1∣Fk]≤(1+ak)uk-vk+wk with probability 1, where Fk={{us,vs,as,ws};1≤s≤k}. If ∑k=1∞‍ak<∞ and ∑k=1∞‍wk<∞ with probability 1, then, with probability 1, the sequence {uk} converges to some random variable and ∑k=1∞‍vk<∞.We now present the main result of the paper, which is given in the following theorem.Theorem 5.
Let{xki}, i∈V, be the sequences generated by method (7) with σki=(Σki)-1 and μki=μσki, where μ is some positive constant. Assume that problem (1) has a nonempty optimal set 𝒳*. Also, assume that the sequence {νki;i∈{Ik+1,Jk+1}} is independent and identically distributed. Then the sequences {xki}, i∈V, converge to the same random point in 𝒳* with probability 1.Proof.
Fork≥0 and i∈{Ik+1,Jk+1}, we have for any x∈𝒳,
(10)∥xk+1i-x∥2=∥Π𝒳[φk+1i-σkiGμki(xki)]-x∥2≤∥φk+1i-σkiGμki(xki)-x∥2≤∥φk+1i-x∥2+(σki)2∥Gμki(xki)∥2-2σki〈Gμki(xki),φk+1i-x〉=∥φk+1i-x∥2+(σki)2∥Gμki(xki)∥2-2kπi〈Gμki(xki),φk+1i-x〉-2(σki-1kπi)〈Gμki(xki),φk+1i-x〉,
where the first inequality follows from the nonexpansive property of the projection operation. For k≥k~, by recalling Lemma 3(c), with probability 1 the last term on the right-hand side of (10) can be bounded as follows:
(11)-2(σki-1kπi)〈Gμki(xki),φk+1i-x〉≤2k3/2-e(1+πmin⁡)2(∥Gμki(xki)∥2+∥φk+1i-x∥2).
Substituting the preceding inequality into (10) gives
(12)∥xk+1i-x∥2≤(1+2k3/2-e(1+πmin⁡)2)∥φk+1i-x∥2+((σki)2+2k3/2-e(1+πmin⁡)2)∥Gμki(xki)∥2-2kπi〈Gμki(xki),φk+1i-x〉.
To simplify the notation, we denote Ak=2/k3/2-e(1+πmin⁡)2 and Bk=4N2/k2(1+πmin⁡)2+Ak; then from Lemma 3(b) and (12) it follows that with probability 1 for all k≥k~ and i∈{Ik+1,Jk+1},
(13)∥xk+1i-x∥2≤(1+Ak)∥φk+1i-x∥2+Bk∥Gμki(xki)∥2-2kπi〈Gμki(xki),φk+1i-x〉.
Taking the conditional expectation on ℱk, Ik+1 and Jk+1 jointly yields
(14)𝔼[∥xk+1i-x∥2∣ℱk,Ik+1,Jk+1]≤(1+Ak)∥φk+1i-x∥2+Bk𝔼[∥Gμki(xki)∥2∣ℱk,Ik+1,Jk+1]-2kπi〈𝔼[Gμki(xki)∣ℱk,Ik+1,Jk+1],φk+1i-x〉≤(1+Ak)∥φk+1i-x∥2+Bk(d+4)2L2(fi)-2kπi〈∇fμkii(xki),φk+1i-x〉,
where the last inequality follows from using Lemma 1. For the last term on the right-hand side of the preceding inequality, we can derive
(15)-2kπi〈∇fμkii(xki),φk+1i-x〉=-2kπi〈∇fμkii(xki),xki-x〉-2kπi〈∇fμkii(xki),φk+1i-xki〉≤-2kπi[fμkii(xki)-fμkii(x)]+2kπi∥∇fμkii(xki)∥∥φk+1i-xki∥≤-2kπi[fμkii(xki)-fμkii(x)]+2kπi(d+4)L(fi)∥φk+1i-xki∥,
where in the last inequality we have use the bound ∥∇fμkii(xki)∥≤(d+4)L(fi), according to Lemma 1. Hence, substituting (15) into (14) yields
(16)𝔼[∥xk+1i-x∥2∣ℱk,Ik+1,Jk+1]≤(1+Ak)∥φk+1i-x∥2+Bk(d+4)2L2(fi)-2kπi[fi(xki)-fi(x)]+2kπiμkidL(fi)+2kπi(d+4)L(fi)∥φk+1i-xki∥,
where we have used the inequalities fμkii(xki)≥fi(xki) and fμkii(x)≤fi(x)+μkidL(fi), based on Lemma 1(a). Using the fact that μki=μσki and Lemma 3(a), we obtain
(17)2kπiμkidL(fi)≤4μk2(πi)2dL(fi)
which implies
(18)𝔼[∥xk+1i-x∥2∣ℱk,Ik+1,Jk+1]≤(1+Ak)∥φk+1i-x∥2+Bk(d+4)2L2(fi)+4μk2(πi)2dL(fi)-2kπi[fi(xki)-fi(x)]+2kπi(d+4)L(fi)∥φk+1i-xki∥.
Taking the expectation with respect to ℱk and using the fact the preceding inequality holds with probability πi, and xk+1i=φk+1i with probability 1-πi, we obtain with probability 1 for all k≥k~ and i∈V,
(19)𝔼[∥xk+1i-x∥2∣ℱk]≤(1+πiAk)𝔼[∥φk+1i-x∥2∣ℱk]+πiBk(d+4)2L2(fi)+4μk2πidL(fi)-2k[fi(xki)-fi(x)]+2k(d+4)L(fi)𝔼[∥φk+1i-xki∥∣ℱk].
Summing the above inequality for i=1,…,N, and noting that πˇ=min⁡i∈Vπi, π^=max⁡i∈Vπi and denoting L^(f)=max⁡i∈VL(fi), we obtain with probability 1 for all k≥k~ and i∈V,
(20)∑i=1N‍𝔼[∥xk+1i-x∥2∣ℱk]≤(1+π^Ak)∑i=1N‍𝔼[∥φk+1i-x∥2∣ℱk]+Nπ^Bk(d+4)2L^2(f)+4Nμk2πˇdL^(f)-2k[f(x¯k)-f(x)]+2kL^(f)∑i=1N‍∥xki-x¯k∥+2k(d+4)L^(f)∑i=1N‍𝔼[∥φk+1i-xki∥∣ℱk],
where x¯k=(1/N)∑i=1N‍xki and we have used the following inequality:
(21)∑i=1N‍[fi(xki)-fi(x¯k)]≥-∑i=1N‍L(fi)∥xki-x¯k∥≥-L^(f)∑i=1N‍∥xki-x¯k∥.
Now by using the definition of the weight matrix Wk+1 and the convexity of the squared norm it follows that
(22)∑i=1N‍𝔼[∥φk+1i-x∥2∣ℱk]≤∑i=1N‍∑j=1N‍[Wk+1]ij∥xkj-x∥2=∑j=1N‍∥xkj-x∥2
which yields the final bound for all k≥k~ and i∈V with probability 1:
(23)∑i=1N‍𝔼[∥xk+1i-x*∥2∣ℱk]≤(1+π^Ak)∑i=1N‍∥xki-x*∥2+Nπ^Bk(d+4)2L^2(f)+4Nμk2πˇdL^(f)-2k[f(x¯k)-f(x*)]+2k(2d+9)L^(f)Nmax⁡i∈V∥xki-x¯k∥,
where x*∈𝒳* and we have used the following inequality:
(24)∑i=1N‍𝔼[∥φk+1i-xki∥∣ℱk]≤∑i=1N‍∑j=1N‍[Wk+1]ij∥xkj-xki∥≤2Nmax⁡i∈V∥xki-x¯k∥.
Now we are ready to establish the convergence of the method. First, note that
(25)∑k=1∞‍π^Ak<∞,∑k=1∞‍Nπ^Bk(d+4)2L^2(f)+∑k=1∞‍4Nμk2πˇdL^(f)<∞
which can be easily seen from the explicit expressions for Ak and Bk. For the term max⁡i∈V∥xki-x¯k∥, we can follow an argument similar to the proof of Lemma 4 in [5] and derive that for each i∈V, ∑k=1∞‍(1/k)∥xki-x¯k∥<∞ and lim⁡k→∞∥xki-x¯k∥=0, which gives
(26)∑k=1∞‍2k(2d+9)L^(f)Nmax⁡i∈V∥xki-x¯k∥<∞.
Hence, combining the preceding fact with Lemma 4, which we can obtain with probability 1, the sequence {𝔼[∥xki-x*∥2]} converges for any x*∈𝒳*, and ∑k=1∞‍(1/k)[f(x¯k)-f(x*)]<∞ (note that x¯k∈𝒳, and hence f(x¯k)-f(x*)≥0), which implies
(27)lim⁡inf⁡k→∞f(x¯k)=f(x*).
This, along with the fact that the sequence {𝔼[∥xki-x*∥2]} converges for any x*∈𝒳* and lim⁡k→∞∥xki-x¯k∥=0, gives our final statement, that is, lim⁡k→∞xki=x* for all i∈V with probability 1.Remark 6.
Note that other choices of the parametersμki(k≥0,i∈V) are possible. For example, we can set μki=μσki, for all k≥0 and any i∈V, under which case the convergence of the method (7) can also be established.Remark 7.
In contrast to the subgradient-based methods in [1–3], the implementation of the proposed method does not need the information of subgradients but only the function values. This makes our method suitable for the cases where explicit gradient calculations are computationally infeasible or expensive. In contrast to the gradient-free method in [13], the proposed method is asynchronous and the step sizes do not require any coordination of the agents.


## 4. Conclusion

In this paper, we have considered the constrained multiagent optimization problem. We present an asynchronous method that is based on the gossip algorithm and the gradient-free oracles for solving the problem. The proposed method removes the need for synchronous communications and the information of the subgradients as well. Finally, we prove that with probability 1 the iterates of all agents converge to the same optimal point of the problem, for a diminishing step size. There are several interesting questions that remain to be explored. For instance, it would be interesting to study the case of constant step size; it would be also interesting to study the effects of message quantization on the proposed method.



---

*Source: 618641-2014-04-02.xml*