# Subgradient averaging for multi-agent optimisation with different constraint
sets

Licio Romao<EMAIL_ADDRESS>Kostas Margellos
<EMAIL_ADDRESS>Giuseppe Notarstefano
<EMAIL_ADDRESS>Antonis Papachristodoulou<EMAIL_ADDRESS>Department of Engineering Science, University of Oxford, Parks Road, Oxford
OX1 3PJ, UK.  Department of Electrical, Electronic, and Information
Engineering G. Marconi at Alma Mater Studiorum Università di Bologna.

###### Abstract

We consider a multi-agent setting with agents exchanging information over a
possibly time-varying network, aiming at minimising a separable objective
function subject to constraints. To achieve this objective we propose a novel
subgradient averaging algorithm that allows for non-differentiable objective
functions and different constraint sets per agent. Allowing different
constraints per agent simultaneously with a time-varying communication network
constitutes a distinctive feature of our approach, extending existing results
on distributed subgradient methods. To highlight the necessity of dealing with
a different constraint set within a distributed optimisation context, we
analyse a problem instance where an existing algorithm does not exhibit a
convergent behaviour if adapted to account for different constraint sets. For
our proposed iterative scheme we show asymptotic convergence of the iterates
to a minimum of the underlying optimisation problem for step sizes of the form
$\frac{\eta}{k+1}$, $\eta>0$. We also analyse this scheme under a step size
choice of $\frac{\eta}{\sqrt{k+1}}$, $\eta>0$, and establish a convergence
rate of $\mathcal{O}(\frac{\ln k}{\sqrt{k}})$ in objective value. To
demonstrate the efficacy of the proposed method, we investigate a robust
regression problem and an $\ell_{2}$ regression problem with regularisation.

###### keywords:

Distributed optimisation, multi-agent networks, parallel algorithms,
subgradient methods, consensus.

AND

††thanks: L. Romao is supported by the Coordination for the Improvement of
Higher Education Personnel (CAPES) - Brazil. The work of K. Margellos and A.
Papachristodoulou has been supported by EPSRC UK under grants
$\mathrm{EP}/\mathrm{P}03277\mathrm{X}/1$ and
$\mathrm{EP}/\mathrm{M}002454/1$, respectively. Giuseppe Notarstefano is
supported by the European Research Council (ERC) under the European Union’s
Horizon $2020$ research and innovation programme (grant $638992$\- OPT4SMART).

, ,

##  1 Introduction

Distributed optimisation deals with multiple agents interacting over a network
and has found numerous applications in different domains, such as wireless
sensor networks [1, 2], robotics [3], and power systems [4], due to its
ability to parallelize computation and prevent agents from sharing information
considered as private. Typically, distributed algorithms are based on an
iterative process in which agents maintain some estimate about the decision
vector in an optimisation context, exchange this information with neighbouring
agents according to an underlying communication protocol/network, and update
their estimate on the basis of the received information.

Despite the intense research activity in this area, only a few algorithms can
simultaneously deal with time-varying networks, non-differentiable objective
functions and account for the presence of constraints [5, 6, 7, 8, 9],
features that are often treated separately in the literature. Several of the
commonly employed methods are based on a projected subgradient or a proximal
step and their analysis consists of selecting the step size underlying these
algorithms, establishing a convergence rate analysis, and quantifying
practical convergence for (near-)real time applications.

In this paper, we study a class of optimisation problems that involves a
separable objective function, while the feasible set can be decomposed as an
intersection of different compact convex sets. A centralised version of this
class of problems has been studied under a stochastic setting in [10, 11].
Distributed algorithms for this class have been proposed in [12, 13, 14, 5,
15, 16, 8, 17]. References [12, 13, 14] rely on [18, 19] to propose a
distributed strategy based on projected sub-gradient methods. These results
consist of an averaging step followed by a local sub-gradient projection
update. In [8] a distributed scheme based on a proximal update is proposed,
thus extending [12, 14] to the case where different local constraint sets and
an arbitrarily time-varying network are considered. The authors in [5] provide
asymptotic convergence for a primal-dual algorithm that allows coupling
between agents’ local estimates. We discuss additional related results in
Section 4, after the proposed algorithm is presented and some notation
introduced.

We motivate our approach by constructing an example showing that extending
available algorithms to the case of different constraint sets might not
exhibit a convergent behaviour for all problem instances. Hence, a direct
adaptation of existing schemes is not always possible when dealing with
different constraint sets. Notice also that distributed algorithms developed
for the unconstrained case cannot be trivially adapted to our setting, as
lifting the constraints in the objective (e.g., via characteristic functions)
would violate boundedness of the subgradient, a typical requirement for such
algorithms [20, 14, 6, 8].

The main contribution of this paper is the introduction and the
characterization of the convergence rate for a new subgradient averaging
algorithm. The proposed scheme allows us to account for time-varying networks,
non-differentiable objective functions and different constraint sets per agent
as in [8], while achieving faster practical convergence as it is based on
subgradient averaging as in [12, 20, 17]. Note that allowing simultaneously
for different constraint sets per agent and time-varying communication network
by means of a subgradient averaging scheme is a distinct feature of the
algorithm in this paper. Preliminary results related to this paper appeared in
[21], where several proofs have been omitted. Moreover, the construction of
Section 2.2 that motivates the analysis of algorithms with different
constraint sets is novel, and offers insight on the limitations of existing
algorithms. We also provide detailed numerical examples, not included in the
conference version.

The paper is organised as follows. In Section 2 we present the problem
statement, the network communication structure, and the main assumptions
adopted in this paper, followed by a numerical construction that motivates the
algorithm of this paper. In Section 3 we present the proposed scheme and the
main convergence results, namely, asymptotic convergence in iterates and a
convergence rate as far as the optimal value is concerned. Section 4 provides
detailed discussion and comparison of our scheme with other results in the
literature. In Section 5 we study the robust linear regression problem and
$\ell_{2}$ regression with regularisation to demonstrate the main algorithmic
features of our scheme and to compare our strategy against existing methods.
Finally, some concluding remarks and future research directions are provided
in Section 6. To ease the reader all proofs have been deferred to the Appendix
(Section 7).

_Notation:_ We denote by $\mathbb{R}$ the set of real numbers and $\mathbb{N}$
the set of natural numbers (excluding zero). The symbol $\mathbb{R}^{n}$
stands for the Cartesian product $\mathbb{R}\times\ldots\times\mathbb{R}$ with
$n$ terms. A sequence of elements in $\mathbb{R}^{n}$ is denoted by
$(x(k))_{k\in\mathbb{N}}$. For any set $X\subset\mathbb{R}^{n}$, we denote its
interior, relative interior and convex hull by $\mathrm{int}(X)$,
$\mathrm{ri}(X)$, and $\mathrm{conv}(X)$, respectively. We also denote by
$f(X)$ as the image of the set $X$ over a function $f$. The subdifferential of
$f$ at a point $x\in\mathrm{dom}f$ is denoted by $\partial f(x)$. For any
point $x\in\mathbb{R}^{n}$, $\|x\|_{2}$ stands for the Euclidean norm of $x$
and $\|x\|_{1}$ for the $\ell_{1}$ norm of $x\in\mathbb{R}^{n}$, which are
reduced to $|x|$ if $x$ is scalar.

##  2 Problem statement and a motivating example

###  2.1 Problem set-up and network communication

Consider the optimisation problem

$\displaystyle\operatorname*{minimise}_{x}$ $\displaystyle\quad
f(x)=\sum_{i=1}^{m}f_{i}(x)$ (1) subject to $\displaystyle\quad
x\in\cap_{i=1}^{m}X_{i},$

where $x\in\mathbb{R}^{n}$ is the vector of decision variables, and
$f_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and $X_{i}\subset\mathbb{R}^{n}$
constitute the local objective function and constraint set, respectively, for
agent $i$, $i=1,\ldots,m$. We suppose that each agent $i$ possesses as private
information the pair $(f_{i},X_{i})$ and maintains a local estimate $x_{i}$ of
the common decision vector $x$.

The goal is for all agents to agree on the local variables, that is,
$x_{i}=x^{\star}$, for all $i=1,\ldots,m$, where $x^{\star}$ is an optimiser
of (1), i.e., a feasible point such that $f(x^{\star})\leq f(x)$ for all
$x\in\cap_{i=1}^{m}X_{i}$. We impose the following assumption.

######  Assumption 1.

We assume that:

  * $i)$

For all $i=1,\ldots,m$, the function $f_{i}$ is convex.

  * $ii)$

The set $X_{i}\subset\mathbb{R}^{n}$ is compact and convex for all
$i=1,\ldots,m$, and $\cap_{i=1}^{m}X_{i}$ has a non-empty interior.

  * $iii)$

The subgradient of the function $f(x)$ is bounded on $\cup_{i=1}^{m}X_{i}$,
that is, $L=\max_{\begin{subarray}{c}\xi\in\partial f(x),\\\
x\in\cup_{i=1}^{m}X_{j}\end{subarray}}\|\xi\|_{2}<\infty.$

Assumption 1 imposes standard restriction for constrained non-smooth
optimisation. Item $ii)$ implies informally that $\cup_{i=1}^{m}X_{i}$ has
volume in $\mathbb{R}^{n}$, i.e., that the affine hull of $\cup_{i=1}X_{i}$
has dimension $n$. Moreover, the compactness assumption of item $ii)$
guarantees that the optimal set of problem (1) is non-empty. Item $iii)$ is an
assumption that is needed to prove convergence of sub-gradient methods applied
to problem (1). Under item $iii)$, the sub-gradient of the function $f$ can be
evaluated at points that belong to $\cup_{i=1}^{m}X_{i}$. We provide in
Appendix 7.2 a technical condition on the domain of the functions $f_{i}$ that
is sufficient to guarantee that Assumption 1, item $iii)$, holds. An important
consequence of Assumption 1 is given in the following lemma.

######  Lemma 1.

Under Assumption 1, we have that:

  * $i)$

The set $\mathrm{conv}(\cup_{i=1}^{m}X_{i})$ is compact.

  * $ii)$

The function $f$ is Lipschitz continuous over $\cap_{i=1}^{m}X_{i}$, i.e., the
following inequality hods

$|f(x)-f(y)|\leq L\|x-y\|_{2},\quad\forall~{}x,y~{}\in~{}\cap_{i=1}^{m}X_{i},$

where $L$ is the constant defined in Assumption 1.

Typical choices of functions that satisfy Assumption 1 are piecewise-linear
functions, quadratic convex functions and the logistic regression function.

In this paper, we aim to solve problem (1) through a network of agents that
use only the available local information, namely, the pair $(f_{i},X_{i})$ and
the current estimate for the optimal solution, $x_{i}(k)$, $i=1,\ldots,m$,
maintained by agent $i$ at a given instance $k$. We will show how
$x_{i}(k),i=1,\ldots,m,$ can be constructed and updated in Section 3, with $k$
playing the role of iteration index. To this end, we now characterise the
underlying communication network. Let
$\mathcal{G}(k)=(\mathcal{N},\mathcal{E}(k))$ be an undirected graph, where
$\mathcal{N}=\\{1,\ldots,m\\}$ is the number of agents and
$\mathcal{E}(k)\subset\mathcal{N}\times\mathcal{N}$ is the set of edges at
iteration $k$, that is, only if node $(j,i)\in\mathcal{E}(k)$ then node $j$
sends information to node $i$ at iteration $k$. We associate the time-varying
matrix $A(k)$ to the edge set $\mathcal{E}(k)$, with $[A(k)]_{j}^{i}>0$ only
if $(j,i)\in\mathcal{E}(k)$ at time $k$. As the graph is undirected, the
matrix $A(k)$ can be chosen to be symmetric. We also define the graph
$\mathcal{G}_{\infty}=(\mathcal{N},\mathcal{E}_{\infty})$, in which
$(j,i)\in\mathcal{E}_{\infty}$ if agent $j$ communicates with agent $i$
infinitely often. We impose the following assumption on the matrix $A(k)$.

######  Assumption 2.

We assume that:

  * $i)$

The graph $(\mathcal{N},\mathcal{E}_{\infty})$ is strongly connected.
Moreover, there exits a uniform upper bound on the communication time for all
$(j,i)\in\mathcal{E}_{\infty}$.

  * $ii)$

There exists $\eta\in(0,1)$ such that for all $k\in\mathbb{N}$ and for all
$i,j=1,\ldots,m$, $[A(k)]_{i}^{i}\geq\eta$, and if $[A(k)]_{j}^{i}>0$ then we
have that $[A(k)]_{j}^{i}$ $\geq\eta$.

  * $iii)$

Matrix $A(k)$ is doubly stochastic.

These are standard requirements in the distributed optimisation literature. We
refer the reader to [22, 14, 20, 8] for more details.

###  2.2 Dealing with different constraint sets

In this section, we highlight the necessity of developing a new algorithmic
scheme to deal with the presence of a different constraint sets per agent. To
this end, consider the iterative scheme111It should be noted that
$z_{i},i=1,\ldots,m,$ in (2a) should not be confused with that of Step 2 in
Algorithm 1 presented in the sequel; we use the same symbol to match the
notation in [20] and ease the reader.

$\displaystyle z_{i}(k+1)$
$\displaystyle=\sum_{j=1}^{m}[A]_{j}^{i}z_{j}(k)+g_{i}(k)$ (2a) $\displaystyle
x_{i}(k+1)$ $\displaystyle=\operatorname*{argmin}_{\xi\in
X_{i}}z_{i}(k+1)^{T}\xi+\frac{1}{c(k)}\|\xi\|_{2}^{2},$ (2b)

which consists of a modified version of the algorithm considered in [20],
adapted to account for different constraint sets in each agent’s local
optimisation problem. In the setting of the previous section, notice that
matrix $A$ in (2a) corresponds to a time-invariant network
$\mathcal{G}(k)=(\mathcal{N},\mathcal{E})$, for all $k\in\mathbb{N}$.
Assumption 2 is satisfied if the graph $(\mathcal{N},\mathcal{E})$ is strongly
connected and matrix $A$ is doubly-stochastic.

