Non-Convex Distributed Optimization

Introduction

Due to emergence of the distributed networked systems, distributed multi-agent optimization problems have gained a lot of attention over the recent years. These systems include, but are not limited to, robust sensor network control , signal processing , power control , network routing , machine learning , opinion dynamics , and spectrum access coordination . In all these areas a number of agents, which can be represented by nodes over communication graphs, are required to optimize a global objective without any centralized computation unit and taking only the local information into account.

Most of the theoretical work on the topic was devoted to optimization of a sum of convex functions, where the assumption on subgradient existence is essentially used. We refer the reader to the following papers that consider various settings on network topology, asynchronous updating rules, and noisy communication . However, in many applications it is crucial to have an efficient solution for non-convex optimization problems . In particular, resource allocation problems with non-elastic traffic were studied in . Such applications cannot be modeled by means of concave utility functions, that renders a problem a non-convex optimization. Another example of non-convex optimization can be found in machine learning, where the independent component analysis needs to be performed for big data by a network of processors. The cumulative loss function is represented by the sum of errors of the model on a cross-validation sample. Due to the increasing size of available data and problem dimensionality, the cumulative loss is to be minimize in a distributed manner, where each error function is assigned to a different processor, and processors can exchange the information only with their local neighbours in a network . Since these problems refer to a non-convex optimization, some more sophisticated solution techniques are needed to handle them.

In , the authors proposed a distributed algorithm for non-convex constrained optimization based on a first order numerical method. However, the convergence to local minima is guaranteed only under the assumption that the communication topology is time-invariant, the initial values of the agents are close enough to a local minimum, and a sufficiently small step-size is used. An approximate dual subgradient algorithm over time-varying network topologies was proposed in . This algorithm converges to a pair of primal-dual solutions to the approximate problem given the Slater’s condition for a constrained optimization problem, and under the assumption that the optimal solution set of the dual limit is singleton. Recently, provided an analysis of the alternating direction method of multipliers and the alternating direction penalty method applied to non-convex settings. Convergence to a primal feasible point under mild conditions was proved. Some additional conditions were introduced to ensure the first order necessary conditions for local optimality for a limit point.

In this paper we study the push-sum protocol, which is a special case of consensus dynamics, applied to distributed optimization. The idea behind such consensus-based algorithm is the combination of a consensus dynamics and a gradient descent along the agent’s local function. The push-sum algorithm was initially introduced in and used in for distributed optimization. The main advantage of the push-sum protocol is that it can be utilized to overcome the restrictive assumptions on the communication graph structure such as double stochastic communication matrices . The work studied this algorithm over time-varying communication in the case of well-behaved convex functions. Similar to , we focus on the perturbed push-sum algorithm. In our work we relax the assumption on the convexity and apply this algorithm to a more general case.

The main contribution of this paper is the proof of convergence of the push-sum distributed optimization algorithm to a critical point of a sum of non-convex smooth functions under some general assumptions on the underlying functions and general connectivity assumptions on the underlying graph. Moreover, a perturbation of the algorithm allows us to use the algorithm to search local optima of this sum. It means that the new stochastic procedure steers every node to some local minimum of the objective function from any initial state. In our analysis we use the result on stochastic recursive approximation procedures extensively studied in . We also present the analysis of the convergence rate for the procedure under consideration.

Some other works dealt with the distributed stochastic approximation with applications to non-convex optimization . The authors in demonstrated convergence of the distributed stochastic approximation procedure under a specific communication protocol to the set of critical points in unconstrained optimization. In the authors generalized this procedure to the case of constrained optimization by considering a projected version of the gradient step and proved convergence of this algorithm to Karush-Kuhn-Tucker (KKT) points. However, critical points and KKT points represent only a necessary condition of local minima. Moreover, the communication protocol proposed in relied on a double-stochastic communication matrix on average, and, thus, required a double-stochastic matrix in the case of deterministic communication, which may also restrict the range of potential applications. In contrast to the papers above, this work presents the push-sum communication protocol requiring agents to know only the number of their out-neighbors. Moreover, this protocol allows the stochastic gradient step to lead the system not only toward some critical point, but to a local minimum almost surely in the absence of saddle points. Note that none of the existing first order methods can guarantee avoidance of saddle points without further assumptions on the second derivative . As the push-sum algorithm presented in this paper does not rely on assumptions on second order derivatives, the procedure converges either to a local minimum or to a saddle point in the presence of a latter one.

