Distributed Subgradient Methods and Quantization Effects

I Introduction

There has been much interest in developing distributed methods for optimization in networked-systems consisting of multiple agents with local information structures. Such problems arise in a variety of environments including resource allocation among heterogeneous agents in large-scale networks, and information processing and estimation in sensor networks. Optimization algorithms deployed in such networks should be completely distributed, relying only on local observations and information, and robust against changes in network topology due to mobility or node failures.

Recent work has proposed a subgradient method for optimizing the sum of convex objective functions corresponding to $n$ agents connected over a time-varying topology (see also the short paper ). The goal of the agents is to cooperatively solve the unconstrained optimization problem

In this paper, we consider the distributed subgradient method discussed in , and provide improved convergence rate results. In particular, we use our recent results on the convergence time of averaging algorithms and establish new upper bounds on the difference between the objective function value of the estimates of each agent and the optimal value of problem (3). These bounds have a polynomial dependence on the number of agents $n$ (in contrast with the error bounds in , which involve exponential dependence on $n$). Furthermore, we study a variation of the distributed subgradient method in which the agents have access to quantized information, and provide bounds on the convergence time that contain additional error terms due to quantization.

In addition to the papers cited above, our work is related to the literature on reaching consensus on a particular scalar value or on computing exact averages of the initial values of the agents, a subject motivated by natural models of cooperative behavior in networked-systems (see, e.g., , , , , , and ). Closely related is also the work in and , which study the effects of quantization on the performance of averaging algorithms. Our work is also related to the utility maximization framework for resource allocation in networks (see , , ). In contrast to this literature, however, we allow the local objective functions to depend on the entire resource allocation vector.

The rest of this paper is organized as follows. In Section II, we describe the distributed subgradient method and present an improved convergence rate estimate using our recently established bounds on the convergence time of our averaging algorithms . In Section III, we consider a version of the method under the additional constraint that the agents can only exchange quantized information. We provide convergence and rate of convergence results as a function of the number of quantization levels. Section IV contains our concluding remarks.

Notation and Basic Notions. We view all vectors as columns. We use $e_{i}$ to denote the vector with $i$th entry equal to 1 and all other entries equal to 0. We use ${\bf 1}$ to denote a vector with all entries equal to 1. For a matrix $A$, we use $a_{ij}$ or $[A]_{ij}$ to denote the matrix entry in the $i$th row and $j$th column. We write $[A]_{i}$ and $[A]^{j}$ to denote respectively the $i$th row and the $j$th column of a matrix $A$. A vector $a$ is said to be a stochastic vector when its components $a_{i}$ are nonnegative and $\sum_{i}a_{i}=1$. A square matrix $A$ is said to be stochastic when each row of $A$ is a stochastic vector, and it is said to be doubly stochastic when both $A$ and its transpose $A^{\prime}$ are stochastic matrices.

We use the notation $f(x)=\sum_{j=1}^{n}f_{i}(x)$. We denote the optimal value of problem (3) by $f^{*}$ and the set of optimal solutions by $X^{*}$.

II Distributed Subgradient Method

where the scalars $a_{i1}(k),\ldots,a_{in}(k)$ are nonnegative weights and the scalar $\alpha>0$ is a stepsize. The vector $d_{i}(k)$ is a subgradient of the agent $i$ cost function $f_{i}(x)$ at $x=x_{i}(k)$. We use the notation $A(k)$ to denote the weight matrix $[a_{ij}(k)]_{i,j=1,\ldots,n}$.

The evolution of the estimates $x_{i}(k)$ generated by Eq. (4) can be equivalently represented using transition matrices. In particular, we define a transition matrix $\Phi(k,s)$ for any $s$ and $k$ with $k\geq s$, as follows:

Using these transition matrices, we relate the estimate $x_{i}(k+1)$ to the estimates $x_{1}(s),\ldots,x_{n}(s)$ for any $s\leq k$. In particular, for the iterates generated by Eq. (4), we have for any $i$, and any $s$ and $k$ with $k\geq s$,

(for more details, see ). As seen from the preceding relation, to study the asymptotic behavior of the estimates $x^{i}(k)$, we need to understand the behavior of the transition matrices $\Phi(k,s)$. We do this under some assumptions on the agent interactions that translate into some properties of transition matrices.

Our first assumption imposes some conditions on the weights $a_{ij}(k)$ in Eq. (4).

For all $k\geq 0$, the weight matrix $A(k)$ is doubly stochastic with positive diagonal. Additionally, there is a scalar $\eta>0$ such that if $a_{ij}(k)>0$, then $a_{ij}(k)\geq\eta$.

The doubly stochasticity assumption on the weight matrix will guarantee that the subgradient of the objective function $f_{i}$ of every agent $i$ will receive the same weight in the long run. The second part of the assumption states that each agent gives significant weight to its own values and to the values of its neighbors.

