OPTIMAL ALGORITHMS FOR DISTRIBUTED OPTIMIZATION∗

arXiv:1712.00232v1 [math.OC] 1 Dec 2017

C.A. URIBE†, S. LEE‡, A. GASNIKOV§, AND A. NEDIĆ

§¶

Abstract. In this paper, we study the optimal convergence rate for distributed convex optimization problems
in networks. We model the communication restrictions imposed by the network as a set of
Paffine constraints and
provide optimal complexity bounds for four different setups, namely: the function F (x) , m
i=1 fi (x) is strongly
convex and smooth, either strongly convex or smooth or just convex. Our results show that Nesterov’s accelerated
gradient descent on the dual problem can be executed in a distributed manner and obtains the same optimal rates as
in the centralized version of the problem (up to constant or logarithmic factors) with an additional cost related to the
spectral gap of the interaction matrix. Finally, we discuss some extensions to the proposed setup such as proximal
friendly functions, time-varying graphs, improvement of the condition numbers.

1. Introduction. The study of distributed algorithms can be traced back to classic papers from the 70s and 80s [5, 9, 71, 23, 14, 15, 24]. The adoption of distributed optimization
algorithms on several fronts of applied and theoretical machine learning, robotics, and resource allocation has increased the attention on such methods in recent years [72, 65, 29,
30, 49]. The particular flexibilities induced by the distributed setup make them suitable for
large-scale problems involving large quantities of data [10, 11, 1, 43, 50].
Initial algorithms for distributed optimization such as distributed subgradient methods
were shown successful for solving optimization problems in a distributed manner over networks [41, 51, 66, 40]. Nevertheless, these algorithms are particularly slow compared with
their centralized counterparts. Moreover, from the optimization perspective, proposing and
analyzing algorithms with equivalent performance to their centralized counterparts have always been a priority. In a recent stream of literature, new distributed methods that achieve linear rates for strongly convex and smooth problems have been proposed in [45, 43, 68, 33, 67].
One can identify three main approaches to the study of distributed algorithms. In [43,
45, 46], the focus is achieving linear convergence rate for strongly convex and smooth problems. These results require some minimal information about the topology of the network
and provide explicit statements about the dependency of the convergence rate on the problem parameters. Specifically, polynomial scalability is shown with the network parameter for
particular choices of small enough step-sizes and even uncoordinated step-sizes are allowed
[46]. One particular advantage of this approach is that can handle time-varying and directed
graphs. Nevertheless, optimal dependencies on the problem parameters and tight convergence
rate bounds are far less understood for such algorithms.
p More recently, in [45] new methods
were proposed where it was shown that O((m2 + L/µm) log ε−1 ) iterations are required
to find an ε solution to the optimization problem when the function is µ-strongly convex and
L-smooth, where m is the number of nodes in the fixed undirected network. Recently in
[69], a unified approach has been proposed for analysis of the convergence rate of distributed
optimization algorithms via a semidefinite programming characterization. There, too, the
focus on strongly convex and smooth functions. This approach provides an innovative procedure to numerically certify worst-case rates of a plethora of distributed algorithms, which can
be useful to fine-tune parameters in existing algorithms based on feasibility conditions of a
semidefinite program. Nevertheless, the questions on the specific dependency on the problem
∗ The work of A. Nedić and C.A. Uribe was supported by the National Science Foundation under grant no.
CPS 15-44953. The work of A. Gasnikov was supported by RFBR 18-01-00347
† ECE Department and Coordinated Science Laboratory, University of Illinois (cauribe2@illinois.edu).
‡ Yahoo! Research (soominl@yahoo-inc.com).
§ Moscow Institute of Physics and Technology, Dolgoprudnyi 141700, Moscow Oblast, Russia.
(gasnikov@yandex.ru).
¶ ECEE Department, Arizona State University (angelia.nedich@asu.edu).

1

2

C.A. URIBE, S. LEE, A. GASNIKOV AND A. NEDIĆ

parameters and optimality certifications of the algorithms remain open. Similarly, in [27],
another unifying approach has been proposed, that encompasses several existing algorithms
proposed general method is able to recover existing
such as those in [68, 64]. This newlyp
rates and achieves an ε precision in O( L/(µλ2 ) log ε−1 ) iterations, where λ2 is the second
largest eigenvalue of the interaction matrix. Finally, a third approach was recently introduced
problems was proin [67], where the first optimal algorithm for distributed
p optimization
√
posed. This new method achieves an ε precision in O( L/µ(1 + τ / γ) log ε−1 ) iterations
for µ-strongly convex and L-smooth problems, where τ is the diameter of the network and
γ is the normalized eigengap of the interaction matrix. Even though extra information about
the topology of the network is required, the work in [67] provides a coherent understanding
of the optimal convergence rates and its dependencies on the communication network.
In this paper, we follow the approach in [67] to study the problem of distributed optimization over networks. Particularly, we consider the following optimization problem
(1)

min F (x)

x∈Rn

where

F (x) ,

m
X

fi (x),

i=1

where each fi : Rn → R is a convex function. Moreover, this problem needs to be solved in a
distributed manner where each function fi is known by an agent i only and agents can interact
with other agents over a network. We provide algorithms with provable optimal convergence
rates for the cases where the function F (x) is strongly convex and smooth, only strongly
convex and Lipschitz, only smooth or just convex and Lipschitz. In each of the cases, we will
study optimal algorithms for solving convex optimization problems with affine constraints
[4, 13, 21]. Initially, we will consider the case when the construction of an explicit dual
problem is possible. Later, we will remove this assumption. Moreover, we consider the case
of proximal friendly functions. Additional extensions to time-varying graphs and improving
the condition number are discussed.
Our results match known optimal complexity bounds for centralized convex optimization
(obtained by classical methods such as Nesterov’s Fast Gradient Method [53]), with an additional cost induced by the network of communication constraints. This extra cost appears in
the form of a multiplicative term proportional to the square root of the spectral gap of the interaction matrix. In summary, our main results provide an algorithm that achieves ε accuracy
on any fixed, connected and undirected graph according Table 1, where universal constants
are hidden for simplicity.
This paper is organized as follows: Section 2 introduces the problem of distributed optimization over networks. Section 3 presents a series of definitions and auxiliary results that
will help in the exposition of the main results. Section 4 provides our main result regarding
the optimal convergence rates for the solution of distributed optimization problems for the
different variations of smoothness and strong convexity properties. In Section 5 we study the
specific cost of having a distributed setup where we use as a guiding example the consensus problem, for which we find an optimal algorithm regarding the condition numbers and
the properties of the graph. In Sections 6 and 7, 8 we discuss extensions when the studied
function is not dual-friendly but proximal operations are easy to compute. Addutionally we
discuss how to improve the condition numbers. In Section 9 we provide some remarks of less
developed extensions for the distributed optimization setup, particularly, we discuss timevarying/directed graphs, the communication time versus the computation time and working
with general p-norms, with p ≥ 1. Finally, in we present some conclusions.
Notation: Generally, we will use the superscript i or j to denote agents, while the subscript
k will denote time (or iterations of an algorithm). We denote as [A]ij the entry of the matrix

3

OPTIMAL ALGORITHMS FOR DISTRIBUTED OPTIMIZATION

Approach

Reference