The paper is organized as follows. In Section 2 we formulate the distributed optimization problem of interest and introduce the push-sum algorithm that we adopt further to solve this problem. Section 3 presents some important preliminaries for the theoretical analysis. Section 4 contains the main results on the convergence to critical points and local optima. Section 5 provides the proofs of the main results. Section 6 contains an illustrative example of implementation of the proposed algorithm for a non-convex optimization problem. Finally, Section 7 concludes the paper.

Distributed Optimization Problem

In this section, we provide the problem formulation.

Consider a network of $n$ agents. At each time $t$, node $i$ can only communicate to its out-neighbors in some directed graph $G(t)$, where the graph $G(t)$ has the vertex set $[n]$ and the edge set $E(t)$. We introduce the following standard definition for the sequence $G(t)$.

We say that a sequence of graphs $\{G(t)\}$ is $S$-strongly connected, if for any time $t\geq 0$, the graph

is strongly connected. In other words, the union of the graphs over every $S$ time intervals is strongly connected.

The assumption on the $S$-strongly connected sequence of communication graphs has been used in many prior works to ensure enough mixing of information among the agents.

We use $N^{in}_{i}(t)$ and $N^{out}_{i}(t)$ to denote the in- and out-neighborhoods of node $i$ at time $t$. Each node $i$ is always considered to be an in- and out-neighbor of itself. We use $d_{i}(t)$ to denote the out-degree of node $i$, and we assume that every node $i$ knows its out-degree at every time $t$.

The goal of the agents is to solve distributively the following minimization problem:

In this paper we introduce the following assumption on the gradients of $F_{i}$:

Note that Assumption 1 is a standard assumption that is made in many of the previous works on subgradient methods (including ). We will further assume that a solution of (1) exists, and the set of critical points of the objective function $F(\mathbf{z})$, i.e. the set of points $\mathbf{z}$ such that $\nabla F(\mathbf{z})=\mathbf{0}$, is a union of finitely many connected components.

Preliminaries

This section is devoted to preliminaries of our main approach to study the problem (1).

is called the generating operator of a Markov process $\{x(t)\}_{t}$.

In the case of a deterministic process $\{x(t)\}_{t}$ on $X$, the generating operator reduces to the difference equation

Let $B$ be a subset of $X$, $U_{\epsilon}(B)$ be its $\epsilon$-neighborhood, i.e. $U_{\epsilon}(B)=\{x:\rho(x,B)<\epsilon\}$. Let $V_{\epsilon}(B)=X\setminus U_{\epsilon}(B)$ and $U_{\epsilon,R}(B)=V_{\epsilon}(B)\cap\{x:\|x\|<R\}$.

The function $\phi(t,x)$ is said to belong to class $\Phi(B)$ if

2) for all $R>\epsilon>0$ there exists some $Q=Q(\epsilon,R)$ such that

Now we turn back to the process (2) and formulate the following theorem, which was proven in (Theorem 2.7.3).

$LV(t,\mathbf{x})\leq-a(t+1)\phi(t,\mathbf{x})+g(t)(1+V(t,\mathbf{x}))$, where $\phi\in\Phi(B)$, $g(t)\geq 0$, $\sum_{t=0}^{\infty}g(t)<\infty$,

$a(t)>0$, $\sum_{t=0}^{\infty}a(t)=\infty$, and $\sum_{t=0}^{\infty}a^{2}(t)<\infty$, and there exists $c(t)$ such that $\|\mathbf{q}(t,\mathbf{X}(t))\|\leq c(t)$ a.s. for all $t\geq 0$ and $\sum_{t=0}^{\infty}a(t+1)c(t)<\infty$, and

Then the process (2) converges almost surely either to a point from $B$ or to the boundary of one of its connected components.

Note that Theorem 1 holds in the deterministic case of the process (2), when $\mathbf{W}(t)\equiv\mathbf{0}$ for all $t\geq 0$.

2 Perturbed Push-Sum Algorithm for Distributed Optimization

where $\mathbf{e}_{i}(t)$ is some $d$-dimensional, possibly random, perturbation at time $t$.