Observe that (2a) constitutes a subgradient update step, with neighbouring
local variables $z_{j}(k)$ being “mixed” according to the matrix $A$ and added
to $g_{i}(k)\in\partial f_{i}(x_{i}(k))$, i.e., a subgradient of $f_{i}$
evaluated at $x_{i}(k)$, $i=1,\ldots,m$. Step (2b) is an optimisation program
with the objective function being the sum (weighted via $c(k)$) of

$z_{i}(k+1)^{T}\xi\text{: linear ``proxy'' of }f_{i},$

and a regularization term $\|\xi\|_{2}^{2}$. To comply with [20], we set
$c(k)=\frac{1}{\sqrt{k+1}}$. Recall that the algorithm in [20] involves the
same constraint set in the update rule of (2b), that is $X_{i}=X$ for all
$i=1,\ldots,m$, and possesses a guaranteed convergence rate of
$\mathcal{O}(\frac{\ln k}{\sqrt{k}})$ for the running averages of the iterates
$x_{i}(k)$; here, we introduce a different set $X_{i}$ per agent and show that
this (natural) modification may lead to erroneous results.

Figure 1: Geometric representation of problem instance encoded by (3). The red
ellipsoids (dashed lines) correspond to the level curves of $f_{1}$, the blue
ellipsoids (double-dashed lines) represent the function $f_{2}$, while the
black (solid lines) ellipsoids to the ones of $f=f_{1}+f_{2}$. The shaded red
box illustrates the constraint set $X_{1}$, while the shaded blue box
illustrates $X_{2}$. Vectors $\hat{x}^{\star}_{1}=[-1,1]^{T}$ and
$\hat{x}^{\star}_{2}=[0.5,2.5]^{T}$ are the optimal solutions of $f_{1}(x)$
and $f_{2}(x)$ under the constraints $X_{1}$ and $X_{2}$, respectively. The
global optimal solution of $f=f_{1}+f_{2}$ with matrices given by (3) subject
to $x\in X_{1}\cap X_{2}$ is denoted by $x^{\star}$. This construction shows
that $\hat{x}_{1}^{\star}$ and $\hat{x}_{2}^{\star}$ constitute fixed-points
of (2) thus preventing the iteration from reaching $x^{\star}$ if initialised
at those points.

Consider a two-agent instance of (1), i.e., $m=2$ with $x\in\mathbb{R}^{2}$,
$f_{i}=x^{T}Qx+q_{i}^{T}x+r_{i},$ for $i=1,2$ and

$\displaystyle Q=\begin{bmatrix}1.2&0.4\\\ 0.4&1.8\end{bmatrix},\quad q_{1}$
$\displaystyle=\begin{bmatrix}8\\\ -4\end{bmatrix},\quad
q_{2}=\begin{bmatrix}2.93\\\ -11.46\end{bmatrix},$ $\displaystyle r_{1}$
$\displaystyle=20,\quad r_{2}=25.$ (3)

The local constraint sets are given by $X_{1}=[-1,1]\times[-1,1]$ and
$X_{2}=[0.5,2.5]\times[0.5,2.5]$. The feasible set $X_{1}\cap X_{2}$ is the
box $[0.5,1]\times[0.5,1]$. Figure 1 depicts the level curves of the quadratic
functions $f_{1}(x)$ (dashed-red lines), $f_{2}$ (double-dashed lines), and
$f=f_{1}+f_{2}$ (solid-black lines). The red and blue boxes represent the sets
$X_{1}$ and $X_{2}$ respectively, with the feasible set, $X_{1}\cap X_{2}$,
being also indicated in the figure in black.

By inspection the optimal solution of $f_{1}$ under the constraint $x\in
X_{1}$ is $\hat{x}^{\star}_{1}=\left[-1,1\right]^{T}$. Similarly, the optimal
solution for $f_{2}$ under $x\in X_{2}$ is
$\hat{x}^{\star}_{2}=\left[0.5,2.5\right]^{T}$. We then have the following
proposition.

######  Proposition 1.

Let $(z_{i}(k))_{k\in\mathbb{N}},(x_{i}(k))_{k\in\mathbb{N}}$, $i=1,2$, be the
sequences generated by algorithm (2) when applied to problem (3) with initial
conditions $x_{i}(0)=\hat{x}_{i}^{\star}$, $i=1,2$, and with
$A=\frac{1}{2}\mathbf{1}\mathbf{1}^{T}$ and $c(k)=\frac{1}{\sqrt{k+1}}$. We
have that

$x_{1}(k)=\hat{x}^{\star}_{1},\quad x_{2}(k)=\hat{x}^{\star}_{2},\quad\forall
k\in\mathbb{N}.$

Proposition 1 shows that $\hat{x}^{\star}_{1}$ and $\hat{x}^{\star}_{2}$
constitute fixed points of (2), hence the iteration cannot reach $x^{\star}$
if initialised from these points. This highlights the necessity of devising a
new algorithm to deal with the presence of a different constraint set per
agent.

##  3 Distributed Methodology

###  3.1 Proposed algorithm

The main steps of the proposed scheme are summarized in Algorithm 1. We
initialise each agents’ local variable with an arbitrary $x_{i}(0)\in X_{i}$,
$i=1,\ldots,m$; such points are not required to belong to
$\cap_{i=1}^{m}X_{i}$.

At iteration $k$, agent $i$ receives $x_{j}$ from the neighbouring agents and
averages them through $A(k)$, which captures the communication network, to
obtain $z_{i}(k)$. Recall that we denote the element of the $j$-th row and
$i$-th column of matrix $A(k)$ by $[A(k)]_{j}^{i}$. Agent $i$ then calculates
a subgradient, $g_{i}$, of its own objective function evaluated at $z_{i}(k)$
and broadcasts this information back to its neighbours. In the sequel, agent
$i$ averages the received $g_{j}(z_{j}(k))$ in order to compose a proxy for a
subgradient of $f(x)$, namely, $d_{i}(k)$. Finally, agents minimise a linear
proxy $d_{i}(k)^{T}\xi$ of $f(\xi)$ plus a regularization term weighted by
$\frac{1}{c(k)}$. An alternative interpretation of this last computation is
that agents update their local estimates by performing a subgradient step with
step size $c(k)$ and projecting $z_{i}(k)-c(k)d_{i}(k)$ onto their local set.
Indeed, this local update can be rewritten as

$x_{i}(k+1)=\mathcal{P}_{X_{i}}[z_{i}(k)-c(k)d_{i}(k)]$

where $\mathcal{P}_{X_{i}}[\cdot]$ denotes projection onto the set $X_{i}$.

Algorithm 1 Proposed distributed algorithm

0: : $x_{i}(0),\quad i=1,\ldots,m$

For $i=1,\ldots,m$, repeat until convergence

1: Compute $z_{i}(k)=\sum_{j=1}^{m}[A(k)]_{j}^{i}x_{j}(k),$

2: Pick $g_{i}(z_{i}(k))\in\partial f_{i}(z_{i}(k)),$

3: Compute $d_{i}(k)=\sum_{j=1}^{m}[A(k)]_{j}^{i}g_{j}(z_{j}(k)),$

4: Compute $x_{i}(k+1)=\operatorname*{argmin}_{\xi\in
X_{i}}d_{i}(k)^{T}\xi+\frac{1}{2c(k)}\|z_{i}(k)-\xi\|_{2}^{2},$

5: Set $k\leftarrow k+1$

end

###  3.2 Algorithm Analysis

####  3.2.1 Convergence in iterates

In this subsection, we impose the following assumption on the step size
$c(k)$.

######  Assumption 3.

Let $(c(k))_{k\in\mathbb{N}}$ be the sequence adopted in Algorithm 1. We
require that:

  * $i)$

$c(k)$ is non-negative and non-increasing;

  * $ii)$

$\sum_{k=1}^{\infty}c(k)=\infty$ and $\sum_{k=1}^{\infty}c(k)^{2}<\infty$.

A sequence satisfying Assumption 3 is $c(k)=\frac{\eta}{k+1}$, for $\eta>0$.

######  Theorem 1.

Let $(x_{i}(k))_{k\in\mathbb{N}}$ be the sequences generated by Algorithm 1,
for all $i=1,\ldots,m$. Under Assumptions 1\- 3, we have that for some
minimizer $x^{\star}$ of (1),

$\lim_{k\rightarrow\infty}\|x_{i}(k)-x^{\star}\|_{2}=0,\quad\forall~{}i=1,\ldots,m.$

The proof of Theorem 1, as well as of Theorem 2 presented in the sequel, is
based on some auxiliary technical results presented in Appendix 7.4.

Theorem 1 extends the result in [8] by allowing an agent to communicate
subgradient information to neighbouring agents, a feature that, as illustrated
in Section 5, can speed up practical convergence.

####  3.2.2 Convergence in objective value and convergence rate

Throughout this section, we impose the following assumption on the step size
$c(k)$.

######  Assumption 4.

The sequence $(c(k))_{k\in\mathbb{N}}$ used in Algorithm (1) is
$c(k)=\frac{\eta}{\sqrt{k+1}}$, for some $\eta>0$.

Our convergence rate results build on the following related sequence generated
by Algorithm 1,

$\hat{x}_{i}(k+1)=\frac{c(k+1)x_{i}(k+1)+S(k)\hat{x}_{i}(k)}{S(k+1)},$ (4)

where $S(k)=\sum_{r=1}^{k}c(r)$, and $(x_{i}(k))_{k\in\mathbb{N}}$, for all
$i=1,\ldots,m$, are the sequences generated by Algorithm 1, with initial
condition $\hat{x}_{i}(0)=x_{i}(0)$. By rewriting (4) as
$\hat{x}_{i}(k)=\frac{1}{S(k)}\sum_{r=1}^{k}c(r)x_{i}(r),$ we can interpret
(4) as a convex combination of past iterates.

Table 1: Summary of distributed schemes for smooth and non-smooth optimisation. | Smooth + Constant step-size | Non-smooth + Diminishing step-size
---|---|---
| Common sets | Different sets | Common sets | Different sets
| Convex | Strongly | Convex | Strongly | Convex | Strongly | Convex | Strongly
| Convex |  | Convex |  | Convex |  | Convex
No (sub)grad. avg. | [13, 23, 24] | [24] | [25] | - | [6, 26] | [27, 28] | [5, 16, 15, 8] | -
(Sub)grad. avg. | [29, 30, 26, 31] | [29, 30, 26] | - | - | [20, 26, 7, 9] | - |  our work, [17] | -

######  Theorem 2.

Consider the running average defined in (4). Under Assumptions 1, 2, and 4, we
have that:

  * $i)$

For all $i,j=1,\ldots,m$, the sequence
$(\|\hat{x}_{i}(k)-\hat{x}_{j}(k)\|)_{k\in\mathbb{N}}$ converges to zero at a
rate $\mathcal{O}(\frac{\ln k}{\sqrt{k}})$.

  * $ii)$

All accumulation points of the sequence $(\hat{x}_{i}(k))_{k\in\mathbb{N}}$
are feasible.

  * $iii)$

There exist $B_{1},B_{2}>0$ such that

$\displaystyle\left|\sum_{i=1}^{m}f_{i}(\hat{x}_{i}(k))-f(x^{\star})\right|$
$\displaystyle\leq B_{1}\frac{1}{\sqrt{k}}+B_{2}\frac{\ln k}{\sqrt{k}}.$ (5)

Note that Theorem 2 asserts convergence of the function value along the
running average $\hat{x}_{i}(k)$, i.e., all limit point of
$(\hat{x}_{i}(k))_{k\in\mathbb{N}}$ are optimal, however, the iterates might
exhibit an oscillatory behaviour. For the exact expression of $B_{1}$ and
$B_{2}$, we refer the reader to Appendix 7.6. The absolute value in Theorem 2
is due to the fact that $\hat{x}_{i}(k)$ may not be necessarily feasible;
however, item $ii)$ in Theorem 2 implies that all accumulation points of
$(\hat{x}_{i}(k))_{k\in\mathbb{N}}$, $i=1,\ldots,m$, are feasible. Item $i)$
states the rate at which consensus is achieved for the sequences
$(\hat{x}_{i}(k))_{k\in\mathbb{N}}$, $i=1,\ldots,m$. Similar rates can be
obtained with more general choices for the step size, e.g.,
$c(k)=\frac{1}{k^{a}}$, for $a\in[0.5,1).$

It should be noted that the result of Theorem 2 further extends the work
presented in [8] not only by allowing agents to communicate their (sub-)
gradients, but by also unveiling how to (non trivially) adapt the proof line
in that paper to come up with convergence results that recover traditional
rates for distributed subgradient methods. This is the first convergence rate
result under the scenario considered in this paper.

##  4 Comparison with related algorithms

In this section we provide a detailed comparison of the proposed algorithm
with other results in the literature. To this end, note that in [12] a similar
distributed sub-gradient scheme is mentioned, but no analysis of such a scheme
is presented. References [15, 16] characterize the convergence rate of a sub-
gradient algorithm under different constraint sets per agent that does not
possess subgradient averaging. References [8, 5] show asymptotic convergence
of distributed algorithms with different constraint sets and time-varying
communication network. Hence, by combining (sub)-gradient averaging and
providing an analysis that yields convergence rates under time-varying
communication networks and different constraint sets per agent, the results in
this paper are distinct from all the above literature.

A closely related algorithm to the one presented here is the one in [17]. This
provides convergence rates assuming a regularity condition on the local sets
(weaker than compactness) and requiring the network to be row-stochastic;
however, it does not analyse the case where the communication network is time-
varying. This requires different analysis arguments, thus complementing the
results in [17], extending them to allow for time-varying networks. Moreover,
the example of Section 2.2 highlights the need for developing a different
analysis when agents possess different constraints sets.