Centralized

[52]
[63]
[45]
[60]

Primal

µ-strongly convex
and L-smooth
q 
L
Õ
µ
 

5/7
L
3
Õ
m
µ

q

2
Õ m + L
µm
Õ

[17]
[31]
[39]
[27]

Dual
Friendly

[67]*
This
paper*

Õ




Õ
q

−

L 2
µm

−
L 4
µm

µ-strongly
convex and
M -Lipschitz
 2
Õ M
µε
−



Õ

L
µm

***
1
ε5/7

Õ


1
ε

−

−

−
Õ
Õ

−
Õ

L
ε

−

−

****

q 
o

−





Õ

−

L 2
µm
q

L
Õ
µm

q

L-smooth

q

M2
µε m



*

Õ

L
εm
L
εm

−
q

M -Lipschitz
Õ



M2
ε2

−



**
o 1ε
 2 
Õ Mε2m
−


3

−


4

L
εm

−

−


Õ

The function F (x) is assumed dual friendly.
Additionally, it is assumed functions
p are proximal friendly.
***
An iteration complexity of Õ( 1/ε) is shown if the objective is the composition of a
linear map and a strongly convex and smooth function.
****
A linear dependence on m is achieved if L is sufficiently close to µ.

M
ε m



**

Table 1: Iteration Complexity of Distributed Optimization Algorithms. The iteration
complexity refers to the required number of oracle calls. For distributed algorithms based
on primal iterations this translates to computations of gradients of the local functions for
each of the agents. On the other side, for dual based algorithms, the complexity refers to
computations of the gradient of the Lagrange dual function, which in translates to the number
of communication rounds in the network.

A at its i-th row and j-th column and In is the identity matrix of size n. We denote the largest
singular value of a matrix A as σmax (A) = λmax (AT A) = max{λ | ∃x 6= 0, AT Ax = λx}.
We use σmin (A) = min{λ > 0 | ∃x 6= 0, AT Ax = λx} as the smallest nonzero singular
(A)
value. Also, we define χ(AT A) = σσmax
. The notation Õ is used to ignore logarithmic
min (A)
factors in an estimate.
2. Problem Statement. In this section we will introduce the problem of distributed optimization. Initially, let us introduce a stacked column vector x = [xT1 , xT2 , . . . , xTm ]T ∈ Rmn
to rewrite the problem in Eq. (1) in an equivalent form as
min

x1 =...=xm

F (x) =

m
X

fi (xi ).

i=1

Now, suppose that we are required to solve this problem in a distributed manner over a
network. We model such a network as a fixed connected undirected graph G = (V, E), where

4

C.A. URIBE, S. LEE, A. GASNIKOV AND A. NEDIĆ

V is a set of m nodes and E is a set of edges. The network structure imposes information
constraints, namely, each node i has access to the function fi only, and a node can exchange
information only with its immediate neighbors, i.e., a node i can communicate with node j if
and only if (i, j) ∈ E.
We can represent the communication constraints imposed by the network by introducing a set of constraints to the original optimization problem in Eq.(1). Initially, define the
Laplacian matrix W̄ ∈ Rm×m of the graph G as


if (i, j) ∈ E,
−1,
[W̄ ]ij = deg(i), if i = j,


0,
otherwise .
where deg(i) is the degree of the node i, i.e., the number of neighbors of the node. Finally,
define the communication matrix, sometimes called interaction matrix as W = W̄ ⊗ In ,
where ⊗ indicates the Kronecker product.
One can verify that W is a nonnegative semidefinite matrix, with the following properties:
• W
√ x = 0 if and only if x1 = . . . = xm .
• W x√
= 0 if and only if x1 = . . . = xm .
• σmax ( W ) = λmax (W ).
Therefore, one can equivalently rewrite the problem in Eq. (1) as:
√min F (x) =

(2)

W x=0

where the constraint
span(1).

m
X

fi (xi ),

i=1

√
√
W x = 0 is equivalent to x1 = . . . = xm given that ker( W ) =

3. Preliminaries. Before presenting our main results, in this section, we will provide
a set of definitions and preliminary information that we will use throughout the paper in the
remaining sections.
R EMARK 3.1. For simplicity of exposition, we will present our results considering the
2-norm only, which is called the Euclidean setup. Nevertheless, in Section 9 we will point out
the generalization to other norms.
D EFINITION 3.2. A function f (·) is a µ-strongly convex function if for any x, y it holds
that
f (y) ≥ f (x) + h∇f (x), y − xi +

µ
kx − yk22 ,
2

where ∇f (x) is any subgradient of f (·) at x.

Particularly, if each of the functions fi (xi ) in the problem in Eq.(2) is µi -strongly convex
then F (x) is µ-strongly convex, with µ = min µi .
i=1,...,m

D EFINITION 3.3. A function f (·) has L-Lipschitz continuous gradient if it is differentiable and its gradient satisfies the Lipschitz condition, i.e. for any x, y
k∇f (x) − ∇f (y)k2 ≤ Lkx − yk2
A function having L-Lipschitz continuous gradient is also referred as L-smooth.

OPTIMAL ALGORITHMS FOR DISTRIBUTED OPTIMIZATION

5

If each of the functions fi (xi ) in the problem in Eq.(2) has Li -Lipschitz continuous
gradients then F (x) has L-Lipschitz continuous gradient with L = max Li .
i=1,...,m

Our main algorithmic tool will be Nesterov’s Fast Gradient Method (FGM) [56]. Next, in
Algorithm 1 we state one variant of the FGM method for a µ-strongly convex and L-smooth
function F (x). Other variants of this method can also be found in [56, 6, 34].
Algorithm 1 Nesterov’s Fast Gradient Method
1:
2:
3:
4:
5:
6:

Choose y0 = x0 ∈ Rn
while stopping criteria do
xk+1 = yk − L1 ∇f (yk )
√
√
µ
√ (xk+1 − xk )
yk+1 = xk+1 + √L−
L+ µ
end while
return xk
Specifically it holds for Algorithm 1 that
r k

µ
∗
f (xk ) − f ≤ L 1 −
kx0 − x∗ k22 ,
L

where f ∗ denotes the minimum value of the function f (x) and x∗ is its minimizer. This
result implies a geometric convergence rate, where one can find a solution that is ε close to
the optimal in
s
!

Lkx0 − x∗ k22
L
(3)
log
N =O
µ
ε
iterations.
In what follows we will consider a µ-strongly convex and L-smooth function f (x) and
the general optimization problem with linear constraints
min f (x)

(4)

Ax=0

where the Lagrangian dual problem of Eq. (4) is
n
o
max min f (x) − AT y, x
.
y

x

Now, rewrite the Lagrangian dual problem in its equivalent form as a minimization prob-

lem
(5)

min ϕ(y)
y

where

ϕ(y) = max
x



AT y, x − f (x) ,

and ϕ(y) is µϕ = σminL(A) -strongly convex in ker(AT )⊥ and has Lϕ = σmaxµ (A) -Lipschitz
continuous gradients.
From the Demyanov-Danskin’s theorem (see Proposition 4.5.1 in [7]) it follows that
∇ϕ(y) = Ax∗ (AT y) where x∗ (AT y) is the unique solution to the inner maximization problem

x∗ (AT y) = arg max AT y, x − f (x) .
x