Consider the sequences $\{\mathbf{z}_{i}(t)\}_{t}$, $i\in[n]$, generated by the algorithm (3). Assume that the graph sequence $\{G(t)\}$ is $S$-strongly connected. Then for some constants $\delta$ and $\lambda$ satisfying $\delta\geq\frac{1}{n^{nS}}$ and $\lambda\leq\left(1-\frac{1}{n^{nS}}\right)^{1/S}$ for all $i\in[n]$ we have

Moreover, if $\{a(t)\}$ is a non-increasing positive scalar sequence with $\sum_{t=1}^{\infty}a(t)\|\mathbf{e}_{i}(t)\|_{1}<\infty$ a.s. for all $i\in[n],$ then

Note that the above theorem implies that, if $\lim_{t\to\infty}\|\mathbf{e}(t)\|_{1}=0$ a.s., then

In other words, under some assumptions on the perturbations $\mathbf{e}_{i}(t)$ one can guarantee that in the push-sum algorithm all $\mathbf{z}_{i}(t)$ track the average state $\bar{\mathbf{x}}(t)$.

Similar to , we adopt the push-sum algorithm (3) to the distributed optimization problem (1) by letting $\mathbf{e}_{i}(t+1)=-a(t+1)\mathbf{f}_{i}(\mathbf{z}_{i}(t+1))$ or $\mathbf{e}_{i}(t+1)~{}=-a(t+1)(\mathbf{f}_{i}(\mathbf{z}_{i}(t+1))+\mathbf{W}_{i}(t+1))$, where $\mathbf{W}_{i}(t+1)$ is a random vector whose entries are independent random variables with zero mean and bounded variance.

Under Assumption 1 and given that $\lim_{t\to\infty}a(t)=0$, in both cases

Thus, in long run, the nodes’ variables $\mathbf{z}_{i}(t+1)$ will track the average state $\bar{\mathbf{x}}(t)=\frac{1}{n}\sum_{j=1}^{n}\mathbf{x}_{j}(t)$ (see Theorem 2). Hence, one can expect that the long run behavior of the iterations in (3) with $\mathbf{e}_{i}(t+1)=-a(t+1)\mathbf{f}_{i}(\mathbf{z}_{i}(t+1))$ is the same as the behavior of the gradient descent iteration:

whereas the long run behavior of the iterations in (3) with $\mathbf{e}_{i}(t+1)=-a(t+1)(\mathbf{f}_{i}(\mathbf{z}_{i}(t+1))+\mathbf{W}_{i}(t+1))$ is equivalent to the behavior of the Robbins-Monro iteration :

Main Results

Here, we discuss the main results of this work. We present the proofs of these results in the subsequent sections.

The process above is a special case of the perturbed push-sum algorithm, whose background and properties are discussed in Section 3.2. According to (7), the average state $\bar{\mathbf{x}}(t)$ follows the dynamics

where $\mathbf{f}(\mathbf{z})=\frac{1}{n}\sum_{i=1}^{n}\mathbf{f}_{i}(\mathbf{z})=\frac{1}{n}\nabla F(\mathbf{z})$. If we denote $\frac{1}{n}\sum_{i=1}^{n}\mathbf{f}_{i}({\mathbf{z}_{i}(t+1)})-\mathbf{f}(\bar{\mathbf{x}}(t))$ by $\mathbf{q}(t,\bar{\mathbf{x}}(t))$, the process (9) becomes a deterministic version of the process (2) ($\mathbf{W}(t)\equiv\mathbf{0}$ for any $t$). It is shown in that if functions $F_{i}(\mathbf{z}_{i})$ are convex functions satisfying Assumption 1, and there exists a solution of (1), then the process (8) converges to an optimizer of the function $F$, given an appropriate choice of step-size sequence $a(t)$.

Let the gradients $\mathbf{f}_{i}(\mathbf{x})$, $i\in[n]$, satisfy the following assumption:

Further we need the following assumption on the behavior of the objective function $F(\mathbf{z})$, when $\|\mathbf{z}\|\to\infty$.

$F(\mathbf{z})$ is coercive, i.e $\lim_{\|\mathbf{z}\|\to\infty}F(\mathbf{z})\to\infty$Since we also require the boundedness of $\nabla F$ (Assumption 1), the function $F(\mathbf{z})$ is assumed to have a linear behavior as $\mathbf{z}\to\infty$..

Let us denote the set of critical points of $F$ by $B$, i.e.

We use $B^{{}^{\prime\prime}}$ to represent its refinement to the set of local minima, i.e.