At each time $k$, the agents’ connectivity can be represented by a directed graph $G(k)=(V,\mathcal{E}(A(k)))$, where $\mathcal{E}(A)$ is the set of directed edges $(j,i)$, including self-edges $(i,i)$, such that $a_{ij}>0$. Our next assumption ensures that the agents are connected frequently enough to persistently influence each other.

There exists an integer $B\geq 1$ such that the directed graph

Here, we provide some results that we use later in our convergence analysis of method (4). These results hold under Assumptions 1 and 2.

Consider a related update rule of the form

where $\bar{z}(k)$ is the average of the entries of the vector $z(k)$. Under the doubly stochasticity of $A(k)$, the initial average $\bar{z}(0)$ is preserved by the update rule (8), i.e., $\bar{z}(k)=\bar{z}(0)$ for all $k$. Hence, the function $V(k)$ measures the “disagreement” in agent values.

In the next lemma, we give a bound on the decrease of the agent disagreement $V(kB)$, which is linear in $\eta$ and quadratic in $n^{-1}$. This bound is an immediate consequence of Lemma 5 in .

Let Assumptions 1 and 2 hold. Then, $V(k)$ is nonincreasing in $k$. Furthermore,

Using Lemma 1 we obtain the following result for the transition matrices $\Phi(k,s)$ of Eq. (7).

Let Assumptions 1 and 2 hold. Then, for all $i,j$ and all $k,s$ with $k\geq s$, we have

Let $k$ and $s$ be arbitrary with $k\geq s$, and let

with $\tau\leq t$. Hence, by the nonincreasing property of $V(k)$, we have

Note that $k-s<(t-\tau)B+B$ implying that ${k-s+1\over B}\leq t-\tau+1$, where we used the fact that both sides of the inequality are integers. Therefore $\lceil{k-s+1\over B}\rceil-2\leq t-\tau-1$, and we have for all $k$ and $s$ with $k\geq s$,

By Eq. (8), we have $z(k+1)=A(k)z(k)$, and therefore $z(k+1)=\Phi(k,s)z(s)$ for all $k\geq s$. Letting $z(s)=e_{i}$ we obtain $z(k+1)=[\Phi(k,s)]^{i}$. Using the inequalities (9) and $V(e_{i})\leq 1$, we obtain

The matrix $\Phi(k,s)$ is doubly stochastic, because it is the product of doubly stochastic matrices. Thus, the average entry of $[\Phi(k,s)]_{i}$ is $1/n$ implying that for all $i$ and $j$,

From the preceding relation and $\sqrt{1-\eta/(2n^{2})}\leq 1-\eta/(4n^{2})$, we obtain

II-B Convergence time

where $\partial f_{i}(x)$ is the set of all subgradients of $f_{i}$ at $x$.

We define the time-averaged vectors $\hat{x}_{i}(k)$ of the iterates $x_{i}(k)$ generated by Eq. (4), i.e.,

The use of these vectors allows us to bound the objective function improvement at every iteration; see . Under the subgradient boundedness assumption, we have the following resultThe assumption $\max_{1\leq i\leq n}\|x_{i}(0)\|\leq\alpha L$ in this theorem is not essential. We use this assumption mainly to present a more compact expression for the bound on the convergence time. A bound that explicitly depends on $\|x_{i}(0)\|$ can be obtained by following a similar line of analysis.

Let Assumptions 1 and 2 hold, and assume that the set $X^{*}$ of optimal solutions of problem (3) is nonempty. Let the sets of subgradients be bounded as in Eq. (10). Also, let the initial vectors $x_{i}(0)$ in Eq. (4) be such that $\max_{1\leq i\leq n}\|x_{i}(0)\|\leq\alpha L$. Then, the averages $\hat{x}_{i}(k)$ of the iterates obtained by the method (4) satisfy

The proof is identical to that of Proposition 3 in and relies on the use of our improved convergence rate bound in Corollary 1. Q.E.D.

The convergence rate result in the preceding theorem improves that of Proposition 3 in , where an analogous estimate is shown with a worse value for the constant $\beta$. In particular, there the constant $\beta$ in is given by $\beta=1-\eta^{(n-1)B}$, and $C_{1}$ increases exponentially with $n$. As seen from Eq. (12), our new constant $C_{1}$ increases only polynomially with $n$, indicating a much more favorable scaling as the network size increases.

III Quantization effects

We next study the effects of quantization on the convergence properties of the subgradient method. In particular, we assume that each agent receives and sends only quantized estimates, i.e., vectors whose entries are integer multiples of $1/Q$. At time $k$, an agent receives quantized estimates $x_{j}^{Q}(k)$ from some of its neighbors and updates according to the following rule:

To analyze the proposed method, we find it useful to rewrite Eq. (13) as follows:

where the error vector $e_{i}(k+1)$ is given by