In order to find x∗ (AT y) one can use optimal (randomized) numerical methods [56, 58].
Nonetheless, initially we will assume that we have access to x∗ (AT y) explicitly. Later in
Section 6 we will provide convergence rate estimates this assumption does not hold.

6

C.A. URIBE, S. LEE, A. GASNIKOV AND A. NEDIĆ

D EFINITION 3.4. A function f (x) is dual-friendly if when considering the optimization
problem in Eq.(4) one has immediate access to an explicit solution x∗ (AT y) to the dual
subproblem or it can be computed efficiently.
In general, the matrix A might not be full row rank. Then, the dual problem in Eq.(5)
can have multiple solutions of the form y ∗ + ker(AT ). If the solution is not unique, we will
choose y ∗ with the smallest norm solution. Moreover, we will denote its norm as R = ky ∗ k2
and assume that R < ∞.
Note that we will use the result in Eq.(3) applied to the dual problem in Eq.(4), which is
not strongly convex in the ordinary sense (in the whole space). Nevertheless, since we will
select y0 = x0 in Algorithm 1 as the initial condition, we will work in the linear space of
gradients on which we have strong convexity.
We will be interested in finding solutions to the problem in Eq.(4) that are arbitrarily
close to an optimal solution, both in terms of the error of the primal problem and the linear
constraints feasibility. For this, we introduce the following definition.
D EFINITION 3.5. We say that a point x̂ is an (ε, ε̃)-optimal solution for the problem in
Eq.(4) if the following condition holds
|f (x̂) − f (x∗ )| ≤ ε

and

kAx̂k2 ≤ ε̃.

where f (x∗ ) denotes the optimal function value the problem in Eq.(4). Moreover note that
f (x∗ (AT y)) − f (x∗ ) ≤ kyk2 kAx∗ (AT y)k2

To solve the dual problem in Eq.(5) one can use the FGM algorithm that specializes to
Algorithm 2.
Algorithm 2 Nesterov’s Fast Gradient Method on the Dual Problem
1:
2:
3:
4:
5:
6:

Choose y0 = ỹ0 = 0 ∈ Rn
while kyk k2 kAx∗ (AT yk )k2 ≥ ε and kAx∗ (AT yk )k2 ≥ ε̃ do
yk+1 = ỹk − L1ϕ Ax∗ (AT ỹk )
√
√
Lϕ − µϕ
√ (yk+1 − yk )
ỹk+1 = yk+1 + √
Lϕ +

µϕ

end while
return yk

From [16], we can immediately conclude that the number of oracle calls (calculations of
Ax and AT y) required for the Algorithm 2 is
s
s
!


!
R2
R
Lϕ
L
N =O
= Õ
log max 4Lϕ , 2Lϕ
(6)
χ(AT A) .
µϕ
ε
ε̃
µ
We will apply the FGM as described in Algorithm 2 to the dual of different variations
of the problem in Eq. (1). The next section presents the main results regarding the optimal
convergence rates for the solution of the distributed optimization problem.
4. Main results. Our main results provide convergence rate estimates for the solution
of the problem in Eq. (1) (or Eq. (2)) for four different cases:
1. F (x) is µ-strongly convex and L-smooth.
2. F (x) is µ-strongly convex and M -Lipschitz.
3. F (x) is L-smooth.
4. F (x) is M -Lipschitz.

OPTIMAL ALGORITHMS FOR DISTRIBUTED OPTIMIZATION

7

4.1. F (x) is L-smooth and µ-strongly convex. This case is a specific version of the
general
problem presented in Eq. (4). Particularly, when the linear constraints Ax = 0 are
√
W x = 0 and the function f (x) corresponds to the function F (x) as defined in Eq.(2).
Line 3 and 4 of Algorithm 2 captures the interaction between
of in√ agents and exchange
√
formation in the distributed setting. If we change of variables W yk = zk and W ỹk = z̃k ,
then the resulting iterations can be executed in a distributed manner. The main observation
is the interaction between agents is dictated by the term W x∗ (z̃k ) which depends only on
local information. Particularly, each node in the graph has its local variables zki and z̃ki , and
to compute the value of these variables on the next iteration it only requires the information
sent by the neighbors defined by the communication graph G. Each node i updates its local
variables as
m

1 X
Wij x∗j (z̃kj )
Lϕ j=1
p
p
L ϕ − µϕ i
i
p (zk+1 − zki )
= zk+1 + p
L ϕ + µϕ

(7a)

i
zk+1
= z̃ki −

(7b)

i
z̃k+1

where Wij = [W̄ ]ij ⊗ In and x∗j (wk ) is the components of solution of the dual subproblem
shared by agent j.
T HEOREM 4.1 (Case 1). Assume F (x) is dual-friendly, L-smooth and µ-strongly convex. Moreover, set ε̃ = ε/R. Then, after
N =O

s

L
χ(W ) log
µ



σmax (W )R2
µǫ

!

iterations (oracle calls) of Eqs.(7), the point x∗ (zN ) is an (ε, ε/R)-optimal solution to the
optimization problem in Eq. (2).
T
Proof.
√ The desired result follows from the estimate in Eq.(6), the definition of χ(A A)
and A = W and ε̃ = ε/R.

4.2. F (x) is µ-strongly convex and M -Lipschitz. The assumption of F (x) being µ-strongly
convex implies that the dual function ϕ(y) is Lϕ -smooth. In this case, we can use a regularization technique to induce the strong convexity of the dual function.
D EFINITION 4.2. For a convex function f (x), we define the strongly convex regularized
function f µ (x) with regularizer r2 (x) as
(8)
T HEOREM 4.3 (Case 2).
convex. Then, after

f µ (x) , f (x) +

µ 2
r (x).
2

Assume F (x) is dual-friendly, M -Lipschitz and µ-strongly

N = Õ

s

M2
χ(W )
µε

!

iterations (oracle calls) of Eqs.(7) on the regularized dual problem ϕµϕ (y), with µϕ = ε/R2
and regularizer kyk22 , the point x∗ (zN ) is an (ε, ε/R)-optimal solution to the optimization
problem in Eq. (2).

8

C.A. URIBE, S. LEE, A. GASNIKOV AND A. NEDIĆ

Proof. Initially, lets construct a regularized dual problem. Then, we have that
min ϕµ̂ (y) = ϕ(y) +

(9)

y

where µ̂ =

ε
R2 .

µ̂
kyk22
2

Assume there exists yN such that
ϕµ̂ (yN ) − ϕµ̂∗ ≤

ε
2

where ϕµ̂∗ is the optimal value of the regularized dual function. Then
ϕ(yN ) − ϕ∗ ≤ ε.