and represent the rest of the critical points by $B^{{}^{\prime}}=B\setminus B^{{}^{\prime\prime}}$. Now we are ready to formulate the main result of this section.

Let the functions $F$ and $\mathbf{f}_{i}$, $i\in[n]$, satisfy Assumptions 1-3. Let $\{a(t)\}$ be a positive and non-increasing step-size sequence such that $\sum_{t=0}^{\infty}a(t)=\infty$ and $\sum_{t=0}^{\infty}a^{2}(t)<\infty$. Then the average state $\bar{\mathbf{x}}(t)$ and $\mathbf{z}_{i}(t)$ (see (9)) for the dynamics (7) with $S$-strongly connected graph sequence $\{G(t)\}$ converge either to a point from the set $B$ or to the boundary of one of its connected components.

Note that the deterministic process (9) suffers from the inherent property of gradient-based optimization methods as the derivative cannot distinguish between various types of critical points.

2 Perturbed Procedure: Convergence to Local Minima

The procedure above implies the following update for the average state:

Let Assumptions 1-4 hold. Let $\{a(t)\}$ be a positive and non-increasing step-size sequence with $\sum_{t=0}^{\infty}a(t)=\infty,$ $\sum_{t=0}^{\infty}a^{2}(t)<\infty$. Then the average state $\bar{\mathbf{x}}(t)$ and $\mathbf{z}_{i}(t)$ defined by (10) and (15) with $S$-strongly connected graph sequence $\{G(t)\}$ converge either to a point from the set $B$ or to the boundary of one of its connected components.

The above result is an analogue of Theorem 3 adapted for (10) and (15). It is clear that Theorem 4 does not guarantee the convergence of the process (15) to some local minimum of the objective function $F$. However, we will prove further the following theorem claiming that the process (15) cannot converge to a critical point that is not some local minimum of the objective function $F(\mathbf{z})$, given an appropriate choice of step-size sequence $a(t)$, Assumptions 1-4, and

For any point $\mathbf{z}^{\prime}\in B^{\prime}$ that is not a local minimum of $F$ there exists a symmetric positive definite matrix $C(\mathbf{z}^{\prime})$ such that $(\mathbf{f}(\mathbf{z}),C(\mathbf{z}^{\prime})(\mathbf{z}-\mathbf{z}^{\prime}))\leq 0$ for any $\mathbf{z}\in U(\mathbf{z}^{\prime})$, where $U(\mathbf{z}^{\prime})$ is some open neighborhood of $\mathbf{z}^{\prime}$.

Note that if the second derivatives of the function $F$ exist, the assumption above holds for any critical point of $F$ that is a local maximum. Indeed, in this case

where $\delta(\|\mathbf{z}-\mathbf{z}^{\prime}\|)=o(1)$ as $\mathbf{z}\to\mathbf{z}^{\prime}$ and $H\{F(\cdot)\}$ is the Hessian matrix of $F$ at the corresponding point.

Let the objective function $F(\mathbf{z})$ and gradients $\mathbf{f}_{i}(\mathbf{z})$, $i\in[n]$, in the distributed optimization problem (1) satisfy Assumptions 1-3, and 5. Let the sequence of the random i.i.d. vectors $\{\mathbf{W}_{i}(t)\}_{t}$, $i\in[n]$, satisfy Assumption 4. Let $\{a(t)\}$ be a positive and non-increasing step-size sequence such that $a(t)=O\left(\frac{1}{t^{\nu}}\right)$, where $\frac{1}{2}<\nu\leq 1$. Then the average state vector $\bar{\mathbf{x}}(t)$ (defined by (15)) and states $\mathbf{z}_{i}(t)$ for the distributed optimization problem (10) with $S$-strongly connected graph sequence $\{G(t)\}$ converges almost surely to a point from the set $B^{{}^{\prime\prime}}=B\setminus B^{{}^{\prime}}$ of the local minima of the function $F(\mathbf{z})$ or to the boundary of one of its connected components, for any initial states $\{\mathbf{x}_{i}(0)\}_{i\in[n]}$.

3 Convergence Rate of the Perturbed Process

In this subsection, we present a result on the convergence rate of the procedure (15) introduced above. Recall that Theorem 5 claims the almost sure convergence of this process either to a point from the set of the local minima of the function in the distributed optimization problem (1) or to the boundary of one of its connected components, given Assumptions 1-4. To formulate the result on the convergence rate, we need the following assumption on gradients’ smoothness.