Although only marginally related to the results of this paper, it is worth
mentioning distributed algorithms that deal with similar optimization problems
[29, 30, 26]. Paper [26] proposes an algorithm whose convergence is valid for
non-convex objectives and directed communication network, while [29, 30] use a
constant step size to establish linear convergence rates for strongly convex
functions. Moreover, distributed algorithms based on proximal methods with
constant step sizes have been proposed in [32]. In this setting, the objective
function is assumed to be differentiable to obtain convergence to the optimal
solution of problem (1), and the size of the allowable step-size is upper
bounded by a quantity related to the Lipschitz constant of the objective
function. Unlike these results, we allow for non-differentiable objective
functions.

To better position this paper within the recent literature, we summarise the
main distributed algorithms that are amenable to smooth and non-smooth
constrained optimisation in Table 1. We highlight both scenarios of common and
different local constraint sets, which are indicated in the table by common
sets and different sets, respectively. In this brief summary, we restrict our
attention to algorithms that use constant step size for smooth optimisation,
and to those that use diminishing step sizes for the non-smooth case. We also
present a categorization of these schemes between those that have results for
general convex functions and strongly convex functions. In row entitled “No
(sub)grad. avg.”, we include distributed algorithms based on projected
(sub)gradient, proximal minimisation, and primal-dual update that do not
leverage on averaging first-order information from neighbouring agents. In
contrast, row “(Sub)grad. avg.” includes algorithms that exploit (sub)
gradient averaging. Among the few papers that are suitable for different local
sets, this is the first result to establish a convergence rate that matches
that of the common local sets case, and simultaneously allows agents to use
first-order information of their neighbours under time-varying communication
networks, thus speeding up practical convergence.

##  5 Numerical Examples

###  5.1 Problem instance of Section 2.2 – revisited

We revisit the two-agent problem in (3), for which the iterative scheme in (2)
is not guaranteed to converge, and apply this time our algorithm. Note that
the optimal solution of (3) is given by

$x^{\star}=\mathcal{P}_{[0.5,1]^{2}}\left[-\frac{1}{8}Q^{-1}(q_{1}+q_{2})\right]=\begin{bmatrix}0.5\\\
1\end{bmatrix}$

where $\mathcal{P}_{[0.5,1]^{2}}[\cdot]$ represents the projection onto the
feasible set of problem (3). Pictorially $x^{\star}$ is shown in Figure 1. To
illustrate the convergence properties of Algorithm 1 we monitor the evolution
of $\sqrt{\sum_{i=1}^{2}\|x_{i}(k)-x^{\star}\|^{2}_{2}}$, where
$(x_{i}(k))_{k\in\mathbb{N}}$, $i=1,2$, are the iterates generated by
Algorithm 1. We use $c(k)=\frac{1}{\sqrt{k+1}}$ similarly to [20],
$A=\frac{1}{2}\mathbf{1}\mathbf{1}^{T}$ and $x_{i}(0)=\hat{x}_{i}^{\star}$,
where $\hat{x}^{\star}_{i}$, $i=1,2$, are defined in Section 2.2. Observe that
our initial condition is the same as in Proposition 1. In contrast, as shown
in Figure 2, the iterates generated by Algorithm 1 converge to the optimal
solution of (3).

Figure 2: Evolution of $\sqrt{\sum_{i=1}^{2}\|x_{i}(k)-x^{\star}\|_{2}^{2}}$
for (3), where $(x_{i}(k))_{k\in\mathbb{N}},i=1,2$, are the iterates generated
by Algorithm 1.

###  5.2 Example 2: robust linear regression

We consider the problem of estimating an unknown (but deterministic) vector
$x\in\mathbb{R}^{n}$ from $m$ noisy measurements $y_{i}$ by means of the
linear model

$y_{i}=b_{i}^{T}x+v_{i},\quad i=1,\ldots,m,$

with $b_{i}\in\mathbb{R}^{n}$, and $v_{i}$ are independent random variables
drawn from a Laplacian distribution, that is, for each $i$ the density of
$v_{i}$ is given by $h_{v_{i}}(z)=\frac{1}{2a}\exp^{-|z|/a}$, for all
$z\in\mathbb{R}$. A common strategy is to impose a norm constraint of the form
$\|x\|_{2}\leq c$, for some $c>0$, to reflect some prior knowledge on the
unknown vector $x$, and solve the second order conic program

$\hat{x}\in\operatorname*{argmin}_{\|x\|_{2}\leq c}\|y-Bx\|_{1}.$ (6)

Typically, (6) is referred to as robust regression in the literature, as the
$\ell_{1}$-norm penalises relatively less outliers than other convex metrics
(e.g., quadratic penalties). In our set-up, we consider the case where data
are collected locally and agents are not willing to share their measurements
with a central processing unit.

Observe that (6) has the format of (1) by setting
$X_{i}=X=\\{x\in\mathbb{R}^{n}:\|x\|_{2}\leq 5\\}$ and
$f_{i}(x)=|y_{i}-b_{i}^{T}x|$, $i=1,\ldots,m$. Moreover, the constraint sets
$X_{i}$ and the objective functions $f_{i}$, $i=1,\ldots,m$, trivially satisfy
Assumption 1. Hence, we can apply the proposed scheme to obtain a solution to
(6). We consider $m=30$ and $n=4$ and generate $y$ independently from a
standard Gaussian distribution, and matrix $B$ from a uniform distribution
with support $[0,1]$.

We solve (6) in a distributed manner, and compare Algorithm 1 with the one
proposed in [20] under four different network connectivity structures: $i)$
complete network graph (which corresponds to the centralised version of the
problem); $ii)$ line network graph; $iii)$ sparse network graph with sparsity
degree $d=0.3$; $iv)$ sparse network graph with sparsity degree $d=0.8$. We
say that a network with $m$ agents has a sparsity degree $d\in(0,1)$ if the
number of connections among the network nodes is given by $dm^{2}$, where
$m^{2}$ indicates the number of connections of a complete graph.

We assess the performance of Algorithm 1 for each of the aforementioned
networks in Figure 3. Solid lines correspond to Algorithm 1, whereas dashed
lines correspond to the algorithm proposed in [20]. Different colours
correspond to the different network connectivities. For each case, we monitor
the evolution of
$\frac{|\sum_{i=1}^{30}f_{i}(x_{i}(k))-f^{\star}|}{f^{\star}}$, where
$f^{\star}$ is the optimal value of (6). The proposed scheme exhibits similar
and often favourable performance with the one in [20], in particular for cases
where the underlying graph is not sparse. It should be noted, however, that
Algorithm 1 possesses more general convergence properties, i.e., the proposed
scheme is guaranteed to converge under non-identical local sets.

Note that due to the fact that Algorithm 1 requires two rounds of
communication per iteration, the results presented in Figure 3 should be
rescaled by a factor of two if we use communication rounds instead of the
iteration index.

Figure 3: Evolution of
$\frac{|\sum_{i=1}^{30}f_{i}(x_{i}(k))-f^{\star}|}{f^{\star}}$ for Algorithm 1
(solid lines) and the one in [20] (dashed lines) when applied to the robust
regression problem given by (6). The different colours correspond the
different network connectivities.

###  5.3 Example 3: $\ell_{2}$ linear regression with regularisation

In this example, we consider a variation of the regression problem where we
assume $v_{i}$, $i=1,\ldots,m$, to be independent and Gaussian, i.e., the
density function is given by
$h_{v_{i}}(z)=\frac{1}{\sqrt{2\pi}}e^{-\frac{z^{2}}{2}}$, for all
$z\in\mathbb{R}$, for all $i=1,\ldots,m$, and we assume that $x$ is sparse. A
common relaxation of this problem is to choose the maximum likelihood
estimator $\hat{x}$ such that

$\displaystyle\hat{x}=\operatorname*{argmin}_{x\in
X}\|y-Bx\|_{2}^{2}+\lambda\|x\|_{1},$ (7)

where $X$ can be interpreted as a set including prior beliefs, e.g.,
$\|x\|_{2}\leq c$ or $\underline{x}\leq x\leq\bar{x}$ for some vectors
$\underline{x},\bar{x}\in\mathbb{R}^{n}$. The estimator $\hat{x}$ obtained by
solving (7) depends on the value of the parameter $\lambda$. In fact, the
larger the value of $\lambda$, the worse the performance is in terms of the
error and the sparser the obtained solution is.

In this example, we aim to verify the performance of Algorithm 1 under step
size choices $c(k)\propto\frac{1}{k+1}$ and a time-varying communication
network. Similar to the previous example, the vector $y$ is generated
according to a standard normal distribution and matrix $B$ from a uniform
distribution on the interval $[0,1]$. We assume $m>n$ and consider the case
where agents possess private, local information, encoded by
$X_{i}=[\underline{x}_{i},\bar{x}_{i}]$ $i=1,\ldots,m$, such that
$X=\cap_{i=1}^{m}X_{i}=[\underline{x},\bar{x}]$.

The algorithm presented in [20] does not necessarily converge in the set-up of
problem (7), as we have different constraint sets per agent. We thus compare
our algorithm against the one proposed in [8], which converges under similar
conditions but does not leverage on subgradient averaging. This allows us to
assess the impact of averaging subgradients on practical convergence.

Figure 4: Evolution of the average distance to the optimal solution given by
$\frac{\sqrt{\sum_{i=1}^{300}\|x_{i}(k)-x^{\star}\|^{2}_{2}}}{300}$ for
Algorithm 1 (solid-red line) and that of [8] (dashed-blue line).

We now investigate the behaviour of the proposed algorithm in the presence of
time-varying communication networks. To this end, we set $m=300$ and $n=10$,
and generate four network configurations with different sparsity patterns,
alternating cyclically among these. We also set $c(k)=\frac{0.2}{k+1}$ for
both Algorithm 1 and the one in [8]. Figure 4 shows the evolution for the
average distance to the optimal solution for Algorithm 1 (solid-red line) and
the one in [8] (dashed-blue line). We observe that Algorithm 1 consistently
outperforms the one proposed in [8]; this is mainly due to the sub-gradient
averaging step of Algorithm 1.

##  6 Conclusion

In this paper we proposed a subgradient averaging algorithm for multi-agent
optimisation problems involving non-differentiable objective functions and
different constraint sets per agent. For this set-up we showed by means of a
geometric construction that available schemes involving subgradient averaging
cannot be used. For the proposed scheme we showed convergence of the algorithm
iterates to some minimiser of a centralised problem counterpart. Moreover, we
have also established a convergence rate under a particular choice for the
underlying step size. The performance of our approach was illustrated by means
of several numerical examples, quantifying also the improvement in terms of
practical convergence with respect to other algorithms that are not based on
(sub)gradient exchange.

Future work will concentrate towards replacing the diminishing step size
employed by our approach with a constant one, showing convergence rates to a
neighbourhood of the set of optimal solutions. A more detailed study on the
communication requirements, and an investigation on how we could reduce the
two rounds of communication required by the proposed algorithm is also a topic
of current work.

##  7 Appendix

###  7.1 Proof of Lemma 1

We start by proving item $i)$. Consider the continuous mapping
$\phi:\mathbb{R}^{m}\times\prod_{i=1}^{m}\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$,
defined as $\phi(\gamma,x_{1},\ldots,x_{m})=\sum_{i=1}^{m}\gamma_{i}x_{i},$
where $\gamma=(\gamma_{1},\ldots,\gamma_{m})$ belongs to the simplex in
$\mathbb{R}^{m}$, denoted by $\Gamma$. Consider
$K=\phi(\Gamma,\prod_{i=1}^{m}X_{i})$, and note that $K$ is compact, as it is
the image of the compact set $\Gamma\times\prod_{i=1}^{m}X_{i}$ under the
continuous map $\phi$. Moreover, note that by definition we have
$K\subseteq\mathrm{conv}(\cup_{i=1}^{m}X_{i}),$ as any element in $K$ is a
convex combination of elements in $\cup_{i=1}^{m}X_{i}$. To conclude the
argument, we need to show that $\mathrm{conv}(\cup_{i=1}^{m}X_{i})\subseteq
K$. To this end, it suffices to show that $K$ is a convex set, due to the fact
that the convex hull is the smallest convex set containing a given set. Let
$z,w\in K$, i.e., $z=\sum_{i=1}^{m}\gamma_{i}z_{i}$ and
$w=\sum_{i=1}^{m}\beta_{i}w_{i}$, with $z_{i},w_{i}\in X_{i}$, and
$\gamma=(\gamma_{1},\ldots,\gamma_{m}),\beta=(\beta_{1},\ldots,\beta_{m})\in\Gamma$.
Fix an $\alpha\in(0,1)$, and note that $\alpha
z+(1-\alpha)w=\sum_{i=1}^{m}(\alpha\gamma_{i}+(1-\alpha)\beta_{i})x_{i},$
where $x_{i}=c_{i}z_{i}+(1-c_{i})w_{i}\in A_{i},$ with
$c_{i}=\frac{\alpha\gamma_{i}}{\alpha\gamma_{i}+(1-\alpha)\beta_{i}}$.

Since $x_{i}\in A_{i}$ due to convexity of $A_{i}$ and
$\alpha\gamma+(1-\alpha)\beta\in\Gamma$, we conclude that $\alpha
z+(1-\alpha)w\in K$ for any $\alpha\in(0,1)$, thus showing that $K$ is a
convex set. This implies then that $K=\mathrm{conv}(\cup_{i=1}^{m}X_{i})$ as
we have established that $K\subseteq\mathrm{conv}(\cup_{i=1}^{m}X_{i})$ and
$\mathrm{conv}(\cup_{i=1}^{m}X_{i})\subseteq K$. Since $K$ was shown to be
compact, we have that $\mathrm{conv}(\cup_{i=1}^{m}X_{i})$ is also compact.
This concludes the proof of item $i).$ An alternative proof can be found at
[33, Prop. 1.2.2]. The proof of item $ii)$ follows from Proposition 5.4.2, p.
186, in [33], and is omitted for brevity. This concludes the proof of the
lemma.

