# Approximate Dual Averaging Method for Multiagent Saddle-Point Problems with Stochastic Subgradients

Authors: Deming Yuan; Yang Yang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper considers the problem of solving the saddle-point problem over a network, which consists of multiple interacting agents. The global objective function of the problem is a combination of local convex-concave functions, each of which is only available to one agent. Our main focus is on the case where the projection steps are calculated approximately and the subgradients are corrupted by some stochastic noises. We propose an approximate version of the standard dual averaging method and show that the standard convergence rate is preserved, provided that the projection errors decrease at some appropriate rate and the noises are zero-mean and have bounded variance.


---

## Body

## 1. Introduction

The problem of solving optimization problems over a multiagent network has attracted a lot of attention in recent years (see, e.g., [1–13]). The objective function of such problems is, in general, a sum of local objective functions, each of which is known to one specific agent only. Moreover, the estimates of all agents are restricted to lie in some convex set. Duo to the lack of a central coordinator, the methods that are developed to solve this problem have to be executed by individual agents through local interactions.In this paper, we consider the multiagent saddle-point problem where the global objective function is given as a sum of local convex-concave functions, subject to some global constraint. We utilize the average consensus algorithm (see, e.g., [14–21]) as a mechanism to design a distributed method for solving this problem. The method is based on the standard dual averaging method (see, e.g., [1, 22]), and it can also be viewed as an approximate version of the distributed dual averaging method in [2]. Different from the distributed dual averaging methods in [1–4], which require that the projection steps have to be very accurately calculated, the proposed method assumes that they only have to be computed approximately. Moreover, the proposed method also considers the case where the subgradients are corrupted by some stochastic noises.Literature Review. In [9], the authors develop a general framework for solving convex optimization problem over a network of multiple agents. Based on the average consensus algorithms, they propose a subgradient-based method; the method is fully distributed, in the sense that each agent only needs to communicate with its neighbors. Different from the work [9], the authors in [1] propose a distributed method that is based on dual averaging of subgradients; in particular, the authors characterize the explicit convergence rate of the proposed method. The authors in [3] further study the effects of communication delays on the distributed dual averaging method. The work [4] utilizes the push-sum algorithm as a mechanism to design a distributed dual averaging method; the implementation of the method removes the need for the doubly stochastic communication matrices. In [2], the authors solve the saddle-point problem over a multiagent network; the objective function is given as a sum of multiple convex-concave functions. Based on the dual averaging method, the authors propose a distributed method and characterize its convergence rate.The contribution of our work in this paper is mainly twofold. First, we propose an approximate dual averaging method, and the implementation of the method does not need to calculate the projection steps accurately. We show how the projection errors affect the error bound of the method and conclude that the standard convergence rate is preserved when the errors decrease at some appropriate rate. Second, we further consider the case where the subgradients are corrupted by stochastic noises that are zero-mean and have bounded variance, and we also highlight the dependence of the error bound on the variance.In contrast with the work [22], we solve the saddle-point problem over a multiagent network; in particular, we show that the standard convergence rate O(1/T) (where T is the iteration counter) is preserved, even when the projection steps are computed approximately and the subgradients are corrupted by some stochastic noises. In contrast with the work [2], we propose an approximate version of the distributed dual averaging method and show that if the projection errors decrease at some appropriate rate, the standard convergence rate is preserved.The remainder of this paper is organized as follows. Section2 gives a formal statement of the multiagent saddle-point problem and the underlying network model. Section 3 presents the method and its main convergence results. Finally, we conclude with Section 4.Notation and Terminology. We use Rd to denote the d-dimensional vector space. We denote the standard inner product on Rd by 〈x,y〉=∑i=1d‍xiyi, for all x,y∈Rd. Let M be a closed convex set in Rd. We say h(x) is aproximal function of the set M if it is continuous and strongly convex on M with respect to some norm ∥·∥; that is, for all 0≤θ≤1, h(θx1+(1-θ)x2)≤θh(x1)+(1-θ)h(x2)-(σ/2)θ(1-θ)∥x1-x2∥2, for all x1,x2∈M, where σ is some positive scalar. We define theproximal center of the set M by x0=argmin⁡x∈Mh(x). For Rn×Rm, we introduce the following norm: ∥x∥∶=[γσw∥w∥22+(1-γ)σz∥z∥22]1/2, where γ∈(0,1), ∥·∥2 denotes the Eculidean norm, and σw and σz are the parameters that will be specified in the sequel. This implies the following dual norm of τ=(τw,τz)∈Rn×Rm: ∥τ∥*=[(∥τw∥22/γσw)+(∥τz∥22/(1-γ)σz)]1/2. A vector G(y0) is called asubgradient of a convex function f:Rd→R at y0∈Rd if, for all y, f(y)≥f(y0)+〈y-y0,G(y0)〉. The supergradient of a concave function can be defined accordingly.