$\frac{\partial f^{k}(\boldsymbol{x})}{\partial x^{l}}$ exists and is bounded for all $k,l=1\dots d,$ where $f^{k}$ is the $k$-th coordinate of the vector $\mathbf{f}$.

Now we are ready to formulate the following theorem.

Let the objective function $F(\mathbf{z})$ have finitely many critical points, i.e. the set $B$ be finiteThis assumption is made to simplify notations in the proof of this theorem. Note that this theorem can be generalized to the case of finitely many connected components in the set of critical points and local minima.. Let the objective function $F(\mathbf{z})$, gradients $\mathbf{f}_{i}(\mathbf{z})$, and $\mathbf{f}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{f}_{i}$, $i\in[n]$, in the distributed optimization problem (1) satisfy Assumptions 1-3, 5-6. Let the sequence of the random i.i.d. vectors $\{\mathbf{W}_{i}(t)\}_{t}$, $i\in[n]$, satisfy Assumption 4 and the graph sequence $\{G(t)\}$ be $S$-strongly connected. Then there exists a constant $\alpha>0$ such that for any $0<a\leq\alpha$, the average state $\bar{\mathbf{x}}(t)$ (defined by (15)) and states $\mathbf{z}_{i}(t)$ for the process (15) with the choice of step-size $a(t)=\frac{a}{t}$ converge to a point in $B^{{}^{\prime\prime}}$ (the set of local minima of $F(\mathbf{z})$). Moreover, for any $\mathbf{x}^{*}\in B^{{}^{\prime\prime}}$

Proof of the Main Results

The rest of the paper is organized to prove results described in Section 4.

Firstly, note that under Assumption 2 each gradient function $\mathbf{f}_{i}(\mathbf{x})$, $i\in[n]$, is a Lipschitz function with some constant $l_{i}$. This allows us to formulate the following lemma which we will need to prove Theorem 3 and Theorem 4.

Let $\{a(t)\}$ be a non-increasing sequence such that $\sum_{t=0}^{\infty}a^{2}(t)<\infty$. Then, there exists $c(t)$ such that the following holds for the process (9), given Assumptions 1, 2 and a $S$-strongly connected graph sequence $\{G(t)\}$:

Since the functions $\mathbf{f}_{i}$ are Lipschitz (Assumption 2) and taking into account Theorem 2, we have that

for some positive $\delta$ and $\lambda$ and where $l=\max_{i\in[n]}{l_{i}}$, $\|\mathbf{e}_{i}(t)\|=a(t)\|\mathbf{f}_{i}(\mathbf{z}_{i}(t))\|$.

Then, $\|\mathbf{q}(t,\bar{\mathbf{x}}(t))\|\leq c(t)$. Taking into account Assumption 1, we get

Hence, due to the Cauchy-Schwarz inequality,

Recall that the function $V(\mathbf{x})$ is nonnegative. Thus, we finally obtain that

for some constant $k_{4}>0$. Lemma 1 and the choice of $a(t)$ imply that $g(t)>0$ and $\sum_{t=0}^{\infty}g(t)<\infty$. Hence,

where, according to the choice of $V(\mathbf{x})$,

Thus, all conditions of Theorem 1 hold and we conclude that either $\lim_{t\to\infty}\bar{\mathbf{x}}(t)=\mathbf{z}_{0}\in B$ or $\bar{\mathbf{x}}(t)$ converges to the boundary of a connected component of the set $B$. By Theorem 2, $\lim_{t\to\infty}\|\mathbf{z}_{i}(t)-\bar{\mathbf{x}}(t)\|=0$ for all $i\in[n]$ and, hence, the result follows. ∎

Unfortunately (and naturally), there exists no function $V(t,\mathbf{x})$ for which

where $B^{{}^{\prime\prime}}$ represents the set of local minima of the function $F(\mathbf{z})$. Thus, the deterministic process (9) is unable to distinguish between local minima, saddle-points, and local maxima and guarantees only the convergence to a zero point of the gradient $\nabla F$. Theorem 4 and Theorem 5 provide a solution on how to rectify this issue.

2 Proof of Theorem 4

3 Proof of Theorem 5

To prove Theorem 5 we use the following result from , Chapter 5. We start by formulating the following important lemma (Lemma 5.4.1, ) for a general Markov process $\{x(t)\}_{t}$ defined on some state space $E$.