###  7.2 Sufficient condition for Assumption 1, item $iii)$.

The goal of this subsection is to provide a sufficient condition for
Assumption 1, item $iii)$. The subsequent arguments can be found in standard
optimisation books, such as [34, Theorem 24.7]; however we present here a more
direct proof.

######  Assumption 5.

Let $X_{i}$, $i=1,\ldots,m$, be the level sets of problem (1) and
$\mathrm{dom}f$ the domain of $f$. We suppose that:

  * $i)$

The distance between the set $\cup_{i=1}^{m}X_{i}$ and the complement of the
interior of the domain of $f$ (which is closed and convex) is strictly greater
than zero, i.e.,

$\displaystyle\mathrm{dist}($
$\displaystyle\cup_{i=1}^{m}X_{i},\big{(}\mathrm{int}(\mathrm{dom}f)\big{)}^{c})$
$\displaystyle=\inf_{\begin{subarray}{c}x\in\cup_{i=1}^{m}X_{i},\\\
y\in\big{(}\mathrm{int}(\mathrm{dom}f)\big{)}^{c}\end{subarray}}\|x-y\|_{2}^{2}>0.$

  * $ii)$

$X_{i}\subset\cap_{i=1}^{m}\mathrm{int}(\mathrm{dom}f_{i})$ for each
$i=1,\ldots,m$.

As a consequence of Assumption 5, and since
$\mathrm{dom}f=\cap_{i=1}^{m}\mathrm{dom}f_{i}$,
$\mathrm{ri}(\mathrm{dom}f)=\cap_{i=1}^{m}\mathrm{ri}(\mathrm{dom}f_{i})$ and
$\mathrm{ri}(\mathrm{dom}f_{i})\subset\mathrm{dom}f_{i}$ we have that the
subdifferential $\partial f(x)$ is non empty for each
$x\in\cap_{i=1}^{m}X_{i}$, as by item $ii)$ of Assumption 5 every feasible
solution of (1) belongs to the interior of the domain of $f$. Furthermore,
$\partial f(x)$ is compact by [33, Proposition 5.4.1] since the affine hull of
$\mathrm{dom}f$ has dimension $n$ due to Assumption 1, item $ii)$. We use this
fact to show that $\cup_{x\in\mathrm{conv}(\cup X_{i})}\partial f(x)$ is a
bounded set, that is, $\|g\|_{2}\leq L$, where $g\in\partial f(x)$ for any
$x\in\cup_{i=1}^{m}X_{i}$. This result is formally stated in the next lemma.

######  Lemma 7.1.

Under Assumptions 1, items $i)$ and $ii)$ , and 5, we have that the set
$\cup_{x\in\mathrm{conv}(\cup X_{i})}\partial f(x)$ is non-empty and bounded.

The proof of the lemma relies on Assumption 5, item $ii)$, that is,
$X_{i}\subset\cap_{j=1}^{m}\mathrm{ri}(\mathrm{dom}f_{j})$, for all
$i=1,\ldots,m$. This implies that
$\mathrm{conv}(\cup_{i=1}^{m}X_{i})\subset\cap_{j=1}^{m}\mathrm{ri}(\mathrm{dom}f_{j})$,
as $\cap_{j=1}^{m}\mathrm{ri}(\mathrm{dom}f_{j})$ is convex and contains
$\cup_{i=1}^{m}X_{i}$. Suppose, by contradiction, that
$\cup_{x\in\mathrm{conv}(\cup X_{i})}\partial f(x)$ is unbounded. Then there
exists a sequence
$(x_{k})_{k\in\mathbb{N}}\subset\mathrm{conv}(\cup_{i=1}^{m}X_{i})$ such that
$(g_{k})_{k\in\mathbb{N}}$, with $g_{k}\in\partial f(x_{k})$, satisfies
$\|g_{k}\|_{2}<\|g_{k+1}\|_{2},\quad\forall~{}k~{}\in~{}\mathbb{N}.$

Notice that $x_{k}\in\cap_{i=1}^{m}\mathrm{int}(\mathrm{dom}f_{i})$ by
Assumption 5, item $ii)$. By item $i)$ of Assumption 5, we can construct a
sequence $(\beta_{k})_{k\in\mathbb{N}}$ such that
$x_{k}+\beta_{k}d_{k}\in\cap_{i=1}^{m}\mathrm{dom}f_{i}.$ with
$d_{k}=g_{k}/\|g_{k}\|_{2}$. Let $\beta=\inf_{k\in\mathbb{N}}\beta_{k}$ and
notice that $\beta>0$ (i.e., it is bounded away from zero) due to Assumption
5, item $i).$ By the definition of $g_{k}$ we have that

$\frac{f(x_{k}+\beta
d_{k})-f(x_{k})}{\beta}\geq\|g_{k}\|_{2},\quad\forall~{}k~{}\in~{}\mathbb{N}.$
(8)

As inequality (8) is valid for all $k\in\mathbb{N}$, we take the limit
superior on both sides to obtain

$\limsup_{k\rightarrow\infty}\|g_{k}\|_{2}\leq\limsup_{k\rightarrow\infty}\frac{f(x_{i}+\gamma
d_{k})-f(x_{k})}{\gamma}<\infty,$ (9)

where the right-hand side of (9) is finite as the sequences
$(x_{k})_{k\in\mathbb{N}}$ and $(d_{k})_{k\in\mathbb{N}}$ are bounded (notice
that $d_{k}$ is a normalised subgradient), and since $f$ is continuous on its
domain ($f$ is convex). This establishes a contradiction, as we assumed
$(g_{k})_{k\in\mathbb{N}}$ were unbounded, thus concluding the proof of item
$ii)$.

###  7.3 Proof of Proposition 1

The proof is based on an induction argument.

#### Base case

We show that $z_{i}(1)^{T}(\xi-\hat{x}_{j}^{\star})\geq 0,$ for all $\xi\in
X_{j}$, for all $i,j=1,2$, and also that $x_{i}(1)=\hat{x}^{\star}$, for all
$i=1,2$. Consider the inequalities

$\displaystyle\nabla
f_{1}(\hat{x}_{1}^{\star})^{T}(\xi-\hat{x}_{i}^{\star})\geq 0,$
$\displaystyle\nabla
f_{2}(\hat{x}_{2}^{\star})^{T}(\xi-\hat{x}_{i}^{\star})\geq
0,\quad\forall\xi\in X_{i},\quad i=1,2.$ (10)

Fix $i=1$. The first inequality in (10) holds due to optimality of
$\hat{x}^{\star}_{1}$ [33]. To show the second inequality observe that $\nabla
f_{2}(\hat{x}_{2}^{\star})=\left[13.68,-3.94\right]^{T},$ and that
$\xi-\hat{x}_{1}^{\star}=[a_{1},a_{2}]^{T}$ with $a_{1}\geq 0$ and $a_{2}\leq
0$, for all $\xi\in X_{1}$.

Since $\nabla f_{1}(\hat{x}_{1}^{\star})=\left[12,-4\right]^{T},$ using a
symmetric argument we show that

$\displaystyle\nabla
f_{2}(\hat{x}_{2}^{\star})^{T}(\xi-\hat{x}^{\star}_{2})\geq 0,$
$\displaystyle\nabla
f_{1}(\hat{x}_{1}^{\star})^{T}(\xi-\hat{x}^{\star}_{2})\geq
0,\quad\forall\xi\in X_{2}.$ (11)

By (2a), and under our choice for $A$,

$z_{i}(1)=\frac{1}{2}\Big{(}\nabla f_{1}(\hat{x}_{1}^{\star})+\nabla
f_{2}(\hat{x}_{2}^{\star})\Big{)}+\nabla f_{i}(\hat{x}^{\star}_{i}),$ (12)

for $i=1,2$, hence inequalities (10) and (11) imply that
$z_{i}(1)^{T}(\xi-\hat{x}^{\star}_{j})\geq 0,~{}\forall\xi\in X_{j}$, for all
$i,j=1,2$.

We will now prove that $x_{i}(1)=\hat{x}^{\star}_{i}$, for $i=1,2$. Fix $i=1$.
Since $z_{1}(1)^{T}\xi+\frac{2}{c(k)}\|\xi\|_{2}^{2}$ is strictly convex,
there is a unique point satisfying

$\Big{(}z_{1}(1)+2x_{1}(1)\Big{)}^{T}(\xi-x_{1}(1))\geq 0,\quad\forall\xi\in
X_{1},$ (13)

where $(z_{1}(1)+2x_{1}(1))$ is the gradient of the objective function in (2b)
evaluated at $x_{1}(1)$, with $c(1)=1$. Therefore, it suffices to show that

$\Big{(}z_{1}(1)+2\hat{x}^{\star}_{1}\Big{)}^{T}(\xi-\hat{x}^{\star}_{1})\geq
0,\quad\forall\xi\in X_{1}.$ (14)

By substituting (3) into (12), we observe that
$z_{1}(1)+2\hat{x}^{\star}_{1}=\left[22.8414,-5.9708\right]^{T},$ and due to
the structure of $\xi-\hat{x}^{\star}_{1}$, (14) holds, thus proving that
$x_{1}(1)=\hat{x}^{\star}_{1}$. A symmetric argument yields that
$x_{2}(1)=x^{\star}_{2}$.

#### Induction hypothesis

Assume that $z_{i}(k)^{T}(\xi-\hat{x}_{j}^{\star})\geq 0$ for all $\xi\in
X_{j}$, for $i,j=1,2$, and that $x_{i}(k)=x^{\star}_{i}$ for $i=1,2$. We aim
to show that the aforementioned relations remain true for the step $k+1.$

#### Proof for iteration $k+1$

Fix $i=1$. Following a similar reasoning with the base case, observe that
$x_{1}(k+1)=x^{\star}_{1}$ if

$\left[z_{1}(k+1)+\frac{2}{c(k)}\hat{x}^{\star}_{1}\right]^{T}(\xi-\hat{x}^{\star}_{1})\geq
0,\quad\forall\xi\in X_{1}.$ (15)

As the sequence $(z_{i}(k))_{k\in\mathbb{N}}$ is generated by (2a), we
propagate the dynamical system in (2a) by $k+1$ steps to obtain

$z_{i}(k+1)=\frac{1}{2}\Big{(}\nabla f_{1}(\hat{x}_{1}^{\star})+\nabla
f_{2}(\hat{x}_{2}^{\star})\Big{)}(k+1)+\nabla f_{1}(\hat{x}^{\star}_{1}),$

where we have used the fact that $A=\frac{1}{m}\mathbf{1}\mathbf{1}^{T}$ and
$c(k)=\frac{1}{\sqrt{k+1}}$. A sufficient condition for equation (15) to hold
is that

$\displaystyle\Bigg{[}\frac{1}{2}\Big{(}\nabla$ $\displaystyle
f_{1}(\hat{x}_{1}^{\star})+\nabla f_{2}(\hat{x}_{2}^{\star})\Big{)}(k+1)$
$\displaystyle+2\hat{x}^{\star}_{1}\sqrt{k+1}\Bigg{]}^{T}(\xi-\hat{x}^{\star}_{1})\geq
0,\quad\forall\xi\in X_{1},$ (16)

since $\nabla f_{1}(\hat{x}^{\star}_{1})^{T}(\xi-\hat{x}^{\star}_{1})\geq 0$
by optimality of $\hat{x}^{\star}_{1}$. Recall that
$(\xi-\hat{x}_{1}^{\star})=[a_{1},a_{2}]$ with $a_{1}\geq 0$ and $a_{2}\leq 0$
for all $\xi\in X_{1}$. To prove (16) we will show that the left-most vector
in the same equation can be written as $[b_{1},b_{2}]$ for some $b_{1}\geq 0$
and $b_{2}\leq 0$. To achieve this, notice that $k+1\geq\sqrt{2}\sqrt{k+1}$,
for all $k\geq 1$, and let $e_{i}$ denote the unit vector with $1$ in the
$i$-th position, $i=1,2$. We then have that

$\displaystyle e_{1}^{T}$ $\displaystyle\left[\frac{1}{2}\Big{(}\nabla
f_{1}(\hat{x}_{1}^{\star})+\nabla
f_{2}(\hat{x}_{2}^{\star})\Big{)}\right](k+1)$ $\displaystyle\geq
e_{1}^{T}\left[\frac{\sqrt{2}}{2}\Big{(}\nabla
f_{1}(\hat{x}_{1}^{\star})+\nabla
f_{2}(\hat{x}_{2}^{\star})\Big{)}\right]\sqrt{k+1},$ (17)

and

$2e_{2}^{T}\hat{x}^{\star}_{1}\sqrt{k+1}\leq\sqrt{2}e_{2}^{T}\hat{x}_{1}^{\star}(k+1),$
(18)

since the first component of the averaged gradient and the second component of
$\hat{x}^{\star}_{1}$ are both positive. Therefore, for all $k\in\mathbb{N}$,

$\displaystyle b_{1}\geq 16.1604\sqrt{k+1}>0,\quad b_{2}\leq-2.5566(k+1)<0.$
(19)

Inequalities (17), (18) and (19), together with the structure of
$\xi-\hat{x}_{1}^{*}$, imply that (16) holds, so we can conclude that
$x_{1}(k+1)=\hat{x}^{\star}_{1}$. A symmetric argument shows that
$x_{2}(k+1)=\hat{x}^{\star}_{2}$.