## 2. Problem Setup

### 2.1. Communication Network Model

We consider a time-varying network withN agents. The network can be viewed as a directed graph with node set V={1,…,N} and time-varying link set. The information exchange at time k is modeled through using the communication matrix P(k)=[pij(k)]i,j∈V∈RN×N, which induces the link set E(P(k)); E(P(k)) is the set of activated links at time k, defined as E(P(k))={(j,i)∣pij(k)>0,i,j∈V}. We represent the agents’ connectivity at each time k by a directed graph G(k)=(V,E(P(k))).


### 2.2. Multiagent Saddle-Point Problem

In this paper, we are interested in solving the following problem:(1)min⁡w∈Wmax⁡z∈Z∑i=1N‍Li(w,z),
where W and Z are convex and compact sets in Rn and Rm, respectively, and each Li is a convex-concave function defined over W×Z known only by agent i.We refer to a vector pair(w*,z*)∈W×Z as asaddle point of L∶=∑i=1N‍Li over W×Z if
(2)L(w*,z)≤L(w*,z*)≤L(w,z*),∀w∈W,z∈Z.
Note that such a vector pair (w*,z*) is a solution to problem (1).We now make some assumptions on problem (1). For the set W, we assume that there exists a proximal function hw(w) with proximal center and convex parameter denoted by w0 and σw, respectively. Without loss of generality, we assume that hw(w0)=0. For the set Z we introduce the similar assumptions and notations; that is, hz(z0)=0. Therefore, for x=(w,z)∈X∶=W×Z, it is natural to introduce a proximal function h(x) of the set X, given by
(3)h(x)=γhw(w)+(1-γ)hz(z),γ∈(0,1).
It is easy to see that the proximal center of X is x0=(w0,z0) and h(x0)=0. Furthermore, we denote H∶=max⁡x∈Xh(x).


## 2.1. Communication Network Model

We consider a time-varying network withN agents. The network can be viewed as a directed graph with node set V={1,…,N} and time-varying link set. The information exchange at time k is modeled through using the communication matrix P(k)=[pij(k)]i,j∈V∈RN×N, which induces the link set E(P(k)); E(P(k)) is the set of activated links at time k, defined as E(P(k))={(j,i)∣pij(k)>0,i,j∈V}. We represent the agents’ connectivity at each time k by a directed graph G(k)=(V,E(P(k))).


## 2.2. Multiagent Saddle-Point Problem

In this paper, we are interested in solving the following problem:(1)min⁡w∈Wmax⁡z∈Z∑i=1N‍Li(w,z),
where W and Z are convex and compact sets in Rn and Rm, respectively, and each Li is a convex-concave function defined over W×Z known only by agent i.We refer to a vector pair(w*,z*)∈W×Z as asaddle point of L∶=∑i=1N‍Li over W×Z if
(2)L(w*,z)≤L(w*,z*)≤L(w,z*),∀w∈W,z∈Z.
Note that such a vector pair (w*,z*) is a solution to problem (1).We now make some assumptions on problem (1). For the set W, we assume that there exists a proximal function hw(w) with proximal center and convex parameter denoted by w0 and σw, respectively. Without loss of generality, we assume that hw(w0)=0. For the set Z we introduce the similar assumptions and notations; that is, hz(z0)=0. Therefore, for x=(w,z)∈X∶=W×Z, it is natural to introduce a proximal function h(x) of the set X, given by
(3)h(x)=γhw(w)+(1-γ)hz(z),γ∈(0,1).
It is easy to see that the proximal center of X is x0=(w0,z0) and h(x0)=0. Furthermore, we denote H∶=max⁡x∈Xh(x).


## 3. Main Results

### 3.1. The Method and Assumptions