This lemma is used to prove the following theorem that is a special case of Theorem 5.4.1 in .

for any $\mathbf{z}^{{}^{\prime}}\in H^{{}^{\prime}}$ there exists positive constants $\delta=\delta(\mathbf{z}^{\prime})$ and $K=K(\mathbf{z}^{\prime})$ such that $\|\mathbf{f}(\mathbf{z})\|\leq K\|\mathbf{z}-\mathbf{z}^{\prime}\|$ for any $\mathbf{z}:$ $\|\mathbf{z}-\mathbf{z}^{\prime}\|<\delta$,

the random vectors $\mathbf{W}(t)$ satisfy Assumption 4,

$\sum_{t=0}^{\infty}a^{2}(t)<\infty$, $\sum_{t=0}^{\infty}\left(\frac{a(t)}{\sqrt{\sum_{k=t+1}^{\infty}a^{2}(k)}}\right)^{3}<\infty$,

Then $\Pr\{\lim_{t\to\infty}\mathbf{x}(t)\in H^{\prime}\}=0$ irrespective of the initial state $x(0)$.

We provide here a sketch of the proof. All details can be found in .

Let $\mathbf{x}^{\prime}\in H^{\prime}$ be any point from the set $H^{\prime}$ and $C=C(\mathbf{x}^{\prime})$ be the matrix figuring in the definition of $H^{\prime}$. Without loss of generality we may assume $\mathbf{x}^{\prime}=\mathbf{0}$. Let

where $y=\frac{U(\mathbf{x})}{\phi(t)}$. Then expanding $LV(t,\mathbf{x})$ at the point $y=\frac{U(\mathbf{x})}{\phi(t)}$ by Taylor’s formula and using the analytical properties of the function $W(y)$ and assumptions 1 and 2 of the theorem, for some positive constant $k$ we have

for any $\mathbf{x}\in D=\{\|\mathbf{x}\|<\delta\}\cap U(\mathbf{0})$, where $U(\mathbf{0})$ and the constant $\delta$ are used in the definition of the set $H^{\prime}$ and condition (1) of theorem, respectively.

We first notice that, under the proposed choice of $a(t)$, $\sum_{t=0}^{\infty}a(t)=\infty$ and $\sum_{t=0}^{\infty}a^{2}(t)<\infty$. Hence, we can use Theorem 4 to conclude that the process (15) converges to a point from the set $B$ represented by critical points of the function $F(\mathbf{z})$ (or to the boundary of one of connected components of $B$). As before, let the set of points that are not local minima be denoted by $B^{\prime}$, $B^{\prime}=B\setminus B^{{}^{\prime\prime}}$. Next, we notice that, according to Assumption 5, for any $\mathbf{z}^{\prime}\in B^{\prime}$ there exist some symmetric positive definite matrix $C=C(\mathbf{z}^{\prime})$ such that $(\mathbf{f}(\mathbf{z}),C(\mathbf{z}-\mathbf{z}^{\prime}))\leq 0$ for $\mathbf{z}\in U(\mathbf{z}^{\prime})$, where $U(\mathbf{z}^{\prime})$ is some neighborhood of $\mathbf{z}^{\prime}$. Moreover, since $B^{\prime}\subset B$ and due to Assumption 2, we can conclude that the condition 1 of Theorem 7 holds for $B^{\prime}$ and $\mathbf{f}$.

It is straightforward to verify that the sequence $a(t)=O\left(\frac{1}{t^{\nu}}\right)$ satisfies condition 3 of Theorem 7. Next, recall (see the discussion in the proof of Theorem 4) that

almost surely for some positive constant $M$. Hence,

Taking into account this and the fact that $\frac{a(t)}{\sqrt{\sum_{k=t+1}^{\infty}a^{2}(k)}}=O(\frac{1}{\sqrt{t}})$, we have

The last inequality is due to following considerations.

since, according to , any series of the type $\sum_{k=0}^{\infty}\left(\sum_{l=0}^{k}\beta^{k-l}\gamma_{l}\right)$ converges, if $\gamma_{k}\geq 0$ for all $k\geq 0$, $\sum_{k=0}^{\infty}\gamma_{k}<\infty$, and $\beta\in(0,1)$.