To complete the proof it remains to show that
$z_{i}(k+1)^{T}(\xi-\hat{x}_{j}^{\star})\geq 0$ for all $\xi\in X_{j}$, for
all $i,j=1,2$, where
$z_{i}(k+1)=\frac{1}{2}\Big{(}z_{1}(k)+z_{2}(k)\Big{)}+\nabla
f_{i}(x_{i}(k)),$ due to (2a) and our choice for $A$. By our induction
hypothesis, $z_{i}(k)(\xi-\hat{x}^{\star}_{j})\geq 0$, for all $i,j=1,2$,
hence it suffices to show that $\nabla
f_{i}(x_{i}(k))^{T}(\xi-\hat{x}^{\star}_{j})\geq 0,~{}\forall\xi\in
X_{j},~{}\forall i=1,2.$ Since $x_{i}(k)=\hat{x}^{\star}_{i}$ for $i=1,2$, due
to our induction hypothesis, the claim follows from (10) and (11), thus
concluding the proof.

###  7.4 Auxiliary Lemmas for the proofs of Theorem 1 and 2.

Let

$v(k)=\frac{1}{m}\sum_{i=1}^{m}x_{i}(k),$ (20)

be the average of the agents’ estimates at time $k$. Since this quantity might
not necessarily belong to the feasible set $\cap_{i=1}^{m}X_{i}$, we define

$\bar{v}(k)=\frac{\rho}{\epsilon(k)+\rho}v(k)+\frac{\epsilon(k)}{\epsilon(k)+\rho}\bar{x},$
(21)

where $\bar{x}$ is a point in the interior of the feasible set (which is non-
empty by Assumption 1, item $ii)$), $\rho>0$ is such that the $2$-norm ball of
centre $\bar{x}$ and radius $\rho$ is contained in $\cap_{i=1}^{m}X_{i}$, and
$\epsilon(k)=\sum_{i=1}^{m}\mathrm{dist}(v(k),X_{i})$. As shown in [14],
$\bar{v}(k)\in\cap_{i=1}^{m}X_{i}$, for all $k\in\mathbb{N}$. We also define
$e_{i}(k+1)=x_{i}(k+1)-z_{i}(k)$, and note that the $z_{i}$-update in
Algorithm 1 can be written as

$x_{i}(k+1)=\sum_{j=1}^{m}[A(k)]_{j}^{i}x_{j}(k)+e_{i}(k+1).$ (22)

######  Lemma 7.2.

The following relations hold.

  * $i)$

Let $(x_{i}(k))_{k\in\mathbb{N}}$, $i=1,\ldots,m$, be the sequences generated
by Algorithm 1, and $(v(k))_{k\in\mathbb{N}}$ and
$(\bar{v}(k))_{k\in\mathbb{N}}$ defined by (20) and (21), respectively. Under
Assumption 1, we have that for all $k\geq 0$,

$\sum_{i=1}^{m}\|x_{i}(k+1)-\bar{v}(k)\|_{2}\leq\mu\sum_{i=1}^{m}\|x_{i}(k)-v(k)\|_{2},$

where $\mu=\frac{2}{\rho}mD+1$, and $D$ is the diameter of the set
$\cup_{i=1}^{m}X_{i}$ (which is well-defined by Lemma 1, item $i)$).

  * $ii)$

Let $(x_{i}(k))_{k\in\mathbb{N}}$, $i=1,\ldots,m$, and
$(v(k))_{k\in\mathbb{N}}$ be as in item $i)$. Under Assumption 2, we have that
for all $i=1,\ldots,m$, for all $k\geq 0$,

$\displaystyle\|x_{i}$ $\displaystyle(k+1)-v(k+1)\|_{2}\leq\lambda
q^{k}\sum_{j=1}^{m}\|x_{j}(0)\|_{2}$
$\displaystyle+\|e_{i}(k+1)\|_{2}+\sum_{r=0}^{k-1}\lambda
q^{k-r-1}\sum_{j=1}^{m}\|e_{j}(r+1)\|_{2}$
$\displaystyle+\frac{1}{m}\sum_{j=1}^{m}\|e_{j}(k+1)\|_{2},$

where $\lambda=2(1+\eta^{-(m-1)T})/(1-\eta^{(m-1)T})\in\mathbb{R}_{+}$ and
$q=(1-\eta^{(m-1)T})^{\frac{1}{(m-1)T}}\in(0,1)$.

  * $iii)$

Given a non-increasing and non-negative sequence $(c(k))_{k\in\mathbb{N}}$,
and a scalar $\bar{L}>0$, we have that

$\displaystyle 2\bar{L}$
$\displaystyle\sum_{k=0}^{N}c(k)\sum_{i=1}^{m}\|x_{i}(k+1)-\bar{v}(k+1)\|_{2}$
$\displaystyle<\beta_{1}\sum_{k=0}^{N}\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}^{2}+\beta_{2}\sum_{k=0}^{N}c(k)^{2}+\beta_{3},$

where $\beta_{1}\in(0,1)$, and $\beta_{2}$ and $\beta_{3}$ are positive
constants.

The proof of item $i)$ is presented in [8, Lemma 1]. For item $ii)$, see [8,
Lemma 2]. Finally, the proof of item $iii)$ follows the line of [8, Lemma 3].

Observe that the values of $\lambda$ and $q$ in Lemma 7.2, item $ii)$, depend
on the parameter $T$ that characterises the uniform bound in Assumption 2,
item $i)$; and on $\eta$, the lower bound for the elements of $A(k)$,
Assumption 2, item $ii)$. The following lemma is instrumental for the proof of
Theorem 2. In particular, Lemma 7.3, item $ii)$, constitutes a non-trivial
extension of the result in [8], allowing some sequences to be iteration-
varying.

######  Lemma 7.3.

Let $(x_{i}(k))_{k\in\mathbb{N}},(z_{i}(k))_{k\in\mathbb{N}}$ and
$(d_{i}(k))_{k\in\mathbb{N}}$, $i=1,\ldots,m$, be the sequences generated by
Algorithm 1, and $x^{\star}$ by any optimal solution of (1). Under Assumptions
1 and 2, we have that:

  * $i)$

For all $k\in\mathbb{N}$,

$\displaystyle
2c(k)\sum_{i=1}^{m}d_{i}(k)^{T}(x_{i}(k+1)-x^{\star})+\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}^{2}$
$\displaystyle+\sum_{i=1}^{m}\|x_{i}(k+1)-x^{\star}\|_{2}^{2}\leq\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}^{2}.$
(23)

  * $ii)$

For any $\beta_{1}\in(0,1)$, there exist sequences
$(\alpha_{1}(k))_{k\in\mathbb{N}}$ and $(\alpha_{2}(k))_{k\in\mathbb{N}}$ such
that, for all $k\in\mathbb{N}$, $\alpha_{1}(k)\in(0,1)$,
$\alpha_{2}(k)\in(0,1)$, $1-\beta_{1}-\alpha_{1}(k)-\alpha_{2}(k)\geq 0$ and

$\displaystyle
2\sum_{k=0}^{N}c(k)\sum_{i=1}^{m}(f_{i}(\bar{v}(k+1))-f_{i}(x^{\star}))$
$\displaystyle+\sum_{k=0}^{N}(1-\alpha_{1}(k)-\alpha_{2}(k)-\beta_{1})\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}^{2}$
$\displaystyle+\sum_{k=0}^{N}\sum_{i=1}^{m}\|x_{i}(k+1)-x^{\star}\|_{2}^{2}\leq\sum_{k=0}^{N}\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}^{2}$
$\displaystyle+\sum_{k=0}^{N}\Big{(}mL^{2}\frac{\alpha_{1}(k)+\alpha_{2}(k)}{\alpha_{1}(k)\alpha_{2}(k)}+\beta_{2}\Big{)}c(k)^{2}+\beta_{3}.$
(24)

Item $i)$: Fix any $i\in\\{1,\ldots,m\\}$ and consider the sequence
$(x_{i}(k))_{k\in\mathbb{N}}$. By optimality of $x_{i}(k+1)$ (see Algorithm
1), for any $\xi\in X_{i}$,

$\displaystyle d_{i}(k)^{T}$ $\displaystyle
x_{i}(k+1)-\frac{1}{c(k)}(z_{i}(k)-x_{i}(k+1))^{T}x_{i}(k+1)$
$\displaystyle\leq
d_{i}(k)^{T}\xi-\frac{1}{c(k)}(z_{i}(k)-x_{i}(k+1))^{T}\xi,$ (25)

where $d_{i}(k)-\frac{1}{c(k)}(z_{i}(k)-x_{i}(k+1))$ constitutes the gradient
of the objective function in the $x_{i}-$update of Algorithm 1, evaluated at
$x_{i}(k+1)$. Fix any optimal solution of (1),
$x^{\star}\in\cap_{i=1}^{m}X_{i},$ and consider the following identity

$\displaystyle-\frac{1}{c(k)}(z_{i}(k)-x_{i}(k+1))^{T}(x_{i}(k+1)-x^{\star})$
$\displaystyle=\frac{1}{2c(k)}\|x_{i}(k+1)-z_{i}(k)\|_{2}^{2}+\frac{1}{2c(k)}\|x_{i}(k+1)-x^{\star}\|_{2}^{2}$
$\displaystyle-\frac{1}{2c(k)}\|z_{i}(k)-x^{\star}\|_{2}^{2}.$ (26)

Combining (26) and (25) with $\xi=x^{\star}$, we obtain

$\displaystyle
d_{i}(k)^{T}x_{i}(k+1)+\frac{1}{2c(k)}\|x_{i}(k+1)-z_{i}(k)\|_{2}^{2}$
$\displaystyle\quad\quad\quad+\frac{1}{2c(k)}\|x_{i}(k+1)-x^{\star}\|_{2}^{2}$
$\displaystyle\leq
d_{i}(k)^{T}x^{\star}+\frac{1}{2c(k)}\|z_{i}(k)-x^{\star}\|_{2}^{2}$
$\displaystyle\leq
d_{i}(k)^{T}x^{\star}+\frac{1}{2c(k)}\sum_{j=1}^{m}[A(k)]_{j}^{i}\|x_{j}(k)-x^{\star}\|_{2}^{2},$
(27)

where the last inequality follows from double stochasticity of $A(k)$ and
convexity of $\|\cdot\|^{2}$.

We now multiply both sides of (27) by $2c(k)$ and sum the result for all
$i=1,\ldots,m,$ to obtain

$\displaystyle 2c(k)$
$\displaystyle\sum_{i=1}^{m}d_{i}(k)^{T}x_{i}(k+1)+\sum_{i=1}^{m}\|x_{i}(k+1)-z_{i}(k)\|_{2}^{2}$
$\displaystyle+\sum_{i=1}^{m}\|x_{i}(k+1)-x^{\star}\|_{2}^{2}\leq
2c(k)\sum_{i=1}^{m}d_{i}(k)^{T}x^{\star}$
$\displaystyle+\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}^{2},$ (28)

where
$\sum_{i=1}^{m}\sum_{j=1}^{m}[A(k)]_{j}^{i}\|x_{j}(k)-x^{\star}\|_{2}^{2}=\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}^{2}$
by exchanging the order of summation, and due to double stochasticity of
$A(k)$. The result follows from (28) by recalling that
$e(k+1)=x_{i}(k+1)-z_{i}(k)$ and moving the first term in the right-hand side
of (28) to the left one. This concludes the proof of item $i)$.

Item $ii)$: Consider the first term in the left-hand side of (23), and rewrite
it as

$\displaystyle 2c(k)$
$\displaystyle\sum_{i=1}^{m}d_{i}(k)^{T}(x_{i}(k+1)-x^{\star})=$
$\displaystyle 2c(k)\sum_{i=1}^{m}d_{i}(k)^{T}(x_{i}(k+1)-\bar{v}(k+1))$
$\displaystyle+$ $\displaystyle
2c(k)\sum_{i=1}^{m}d_{i}(k)^{T}(\bar{v}(k+1)-x^{\star})$ (29)

by adding and subtracting $\bar{v}(k+1)$. We next consider the terms in the
right hand-side of (29) separately. First, observe that

$\displaystyle 2c(k)$
$\displaystyle\sum_{i=1}^{m}d_{i}(k)^{T}(x_{i}(k+1)-\bar{v}(k+1))$
$\displaystyle\geq$
$\displaystyle-2c(k)L\sum_{i=1}^{m}\|x_{i}(k+1)-\bar{v}(k+1)\|_{2},$ (30)

by the Cauchy-Schwartz inequality, where
$L=\max_{\xi\in\cup_{i=1}^{m}X_{j}}\|g_{j}(\xi)\|_{2},$ which is well-defined
due to Lemma 1. Using the definition of $d_{i}(k)$ – see Algorithm 1 – into
the second term in the right-hand side of (29), we then have that (via double
stochasticity of $A$)

$\displaystyle 2c(k)$
$\displaystyle\sum_{i=1}^{m}d_{i}(k)^{T}(\bar{v}(k+1)-x^{\star})$
$\displaystyle=2c(k)\sum_{i=1}^{m}g_{i}(z_{i}(k))^{T}(\bar{v}(k+1)-x^{\star}).$
(31)

Moreover, by adding and subtracting $x_{i}(k+1)$ and $z_{i}(k)$ for all
$i=1,\ldots,m,$ into the right-hand side of (31) we obtain

$\displaystyle 2c(k)$
$\displaystyle\sum_{i=1}^{m}g_{i}(z_{i}(k))^{T}(\bar{v}(k+1)-x^{\star})$
$\displaystyle=$ $\displaystyle
2c(k)\sum_{i=1}^{m}g_{i}(z_{i}(k))^{T}(\bar{v}(k+1)-x_{i}(k+1))$
$\displaystyle+$ $\displaystyle
2c(k)\sum_{i=1}^{m}g_{i}(z_{i}(k))^{T}(x_{i}(k+1)-z_{i}(k))$ $\displaystyle+$
$\displaystyle 2c(k)\sum_{i=1}^{m}g_{i}(z_{i}(k))^{T}(z_{i}(k)-x^{\star}).$
(32)

Consider now the right-hand side of (32). The left-most term can be lower-
bounded as