We now propose the method, which is based on the method in [2]. Specifically, each agent i∈V updates its estimates by setting (k=0,1,…):
(4)φk+1i=∑j=1N‍pij(k)φkj+Gki+ϕki,(5)xk+1i=παk+1ξk+1(-φk+1i),
where φ0i=0∈Rn×Rm, x0i=x0, Gki=(Gwi(xki),-Gzi(xki)) (Gwi(xki) and Gzi(xki) denote a subgradient of Li with respect to w and a supergradient of Li with respect to z at point xki, respectively), ϕki∈Rn×Rm is thestochastic noise vector in evaluating Gki, {αk+1} is a positive and nondecreasing sequence, πα(φ):=argmin⁡x∈X{-〈x,φ〉+αh(x)}, and παξ(φ) satisfies the following two properties:
(6)(i)παξ(φ)∈X,(ii)∥παξ(φ)-πα(φ)∥≤ξ,
where ξ is a positive scalar that represents the error in computing the next iterate by a projection defined by the proximal function h and parameter α. Note that παξ(φ) is not uniquely defined for each ξ.In the paper, we make the following assumptions.Assumption 1 (connectivity).
For allk≥0, there exists a positive integer B such that the directed graph (V,E(P(kB))∪⋯∪E(P((k+1)B-1))) is strongly connected.Assumption 2 (weight matrix).
For allk≥0, the communication matrix P(k) satisfies the following properties: (i) P(k) is doubly stochastic and (ii) there exists a positive scalar ζ such that pii(k)≥ζ for all i∈V. In addition, if pij(k)>0, then pij(k)≥ζ for all i,j∈V.Assumption 3 (bounded subgradients).
We assume that the following inequalities hold for alli∈V and x∈X:
(7)∥Gwi(x)∥2≤GW,∥Gzi(x)∥2≤GZ,
where GW and GZ are positive scalars.Assumption 4 (stochastic subgradient).
We assume that the stochastic noise vectorϕki satisfies the following properties, for all i∈V and k≥0:
(8)(i)E[ϕki]=0,(ii)E[∥ϕki∥*2]≤Φ2,
where Φ is some positive constant.


### 3.2. Convergence Results

We show convergence of the method (4) and (5) via local average pair (w^tv,z^tv) defined at each agent v∈V,
(9)w^Tv=1T∑k=0T-1‍wkv,z^Tv=1T∑k=0T-1‍zkv,
where T≥1 is the iteration counter.With the assumptions made in Section3.1, we have the following main convergence result.Theorem 5.
Under Assumptions1, 2, 3, and 4, consider a sequence {xk+1i} generated according to the method (4) and (5), with step and projection error sizes:
(10)α0=Cα,αk=Cαk,fork≥1,ξ0=0,ξk=Cξk,fork≥1,
where Cα and Cξ are some positive scalars. Let (w*,z*)∈W×Z be a saddle point of L(w,z), and then, for each agent v∈V and all T≥1, we have
(11)E[|L(w^Tv,z^Tv)-L(w*,z*)|]≤1T[2RξCξ+NHCα+2RαCα],
where Rξ=N(5GX+Φ), Rα=(N/σ)((1/2)(GX+Φ)2+(GX+Φ)R+4GXR), GX=[(GW2/γσw)+(GZ2/(1-γ)σz)]1/2, R=((NB/V(1-V))+2)(GX+Φ), and V=1-(ζ/4N2).Proof.
See The Appendix.Remark 6.
Theorem5 represents the main convergence of the method (4) and (5), which shows that the function value L(w^tv,z^tv) converges to L(w*,z*) at rate O(1/T) in expectation, for each v∈V. It is easy to see that the error bound is an increasing function of the noise magnitude Φ. It is worth noting that, in method (4) and (5), we have considered the case where the subgradients are corrupted by stochastic noises that are zero-mean and have bounded variance, and moreover, the projection steps are calculated only approximately. In fact, the proposed method converges when the projection error ξk decreases as O(1/ka), where a>0. However, for the case when 0<a<1/2, the O(1/T) convergence rate cannot be achieved.Remark 7.
As compared to the work [2], we show that the standard O(1/T) convergence rate for the dual averaging method is preserved, under the assumption that the projection steps are only computed approximately, and the subgradients are corrupted by some stochastic noises as well. As compared to [23], the proposed method solves the saddle-point problem in a distributed setting, and the expected convergence rate is also established.


## 3.1. The Method and Assumptions