Thus, all conditions of Theorem 7 are fulfilled for the points from the set $B^{\prime}$. It implies that the process (15) cannot converge to the points from the set $B^{{}^{\prime}}$ and, thus, either $\Pr\{\lim_{t\to\infty}\bar{\mathbf{x}}(t)=\mathbf{z}_{0}\in B^{{}^{\prime\prime}}\}=1$ or $\bar{\mathbf{x}}(t)$ converges almost surely to the boundary of one of connected components of the set $B^{{}^{\prime\prime}}$. We conclude the proof by noting that, according to Theorem 2, $\lim_{t\to\infty}\|\mathbf{z}_{i}(t)-\bar{\mathbf{x}}(t)\|=0$ almost surely for all $i\in[n]$ and, hence, the result follows. ∎

4 Proof of Theorem 6

We start by revisiting a well-known result in linear systems theory .

If some matrix $A$ is stableA matrix is called stable (Hurwitz) if all its eigenvalue have a strictly negative real part., then for any symmetric positive definite matrix $D$, there exists a symmetric positive definite matrix $C$ such that $CA+A^{T}C=-D$. In fact, $C=\int_{0}^{\infty}e^{A^{T}\tau}De^{A\tau}d\tau$.

Recall that we deal with the objective function $F(\mathbf{z})$ that has finitely many local minima $\{\mathbf{x}^{*}_{1},\ldots,\mathbf{x}^{*}_{R}\}$. We begin by noticing that according to Assumption 6 the function $\mathbf{f}(\mathbf{x})$ admits the following representation in some neighborhood of any local minimum $\mathbf{x}^{*}_{m}$, $m=1,\ldots,R$,

where $\delta_{m}(\|\mathbf{x}-\mathbf{x}^{*}_{m}\|)=o(1)$ as $\mathbf{x}\to\mathbf{x}^{*}_{m}$ and $H\{F(\cdot)\}$ is the Hessian matrix of $F$ at the corresponding point.

For the sake of notational simplicity, let the matrix $H\{F(\mathbf{x}^{*}_{m})\}$ be denoted by $H_{m}$. Now we are ready to formulate the following lemma.

Under Assumption 6, for any local minimum $\mathbf{x}^{*}_{m}$, $m=1,\ldots,R$, of the objective function $F$ there exist a symmetric positive definite matrix $C_{m}$ and positive constants $\beta(m)$, $\varepsilon(m)$, and $a<\infty$ (independent on $m$), such that for any $\mathbf{x}$: $\|\mathbf{x}-\mathbf{x}^{*}_{m}\|<\varepsilon(m)$ the following holds:

Since $\mathbf{x}^{*}_{m}$, for $m\in[R]$, is a local minima of $F$, we can conclude that $H_{m}$, $m\in[R]$, is a symmetric positive definite matrix. Hence, there exists a finite constant $a>0$ such that the matrix $-aH_{m}+\frac{1}{2}I$ is stable for all $m\in[R]$, where $I$ is the identity matrix.

Now we remind that in some neighborhood of $\mathbf{0}$

We proceed to show this result in two steps: we first show that a trimmed version of the dynamics converges on $O\left(\frac{1}{t}\right)$ and then, we show that the convergence rate of the trimmed dynamics and the original dynamics are the same. Without loss of generality we assume that $\mathbf{x}^{*}=\mathbf{0}$ and

From Lemma 4, we know that there exist a symmetric positive definite matrix $C$ and positive constants $\beta$, $\varepsilon$, and $a$ such that $(C\mathbf{f}(\mathbf{x}),\mathbf{x})\geq\beta(C\mathbf{x},\mathbf{x}),$ for any $\mathbf{x}$: $\|\mathbf{x}\|<\varepsilon$. Moreover, $2a\beta>1$.

Let us consider the following trimmed process $\hat{\mathbf{x}}^{\tau,\boldsymbol{\kappa}}(t)$ defined by:

for $t\geq\tau$ with $\hat{\mathbf{x}}^{\tau,\boldsymbol{\kappa}}(\tau)=\boldsymbol{\kappa}$, where the random vector $\bar{\mathbf{x}}(t)$ is updated according to (15) with $a(t)=\frac{a}{t}$,

Recall from the proof of Lemma 1 that for some positive constants $M$ and $M^{\prime}$ almost surely