$\displaystyle 2c(k)$
$\displaystyle\sum_{i=1}^{m}g_{i}(z_{i}(k))^{T}(\bar{v}(k+1)-x_{i}(k+1))$
$\displaystyle\geq-2c(k)L\sum_{i=1}^{m}\|\bar{v}(k+1))-x_{i}(k+1)\|_{2},$ (33)

by the Cauchy-Schwartz inequality. As for the middle term, we have that

$\displaystyle 2c(k)\sum_{i=1}^{m}g_{i}(z_{i}(k))^{T}(x_{i}(k+1)-z_{i}(k))$
$\displaystyle\geq-2c(k)L\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}$
$\displaystyle\geq-\alpha_{1}(k)\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}^{2}-m\frac{L^{2}}{\alpha_{1}(k)}c(k)^{2}$
(34)

where the first inequality follows from the Cauchy-Schwartz inequality and the
definition $e_{i}(k)$ in (22). For the second inequality, we employed the
relation $2xy\leq x^{2}+y^{2}$ with $x=\frac{L}{\sqrt{\alpha_{1}(k)}}c(k)$ and
$y=\sqrt{\alpha_{1}(k)}\|e_{i}(k+1)\|_{2}$ for some $\alpha_{1}(k)\in(0,1)$,
$k\in\mathbb{N}$.

Similarly, the right-most term of (32) can be manipulated to yield

$\displaystyle 2c(k)$
$\displaystyle\sum_{i=1}^{m}g_{i}(z_{i}(k))^{T}(z_{i}(k)-x^{\star})$
$\displaystyle\geq
2c(k)\sum_{i=1}^{m}\Big{(}f_{i}(z_{i}(k))-f_{i}(x^{\star})\Big{)}$
$\displaystyle=2c(k)\sum_{i=1}^{m}\Big{(}f_{i}(z_{i}(k))-f_{i}(\bar{v}(k+1))\Big{)}$
$\displaystyle+2c(k)\sum_{i=1}^{m}\Big{(}f_{i}(\bar{v}(k+1))-f_{i}(x^{\star})\Big{)}$
(35)

where the inequality follows from the definition of the subgradient for a
convex function, and the equality by adding and subtracting
$f_{i}(\bar{v}(k+1))$. The first term in the right-hand side of (35) can be
lower bounded as

$\displaystyle
2c(k)\sum_{i=1}^{m}\Big{(}f_{i}(z_{i}(k))-f_{i}(\bar{v}(k+1))\Big{)}$
$\displaystyle\geq-2c(k)L\sum_{i=1}^{m}\|z_{i}(k)-\bar{v}(k+1)\|_{2}$
$\displaystyle\geq-2c(k)L\left(\sum_{i=1}^{m}\left(\|e_{i}(k+1)\|_{2}+\|x_{i}(k+1)-\bar{v}(k+1)\|_{2}\right)\right)$
$\displaystyle\geq-\alpha_{2}(k)\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}^{2}-m\frac{L^{2}}{\alpha_{2}(k)}c(k)^{2}$
$\displaystyle-2c(k)L\sum_{i=1}^{m}\|x_{i}(k+1)-\bar{v}(k+1)\|_{2}$ (36)

where the first inequality follows from the relation $x\geq-|x|$, for all
$x\in\mathbb{R}$, and from item $iii)$ of Lemma 1, and the second inequality
by adding and subtracting $x_{i}(k+1)$, for all $i=1,\ldots,m$, and then using
triangle inequality. The last inequality follows from $2xy\leq x^{2}+y^{2}$
with $x=\frac{L}{\sqrt{\alpha_{2}(k)}}c(k)$ and
$y=\sqrt{\alpha_{2}(k)}\|e_{i}(k+1)\|_{2}$ for some $\alpha_{2}(k)\in(0,1)$,
$k\in\mathbb{N}$. Substituting (36) into (35)

$\displaystyle 2c(k)$
$\displaystyle\sum_{i=1}^{m}g_{i}(z_{i}(k))^{T}(z_{i}(k)-x^{\star})$
$\displaystyle\geq-\alpha_{2}(k)\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}^{2}-m\frac{L^{2}}{\alpha_{2}(k)}c(k)^{2}$
$\displaystyle-2c(k)L\sum_{i=1}^{m}\|x_{i}(k+1)-\bar{v}(k+1)\|_{2}$
$\displaystyle+2c(k)\sum_{i=1}^{m}\Big{(}f_{i}(\bar{v}(k+1))-f_{i}(x^{\star})\Big{)}.$
(37)

Substituting (29), (30), (33), (34), (37) into (23)

$\displaystyle 2c(k)$
$\displaystyle\sum_{i=1}^{m}(f_{i}(\bar{v}(k+1))-f_{i}(x^{\star}))+\sum_{i=1}^{m}\|x_{i}(k+1)-x^{\star}\|_{2}^{2}$
$\displaystyle+$
$\displaystyle\Big{(}1-\alpha_{1}(k)-\alpha_{2}(k)\Big{)}\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}^{2}+mL^{2}\Big{(}\frac{\alpha_{1}(k)+\alpha_{2}(k)}{\alpha_{1}(k)\alpha_{2}(k)}\Big{)}c(k)^{2}$
$\displaystyle+6c(k)L\sum_{i=1}^{m}\|x_{i}(k+1)-\bar{v}(k+1)\|_{2}.$ (38)

Summing (38) from $k=0$ to $k=N$, and using Lemma 7.3, item $iii)$, with
$\bar{L}=3L$, the desired inequality (24) follows. This concludes the proof of
item $ii)$.

Note that for any $\beta_{1}\in(0,1)$, the sequences
$(\alpha_{1}(k))_{k\in\mathbb{N}}$ and $(\alpha_{2}(k))_{k\in\mathbb{N}}$ can
be chosen to guarantee that $1-\alpha_{1}(k)-\alpha_{2}(k)-\beta_{1}\geq 0$
for all $k\in\mathbb{N}$. For instance, one particular choice is
$\alpha_{1}(k)=\alpha_{2}(k)=\alpha$ with $1-\beta_{1}-2\alpha>0$. Three
immediate consequences of Lemma 7.3 are presented in the following
proposition.

######  Proposition 2.

Consider Assumptions 1–3. The following statements hold

  * $i)$

We have that $\sum_{k=0}^{\infty}\sum_{i=1}^{m}\|e_{i}(k)\|_{2}^{2}<\infty$;

  * $ii)$

For all $i=1,\ldots,m$, we have that
$\lim_{k\rightarrow\infty}\|e_{i}(k)\|_{2}=0$;

  * $iii)$

For all $i=1,\ldots,m$, $\lim_{k\rightarrow\infty}\|x_{i}(k)-v(k)\|_{2}=0.$

Item $i)$: Consider Lemma 7.3, item $ii)$. Note that
$\sum_{k=0}^{N}\sum_{i=1}^{m}\|x_{i}(k+1)-x^{\star}\|_{2}$ and
$\sum_{k=0}^{N}\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}$ form a telescopic
series, so they can be replaced by
$\sum_{i=1}^{m}\|x_{i}(N+1)-x^{\star}\|_{2}$ and
$\sum_{i=1}^{m}\|x_{i}(0)-x^{\star}\|_{2}$, respectively. Let
$\beta_{1}\in(0,1)$, choose $\alpha_{1}(k)=\alpha_{2}(k)=\alpha$ so that
$1-2\alpha-\beta_{1}>0$. Observe that
$\sum_{i=1}^{m}(f_{i}(\bar{v}(k+1))-f_{i}(x^{\star}))\geq 0$ for all
$k\in\mathbb{N}$, due to optimality of $x^{\star}$, so this term can be
dropped from (24). Besides, we can also drop the term
$\sum_{i=1}^{m}\|x_{i}(N+1)-x^{\star}\|_{2}^{2}\geq 0$ since it is non-
negative and appears in the left-hand side of (24). This yields

$\displaystyle(1-2\alpha-\beta_{1})\sum_{k=0}^{N}\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}^{2}\leq\sum_{i=1}^{m}\|x_{i}(0)-x^{\star}\|_{2}^{2}$
$\displaystyle\hskip
42.67912pt+\Bigg{(}mL^{2}\frac{2}{\alpha}+\beta_{2}\Bigg{)}\sum_{k=0}^{N}c(k)^{2}+\beta_{3}.$

Letting $N\rightarrow\infty$, we conclude that
$\sum_{k=0}^{\infty}\sum_{i=1}^{m}\|e_{i}(k)\|_{2}^{2}$ is finite since the
sequence $(c(k))_{k\in\mathbb{N}}$ is square-summable under Assumption 3 and
the feasible set is compact. This concludes the proof of item $i)$.

Item $ii)$: Follows directly from item $i)$.

Item $iii)$: This proof follows directly from the arguments presented in [8,
Proposition 3], and is omitted for brevity.

###  7.5 Proof of Theorem 1

We are now in a position to prove Theorem 1. To this end, we use the
inequality (38) and leverage on Lemma 3.4 in [35] to establish convergence of
the sequences $(\|x_{i}(k)-x^{\star}\|_{2})_{k\in\mathbb{N}}$, $i=1,\ldots,m$,
to zero for some minimiser $x^{\star}$ of (1). We first present Lemma 3.4 in
[35].

######  Lemma 7.4 ([35]).

Consider non-negative scalar sequences $(\ell(k))_{k\in\mathbb{N}}$,
$(u(k))_{k\in\mathbb{N}}$ and $(\zeta(k))_{k\in\mathbb{N}}$ that satisfy the
recursion $\ell(k+1)\leq\ell(k)-u(k)+\zeta(k).$ If
$\sum_{k=0}^{\infty}\zeta(k)<\infty$, then the sequence
$(\ell(k))_{k\in\mathbb{N}}$ converges and the sequence
$(u(k))_{k\in\mathbb{N}}$ is summable.

Consider inequality (38), and choose $\alpha_{1}(k),\alpha_{2}(k)$ and
$\beta_{1}$ as in the proof of Proposition 2 item $i)$. We now drop the term
involving $(1-2\alpha)\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}^{2}$ as it appears on
the left-hand side of the inequality and is non-negative so that we obtain

$\displaystyle\sum_{i=1}^{m}\|$ $\displaystyle
x_{i}(k+1)-x^{\star}\|_{2}^{2}\leq\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}^{2}$
$\displaystyle-2c(k)\sum_{i=1}^{m}(f_{i}(\bar{v}(k+1))-f_{i}(x^{\star}))+\frac{2mL^{2}}{\alpha}c(k)^{2}$
$\displaystyle+6c(k)L\sum_{i=1}^{m}\|x_{i}(k+1)-\bar{v}(k+1)\|_{2}.$ (39)

With reference to Lemma 7.4 and considering inequality (39), we set
$\ell(k)=\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}^{2},$ and

$\displaystyle\zeta(k)=\frac{2mL^{2}}{\alpha}c(k)^{2}+6c(k)L\sum_{i=1}^{m}\|x_{i}(k+1)-\bar{v}(k+1)\|_{2},$
$\displaystyle u(k)=2c(k)\big{(}f(\bar{v}(k+1))-f(x^{\star})\big{)}.$ (40)

By Lemma 7.2, item iii), with $\bar{L}=3L$, and by Proposition 2, item i), it
follows that
$6L\sum_{k=1}^{\infty}c(k)\sum_{i=1}^{m}\|x_{i}(k+1)-\bar{v}(k+1)\|<\infty,$
hence, $\sum_{k=1}^{\infty}\zeta(k)<\infty$, as $c(k)$ is square-summable due
to Assumption 3, which implies that the assumptions of Lemma 7.4 hold.

Therefore, we have that the sequence
$(\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}^{2})_{k\in\mathbb{N}}$ converges,
which implies that $(\sum_{i}\|x_{i}(k)-x^{\star}\|_{2})_{k\in\mathbb{N}}$
also converges. To see this, note that, by continuity of the square-root
function, $(\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}^{2})_{k\in\mathbb{N}}$
being a convergent sequence implies that
$(\|X(k)-x^{\star}\otimes\mathbf{1}^{T}\|_{F})_{k\in\mathbb{N}}$ also
converges, where, for a fixed $k\in\mathbb{N}$, $X(k)$ is a $n\times m$ matrix
whose $i$-th column is given by $x_{i}(k)$, and $\otimes$ represents the
Kronecker product. Moreover, note that the set of $n\times m$ matrices can be
equipped with the norm $\sum_{i=1}^{m}\|x_{i}\|_{2}$, where $x_{i}$,
$i=1,\ldots,m$, is the $i$-th column of a generic element
$X\in\mathbb{R}^{n\times m}$. Since all norms in finite-dimensional spaces are
equivalent, we conclude that the sequence
$(\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2})_{k\in\mathbb{N}}$ also converges.
An alternative but more tedious justification of this argument can be found in
[8].

By Lemma 7.4, we also have that
$\sum_{k=1}^{\infty}c(k)\big{(}f(\bar{v}(k+1))-f(x^{\star})\big{)}<\infty.$The
latter implies that
$\liminf_{k\rightarrow\infty}(f(\bar{v}(k+1))-f(x^{\star}))=0.$ Therefore,
there exists a subsequence of
$(f(\bar{v}(k+1))-f(x^{\star}))_{k\in\mathbb{N}}$ that converges to zero.
Since the function $f(x)$ is continuous (by convexity) there exists some
minimizer $x^{\star}$ such that a subsequence of
$(\|\bar{v}(k)-x^{\star}\|_{2})_{k\in\mathbb{N}}$ converges to zero. Moreover,
we obtain
$\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}\leq\sum_{i=1}^{m}\|\bar{v}(k)-x^{\star}\|_{2}+\mu\sum_{i=1}^{m}\|x_{i}(k)-v(k)\|_{2}.$
by adding and subtracting $\bar{v}(k)$, then applying triangle inequality and
invoking Lemma 7.2, item $i)$.