where ϕ∗ is the optimal value of the dual function.
It follows from [22] that the number of oracle calls required to find a (ε, ε̃)-optimal
solution is



 
r
min
F
(x)
−
min
F
(x))(ε
+
2Rε̃
4L
ϕ


 2Lϕ (ε + 2Rε̃)
x
Ax=0
log 
O

2
2
ε̃
ε · ε̃
Additionally, from Theorem 3 in [33] it follows that

(10)

R2 = ky ∗ k22 ≤

k∇F (x∗ )k22
M2
=
.
σmin (A)
σmin (A)

The final results follow by the definitions of ε̃ and Lϕ .
Note that we typically do not know R2 = ky ∗ k22 . Thus, we require a method to estimate
the strong convexity parameter µ̂ which is challenging [55, 59]. Therefore, we can apply the
restarting technique on µ [59]. The payment for that is just an 8 multiplicative factor in the
estimation [26]. Similarly, a generalization of the FGM algorithm can be proposed when Lϕ
is unknown [4]. The specific details of this generalizations are out of the scope of this paper.
4.3. F (x) is L-smooth. In this case, we can follows the same regularization technique
as in the previous scenario. However, in this case we can regularize the primal function.
T HEOREM 4.4 (Case 3). Assume F (x) is dual-friendly and L-smooth convex. Then,
after
!
r
LRx2
N = Õ
χ(W )
ε
iterations (oracle calls) of Eqs.(7) on the dual problem of the regularized function F µ (x)
with µ = ε/Rx2 = ε/kx∗ − x∗ (z0 )k22 and regularizer kx − x∗ (z0 )k22 , the point x∗ (zN ) is an
(ε, ε/R)-optimal solution to the optimization problem in Eq. (2).
Proof. We can regularize the primal problem in Eq. (4) such that we instead try to solve
µ
min F (x) + kx − x∗ (z0 )k22 ,
Ax=0
2
with µ = Rε2 . Additionally, if the minimizer x∗ is not unique we will consider it as the closest
x
solution from x∗ (z0 ), i.e. closest to the initial point of the algorithm.
This take us back to the case of subsection 4.1 for which we can conclude that up to
logarithmic factor that the number of iterations required is:
!
r
LRx2
T
Õ
(11)
χ(A A) .
ε

OPTIMAL ALGORITHMS FOR DISTRIBUTED OPTIMIZATION

9

4.4. F (x) is M -Lipschitz.
T HEOREM 4.5 (Case 4). Assume F (x) is dual-friendly and M -Lipschitz. Then, after
!
r
M 2 Rx2
χ(W )
N = Õ
ε2
iterations (oracle calls) of Eqs.(7) on the regularized dual problem ϕµϕ (y), with µϕ = ε/R2
and regularizer kyk22 , of the regularized function F µ (x) with µ = ε/Rx2 and regularizer
kx − x∗ (z0 )k22 , the point x∗ (zN ) is an (ε, ε/R)-optimal solution to the optimization problem
in Eq. (2).
Proof. Similarly as in the cases above we will use regularization. We will regularize
the primal problem with µ = Rε2 and then regularize the dual problem too with µ̂ = Rε2 .
x
Therefore, up to logarithmic factors the Algorithm 2 will stop in no more than
!
r
σmax (A)Rx2 (ε + 2Rε̃)
(12)
O
εε̃2
iterations. Where the estimate in Eq. (12) is unimporvable up to logarithmic factors.
4.5. A summary. Table 2 presents an informal summary of the results presented in this
section. In particular, it shows the number of oracle calls required in each of the problems to
obtain an ε-optimal solution. Moreover, it shows the specific dependency of the convergence
rates regarding the properties of the functions considered.
Property of F (x)
µ-strongly convex and L-smooth
µ-strongly convex and M -Lipschitz
L-smooth
M -Lipschitz

Iterations Required

q
L
χ(W
)
Õ
µ
q

M2
Õ
χ(W )
µε
q

LR2x
Õ
ε χ(W )
q

M 2 R2x
Õ
ε2 χ(W )

Table 2: A summary of Algorithmic Performance

The specific value of χ(W ) and its dependency on the number of nodes m has been
extensively studied in the literature of distributed optimization [50]. In [42], Proposition 5
provides an extensive list of worst-case dependencies of the spectral gap for large classes of
graphs. Particularly, for fixed undirected graphs, one can construct a set of weights W for
which χ(W ) = O(m2 ) [60]. This matches the best upper bound found in the literature of
consensus and distributed optimization [61, 36, 60]. As√an immediate conclusion it is clear
that the form in Eq.(2) with the constraint described as W x = 0 should be preferred over
the description as W x = 0, even though both representation√correctly describe the consensus
T
subspace x1 = . . . xm . Particularly, when we pick A = W , we have
pχ(A A) = χ(W
√ )
T
2
instead of χ(W W ) p
= χ(W ) ≫ χ(W ). For example forpa star graph χ(W ) = O( m),
for complete graphs χ(W ) = O(1), for path graphs χ(W ) ∼ diam(G) = O(m), for
p
p
regular networks χ(W ) ≥ diam(G)
χ(W ) corresponds to
log m . We can observe that typically
the diameter of the graph G and the square root of the spectral gap of the interaction matrix.

10

C.A. URIBE, S. LEE, A. GASNIKOV AND A. NEDIĆ

5. The cost of communications. In this section, we will study a particular form of the
optimization problem in Eq. (1) known as the consensus problem. This will help us further
understand the execution and performance of the studied distributed optimization algorithms.
Moreover, it will provide an answer to what is the additional cost, regarding algorithmic
complexity, when we try to solve an optimization problem in a distributed manner. We refer
to this cost as the cost of communication. We will show how, in the most basic setting, the
cost of communications and it depends on the topology of the communication network over
which the agents exchange information.
Assume that each node in the graph G holds an initial numeric value xi0 and can compute
the weighted average of the values held by its neighbors at each iteration. Let xik be the value
of node i at iteration k. We would like to know how many iterations are required (and what is
the proper algorithm) to reach consensus. Particularly, we will reach ε-consensus if for any
ε>0
v
v


2
2
u
u
uX
uX
m
m
m
m
X j
X
u
u
1
1
xi −
xi0 −
t
x0  ≤ εt
xj0  .
N
m
m
i=1
i=1
j=1
j=1
This problem can be solved by considering the convex optimization problem

(13)

min
x

1
hx, W xi .
2

where W is a communication matrix as defined in Section 2.
the number of iterations required to reach conTheorem 4.1 provides a direct
pestimate on −1
sensus,
particularly
we
need
O(
χ(W
)
log
ε
), where we√have used the fact that (13) is
√
σmin ( W )-strongly convex in x0 + ker(W ) and has σmax ( W )-Lipschitz continuous gradients. Moreover, it follows that this estimate cannot be improved up to constant factors. It is
important to remark that the Fast Gradient Method, with xi0 = ỹ0i , does respect the information constraints imposed by the network. That is, each node only requires the computation of
the average of its immediate neighbors and aggregation can be performed in a fully distributed
manner.
The estimates presented in the Theorems 4.1 and 4.3 to 4.5 cannot be improved up to
logarithmic factors. Particularly in the smooth cases where L < ∞ these estimations follow
(up to logarithmic factors) form the classical centralized complexity estimation of the FGM
algorithm, where for a µ-strongly convex and L-smooth convex problem we require at most
s
 2 !
µRx
L
log
O
µ
ε
oracle calls and for a L-smooth convex problem we require at most
!
r
LRx2
O
.
ε
oracle calls.
In additionp
to these centralized estimates we need to take into account the fact that one
has to perform χ(W ) log(ε−1 ) additional consensus steps at each iteration of the classical
FGM.
The Laplacian matrix W̄ can be written as W̄ = D − Ã where Ã is the adjacency
matrix of the graph G and D is the degree matrix. In addition, Ã = DP for a stochastic

OPTIMAL ALGORITHMS FOR DISTRIBUTED OPTIMIZATION

11

matrix P (the transition matrix of a Markov Chain). Thus, one can apply a simple power
method such as xk+1 = P xk to find the consensus value (see ergodic theorem for Markov
Chains). Each node depends only on the computation of averages of its neighbor values
because of the matrix-vector multiplication P xk . As a result the number of required iterations
is O(χ(W ) log ε−1 ) ([41, 71, 8]). This result can be considered as a non-accelerated weighted
gradient method for the problem in Eq. (13) and holds even if the graph is time-varying and
directed (i.e. Ã is not symmetric [40, 48, 47]). However, it is still an open question whether
one can get accelerated rates as those provided by Algorithm 2 when the graph is directed.
In the following sections, we explore extensions and open problems related to the results presented so far. We study the case when the functions are not dual-friendly, when the
function is proximal-friendly and how to improve the condition number L/µ.
6. No Explicit Dual Solution is available. In all the results presented so far, we have
assumed that the problem is dual-friendly in the sense that we have readily available solutions
to the dual subproblem. In this section, we will explore the case when this is not possible.
Note that the dual subproblem can also be computed in a distributed manner. Specifically,
we have that

*
+
m

 X
 T
ATij yj , xi − fi (xi ) .
arg max A y, x − f (x) = arg max

x
xi ,i=1,...,m 
j=1

When the function is smooth or when is strongly convex and smooth, one can solve the
auxiliary problem
max {hy, Axi − f (x)} = y, Ax∗ (AT y) − f (x∗ (AT y))
x

using fast gradient methods (if the function is smooth, one should make one additional regularization µ = Rε2 ) applied for the strongly convex problem. Therefore, we can find a
x
solution for the dual problem, i.e. x∗ (AT y), in a logarithmic number of iterations from a desired relative precision δ. This fact allows us avoid considering the error in the computation
of x∗ (AT y). When
 is strongly convex and smooth, we can solve the auxiliary
q the function
L
µ

log(δ −1 ) oracle calls (oracle call is the calculation of ∇f (x)). On the

q
LR2x
−1
log(δ
)
iterations.
other hand, when the function is only smooth, we require O
ε

problem in O

Both estimates are optimal up to logarithmic factor. Therefore, in those cases, we propose
totally optimal methods.
Unfortunately, this is not the case when the function f (x) is not smooth. Nevertheless,
in these cases we might use another approach, that gives optimal estimates in both senses: the
total number of oracle calls (calculations ∇f (x)) and the total number of communications
(Ax, AT y multiplications).
Lets consider first the case where f (x) is convex and apply Nesterov’s smoothing technique [54, 37] to the dual problem


min f (x) = min max {hy, Axi − f (x)}
x
y
Ax=0
n
o
= max min {f (x) + hy, Axi}
(14)
y

x

Moreover, by using the bound in Eq. (10), we can replace the function
G(Ax) = max hy, Axi
y

12

C.A. URIBE, S. LEE, A. GASNIKOV AND A. NEDIĆ

by
n
o R2
ε
2
Gε (Ax) = max hy, Axi −
kyk
kAxk22 .
2 =
y
2R2
2ε
T

2

)R
-Lipschitz continuous
Finally, one can show that the function Gε (Ax) has a σmax (A
ε
T
gradient, (note that σmax (A ) = σmax (A)). So, we can solve the composite type mixed
smooth/non-smooth type problem

Gε (Ax)
| {z }

min

(15)

kxk2 ≤Rx

+

∼ ε1 -Lipschitz gradient

f (x)
|{z}

M−Lipschitz

where gradient oracle for Gε (Ax) requires a constant number of Ax multiplications (because
we can explicitly write the formula for ∇Gε (z)) and the gradient oracle for f (x) requires one
∇f (x) calculations. Using Lan’s accelerated gradient sliding [32], one can find an ε-solution
(in function value) of Eq. (15) without any auxiliary dual problem, after

s
!
r
σmax (A)R2 2
R
M 2 Rx2
x
ε
T

=O
χ(A A)
NAx = O
ε
ε2
oracle calls, i.e., Ax multiplications and

N∇f (x) = O



M 2 Rx2
ε2



oracle calls, i.e., ∇f (x)-gradient calculations. Unfortunately, in this approach we can guarantee kAxN k ≤ Rε only in the best case [3].
Using the restart technique [26, 28] one can extend Lan’s accelerated gradient sliding for f (x)
convex. At the k-th restart the number of oracle calls is

qbeing µ-strongly
 k 2
2
σmax (A)R
2 M
computations
of
Ax
and
N
=
O
oracle calls for
NAx = O
∇f
(x)
µε
ε2 R2
x

∇f (x). This allows to improve estimates for the problem in Eq. (15) in the following manner:
s
 2 !
µRx
M2
(16)
χ(AT A) log
NAx = O
µε
ε
computations of Ax and
N∇f (x) = O

(17)



M2
µε



oracle calls of ∇f (x), where these estimates are optimal up to logarithmic factors. Moreover,
one can extend these results to stochastic optimization problems and the estimations will not
change [33].
7. Acceleration when f (x) is a proximal-friendly functional. Let us consider the case
when f (x) is convex, but not strongly convex nor smooth, and return to Eq. (14) which can
be rewritten as
min f (x) = max min {f (x) + hy, Axi}

Ax=0

y

x

OPTIMAL ALGORITHMS FOR DISTRIBUTED OPTIMIZATION

13



1
= max min min f (x) + hy, Axi + kx − zk22 .
y
z
x
2
|
{z
}
G(y,z)

We will say the function f (x) is proximal-friendly, if we can solve the auxiliary strongly
convex problem


1
2
proxf,AT y (z) = arg min f (x) + hy, Axi + kx − zk2
2
x
explicitly, similarly as the definition of dual-friendly.
Therefore, given that
k∇G(y ′ , z ′ ) − ∇G(y, z)k2 ≤ Ly ky ′ − yk2 + Lz kz ′ − zk2 ,
one can find an ε- solution (in terms of the duality gap) of the saddle point problem
max min G(y, z)

kyk2 ≤R

z


after NAx = O 1ε , Ax multiplications, see [12], section 5.2.
Unfortunately, this does not provide any acceleration. Since, to find proxf,AT y (z) typically, one has to find an ε-solution of a strongly convex optimization problem. This can be
done in O( 1ε ) calculations
of ∇f (x). So the total number of iterations will be of the order

N∇f (x) = O ε12 .
Now, let us propose another approach, consider the original problem in Eq. (4) and add
the additional term 21 kAxk22 which is identically zero on any feasible point Ax = 0. Thus,


1
f (x) + kAxk22
Ax=0
2


1
= min
f (x) + max h−y, Azi + kAxk22
y
x,z;Ax=Az
2


1
′
2
= min f (x) + max h−y, Azi + max
hy
,
Az
−
Axi
+
kAxk
2
x,z
y
y′
2


Az=u

1
′
T ′
2
= − min′ max A y , x − f (x) + max hy − y , ui − kuk2
x
u∈ImA
y,y
2


1
= − min′ ϕ(y ′ ) + kprojker(AT )⊥ (y − y ′ )k22
y,y
2

min f (x) = min

Ax=0

If ϕ(y ′ ) is proximal friendly, we can solve the auxiliary problem (this is the proximal
version of the standard dual problem) explicitly, then using accelerated proximal
 1  gradient
descent (in the space of y) one can find an ε solution to the dual problem in O ε− 2 proximal
steps [62]. Moreover, the results in [35] allows for an extension to randomized methods.
Therefore, we obtain acceleration.
8. Improving the condition number L
µ when F (x) is strongly convex and smooth.
Considering the problem in Eq. (1), if each fi (xi ) is a µi -strongly convex function , and has
Li -Lipschitz continuous gradients, then F (x) is a µ = mini=1,...,m µi -strongly convex and
has L = maxi=1,...,m Li -Lipschitz continuous gradients.

14

C.A. URIBE, S. LEE, A. GASNIKOV AND A. NEDIĆ

As a result, the condition number L
µ can be large in general, at least if one of the µi is
small. To overcome this drawback, we can formulate another regularization for the problem
in Eq. (2) as
√min Fα (x) =

(18)

W x=0

m
X
i=1

fi (xi ) +

α
hx, W xi
2
m
P


µi , αλmin (W ) -strongly

Furthermore, the regularized function Fα is µ ≥ min
i=1


convex and has L ≤
max Li + αλmax (W ) -Lipschitz continuous gradient. Moreover,
i=1,...,m

if we set α ≃

m
P

µk /λmin (W ), one can solve the problem in Eq. (18) with relative precision

k=1

ε after (see also [43])

NW x





max
L
i
 i=1,...,m
p

2 −1 

= O
+ χ(W )
m
 P
 χ(W ) log (ε )
µi
i=1

communication steps and


N∇F (x) = O NW x log−1 (ε−1 )

gradient ∇F (x) calculations.
This estimate shows that we can replace the smallest strong convexity constant for the
sum among all of them, but we have to pay an additive price proportional to the condition
number of the graph.
Using the regularization technique with µi = mRε 2 = Rε2 one can extend this result to
xi
x
the case where the function is just smooth.
9. Discussion and Conclusions. In this section, we will discuss a set of possible extensions and open problems related to the results presented so far. Particularly, we will explore
the case when the graph is directed or changing with time. What to do if the time required for
by the oracle is not comparable with the communication steps. How to handle non-Euclidean
setups.
Time-Varying/Directed Graphs: Throughout this paper, we have assumed that the considered network of agents is fixed and undirected. This implies that the construction of the
interaction matrix can be done in a distributed manner and the result will be a symmetric matrix, i.e., W = W T . In a very specific case, when we have two communication
networks, dual to each other, our approach will work, but this is a rare situation. Nonaccelerated approaches have been shown successful in the study of time-varying directed
graphs [40, 47, 48, 44]. They have been shown to provide solutions to the distributed optimization problem for strongly convex and smooth functions with linear rates. Nevertheless,
it is an open problem to show that optimal convergence rates, comparable to those in the
centralized case can be achieved for time-varying and directed graphs.
Let us return to the consensus problem in Eq. (13). But now assume that from time to
time the matrix W changes, nonetheless remaining a interaction matrix. Therefore, we have
a family of nonnegative semi-definite quadratic functions with the same kernel, ker(W ) (in
our case described as x1 = . . . = xk ). How can we find a projection of x01 , . . . , x0m on this set
working at each iteration with different matrices W ? One can solve the problem in Eq. (13)

OPTIMAL ALGORITHMS FOR DISTRIBUTED OPTIMIZATION

15

with relative precision by the simple gradient descent method on χ(W ) log ε−1 communication steps because this dynamic has a Lyapunov function: that is the square distance between
the
and ker(W ). Nevertheless, it is known that one can accelerate this value to
p current point
χ(W ) log ε−1 for fixed graphs. Whether acceleration is possible for time-varying graphs
remains an open question to the best of the authors’ knowledge. Such generalization of Nesterov’s accelerated gradient method is unknown [38, 12, 2, 35, 70, 25, 69]. On the other side,
if one can detect the moment the graph changes, and such changes don’t happen very often
one can use restarting techniques [19, 21], which provide the following estimations for the
number of communication steps needed
v
!
u
√
u
tmax σmax (√ W ) log ε−1 .
W
σmin ( W )

Fast Gossip Steps: CPUs in these days can read and write from and to memory at over
10GB per second, whereas communication over T CP/IP is about 10M B per second [33].
Therefore, the gap between intra-node computation and inter-node communication is about
3 order of magnitude. Communication start-up cost itself is also not negligible as it usually
takes a few milliseconds. Let us consider that one node can calculate ∇fi (xi ) (or even calculate x∗i (AT y)) in 1 unit of time and the communication step takes τ units of time. In case
τ ≫ 1, in this regime all the results above seem reasonable because we first think of communication steps. However, if τ ≪ 1 one should use a method with multiple communication
steps. Chebyshev acceleration is suggested in [67], where instead of using the interaction
matrix W one can analyze the algorithm with a different one PK (W ). PK (W ) is a polynomial of degree K, and its eigengap is maximized
 choice based on Chebyshev
 with a specific
p
√
polynomials. If K is chosen as χ(W ) then χ P χ(W ) (W ) ∼ 1.
p-norms, with p ≥ 1: The cases when F (x) is convex or strongly convex can be generalized
to p-norms, with p ≥ 1 see [4]. Particularly, the definitions of the condition number χ(·)
needs to be defined accordingly. Let’s introduce a norm kxk2p = kx1 k2p + ... + kxm k2p for
p ≥ 1 and assume that F (x) is µ-strongly convex and L-Lipschitz continuous gradient in this
(new) norm k · kp (in Rmn ), see [57] (Lemma 1), [18] (Lemma 1) and [54] (Theorem 1)..
Thus
χ(W ) =

<h,W h>
µ
h>
minkhk=1,h⊥ker(W ) <h,W
L

maxkhk=1

One can try to generalize this results to an intermediate level of smoothness. That is, try
to propose the method for arbitrary Hölder parameter ν ∈ [0, 1]. For example, one can use
Universal Nesterov’s method by skipping the adaptation and proper choosing of δ(ν, ǫ). This
is another way to obtain results in the non-smooth case as a special situation ν = 0. In the
dual space, we will not have classical strong convexity but just uniform convexity. However,
it can be studied by introducing inexact oracle as in [20].
We have provided convergence rate estimates for the solution of convex optimization
problems in a distributed manner. The provided complexity bounds depend explicitly on the
properties of the function to be optimized. If F (x) is smooth, then our estimates are optimal
up to logarithmic factors otherwise our estimates
p are optimal up to constant factors. The inclusion of the graph properties in the form of χ(W ) shows the additional price to be paid
in contrast with classical (centralized/non-distributed) optimal estimates. The authors recognize that the proposed algorithms required, to some extent, some global knowledge about

16

C.A. URIBE, S. LEE, A. GASNIKOV AND A. NEDIĆ

the graph properties and the condition number of the global function, nevertheless we aim
to provide a theoretical foundation for the performance limits of the distributed algorithms.
Further explorations of the cases where such information is not available require additional
study.
REFERENCES
[1] M. A BADI , A. A GARWAL , P. BARHAM , E. B REVDO , Z. C HEN , C. C ITRO , G. S. C ORRADO , A. D AVIS ,
J. D EAN , M. D EVIN , ET AL ., Tensorflow: Large-scale machine learning on heterogeneous distributed
systems, arXiv preprint arXiv:1603.04467, (2016).
[2] Z. A LLEN -Z HU AND L. O RECCHIA, Linear coupling: An ultimate unification of gradient and mirror descent,
arXiv preprint arXiv:1407.1537, (2014).
[3] A. A NIKIN , P. D VURECHENSKY, A. G ASNIKOV, A. G OLOV, A. G ORNOV, Y. M AXIMOV, M. M ENDEL ,
AND V. S POKOINY , Efficient numerical algorithms for regularized regression problem with applications
to traffic matrix estimations, arXiv preprint arXiv:1508.00858, (2015).
[4] A. A NIKIN , A. G ASNIKOV, P. D VURECHENSKY, A. T YURIN , AND A. C HERNOV, Dual approaches to the
minimization of strongly convex functionals with a simple structure under affine constraints, Computational Mathematics and Mathematical Physics, 57 (2017), pp. 1262–1276.
[5] R. J. AUMANN, Agreeing to disagree, The Annals of Statistics, 4 (1976), pp. 1236–1239.
[6] A. B ECK AND M. T EBOULLE, A fast iterative shrinkage-thresholding algorithm for linear inverse problems,
SIAM journal on imaging sciences, 2 (2009), pp. 183–202.
[7] D. P. B ERTSEKAS , A. N EDI Ć , AND A. E. O ZDAGLAR, Convex analysis and optimization, Athena Scientific,
2003.
[8] D. P. B ERTSEKAS AND J. N. T SITSIKLIS, Parallel and distributed computation: numerical methods,
Prentice-Hall, Inc., 1989.
[9] V. B ORKAR AND P. P. VARAIYA, Asymptotic agreement in distributed estimation, IEEE Transactions on
Automatic Control, 27 (1982), pp. 650–655.
[10] L. B OTTOU, Large-scale machine learning with stochastic gradient descent, in Proceedings of COMPSTAT’2010, Springer, 2010, pp. 177–186.
[11] S. B OYD , N. PARIKH , E. C HU , B. P ELEATO , AND J. E CKSTEIN, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends R in Machine
Learning, 3 (2011), pp. 1–122.
[12] S. B UBECK, Convex optimization: Algorithms and complexity, Found. Trends Mach. Learn., 8 (2015),
pp. 231–357.
[13] A. C HERNOV, P. D VURECHENSKY, AND A. G ASNIKOV, Fast Primal-Dual Gradient Method for Strongly
Convex Minimization Problems with Linear Constraints, Springer International Publishing, Cham, 2016,
pp. 391–403.
[14] R. C OOKE, Statistics in expert resolution: A theory of weights for combining expert opinion, in Statistics
in Science, R. Cooke and D. Costantini, eds., vol. 122 of Boston Studies in the Philosophy of Science,
Springer Netherlands, 1990, pp. 41–72.
[15] M. H. D E G ROOT, Reaching a consensus, Journal of the American Statistical Association, 69 (1974), pp. 118–
121.
[16] O. D EVOLDER , F. G LINEUR , AND Y. N ESTEROV, Double smoothing technique for large-scale linearly
constrained convex optimization, SIAM Journal on Optimization, 22 (2012), pp. 702–727.
[17] T. T. D OAN AND A. O LSHEVSKY, Distributed resource allocation on dynamic networks in quadratic time,
Systems & Control Letters, 99 (2017), pp. 57–63.
[18] P. D VURECHENSKY, Gradient method with inexact oracle for composite non-convex optimization, arXiv
preprint arXiv:1703.09180, (2017).
[19] O. F ERCOQ AND Z. Q U, Restarting accelerated gradient methods with a rough strong convexity estimate,
arXiv preprint arXiv:1609.07358, (2016).
[20] A. G ASNIKOV, P. D VURECHENSKY, AND D. K AMZOLOV, Gradient and gradient-free methods for stochastic
convex optimization with inexact oracle, arXiv preprint arXiv:1502.06259, (2015).
[21] A. G ASNIKOV, S. K ABANIKHIN , A. M OHAMED , AND M. S HISHLENIN, Convex optimization in hilbert
space with applications to inverse problems, arXiv preprint arXiv:1703.00267, (2017).
[22] A. V. G ASNIKOV, E. G ASNIKOVA , Y. E. N ESTEROV, AND A. C HERNOV, Efficient numerical methods
for entropy-linear programming problems, Computational Mathematics and Mathematical Physics, 56
(2016), pp. 514–524.
[23] C. G ENEST AND J. V. Z IDEK, Combining probability distributions: A critique and an annotated bibliography, Statistical Science, 1 (1986), pp. 114–135, http://www.jstor.org/stable/2245510.
[24] G. L. G ILARDONI AND M. K. C LAYTON, On reaching a consensus using degroot’s iterative pooling, The
Annals of Statistics, 21 (1993), pp. 391–401.

OPTIMAL ALGORITHMS FOR DISTRIBUTED OPTIMIZATION

17

[25] B. H U AND L. L ESSARD, Dissipativity theory for nesterov’s accelerated method, arXiv preprint
arXiv:1706.04381, (2017).
[26] A. I OUDITSKI AND Y. N ESTEROV, Primal-dual subgradient methods for minimizing uniformly convex functions, arXiv preprint arXiv:1401.1792, (2014).
[27] D. JAKOVETIC, A unification, generalization, and acceleration of exact distributed first order methods, arXiv
preprint arXiv:1709.01317, (2017).
[28] A. J UDITSKY AND A. N EMIROVSKI , First order methods for nonsmooth convex large-scale optimization, i:
general purpose methods, Optimization for Machine Learning, (2011), pp. 121–148.
[29] J. K ONE ČN Ỳ , B. M C M AHAN , AND D. R AMAGE, Federated optimization: Distributed optimization beyond
the datacenter, arXiv preprint arXiv:1511.03575, (2015).
[30] T. K RASKA , A. TALWALKAR , J. C. D UCHI , R. G RIFFITH , M. J. F RANKLIN , AND M. I. J ORDAN, Mlbase:
A distributed machine-learning system., in CIDR, vol. 1, 2013, pp. 2–1.
[31] H. L AKSHMANAN AND D. P. D E FARIAS , Decentralized resource allocation in dynamic networks of agents,
SIAM Journal on Optimization, 19 (2008), pp. 911–940.
[32] G. L AN, Gradient sliding for composite optimization, Mathematical Programming, 159 (2016), pp. 201–235.
[33] G. L AN , S. L EE , AND Y. Z HOU, Communication-efficient algorithms for decentralized and stochastic optimization, arXiv preprint arXiv:1701.03961, (2017).
[34] G. L AN , Z. L U , AND R. D. C. M ONTEIRO, Primal-dual first-order methods with o(1/ε) iteration-complexity
for cone programming, Mathematical Programming, 126 (2011), pp. 1–29.
[35] H. L IN , J. M AIRAL , AND Z. H ARCHAOUI , A universal catalyst for first-order optimization, in Advances in
Neural Information Processing Systems, 2015, pp. 3384–3392.
[36] J. L IU , B. D. A NDERSON , M. C AO , AND A. S. M ORSE, Analysis of accelerated gossip algorithms, Automatica, 49 (2013), pp. 873–883.
[37] N. M. N AM , N. T. A N , R. B. R ECTOR , AND J. S UN, Nonsmooth algorithms and nesterov’s smoothing technique for generalized fermat–torricelli problems, SIAM Journal on Optimization, 24 (2014), pp. 1815–
1839.
[38] G. N ARKISS AND M. Z IBULEVSKY, Sequential subspace optimization method for large-scale unconstrained
problems, Technion-IIT, Department of Electrical Engineering, 2005.
[39] I. N ECOARA, Random coordinate descent algorithms for multi-agent convex optimization over networks,
IEEE Transactions on Automatic Control, 58 (2013), pp. 2001–2012.
[40] A. N EDI Ć AND A. O LSHEVSKY, Distributed optimization over time-varying directed graphs, IEEE Transactions on Automatic Control, 60 (2015), pp. 601–615.
[41] A. N EDI Ć , A. O LSHEVSKY, A. O ZDAGLAR , AND J. N. T SITSIKLIS, On distributed averaging algorithms
and quantization effects, IEEE Transactions on Automatic Control, 54 (2009), pp. 2506–2517.
[42] A. N EDI Ć , A. O LSHEVSKY, AND M. G. R ABBAT, Network topology and communication-computation tradeoffs in decentralized optimization, arXiv preprint arXiv:1709.08765, (2017).
[43] A. N EDI Ć , A. O LSHEVSKY, AND W. S HI , Achieving geometric convergence for distributed optimization over
time-varying graphs, arXiv preprint arXiv:1607.03218, (2016).
[44] A. N EDI Ć , A. O LSHEVSKY, AND W. S HI , Linearly convergent decentralized consensus optimization over
directed networks, in Signal and Information Processing (GlobalSIP), 2016 IEEE Global Conference on,
IEEE, 2016, pp. 485–489.
[45] A. N EDI Ć , A. O LSHEVSKY, AND W. S HI , Improved convergence rates for distributed resource allocation,
arXiv preprint arXiv:1706.05441, (2017).
[46] A. N EDI Ć , A. O LSHEVSKY, W. S HI , AND C. A. U RIBE, Geometrically convergent distributed optimization
with uncoordinated step-sizes, in American Control Conference (ACC), 2017, IEEE, 2017, pp. 3950–
3955.
[47] A. N EDI Ć , A. O LSHEVSKY, AND C. A. U RIBE, Distributed gaussian learning over time-varying directed
graphs, in 2016 50th Asilomar Conference on Signals, Systems and Computers, Nov 2016, pp. 1710–
1714.
[48] A. N EDI Ć , A. O LSHEVSKY, AND C. A. U RIBE, Network independent rates in distributed learning, in Proceedings of the American Control Conference, 2016, pp. 1072–1077.
[49] A. N EDI Ć , A. O LSHEVSKY, AND C. A. U RIBE, Distributed learning for cooperative inference, arXiv
preprint arXiv:1704.02718, (2017).
[50] A. N EDI Ć , A. O LSHEVSKY, AND C. A. U RIBE, Fast convergence rates for distributed non-bayesian learning, IEEE Transactions on Automatic Control, 62 (2017), pp. 5538–5553.
[51] A. N EDI Ć AND A. O ZDAGLAR, Distributed subgradient methods for multi-agent optimization, IEEE Transactions on Automatic Control, 54 (2009), pp. 48–61.
[52] A. N EMIROVSKII AND Y UDIN, Problem complexity and method efficiency in optimization, Wiley, 1983.
[53] Y. N ESTEROV, A method of solving a convex programming problem with convergence rate o (1/k2), in Soviet
Mathematics Doklady, vol. 27, 1983, pp. 372–376.
[54] Y. N ESTEROV, Smooth minimization of non-smooth functions, Mathematical programming, 103 (2005),
pp. 127–152.

18

C.A. URIBE, S. LEE, A. GASNIKOV AND A. NEDIĆ

[55] Y. N ESTEROV, Gradient methods for minimizing composite functions, Mathematical Programming, 140
(2013), pp. 125–161.
[56] Y. N ESTEROV, Introductory lectures on convex optimization: A basic course, vol. 87, Springer Science &
Business Media, 2013.
[57] Y. N ESTEROV, Universal gradient methods for convex optimization problems, Mathematical Programming,
152 (2015), pp. 381–404.
[58] Y. N ESTEROV AND A. N EMIROVSKII, Interior-point polynomial algorithms in convex programming, SIAM,
1994.
[59] B. O DONOGHUE AND E. C ANDES , Adaptive restart for accelerated gradient schemes, Foundations of computational mathematics, 15 (2015), pp. 715–732.
[60] A. O LSHEVSKY, Linear time average consensus on fixed graphs and implications for decentralized optimization and multi-agent control, preprint arXiv:1411.4186, (2014), https://arxiv.org/abs/arXiv:1411.4186.
[61] B. N. O RESHKIN , M. J. C OATES , AND M. G. R ABBAT, Optimization and analysis of distributed averaging
with short node memory, IEEE Transactions on Signal Processing, 58 (2010), pp. 2850–2865.
[62] N. PARIKH , S. B OYD , ET AL ., Proximal algorithms, Foundations and Trends R in Optimization, 1 (2014),
pp. 127–239.
[63] G. Q U AND N. L I , Accelerated distributed nesterov gradient descent, (2017), https://arxiv.org/abs/1705.
07176v2.
[64] G. Q U AND N. L I , Harnessing smoothness to accelerate distributed optimization, IEEE Transactions on
Control of Network Systems, (2017).
[65] M. R ABBAT AND R. N OWAK, Decentralized source localization and tracking wireless sensor networks, in
Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 3,
2004, pp. 921–924.
[66] S. S. R AM , A. N EDI Ć , AND V. V. V EERAVALLI , Distributed stochastic subgradient projection algorithms
for convex optimization, Journal of optimization theory and applications, 147 (2010), pp. 516–545.
[67] K. S CAMAN , F. BACH , S. B UBECK , Y. T. L EE , AND L. M ASSOULI É, Optimal algorithms for smooth and
strongly convex distributed optimization in networks, arXiv preprint arXiv:1702.08704, (2017).
[68] W. S HI , Q. L ING , G. W U , AND W. Y IN, Extra: An exact first-order algorithm for decentralized consensus
optimization, SIAM Journal on Optimization, 25 (2015), pp. 944–966.
[69] A. S UNDARARAJAN , B. H U , AND L. L ESSARD, Robust convergence analysis of distributed optimization
algorithms, (2017).
[70] A. B. TAYLOR , J. M. H ENDRICKX , AND F. G LINEUR, Exact worst-case performance of first-order methods
for composite convex optimization, SIAM Journal on Optimization, 27 (2017), pp. 1283–1313.
[71] J. N. T SITSIKLIS AND M. ATHANS , Convergence and asymptotic agreement in distributed decision problems, IEEE Transactions on Automatic Control, 29 (1984), pp. 42–50.
[72] L. X IAO AND S. B OYD, Optimal scaling of a gradient method for distributed resource allocation, Journal of
optimization theory and applications, 129 (2006), pp. 469–488.