where $k_{1},$ $k_{2}$, and $k_{3}$ are some positive constants. Taking into account that $(C\mathbf{\hat{f}}(\mathbf{x}),\mathbf{x})\geq\beta(C\mathbf{x},\mathbf{x})$ and $2a\beta>1$, we conclude that

where $p_{1}>1$. According to (19), there exists such constant $p\in(1,p_{1})$ that

are fulfilled simultaneously, if $t>T$, where $T\geq\tau$ is some finite sufficiently large constant. Thus, for some $p>1$ and $T\geq 0$, we have

The last inequalities are due to (19) and the fact that $\sum_{r=1}^{t}r^{p-2}=O(t^{p-1})$This estimation can be obtained by considering the sum $\sum_{r=1}^{t}r^{p-2}$ the low sum of the corresponding integrals for two cases: $p\geq 2$, $1<p<2$.. Thus, we finally conclude that

since $V_{1}(\mathbf{x})=(C\mathbf{x},\mathbf{x})$ and the matrix $C$ is positive definite.

Taking into account the Markovian property of the process $\{\hat{\mathbf{x}}^{u,\bar{\mathbf{x}}(u)}(t)\}$, we conclude from the inequality above that

Since $\sigma$ can be chosen arbitrary small, (21)-(25) imply that

Thus, we conclude that the asymptotic behavior of $\Pr\{\|\bar{\mathbf{x}}(t)\|^{2}\leq x,\lim_{s\to\infty}\bar{\mathbf{x}}(s)=\mathbf{0}\}$ coincides with the asymptotics of $\Pr\{\|\hat{\mathbf{x}}^{u,\bar{\mathbf{x}}(u)}(t)\|^{2}\leq x\}\Pr\{\lim_{s\to\infty}\bar{\mathbf{x}}(s)=\mathbf{0}\}$. Now we can use (20) and the fact that $\Pr\{\lim_{s\to\infty}\bar{\mathbf{x}}(s)=\mathbf{0}\}\in(0,1]$ to get

Simulation Results

For illustration purposes, let us consider a simple distributed optimization problem:

over a network of $3$ agents. We assume that the function $F_{i}$ is known only to the agent $i$, $i=1,2,3$, and

For this simulation, the communication graph $G(t)$ is chosen in the following manner: the connectivity graph for each two consecutive time slots is chosen to be the following two graph combinations that is randomly set up for the information exchange:

Obviously, such sequence of communication graphs is $4$-strongly connected. Moreover, Assumptions 1-3 hold for the functions $\{F_{i}(z)\}_{i}$ and $F(z)$ and we can apply the perturbed push-sum algorithm to guarantee the almost sure convergence to a local minimum, namely either to $z=-2.49$ or to $z=2.62$. The performance of the algorithm for the initial agents’ estimations $x_{1}(0)=0$, $x_{1}(0)=0$, $x_{1}(0)=0$ and $x_{1}(0)=-1$, $x_{2}(0)=-1.2$, $x_{3}(0)=-1.1$ are demonstrated in Figures 2-4 and Figures 5-7, respectively. We observe that in the first case the algorithm converges to the global minimum $z=2.62$. In the second case, although the initial estimations is close to the local maximum of $F$, $z=-1.12$, the algorithm converges to the local minimum $z=-2.49$.

Acknowledgment

The authors are grateful for the valuable time and comments of the anonymous reviewers to improve this work. This work was gratefully supported by the German Research Foundation (DFG) within the GRK 1362 “Cooperative, Adaptive and Responsive Monitoring of Mixed Mode Environments” (www.gkmm.de). Behrouz Touri is also thankful to the Air Force Office of Scientific Research for supporting this work under the AFOSR-YIP award FA9550-16-1-0400.

Discussions and Concluding Remarks

In this paper we studied non-convex distributed optimization problems. We demonstrated that under some assumptions on the gradient of the objective function, the known deterministic push-sum algorithm converges to some critical point of the global objective function. However, the deterministic procedure based on the gradient optimization methods cannot distinguish between local maxima and local optima. Motivated by this, we considered the stochastic version of the distributed procedure and proved its almost sure convergence to some local minimum (or to the boundary of one of the connected components of the set of critical points) of the objective function, in the absence of any saddle point. The convergence rate estimations was also obtained for the stochastic process under consideration.

The future analysis may include possible modifications of the algorithm to approach the global minima of the objective function. Moreover, a payoff-based version of the proposed procedure is also of interest, especially in the application of optimal wind farm control .

References