Note that $(\|\bar{v}(k)-x^{\star}\|_{2})_{k\in\mathbb{N}}$ converges to zero
across a subsequence and
$(\sum_{i=1}^{m}\|x_{i}(k)-v(k)\|_{2})_{k\in\mathbb{N}}$ converges to zero
(due to Proposition 2, item $iii)$) hence we can find a subsequence of
$(\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2})_{k\in\mathbb{N}}$ that converges
to zero. However, we have shown by means of Lemma 7.4 that the sequence
$(\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2})_{k\in\mathbb{N}}$ converges; as a
result it should converge to zero since every Cauchy sequence has a unique
limit point. To conclude the proof, note that, for all $k\in\mathbb{N}$ and
for all $j=1,\ldots,m$,
$\|x_{j}(k)-x^{\star}\|_{2}\leq\sum_{i=1}^{m}\|x_{i}(k)-x^{\star}\|_{2}$, so
we conclude that the sequences
$(\|x_{j}(k)-x^{\star}\|_{2})_{k\in\mathbb{N}}$, $j=1,\ldots,m$, converge to
zero. This concludes the proof.

###  7.6 Proof of Theorem 2

Consider Assumption 4. We drop the constant $\eta$ for simplicity of
exposition, but general choices $\frac{\eta}{\sqrt{k+1}}$, $\eta>0$, are also
applicable. Let $(\hat{v}(k))_{k\in\mathbb{N}}$ be the running average
sequence associated with $(\bar{v}(k))_{k\in\mathbb{N}}$ (definition is
analogous to $(\hat{x}_{i}(k))_{k\in\mathbb{N}}$ in (4)). Note that since
$\cap_{i=1}^{m}X_{i}$ is assumed to be convex, we have that $\hat{v}(k)$ is
feasible for all $k\in\mathbb{N}$ (see also the discussion below (21)). We
have that

$\displaystyle\left|\sum_{i=1}^{m}f_{i}(\hat{x}_{i}(k+1))-f(x^{\star})\right|\leq
f(\hat{v}(k+1))-f(x^{\star})$
$\displaystyle+L\sum_{i=1}^{m}\|\hat{x}_{i}(k+1)-\hat{v}(k+1)\|_{2},$ (41)

which follows from triangle inequality and Lemma 1, item $iii)$. Note that the
first term in the right-hand side of (41) does not involve an absolute value
due to feasibility of the sequence $(\hat{v}(k))_{k\in\mathbb{N}}$, which in
turn implies that $f(\hat{v}(k+1))\geq f(x^{\star})$.

To facilitate subsequent statements, we change the notation in Lemma 7.3, item
$ii)$, by replacing $k$ by $r$, and $N$ by $k$. The inequality with this
modified notation is repeated here for clarity. Indeed, we have that for all
$k\in\mathbb{N}$

$\displaystyle
2\sum_{r=0}^{k}c(r)\sum_{i=1}^{m}(f_{i}(\bar{v}(r+1))-f_{i}(x^{\star}))$
$\displaystyle+\sum_{r=0}^{k}(1-\alpha_{1}(r)-\alpha_{2}(r)-\beta_{1})\sum_{i=1}^{m}\|e_{i}(r+1)\|_{2}^{2}$
$\displaystyle+\sum_{r=0}^{k}\sum_{i=1}^{m}\|x_{i}(r+1)-x^{\star}\|_{2}^{2}\leq\sum_{r=0}^{k}\sum_{i=1}^{m}\|x_{i}(r)-x^{\star}\|_{2}^{2}$
$\displaystyle+\sum_{r=0}^{k}\Big{(}mL^{2}\frac{\alpha_{1}(r)+\alpha_{2}(r)}{\alpha_{1}(r)\alpha_{2}(r)}+\beta_{2}\Big{)}c(r)^{2}+\beta_{3},$
(42)

where $(\alpha_{1}(r))_{r\in\mathbb{N}}$ and
$(\alpha_{2}(r))_{r\in\mathbb{N}}$ are sequences such that
$1-\beta_{1}-\alpha_{1}(r)-\alpha_{2}(r)\geq 0$ for all $r\in\mathbb{N}$.

The proofs of items $i)$, $ii)$ and $iii)$ of Theorem 2 are intertwined and
will be composed into two parts: we first assume that there exist constants
$d_{1},d_{2},d_{3},d_{4}>0$ such that (43) and (44) bellow are satisfied, and
on this basis prove the claims of the theorem; we then return to (43) and
(44), and prove the existence of such constants. To this end, consider

$\displaystyle f(\hat{v}(k+1))-f(x^{\star})\leq
d_{1}\frac{1}{S(k+1)}+d_{2}\frac{\sum_{r=0}^{k}c(r)^{2}}{S(k+1)}$ (43)
$\displaystyle
L\sum_{i=1}^{m}\|\hat{x}_{i}(k+1)-\hat{v}(k+1)\|_{2}\leq\frac{d_{3}}{S(k+1)}+d_{4}\frac{\sum_{r=0}^{k}c(r)^{2}}{S(k+1)}.$
(44)

Note that $S(k+1)$ can be lower-bounded as

$\displaystyle S($ $\displaystyle
k+1)=\sum_{r=1}^{k+1}\frac{1}{\sqrt{r+1}}\geq\int_{2}^{k+3}\frac{1}{\sqrt{x}}dx$
$\displaystyle=2(\sqrt{k+3}-\sqrt{2})\geq\nu\sqrt{k+3}\geq\nu\sqrt{k+1},$ (45)

with $\nu=2-\sqrt{2}$, and where we employed monotonicity of
$\frac{\sqrt{x+3}-\sqrt{2}}{\sqrt{x+1}}$ for $x\geq 1$. Moreover, we have that

$\displaystyle\sum_{r=0}^{k}c(r)^{2}=$
$\displaystyle\sum_{r=0}^{k}\frac{1}{r+1}=\sum_{r=1}^{k+1}\frac{1}{r}$
$\displaystyle\leq\int_{1}^{k+1}\frac{1}{x}dx+1\leq\ln(k+1)+1.$ (46)

The result of the Theorem 2, item $iii)$, follows then from (41) by
substituting (43)–(46), and setting $B_{1}=\sum_{i=1}^{4}\frac{d_{i}}{\nu}$
and $B_{2}=\frac{d_{2}}{\nu}+\frac{d_{4}}{\nu}$. Since (44) is valid for all
$i=1,\ldots,m$, we have that (via a direct application of triangle inequality)
$\|\hat{x}_{i}(k)-\hat{x}_{j}(k)\|_{2}\leq\sum_{i=1}^{m}\|\hat{x}_{i}(k)-\hat{v}(k)\|+\sum_{i=1}^{m}\|\hat{x}_{j}(k)-\hat{v}(k)\|,$
which due to (45) and (46) then implies that the sequence
$(\|\hat{x}_{i}(k)-\hat{x}_{j}(k)\|_{2})_{k\in\mathbb{N}}$ converges to zero
at a rate $\mathcal{O}(\frac{\ln k}{\sqrt{k}})$. This concludes the proof of
item $i)$.

Moreover, these relations also imply that the set of accumulation points of
the sequence $(\hat{v}(k))_{k\in\mathbb{N}}$ coincides to that of the
sequences $(\hat{x}_{i}(k))_{k\in\mathbb{N}}$, $i=1,\dots,m$. Hence, we
conclude that all accumulation points of $(\hat{x}_{i}(k))_{k\in\mathbb{N}}$
are feasible due to the fact that all accumulation points of
$(\hat{v}(k))_{k\in\mathbb{N}}$ are in $\cap_{i=1}^{m}X_{i}$ and the latter is
a closed set, thus concluding the proof of item $ii)$. This concludes the
proof of Theorem 2.

### Derivation of (43)

We first construct an upper-bound for the term on the left-hand side of (43).
In fact, observe that

$\displaystyle f($
$\displaystyle\hat{v}(k+1))-f(x^{\star})=f\left(\frac{1}{S(k+1)}\sum_{r=1}^{k+1}c(r)\bar{v}(r)\right)-f(x^{\star})$
$\displaystyle\leq\sum_{r=1}^{k+1}\frac{c(r)}{S(k+1)}f(\bar{v}(r))-f(x^{\star})$
$\displaystyle=\sum_{r=0}^{k}\frac{c(r+1)}{S(k+1)}\sum_{i=1}^{m}(f_{i}(\bar{v}(r+1))-f_{i}(x^{\star}))$
$\displaystyle\leq\sum_{r=0}^{k}\frac{c(r)}{S(k+1)}\sum_{i=1}^{m}(f_{i}(\bar{v}(r+1))-f_{i}(x^{\star})),$
(47)

where the first equality follows by definition of $\hat{v}(k+1)$, the first
inequality by convexity of $f$, the second equality by using the fact that
$f=\sum_{i=1}^{m}f_{i}$ and changing the summation index, and the second
inequality by using the fact that
$c(r+1)=\frac{1}{\sqrt{r+1}}\leq\frac{1}{\sqrt{r}}=c(r)$ for all
$r\in\mathbb{N}$.

In light of (42), for any $\beta_{1}\in(0,1)$, a valid choice for the
sequences $(\alpha_{1}(k))_{k\in\mathbb{N}}$ and
$(\alpha_{2}(k))_{k\in\mathbb{N}}$ is $\alpha_{1}(k)=\alpha_{2}(k)=\alpha(k)$,
where $\alpha(k)=a\Big{(}1-\frac{1}{\sqrt{k+1}}\Big{)}$; to ensure that
$1-\beta_{1}-\alpha_{1}(k)-\alpha_{2}(k)\geq 0$ as required by Lemma 7.3, item
$ii)$, it suffices to set $a=(1-\beta_{1})/2$. Under these choices we have
that

$1-\beta_{1}-2\alpha(k)=\frac{1-\beta_{1}}{\sqrt{k+1}}=(1-\beta_{1})c(k).$
(48)

Consider now (42) with the above choices for $\alpha_{1}(k)$ and
$\alpha_{2}(k)$. Note that the series
$\sum_{r=0}^{k}\sum_{i=1}^{m}\|x_{i}(r+1)-x^{\star}\|_{2}$ and
$\sum_{r=0}^{k}\sum_{i=1}^{m}\|x_{i}(r)-x^{\star}\|_{2}$ are telescopic, thus
all intermediate terms cancel. We now drop the terms involving
$\|e_{i}(r+1)\|_{2}^{2}$ and $\|x_{i}(k+1)-x^{\star}\|_{2}$ as they are non-
negative, and then divide the resulting expression by
$2S(k+1)=2\sum_{r=1}^{k+1}\frac{1}{\sqrt{r+1}}$ to obtain the following upper
bound on the right-hand side of (47)

$\displaystyle\sum_{r=0}^{k}\frac{c(r)}{S(k+1)}\sum_{i=1}^{m}(f_{i}(\bar{v}(r+1))-f_{i}(x^{\star}))$
$\displaystyle\leq\frac{\sum_{i=1}^{m}\|x_{i}(0)-x^{\star}\|_{2}^{2}}{2S(k+1)}+\frac{\beta_{3}}{2S(k+1)}$
$\displaystyle+\frac{\beta_{2}}{2}\sum_{r=0}^{k}\frac{c(r)^{2}}{S(k+1)}+mL^{2}\frac{1}{S(k+1)}\sum_{r=0}^{k}\frac{c(r)^{2}}{\alpha(r)}.$
(49)

By the right-hand side of (49), we obtain (43) with
$d_{1}=\frac{4mD^{2}+\beta_{3}}{2},\quad
d_{2}=\frac{\beta_{2}}{2}+\frac{4mL^{2}}{a}.$ where, by Assumption 1,
$\sum_{i=1}^{m}\|x_{i}(0)-x^{\star}\|_{2}^{2}\leq 4mD^{2}$, with $D$ defined
as in Lemma 7.2, item $i)$. Moreover, we used the fact that
$\frac{c(r)^{2}}{\alpha(r)}=\frac{1}{a}\frac{\sqrt{r+1}}{\sqrt{r+1}-1}\frac{1}{r+1}\leq\frac{4}{a}c(r)^{2},$
due to monotonicity of $\frac{\sqrt{x+1}}{\sqrt{x+1}-1}$.

### Derivation of (44)

Similarly to the derivation of (43), we apply the definition of both
$\hat{x}_{i}(k)$, $i=1,\ldots,m$, and $\hat{v}(k)$ to upper-bound the left-
hand side of (44) as

$\displaystyle L$
$\displaystyle\sum_{i=1}^{m}\|\hat{x}_{i}(k+1)-\hat{v}(k+1)\|_{2}$
$\displaystyle=L\sum_{i=1}^{m}\left\|\frac{1}{S(k+1)}\sum_{r=1}^{k+1}c(r)\Big{(}x_{i}(r)-\bar{v}(r)\Big{)}\right\|_{2}$
$\displaystyle\leq\frac{L\mu}{S(k+1)}\sum_{r=1}^{k+1}c(r)\sum_{i=1}^{m}\|x_{i}(r)-v(r)\|_{2},$
(50)

where the inequality follows from convexity of the norm. We will now construct
an upper-bound on the right-hand side of (50). To this end, note that

$\displaystyle\frac{L\mu}{S(k+1)}\sum_{r=1}^{k+1}c(r)\sum_{i=1}^{m}\|x_{i}(r)-v(r)\|_{2}$
$\displaystyle=\frac{L\mu c(1)}{S(k+1)}\sum_{i=1}^{m}\|x_{i}(1)-v(1)\|_{2}$
$\displaystyle+\frac{L\mu}{S(k+1)}\sum_{r=2}^{k+1}c(r)\sum_{i=1}^{m}\|x_{i}(r)-v(r)\|_{2}.$
(51)

We now invoke Lemma 7.2, item $ii)$ – with $r$ in the place of $k$, and $t$ in
the place of $r$ – for the last term on the right-hand side of (51) so that