We now propose the method, which is based on the method in [2]. Specifically, each agent i∈V updates its estimates by setting (k=0,1,…):
(4)φk+1i=∑j=1N‍pij(k)φkj+Gki+ϕki,(5)xk+1i=παk+1ξk+1(-φk+1i),
where φ0i=0∈Rn×Rm, x0i=x0, Gki=(Gwi(xki),-Gzi(xki)) (Gwi(xki) and Gzi(xki) denote a subgradient of Li with respect to w and a supergradient of Li with respect to z at point xki, respectively), ϕki∈Rn×Rm is thestochastic noise vector in evaluating Gki, {αk+1} is a positive and nondecreasing sequence, πα(φ):=argmin⁡x∈X{-〈x,φ〉+αh(x)}, and παξ(φ) satisfies the following two properties:
(6)(i)παξ(φ)∈X,(ii)∥παξ(φ)-πα(φ)∥≤ξ,
where ξ is a positive scalar that represents the error in computing the next iterate by a projection defined by the proximal function h and parameter α. Note that παξ(φ) is not uniquely defined for each ξ.In the paper, we make the following assumptions.Assumption 1 (connectivity).
For allk≥0, there exists a positive integer B such that the directed graph (V,E(P(kB))∪⋯∪E(P((k+1)B-1))) is strongly connected.Assumption 2 (weight matrix).
For allk≥0, the communication matrix P(k) satisfies the following properties: (i) P(k) is doubly stochastic and (ii) there exists a positive scalar ζ such that pii(k)≥ζ for all i∈V. In addition, if pij(k)>0, then pij(k)≥ζ for all i,j∈V.Assumption 3 (bounded subgradients).
We assume that the following inequalities hold for alli∈V and x∈X:
(7)∥Gwi(x)∥2≤GW,∥Gzi(x)∥2≤GZ,
where GW and GZ are positive scalars.Assumption 4 (stochastic subgradient).
We assume that the stochastic noise vectorϕki satisfies the following properties, for all i∈V and k≥0:
(8)(i)E[ϕki]=0,(ii)E[∥ϕki∥*2]≤Φ2,
where Φ is some positive constant.


## 3.2. Convergence Results

We show convergence of the method (4) and (5) via local average pair (w^tv,z^tv) defined at each agent v∈V,
(9)w^Tv=1T∑k=0T-1‍wkv,z^Tv=1T∑k=0T-1‍zkv,
where T≥1 is the iteration counter.With the assumptions made in Section3.1, we have the following main convergence result.Theorem 5.
Under Assumptions1, 2, 3, and 4, consider a sequence {xk+1i} generated according to the method (4) and (5), with step and projection error sizes:
(10)α0=Cα,αk=Cαk,fork≥1,ξ0=0,ξk=Cξk,fork≥1,
where Cα and Cξ are some positive scalars. Let (w*,z*)∈W×Z be a saddle point of L(w,z), and then, for each agent v∈V and all T≥1, we have
(11)E[|L(w^Tv,z^Tv)-L(w*,z*)|]≤1T[2RξCξ+NHCα+2RαCα],
where Rξ=N(5GX+Φ), Rα=(N/σ)((1/2)(GX+Φ)2+(GX+Φ)R+4GXR), GX=[(GW2/γσw)+(GZ2/(1-γ)σz)]1/2, R=((NB/V(1-V))+2)(GX+Φ), and V=1-(ζ/4N2).Proof.
See The Appendix.Remark 6.
Theorem5 represents the main convergence of the method (4) and (5), which shows that the function value L(w^tv,z^tv) converges to L(w*,z*) at rate O(1/T) in expectation, for each v∈V. It is easy to see that the error bound is an increasing function of the noise magnitude Φ. It is worth noting that, in method (4) and (5), we have considered the case where the subgradients are corrupted by stochastic noises that are zero-mean and have bounded variance, and moreover, the projection steps are calculated only approximately. In fact, the proposed method converges when the projection error ξk decreases as O(1/ka), where a>0. However, for the case when 0<a<1/2, the O(1/T) convergence rate cannot be achieved.Remark 7.
As compared to the work [2], we show that the standard O(1/T) convergence rate for the dual averaging method is preserved, under the assumption that the projection steps are only computed approximately, and the subgradients are corrupted by some stochastic noises as well. As compared to [23], the proposed method solves the saddle-point problem in a distributed setting, and the expected convergence rate is also established.


## 4. Conclusion

We have studied the problem of solving saddle-point problems over a multiagent network. The objective function is given as a sum of local convex-concave functions, subject to some global constraint. Based on the average consensus algorithm and the dual averaging method, we propose an approximate dual averaging method under the constraint that the projection steps are computed approximately and the subgradients are corrupted by stochastic noises. Finally, we have presented the main convergence results of the proposed method.



---

*Source: 202737-2014-09-02.xml*