Thus, the method can be viewed as a subgradient method with external (possibly persistent) noise, represented by $e_{i}(k+1)$. Due to the rounding down to the nearest multiple of ${1/Q}$, the error vector $e_{i}(k+1)$ satisfies

where the inequalities above hold componentwise.

Using the transition matrices $\Phi(k,s)$, we can rewrite the update equation (14) as

Using the result of Corollary 1, we can show that the stopped process converges as $k\to\infty$. In particular, we have the following result.

Furthermore, for the limit sequence $y(k)$, we have:

where $\beta=1-\frac{\eta}{4n^{2}}$ and $m$ is the dimension of the vectors $x_{i}^{Q}$.

Using the relations in Eqs. (20) and (25), and the subgradient boundedness, we obtain for all $k$,

By using Corollary 1, we have for all $i$ and $j$, and any $k\geq s$,

Since $e_{i}(k)\leq{\rm\bf 1}/Q$ [cf. Eq. (16)], we have

From the preceding two relations, and the inequality $\max_{j}\|x_{j}^{Q}(0)\|\leq\alpha L$, we obtain for all $i$ and $k$, $\|x_{i}^{Q}(k)-y(k)\|\leq\alpha Ln\beta^{\lceil{k+1\over B}\rceil-2}$

By using $\sum_{s=0}^{k-1}\beta^{\lceil{k-s+1\over B}\rceil-2}\leq\frac{1}{\beta}\,\sum_{r=0}^{\infty}\beta^{\lceil{r+2\over B}\rceil-1}$, and

According to part (a) of Lemma 2, the vectors $y(k)$ can be viewed as the iterates produced by the “fictitious” centralized algorithm:

Let Assumptions 1 and 2 hold, and assume that the set $X^{*}$ of optimal solutions of problem (3) is nonempty. Let the sequence $\{y(k)\}$ be defined by Eq. (26), and the sequences $\{x_{j}^{Q}(k)\}$ for $j\in\{1,\ldots,n\}$ be generated by the quantized subgradient method (13). Also, assume that the subgradients are uniformly bounded as in Eq. (10), and that $\max_{j}\|x_{j}^{Q}(0)\|\leq\alpha L$. Then, the average vectors $\hat{y}(k)$ defined as in Eq. (11), satisfy for all $k\geq 1$,

$\beta=1-{\eta\over 4n^{2}}$ and $y(0)={1\over n}\sum_{j=1}^{n}x_{j}^{Q}(0)$.

Using the same line of analysis as in the proof of Lemma 5 in , we can show that for all $k$, ${\rm dist}^{2}(y(k+1),X^{*})\leq{\rm dist}^{2}(y(k),X^{*})$

where $g_{j}(k)$ is a subgradient of $f_{j}$ at $y(k)$. By using the subgradient boundedness, we further obtain ${\rm dist}^{2}(y(k+1),X^{*})\leq{\rm dist}^{2}(y(k),X^{*})$

By using Lemma 2(b), we have ${\rm dist}^{2}(y(k+1),X^{*})\leq{\rm dist}^{2}(y(k),X^{*})$

By adding these inequalities for different values of $k$, and by using the convexity of $f$, we obtain the desired inequality. Q.E.D.

Assuming that the agents can store real values (infinitely many bits), we consider the time-average of the iterates $x_{i}^{Q}(k)$, defined by

Using Lemma 3, we have the following result.

Under the same assumptions as in Lemma 3, the averages ${\hat{x}}^{Q}_{i}(k)$ of the iterates obtained by the method (13) satisfy, for all $i$,

By the convexity of the functions $f_{j}$, we have, for any $i$ and $k$,

where $g_{ij}(k)$ is a subgradient of $f_{j}$ at $\hat{x}^{Q}_{i}(k)$. Then, by using the boundedness of the subgradients and Lemma 2(b), we obtain for all $i$ and $k$,

with $C_{1}=1+{nB\over\beta(1-\beta)}$. Thus, for the error term of Theorem 2, we have

where $C=1+8nC_{1}$ and $C_{1}=1+{nB\over\beta(1-\beta)}$. Hence, in the limit as $Q\to\infty$, the error terms in the estimate of Theorem 2 reduce to the error terms in the estimate of Theorem 1.

IV Conclusions

We studied distributed subgradient methods for convex optimization problems that arise in networks of agents connected through a time-varying topology. We first considered an algorithm for the case where agents can exchange and store continuous values, and proved a bound on the convergence rate. We next studied the algorithm under the additional constraint that agents can only send and receive quantized values. We showed that our algorithm guarantees convergence of the agent values to the optimal objective value within some error. Our bound on the error highlights the dependence on the number of quantization levels, and the polynomial dependence on the number $n$ of agents. Future work includes investigation of the effects of other quantization schemes and of noise in the agents’ estimates on the performance of the algorithm.

References