$\displaystyle\sum_{r=2}^{k+1}c(r)\sum_{i=1}^{m}\|x_{i}(r)-v(r)\|_{2}$
$\displaystyle=\sum_{r=1}^{k}c(r+1)\sum_{i=1}^{m}\|x_{i}(r+1)-v(r+1)\|_{2}$
$\displaystyle\leq
2\sum_{r=0}^{k}c(r)\sum_{i=1}^{m}\|e_{i}(r+1)\|_{2}+m\lambda\sum_{i=1}^{m}\|x_{i}(0)\|_{2}\sum_{r=0}^{k}c(r)q^{r}$
$\displaystyle+m\lambda\sum_{r=1}^{k}c(r+1)\sum_{t=0}^{r-1}q^{r-t-1}\sum_{i=1}^{m}\|e_{i}(t+1)\|_{2}$
(52)

where we added the term corresponding to $r=0$ and used the fact that
$c(r+1)\leq c(r)$ for all $r\in\mathbb{N}$, in first two terms on the right-
hand side of (52). We analyse each term in the right-hand side of (52)
separately. First, observe that

$\displaystyle 2\sum_{r=0}^{k}c(r)\sum_{i=1}^{m}\|e_{i}(r+1)$
$\displaystyle\|_{2}\leq\sum_{r=0}^{k}c(r)^{2}+\sum_{i=1}^{m}\|e_{i}(r+1)\|_{2}^{2},$
(53)

using the identity $2xy\leq x^{2}+y^{2}$. The intermediate term in the right-
hand side of (52) can be manipulated to yield

$\displaystyle
m\lambda\sum_{i=1}^{m}\|x_{i}(0)\|_{2}\sum_{r=0}^{k}c(r)q^{r}\leq\frac{m^{2}\lambda
D}{1-q},$ (54)

since $c(r)\leq 1$ for all $r\in\mathbb{N}\cup\\{0\\}$, $\|x_{i}(0)\|_{2}\leq
D$ (Lemma 1) for all $i=1,\ldots,m$, and using the closed-form expression for
the sum of geometric series as $q\in(0,1)$. We deal with the last term in (52)
in several steps. We start by expanding the terms to obtain

$\displaystyle\sum_{r=1}^{k}c(r+1)\sum_{t=0}^{r-1}q^{r-t-1}\sum_{i=1}^{m}\|e_{i}(t+1)\|_{2}$
$\displaystyle=c(2)\sum_{i=1}^{m}\|e_{i}(1)\|_{2}+c(3)\left(q\sum_{i=1}^{m}\|e_{i}(1)\|_{2}\sum_{i=1}^{m}\|e_{i}(2)\|_{2}\right)$
$\displaystyle+\ldots+c(k+1)\left(\sum_{t=1}^{k}q^{k-t}\sum_{i=1}^{m}\|e_{i}(t)\|_{2}\right).$
(55)

We now collect the terms containing the error vector $e_{i}(r)$,
$r=1,\ldots,k$, to obtain

$\displaystyle
m\lambda\sum_{r=1}^{k}c(r+1)\sum_{t=0}^{r-1}q^{r-t-1}\sum_{i=1}^{m}\|e_{i}(t+1)\|_{2}$
$\displaystyle=m\lambda\sum_{i=1}^{m}\|e_{i}(1)\|_{2}\Big{(}c(2)+qc(3)+\ldots$
$\displaystyle+q^{k-1}c(k+1)\Big{)}+\ldots+\sum_{i=1}^{m}\|e_{i}(k)\|_{2}c(k+1)$
$\displaystyle\leq\frac{m\lambda}{1-q}\sum_{r=1}^{k}c(r+1)\sum_{i=1}^{m}\|e_{i}(r)\|_{2}$
$\displaystyle\leq\frac{m\lambda}{1-q}\sum_{r=1}^{k}c(r)\sum_{i=1}^{m}\|e_{i}(r)\|_{2}\leq\frac{m\lambda}{2(1-q)}\sum_{r=0}^{k}c(r)^{2}$
$\displaystyle\quad\quad\quad\quad+\frac{m\lambda}{2(1-q)}\sum_{r=0}^{k}\sum_{i=1}^{m}\|e_{i}(r+1)\|_{2}^{2}$
(56)

where in the first inequality we used the fact that $q\leq\frac{1}{1-q}$ and
$1\leq\frac{1}{1-q}$ for any $q\in(0,1)$, while in the second inequality we
used the fact that $c(r+1)\leq c(r)$. To obtain the last inequality we applied
the relation $2xy\leq x^{2}+y^{2}$ with $x=c(r)$ and $y=\|e_{i}(r+1)\|_{2}$,
and then added the non-negative terms involving $c(0)^{2}$ and
$\sum_{i=1}^{m}\|e_{i}(k+1)\|_{2}^{2}$. Substituting (51)–(54) and (56) into
(50) we have that

$\displaystyle L\sum_{i=1}^{m}\|\hat{x}_{i}(k+1)-\hat{v}(k+1)\|_{2}$
$\displaystyle\leq
L\mu\left(1+\frac{m\lambda}{2(1-q)}\right)\frac{\sum_{r=0}^{k}c(r)^{2}}{S(k+1)}$
$\displaystyle+\Bigg{(}m\lambda+2c(1)\Bigg{)}\frac{L\mu mD}{S(k+1)}$
$\displaystyle+\frac{L\mu}{S(k+1)}\left(1+\frac{m\lambda}{2(1-q)}\right)\sum_{r=0}^{k}\sum_{i=1}^{m}\|e_{i}(r+1)\|_{2}^{2}.$
(57)

To obtain the result, we need to manipulate the last term in the right-hand
side of (57). To this end, we invoke (42) with the same $\beta_{1}$ as in
(48), but with $(\alpha_{1}(k))_{k\in\mathbb{N}}$ and
$(\alpha_{2}(k))_{k\in\mathbb{N}}$ such that
$\alpha_{1}(k)=\alpha_{2}(k)=\alpha$, for all $k\in\mathbb{N}$, following the
same rationale as in Proposition 2 to obtain

$\displaystyle\sum_{r=0}^{k}$
$\displaystyle\sum_{i=1}^{m}\|e_{i}(r+1)\|_{2}^{2}\leq\frac{\sum_{i=1}^{m}\|x(0)-x^{\star}\|_{2}^{2}+\beta_{3}}{1-\beta_{1}-2\alpha}$
$\displaystyle+\frac{1}{1-\beta_{1}-2\alpha}\Big{(}mL^{2}\frac{2}{\alpha}+\beta_{2}\Big{)}\sum_{r=0}^{k}c(r)^{2}$
$\displaystyle\leq\frac{4mD^{2}+\beta_{3}}{1-\beta_{1}-2\alpha}$
$\displaystyle+\frac{1}{1-\beta_{1}-2\alpha}\Big{(}mL^{2}\frac{2}{\alpha}+\beta_{2}\Big{)}\sum_{r=0}^{k}c(r)^{2}.$
(58)

Substituting (58) into (57) we obtain (44) with constants

$\displaystyle d_{3}$
$\displaystyle=L\mu\Biggl{[}\Bigg{(}1+\frac{m\lambda}{2(1-q)}\Bigg{)}\frac{4mD^{2}+\beta_{3}}{1-\beta_{1}-2\alpha}+mD\Bigg{(}m\lambda+2c(1)\Bigg{)}\Biggr{]},$
$\displaystyle d_{4}$
$\displaystyle=L\mu\Bigg{(}1+\frac{m\lambda}{2(1-q)}\Bigg{)}\Bigg{(}1+\frac{1}{1-\beta_{1}-2\alpha}\Big{(}mL^{2}\frac{2}{\alpha}+\beta_{2}\Big{)}\Bigg{)},$

thus concluding the proof of Theorem 2.

## References

  * [1] G. Mateos, G. B. Giannakis, Distributed recursive least-squares: Stability and performance analysis, IEEE Transactions on Signal Processing 60 (7) (2012) 3740–3754.
  * [2] B. Baingana, G. Mateos, G. B. Giannakis, Proximal-Gradient Algorithms for Tracking Cascades Over Social Networks, IEEE Journal of Selected Topics in Signal Processing 8 (4) (2014) 563–575.
  * [3] S. Martinez, F. Bullo, J. Cortes, E. Frazzoli, On Synchronous Robotic Networks \- Part I: Models, Tasks and Complexity, IEEE Transactions on Automatic Control 52 (12) (2007) 2199–2213.
  * [4] S. Bolognani, R. Carli, G. Cavraro, S. Zampieri, Distributed Reactive Power Feedback Control for Voltage Regulation and Loss Minimization, IEEE Transactions on Automatic Control 60 (4) (2015) 966–981.
  * [5] M. Zhu, S. Martinez, On distributed convex optimization under inequality and equality constraints, IEEE Transactions on Automatic Control 57 (1) (2012) 151–164.
  * [6] A. Nedić, A. Olshevsky, Distributed optimization over time-varying directed graphs, IEEE Transactions on Automatic Control 60 (3) (2015) 601–615.
  * [7] C. Xi, U. A. Khan, Distributed Subgradient Projection Algorithm Over Directed Graphs, IEEE Transactions on Automatic Control 62 (8) (2017) 3986–3992.
  * [8] K. Margellos, A. Falsone, S. Garatti, M. Prandini, Distributed Constrained Optimization and Consensus in Uncertain Networks via Proximal Minimization, IEEE Transactions on Automatic Control 63 (5) (2018) 1372–1387.
  * [9] S. Liang, L. Wang, G. Yin, Distributed quasi-monotone subgradient algorithm for nonsmooth convex optimization over directed graphs, Automatica 101 (2019) 175–181.
  * [10] P. Bianchi, Ergodic convergence of a stochastic proximal point algorithm, SIAM Journal on Optimization 26 (4) (2016) 2235–2260.
  * [11] A. Patrascu, I. Necoara, Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization, Journal of Machine Learning Research 18 (2018) 1–42.
  * [12] B. Johansson, T. Keviczky, M. Johansson, K. H. Johansson, Subgradient methods and consensus algorithms for solving convex optimization problems, Proceedings of the IEEE Conference on Decision and Control (5) (2008) 4185–4190.
  * [13] A. Nedic, A. Ozdaglar, Approximate primal solutions and rate analysis for dual subgradients methods, SIAM Journal on Optimization 33 (5) (2009) 2295–2317.
  * [14] A. Nedic, A. Ozdaglar, P. A. Parrilo, Constrained Consensus and Optimization in Multi-Agent Networks, IEEE Transactions on Automatic Control 55 (4) (2010) 922–938.
  * [15] P. Lin, W. Ren, Y. Song, Distributed multi-agent optimization subject to nonidentical constraints and communication delays, Automatica 65 (2016) 120–131.
  * [16] S. Lee, A. Nedić, Distributed random projection algorithm for convex optimization, IEEE Journal on Selected Topics in Signal Processing 7 (2) (2013) 221–229.
  * [17] V. S. Mai, E. H. Abed, Distributed optimization over directed graphs with row stochasticity and constraint regularity, Automatica 102 (2019) 94–104.
  * [18] J. N. Tsitsiklis, D. P. Bertsekas, M. Athans, Distributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms, IEEE Transactions on Automatic Control 31 (9) (1986) 803–812.
  * [19] D. P. Bertsekas, J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Scientific, Athena, 1989.
  * [20] J. C. Duchi, A. Agarwal, M. J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling, IEEE Transactions on Automatic Control 57 (3) (2012) 592–606.
  * [21] L. Romao, K. Margellos, G. Notarstefano, A. Papachristodoulou, Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets, in: 58th Conference on Decision and Control, 2019, pp. 7448–7453.
  * [22] A. Nedić, A. Ozdaglar, Distributed Subgradient Methods for Multi-Agent Optimization, IEEE Trans. Automatic Control 54 (1) (2009) 48–61.
  * [23] D. Jakovetic, J. M. Moura, J. Xavier, Distributed Nesterov-like gradient algorithms, in: 51st IEEE Conference on Decision and Control, 2012, pp. 5459–5464.
  * [24] K. Yuan, Q. Ling, W. Yin, On the convergence of decentralized gradient descent, SIAM Journal on Optimization 26 (5) (2016) 1835–1854.
  * [25] J. Lei, H.-F. Chen, H.-T. Fang, Primal–dual algorithm for distributed constrained optimization, Systems & Control Letters 96 (2016) 110–117.
  * [26] G. Scutari, Y. Sun, Distributed Nonconvex Constrained Optimization over Time-Varying Digraphs, Mathematical Programming, 2019, pp.497–544.
  * [27] K. I. Tsianos, S. Lawlor, M. G. Rabbat, Push-Sum Distributed Dual Averaging for convex optimization, 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) (2012) 5453–5458.
  * [28] S. Liu, Z. Qiu, L. Xie, Convergence rate analysis of distributed optimization with projected subgradient algorithm, Automatica 83 (2017) 162–169.
  * [29] W. Shi, Q. Ling, G. Wu, W. Yin, EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization, SIAM Journal on Optimization 25 (2) (2015) 944–966.
  * [30] G. Qu, N. Li, Harnessing smoothness to accelerate distributed optimization, IEEE Transactions on Control of Network Systems 5 (3) (2018) 1245–1260.
  * [31] F. Zanella, D. Varagnolo, A. Cenedese, G. Pillonetto, L. Schenato, Newton-Raphson Consensus for Distributed Convex Optimization, IEEE Transactions on Automatic Control 61 (4) (2016) 994–1009.
  * [32] A. I. Chen, A. Ozdaglar, A fast distributed proximal-gradient method, 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012, 2012, pp. 601–608.
  * [33] D. P. Bertsekas, Convex Optimization Theory, Athena Scientific, 2009.
  * [34] R. T. Rockafellar, Convex Analysis, Princeton University Press, 1972.
  * [35] D. P. Bertsekas, J. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996\.