Decentralized Frank-Wolfe Algorithm for Convex and Non-convex
Problems

arXiv:1612.01216v2 [math.OC] 17 Mar 2017

Hoi-To Wai, Jean Lafond, Anna Scaglione, Eric Moulines

∗†

March 21, 2017

Abstract
Decentralized optimization algorithms have received much attention due to the recent advances in network information processing. However, conventional decentralized algorithms based
on projected gradient descent are incapable of handling high dimensional constrained problems,
as the projection step becomes computationally prohibitive to compute. To address this problem, this paper adopts a projection-free optimization approach, a.k.a. the Frank-Wolfe (FW) or
conditional gradient algorithm. We first develop a decentralized FW (DeFW) algorithm from
the classical FW algorithm. The convergence of the proposed algorithm is studied by viewing
the decentralized algorithm as an inexact FW algorithm. Using a diminishing step size rule
and letting t be the iteration number, we show that the DeFW algorithm’s convergence rate is
O(1/t) for convex objectives; is O(1/t2 ) for strongly√convex objectives with the optimal solution in the interior of the constraint set; and is O(1/ t) towards a stationary point for smooth
but non-convex objectives. We then show that a consensus-based DeFW algorithm meets the
above guarantees with two communication rounds per iteration. Furthermore, we demonstrate
the advantages of the proposed DeFW algorithm on low-complexity robust matrix completion
and communication efficient sparse learning. Numerical results on synthetic and real data are
presented to support our findings.

1

Introduction

Recently, algorithms for tackling high-dimensional optimizations have been sought for the ‘big-data’
challenge [3]. As these data/measurements are dispersed over clouds of networked machines, it is
important to consider decentralized algorithms that can allow the agents/machines to co-operate
and leverage the aggregated computation power [4].
This paper considers decentralized algorithm for tackling a constrained optimization problem
with N agents:
N
1 X
min F (θ) s.t. θ ∈ C, where F (θ) :=
fi (θ) ,
(1)
N
θ∈Rd
i=1

∗
The work of H.-T. Wai is supported by NSF CCF-1553746, NSF CCF-1531050 and J. Lafond by Direction
Générale de l’Armement and the labex LMH (ANR-11-LABX-0056-LMH). Preliminary versions of this work are
presented at ICASSP 2016 [1] and GlobalSIP 2016 [2].
†
H.-T. Wai and A. Scaglione are with the School of Electrical, Computer and Energy Engineering, Arizona State
University, Tempe, AZ 85281, USA. E-mails: {htwai,Anna.Scaglione}@asu.edu. J. Lafond was with Institut MinesTelecom, Telecom ParisTech, CNRS LTCI, Paris, France. Email: lafond.jean@gmail.com. E. Moulines is with
CMAP, Ecole Polytechnique, Palaiseau, France. Email: eric.moulines@polytechnique.edu.

1

and fi (θ) is a continuously differentiable (possibly non-convex) function held by the ith agent and
C is a closed and bounded convex set in Rd . Typically, the function fi (θ) models the loss function
over the private data held by agent i, and C corresponds to a regularization constraint imposed on
the optimization variable θ such as sparsity or low rank of an array of values. Problem (1) covers a
number of applications in control theory, signal processing and machine learning, including system
identification [5], matrix completion [6] and sparse learning [7, 8].
To tackle (1), the agents communicate on a network described as a graph G = (V, E), where
V = {1, ..., N } is the set of agents and E ⊆ V × V describes the connectivity. As G is not fully
connected, it is useful to apply decentralized algorithms that relies on near-neighbor information
exchanges. In light of this, various authors have proposed to tackle (1) through decentralized algorithms that are built on the average consensus protocol [9, 10]. For example, [11–18] studied the
decentralized gradient methods; [19, 20] considered the Newton-type methods; [21–25] considered
the decentralized primal-dual algorithms. [26, 27] are built on the successive convex approximation
framework. The convergence properties of these algorithms were investigated extensively, especially for convex objectives [4, 12–25]; for non-convex objectives, a few recent results can be found
in [11, 25–29]. However, most prior work are projection-based such that each iteration of the above
algorithms necessitates a projection step onto the constraint set C, or solving a sub-problem with
similar complexity. While the projection step entails a modest complexity for problems with moderate dimension, it may become computationally prohibitive for high dimensional problems, thereby
rendering the above methods impractical for our scenario of interest.
To address the issue above, this paper focuses on a decentralized projection-free algorithm. We
extend the Frank-Wolfe (FW) algorithm [30] to operate with near-neighbor information exchange,
leading to a decentralized FW (DeFW) algorithm. The FW (a.k.a. conditional gradient) algorithm
has been recently popularized due to its efficacy in handling high-dimensional constrained problems.
Examples of its applications include optimal control [31], matrix completion [32], image and video
colocation [33], electric vehicle charging [34] and traffic assignment [35]; see the overview article [36].
From the algorithmic perspective, the FW algorithm replaces the costly projection step in PG based
algorithms with a constrained linear optimization, which often admits an efficient solution. In a
centralized setting, the convergence of FW algorithm has been studied for convex problems [30,36],
yet little is known for non-convex problems [37–39].
Our contributions are as follows. We first describe abstractly the DeFW algorithm as a variation
of the FW algorithm with inexact iterates and gradients. We then analyze its convergence —
for convex objectives, the sub-optimality (of objective values) of the iterates produced by the
proposed algorithm is shown to converge as O(1/t) with t being the iteration number, and is
O(1/t2 ) for strongly convex objectives when the optimal solution is in the interior of C; for nonconvex objectives, we demonstrate that the proposed algorithm
has limit points that are stationary
p
points of (1), and they can be found at the rate of O( 1/t). We then show that a consensusbased implementation of the proposed algorithm with fixed number of communication rounds of
near-neighbor information exchanges achieves all the above guarantees. To our knowledge, this is
the first decentralized FW algorithm. Moreover, our convergence rate in the non-convex setting is
comparable to that of a centralized projected gradient method [40]. Lastly, we present examples
on communication-efficient LASSO and decentralized matrix completion.
The rest of this paper is organized as follows. Section 2 develops the DeFW algorithm. We summarize the main theoretical results of convergence for convex and non-convex objective functions.
A consensus-based implementation of the DeFW algorithm will then be presented in Section 3. Ap-

2

plications of the DeFW algorithm are discussed in Section 4. Finally, Section 5 presents numerical
results to support our findings.

1.1

Notations & Mathematical Preliminaries

For any d ∈ N, we define [d] as the set {1, ..., d}. We use boldfaced lower-case letters to denote
vectors and boldfaced upper-case letters to denote matrices. For a vector x (or a matrix X), the
notation [x]i (or [X]i,j ) denotes its ith element (or (i, j)th element). The vectorization of a matrix
X ∈ Rm1 ×m2 is denoted by vec(X) = [x1 ; x2 ; . . . ; xm2 ] ∈ Rm1 m2 such that xi is the ith column of
X. The vector ei ∈ Rd is the ith unit vector such that [ei ]j = 0 for all j 6= i and [ei ]i = 1. For some
positive finite constants C1 , C2 , C3 , C2 ≤ C3 and non-negative functions f (t), g(t), the notations
f (t) = O(g(t)), f (t) = Θ(g(t)) indicate f (t) ≤ C1 g(t), C2 g(t) ≤ f (t) ≤ C3 g(t) for sufficiently large
t, respectively.
Let E be a Euclidean space embedded in Rd and the Euclidean norm is denoted by k · k2 . The
binary operator h·, ·i denotes the inner product on E. In addition, E is equipped with a norm k · k
and the corresponding dual norm k · k? . Let G, L, µ be non-negative constants. Consider a function
f : Rd → R, the function f is G-Lipschitz if for all θ, θ 0 ∈ E,
|f (θ) − f (θ 0 )| ≤ Gkθ − θ 0 k ;

(2)

the function f is L-smooth if for all θ, θ 0 ∈ E,
f (θ) − f (θ 0 ) ≤ h∇f (θ 0 ), θ − θ 0 i +

L
kθ − θ 0 k22 ,
2

(3)

the above is equivalent to k∇f (θ 0 ) − ∇f (θ)k2 ≤ Lkθ 0 − θk2 ; the function f is µ-strongly convex if
for all θ, θ 0 ∈ E,
µ
(4)
f (θ) − f (θ 0 ) ≤ h∇f (θ), θ − θ 0 i − kθ − θ 0 k22 ;
2
moreover, f is convex if the above is satisfied with µ = 0.
Consider Problem (1), its constraint set C ⊆ E is convex and bounded with the diameter defined
as:
ρ := max
kθ − θ 0 k, ρ̄ := max
kθ − θ 0 k2 ,
(5)
0
0
θ,θ ∈C

θ,θ ∈C

note that ρ is defined with respect to (w.r.t.) the norm k · k while ρ̄ is defined w.r.t. the Euclidean
norm. When the objective function F is µ-strongly convex with µ > 0, the optimal solution to (1)
is unique and denoted by θ ? , we also define
δ := min ks − θ ? k2 ,
s∈∂C

(6)

where ∂C is the boundary set of C. If δ > 0, the solution θ ? is in the interior of C.

2

Decentralized Frank-Wolfe (DeFW)

We develop the decentralized Frank-Wolfe (DeFW) algorithm from the classical FW algorithm [30].
Let t ∈ N be the iteration number and the initial point θ0 ∈ C is feasible. Recall the definition

3

Algorithm 1 Decentralized Frank-Wolfe (DeFW).
1: Input: Initial point θ1i for i = 1, . . . , N .
2: for t = 1, 2, . . . do
3:
Consensus: approximate the average iterate:
θ̄ti ← NetAvgit ({θtj }N
j=1 ), ∀ i ∈ [N ] .
4:

Aggregating: approximate the average gradient:
∇it F ← NetAvgit ({∇fj (θ̄tj )}N
j=1 ), ∀ i ∈ [N ] .

5:

Frank-Wolfe Step: update
i
θt+1
← (1 − γt )θ̄ti + γt ait where ait ∈ arg minh∇it F , ai,
a∈C

for all agent i ∈ [N ] and γt ∈ (0, 1] is a step size.
end for
i , ∀ i ∈ [N ].
7: Return: θ̄t+1
6:

F (θ) := (1/N )

PN

i=1 fi (θ),

the centralized FW algorithm for problem (1) proceeds by:
at−1 ∈ arg min h∇F (θt−1 ), ai ,
a∈C

θt = θt−1 + γt−1 (at−1 − θt−1 ) ,

(7a)
(7b)

where γt−1 ∈ (0, 1] is a step size to be determined. Observe that θt is a convex combination of θt−1
and at−1 which are both feasible, therefore θt ∈ C as C is a convex set. When the step size is chosen
as γt = 2/(t + 1), the FW algorithm is known to converge at a rate of O(1/t) if F is L-smooth and
convex [36]. A main feature of the FW algorithm is that the linear optimization1 (LO) (7a) can be
solved more efficiently than computing a projection, leading to a projection-free algorithm. At the
end of this section, we will illustrate a few examples of C with efficient LO computations.
Our next endeavor is to extend the FW algorithm to a decentralized setting via mimicking
(7) with only near-neighbor information exchanges. Doing so requires replacing the centralized
gradient/iterate ∇F (θt ), θt in (7) with local approximations, as similar to the strategy in [14, 24].
In the following, we offer a high-level description of the proposed DeFW algorithm and discuss the convergence properties of it. Details regarding the implementation will be postponed to
Section 3. Let θti denotes an auxillary iterate kept by agent i at iteration t. Define the average
iterate:
P
i
θ̄t := N −1 N
(8)
i=1 θt
and the local iterate θ̄ti as an approximation of the average iterate above, also kept by agent i.
We require θ̄ti to track θ̄t with an increasing accuracy. Let {∆pt }t≥1 be a non-negative, decreasing
sequence with ∆pt → 0, we assume
1

Notice that (7a) is a convex optimization problem with a linear objective.

4

Assumption 1 ({∆pt }t≥1 ) For all t ≥ 1, it holds that
maxi∈[N ] kθ̄ti − θ̄t k2 ≤ ∆pt .

(9)

To compute (7a), ideally each agent has to access the global gradient, ∇F (θ̄t ). However, just the
local function fi (·) is available and agent i can only compute the local gradient ∇fi (θ̄ti ). Therefore,
we also need to track the average gradient,
P
j
∇t F := N −1 N
(10)
j=1 ∇fj (θ̄t ) ,
by the local approximation ∇it F . Note that ∇t F is close to ∇F (θ̄t ) when each of the function fi (θ)
is smooth and θ̄ti is close to θ̄t . Let {∆dt }t≥1 be a non-negative, decreasing sequence with ∆dt → 0,
we assume:
Assumption 2 ({∆dt }t≥1 ) For all t ≥ 1, it holds that
maxi∈[N ] k∇it F − ∇t F k2 ≤ ∆dt .

(11)

Naturally, from the local approximation ∇it F , the ith agent can compute the update direction
i
ait = arg mina∈C h∇it F , ai and update θt+1
similarly as in (7b). To summarize, a sketch of the
DeFW algorithm can be found in Algorithm 1.
Under Assumptions 1-2, for each agent i, line 5 in Algorithm 1 can be regarded as performing
an inexact FW update on θ̄t , whose convergence can be characterized below. For convex objective
functions, we have:
Theorem 1 Set the step size as γt = 2/(t + 1). Suppose that each of fi is convex and L-smooth.
Let Cp and Cg be two positive constants. Under Assumptions 1-2 [∆pt = Cp /t, ∆dt = Cg /t], we
have
8ρ̄(Cg + LCp ) + 2Lρ̄2
F (θ̄t ) − F (θ ? ) ≤
,
(12)
t+1
for all t ≥ 1, where θ ? is an optimal solution to (1). Furthermore, if F is µ-strongly convex and
the optimal solution θ ? lies in the interior of C, i.e., δ > 0 (cf. (6)), we have
F (θ̄t ) − F (θ ? ) ≤

(4ρ̄(Cg + LCp ) + Lρ̄2 )2
9
·
,
2
2δ µ
(t + 1)2

(13)

for all t ≥ 1.
The proof can be found in Appendix A. We remark that θ̄t is always feasible. For strongly convex
objective functions, the conditions (12), (13) imply that the sequence {θ̄t }t≥1 converges to an
optimal solution of (1). Furthermore, as the consensus error, maxi∈[N ] kθ̄ti − θ̄t k2 , decay to zero
(cf. Assumption 1), the local iterates {θ̄ti }t≥1 share similar convergence guarantee as {θ̄t }t≥1 .
For non-convex objective functions, we study the convergence of the FW/duality gap:
gt := maxh∇F (θ̄t ), θ̄t − θi .
θ∈C

(14)

From the definition, when gt = 0, the iterate θ̄t will be a stationary point to (1). Thus we may
regard gt as a measure of the stationarity of the iterate θ̄t . Also, define the set of stationary point
to (1) as:

C ? = θ ∈ C : max h∇F (θ), θ − θi = 0 .
(15)
θ∈C

We consider the following technical assumption:
5

Assumption 3 The set C ? is non-empty. Moreover, the function F (θ) takes a finite number of
values over C ? , i.e., the set F (C ? ) = {F (θ) : θ ∈ C ? } is finite.
Verifying Assumption 3 may be hard in practice. Meanwhile, it is reasonable to assume that (1)
has a finite number of stationary points since the set C is bounded. In the latter case, Assumption 3
is satisfied. We now have:
Theorem 2 Set the step size as γt = 1/tα for some α ∈ (0, 1]. Suppose each of fi is L-smooth and
G-Lipschitz (possibly non-convex). Let Cp , Cg be two positive constants. Under Assumption 1-2
[∆pt = Cp /tα , ∆dt = Cg /tα ], it holds that:
1. for all T ≥ 6 that are even, if α ∈ [0.5, 1),
min
t∈[T /2+1,T ]



gt ≤

1
T 1−α

·

1−α
·
(1 − (2/3)1−α )


2

(16)

Gρ + (Lρ̄ /2 + 2ρ̄(Cg + LCp )) log 2 ;

if α ∈ (0, 0.5),
min
t∈[T /2+1,T ]



gt ≤

1
1−α
·
·
α
T
(1 − (2/3)1−α )

(Lρ̄2 /2 + 2ρ̄(Cg + LCp ))(1 − (1/2)1−2α ) 
.
Gρ +
1 − 2α

(17)

2. additionally, under Assumption 3 and α ∈ (0.5, 1], the sequence of objective values {F (θ̄t )}t≥1
converges, {θ̄t }t≥1 has limit points and each limit point is in C ? .
The proof can
√ be found in Appendix B. Note that setting α = 0.5 gives the quickest convergence
rate of O(1/ T ). It is worth mentioning that our results are novel compared to prior work on
non-convex FW even in a centralized setting (N = 1, ∆pt = 0, ∆dt = 0). For instance, [37] requires
that the local minimizer is unique; [38] gives the same convergence rate but uses an adaptive step
size. We remark that the local iterates {θ̄ti }t≥1 share similar convergence property as {θ̄t }t≥1 due
to Assumption 1.
Lastly, we survey some relevant examples of the constraint set C where the LO in the DeFW
algorithm (cf. line 5 in Algorithm 1) can be computed efficiently:
1. When C is the `1 ball, C = {θ ∈ Rd : kθk1 ≤ R},
ait = −R · ek , where k ∈ arg max [∇it F ]j .

(18)

j∈[d]

The solution above amounts to finding the coordinate index of ∇it F with the maximum
magnitude. Importantly, this solution is only 1-sparse. Consequently, the tth iterate θ̄t will
be at most tN -sparse. The worst-case complexity of computing ait is O(d); in comparison,
the worst-case complexity for the projection into an `1 ball is O(d log d)2 .
2

There exists a randomized, accelerated algorithm for projection in [41] with an expected complexity of O(d).

6

2. When C is the trace norm ball, C = {θ ∈ Rm1 ×m2 : kθkσ,1 ≤ R}, where kθkσ,1 is the sum of
the singular values of θ. Let u1 , v1 be the top-1 left/right singular vector of ∇it F , we have
ait = −R · u1 v1> .

(19)

Importantly, at a target solution accuracy of δ, the top singular vectors can be computed with
a complexity of O(max{m1 , m2 } log(1/δ)) using the power/Lanczos method if kvec(∇it F )k0 =
O(max{m1 , m2 }). In comparison, the projection onto the trace norm ball requires a complexity of O(max{m1 m22 , m2 m21 } log(1/δ)) for computing the full SVD of an m1 × m2 matrix [42].
For more examples of C with efficient LO computations, the interested readers are referred
to [36] for an overview.

3

Consensus-based DeFW algorithm

This section demonstrates how an average consensus (AC) based scheme can generate local approximations θ̄ti , ∇it F at the desirable sub-linear accuracies (cf. Assumptions 1-2) using as few as two
communication rounds per iteration.
Specifically, the following discussions are based on the static AC [9, 10]. While the exact details
are left for a future work, we believe that it is possible to extend our protocol to a time varying
network’s setting. We consider an undirected graph G = (V, E) and assign a non-negative, sym×N
metric weighted adjacency matrix W ∈ RN
that describes the local communication between the
+
N agents. The matrix satisfies Wij := [W ]ij > 0 iff (i, j) ∈ E and it is doubly stochastic, i.e.,
W 1 = W > 1 = 1. Moreover,
Assumption 4 The second largest (in magnitude) eigenvalue of W is strictly less than one, i.e.,
|λ2 (W )| < 1.
The existence of such matrix W is guaranteed if G is connected. For each round of the AC update,
the agents take a weighted average of the values from its neighbors according to W . We now state
the following fact regarding W .
P
Fact 1 Let x1 , ..., xN ∈ Rd be a set of vectors and xavg := N −1 N
i=1 xi be their average. Suppose
W is a doubly stochastic, non-negative matrix. The output after performing one round of AC
update:
P
xi = N
(20)
j=1 Wij · xj
must satisfy
v
v
uN
uN
uX
uX
t
2
kxi − xavg k2 ≤ |λ2 (W )| · t
kxi − xavg k22 ,
i=1

(21)

i=1

where λ2 (W ) is the second largest eigenvalue of W .
The fact above can be verified from linear algebra. Together with Assumption 4, the above implies
that each AC update (20) moves the vectors closer to the average xavg . Repeatedly applying (21)
shows the well known fact that AC computes the average xavg at a linear rate.

7

Let us consider the near-neighbor computation of θ̄ti in line 3 of Algorithm 1. Here, the consensus
step is computed by:
P
j
θ̄ti = N
(22)
j=1 Wij · θt ,
i.e., we apply one round of the AC update. Since Wij = 0 if (i, j) ∈
/ E, the above operation is
achievable by information exchanges with the near-neighbors of agent i.
Now, for some α ∈ (0, 1], we define t0 (α) as the smallest integer such that
λ2 (W ) ≤

 t (α) α
1
0
·
.
t0 (α) + 1
1 + (t0 (α))−α

(23)

Notice that t0 (α) is upper bounded by:
t0 (α) ≤ d(|λ2 (W )|−1/(1+α) − 1)−1 e ,

(24)

which is finite under Assumption 4. The following lemma can be easily proven:
Lemma 1 Set the step size γt = 1/tα in the DeFW algorithm for some α ∈ (0, 1], then θ̄ti in (22)
satisfies Assumption 1:
maxi∈[N ] kθ̄ti − θ̄t k2 ≤ ∆pt = Cp /tα , ∀ t ≥ 1 ,
Cp := (t0 (α))α ·

(25)

√
N ρ̄ .

(26)

The proof is postponed to Appendix C, which relies on the observation that θti is a convex combii
i
nation of θ̄t−1
and ait−1 . In particular, θ̄t−1
is already O(1/(t − 1)α )-close to the network average
from the last iteration and the update direction ait−1 is weighted by a decaying step size γt−1 .
In comparison to what we were able to establish above, the near-neighbor computation of ∇it F
in line
algorithm is less straightforward. Unlike the computation of θ̄t , computing
P4N of the DeFW
i
α
i
−1
N
i=1 ∇fi (θ̄t ) to an accuracy of O(1/t ) by only communicating the local gradient ∇fi (θ̄t )
requires ∼ log t rounds of updates when the AC protocol is employed. The main issue is that the
local gradient ∇fi (θ̄ti ) computed by the ith agent is different from the local gradient computed at
the other agent, even when θ̄ti is close to θ̄tj for j 6= i.
We propose an approach that is inspired by the fast stochastic average gradient (SAGA) method
[43] which re-uses the gradient approximation ∇it−1 F from the last iteration3 . Define the following
surrogate of local gradient at iteration t:
i
∇it F := ∇it−1 F + ∇fi (θ̄ti ) − ∇fi (θ̄t−1
),

(27)

for all i ∈ [N ]. When t = 1, we set ∇i1 F = ∇fi (θ̄1i ). We now apply the AC update to the gradient
surrogate. In line 4 of Algorithm 1, the aggregating step is computed by:
P
j
∇it F = N
(28)
j=1 Wij · ∇t F ,
i.e., using just one round of AC update on ∇it F . Below we show that the average gradient is
preserved by ∇it F . Moreover, ∇it F has an approximation error similar to Lemma 1:
3

After the submission, the authors notice that a similar technique is adopted in [13, 18, 27] under the name of
‘gradient tracking’ for various decentralized methods. We provide a rate analysis with non-asymptotic constants.

8

Lemma 2 Set the step size γt = 1/tα in the DeFW algorithm for some α ∈ (0, 1]. Suppose that
each of fi is L-smooth, θ̄ti is updated according to (22), then ∇it F in (28) satisfies
P
PN
i
−1
i
N −1 N
(29)
i=1 ∇t F = N
i=1 ∇fi (θ̄t ), ∀ t ≥ 1 ,
and Assumption 2:
maxi∈[N ] k∇it F − ∇t F k2 ≤ ∆dt = Cg /tα , ∀ t ≥ 1 ,
√
Cg := (t0 (α))α · 2 N (2Cp + ρ̄)L .

(30)
(31)

The proof can be found in Appendix D. Similar intuition as in Lemma 1 was used in the proof. In
i ). The
particular, we observe that ∇tt F is a linear combination of ∇it−1 F and ∇fi (θ̄ti ) − ∇fi (θ̄t−1
former is O(1/(t − 1)α )-close to the average, and the latter decays to zero as enforced by the step
size γt .
Finally, the conditions on ∆pt , ∆dt necessitated by Theorem 1 & 2 can be satisfied by (22) &
(28).
Corollary 1 Under Assumption 4, the results in Theorem 1 & 2 hold when line 3, line 4 in the
DeFW algorithm (Algorithm 1) are computed by (22), (28) respectively.
In other words, the consensus-based DeFW algorithm converges for both convex and non-convex
problems, while using a constant number of communication rounds per iteration.
As a final remark, recall from Theorem 2 that for non-convex objectives, the best rate of
convergence can be achieved if we set α = 0.5. However, from Lemma 1 & 2, we notice that
the approximation error also decays the slowest when α = 0.5. This presents a potential tradeoff
in the choice of α. From our numerical experience, we find that setting α = 0.75 yields a good
performance in practice.

4

Applications

In this section, we study two applications of the DeFW algorithm to illustrate its flexibility and
efficacy.

4.1

Example I: Decentralized Matrix Completion

Consider a setting when the network of agents obtain incomplete observations of a matrix θtrue of
dimension m1 × m2 with m1 , m2  0. The ith agent has corrupted observations from the training
set Ωi ⊂ [m1 ] × [m2 ] that are expressed as:
Yk,l = [θtrue ]k,l + Zk,l , ∀ (k, l) ∈ Ωi .

(32)

To recover a low-rank θtrue , we consider the following trace-norm constrained matrix completion
(MC) problem:
N
X
X
min
f˜i ([θ]k,l , Yk,l ) s.t. kθkσ,1 ≤ R ,
(33)
θ∈Rm1 ×m2

i=1 (k,l)∈Ωi

where f˜i : R2 → R is a loss function picked by agent i according to the observations he/she received.
Notice that (33) is also related to the low rank subspace system identification problem described
9

in [5], where Y with [Y ]k,l = Yk,l , θtrue are modeled as the measured system response and the
ground truth low rank response; also see [44] for a related work.
Similar MC problems have been considered in [45–48], where [45] studied a consensus-based
optimization method similar to ours and [46–48] studied the parallel computation setting where
the agents are working synchronously in a fully connected network. Compared to our approach,
these work assume that the rank of θtrue is known in advance and solve the MC problem via matrix
factorization. In addition, [45,46] required that each local observation set Ωi only have entries taken
from a disjoint subset of the columns/rows only. Our approach does not have any restrictions above.
We consider two different observation models. When Zk,l is the i.i.d. Gaussian noise of variance
2
σi , we choose f˜i (·, ·) to be the square loss function, i.e.,
f˜i ([θ]k,l , Yk,l ) := (1/σi2 ) · (Yk,l − [θ]k,l )2 .

(34)

This yields the classical MC problem in [6]. The next model considers the sparse+low rank matrix
completion in [49], where the observations are contaminated with a sparse noise. Here, we model
Zk,l as a sparse noise in the sense that there are a few number of entries in Ωi where Zk,l is non-zero.
We choose f˜i (·, ·) to be the negated Gaussian loss, i.e.,

 ([θ] − Y )2 
k,l
k,l
f˜i ([θ]k,l , Yk,l ) := 1 − exp −
,
(35)
σi
where σi > 0 controls the robustness to outliers for the data obtained at the ith agent. Here, f˜i (·, ·)
is a smoothed `0 loss [50] with enhanced robustness to outliers in the data. Notice that the resultant
MC problem (33) is non-convex.
Note that (33) is a special case of problem (1) with C being the trace-norm ball. The consensusbased DeFW algorithm can be applied on (33) directly. The projection-free nature of the DeFW
algorithm leads to a low complexity implementation (33). Lastly, several remarks on the communication and storage cost of the DeFW algorithm are in order:
• The SAGA-like gradient surrogate ∇it F (27) is supported only on ∪N
i=1 Ωi since for all i ∈ [N ],
the local gradient
X
∇fi (θ̄ti ) =
(36)
f˜i0 ([θ̄ti ]k,l , Yk,l ) · ek (e0l )>
(k,l)∈Ωi

is supported on Ωi , where θ̄ti is defined in (22). In the above, ek (e0l ) is the kth (lth) canonical
basis vector for Rm1 (Rm2 ) and f˜i0 (θ, y) is the derivative of f˜i (θ, y) taken with respect to θ.
N
Consequently, the average ∇it F is supported only on ∪N
i=1 Ωi . As | ∪i=1 Ωi |  m1 m2 , the
amount of information exchanged during the aggregating step (Line 4 in DeFW) is low.
• The update direction ait is a rank-one matrix composed of the top singular vectors of ∇it F
(cf. (19)). Since every iteration in DeFW adds at most N distinct pair of singular vectors
to θ̄t , the rank of θ̄ti is upper bounded by tN if we initialize by θ̄0i = 0. We can reduce
the communication cost in Line 3 in DeFW by exchanging these singular vectors. Note that
(tN ) · (m1 + m2 ) entries are stored/exchanged instead of m1 · m2 .
• When the agents are only concerned with predicting the entries of θtrue in the subset Ξ ⊂
[m1 ] × [m2 ], instead of propagating the singular vectors as described above, the consensus
i
step can be carried out by exchanging only the entries of θt+1
in Ξ ∪ ∪N
i=1 Ωi without
affecting the operations
 of the DeFW algorithm. In this case, the storage/communication
cost is |Ξ ∪ ∪N
Ω
|.
i
i=1
10

4.2

Example II: Communication Efficient DeFW for LASSO

Let (yi , Ai ) be the available data tuple at agent i ∈ [N ] such that Ai ∈ Rm×d and yi ∈ Rm . The
data yi is a corrupted measurement of an unknown parameter θtrue :
yi = Ai θtrue + zi ,

(37)

N (0, σ 2 I)

where zi ∼
are independent noise vectors. Furthermore, we assume m  d such that the
>
matrix Ai Ai is rank-deficient. However, the parameter θtrue is s-sparse such that s = kθtrue k0  d.
This motivates us to consider the following distributed LASSO problem:
min

θ∈Rd

N
X
1
i=1

2

kyi − Ai θk22 s.t. kθk1 ≤ R ,

(38)

Notice that the above is a special case of (1) with fi (θ) = (1/2)kyi − Ai θk22 and C is an `1 -ball in
Rd with radius R. We assume that (38) has an optimal solution θ ? that is sparse. The settings
above also correspond to identifying a linear system described by a sparse parameter θtrue , where
Ai , yi are the input, output of the system, respectively; see [51] for a related formulation on the
identification of switched linear systems.
A number of decentralized algorithms are easily applicable to (38). For example, the decentralized projected gradient (DPG) algorithm in [15] is described by — at iteration t,
PN
PN
j,P G 
i,P G
j,P G
,
(39)
θt+1
= PC
− αt ∇fi
j=1 Wij θt
j=1 Wij θt
where αt ∈ (0, 1] is a diminishing step size and Wij is the weighted adjacency matrix described in
Section 3. For convex problems,
the DPG algorithm is shown to converge to an optimal solution
√
?
θ of (38) at a rate of O(1/ t) [12].
Let us focus on the communication efficiency of the DPG algorithm, which is important when
the network between agents is limited in bandwidth. To this end, we define the communication cost
as the number of non-zero real numbers exchanged per agent. As seen from (39), at each iteration
the ith agent exchanges its current iterate θti,P G with the neighboring agents. From the computation
step shown, θti,P G may contain as high as O(d) non-zeros and the per-iteration communication cost
will be O(d). Despite the high communication cost, the per-iteration computation complexity of
(39) is also high, i.e., at O(d log d) [41]. We notice that [7, 8] have considered distributed sparse
recovery algorithm with focus on the communication efficiency. However, their algorithms are based
on the iterative hard thresholding (IHT) formulation [52] that requires a-priori knowledge on the
sparsity level of θtrue . Our consensus-based DeFW algorithm in Section 3 may also be applied
directly to (38). However, similar issue as the DPG algorithm may arise during the aggregating
step, since the gradient surrogate (27) may also have O(d) non-zeros. Lastly, another related work
is [53] which applies coding to ‘compress’ the message exchanged in the consensus-based algorithms.
This section proposes a sparsified DeFW algorithm for solving (38). The modified algorithm
applies a novel ‘sparsification’ procedure to reduce communication cost during the iterations, which
is enabled by the structure of the DeFW algorithm. To describe the sparsified DeFW algorithm,
we first argue that the consensus step in the consensus-based DeFW should remain unchanged as it
already has a low communication cost. From (18) and (22), we see that θti is at most (t − 1)N + 1sparse since ait is always a 1-sparse vector4 (cf. (18)). As such, the communication cost of this step
is bounded by tN .
4

As pointed out by [36], this observation also leads to an interesting sparsity-accuracy trade-off when applying
FW on `1 constrained problems.

11

Our focus is to improve the communication efficiency of aggregating step. Here, the key idea is
that only the largest magnitude coordinate in ∇it F is sought when computing ait (cf. (18)). As long
as the largest magnitude coordinate in ∇it F is preserved, the updates in the DeFW algorithm can
remain unaffected. This motivates us to ‘sparsify’ the gradient information at each iteration before
exchanging them with the neighboring agents. Let Ωt ⊆ [d] be the coordinates of the gradient
information to be exchanged at iteration t. The agents exchange the following gradient surrogate
in lieu of (27):

P
d
i F := ∇f (θ̄ i )
∇
1Ωt , where 1Ωt = k∈Ωt ek ,
(40)
i t
t
and denotes the Hadamard/element-wise product.
Let `t = dCl + log(t)/ log |λ−1
2 (W )|e where Cl is some finite constant and λ2 (W ) is the second
largest eigenvalue of the weight matrix W , the sparsified DeFW algorithm computes the approximate gradient average ∇it F in line 4 of Algorithm 1 by:
∇it F =

PN

j=1 [W

`t ]
ij

[
· ∇jt F .

(41)

Note that (41) requires `t rounds of AC updates to be performed at iteration t, i.e., a logarithmically
increasing number of rounds of AC updates. The update direction ait can then be computed by
sorting the vector ∇it F . As ∇it F is |Ωt |-sparse, this update direction can be computed in O(|Ωt |)
time.
We pick the coordinate set Ωt in a decentralized manner. Consider the following decomposition:
S
(42)
Ωt = N
i=1 Ωt,i ,
where Ωt,i ⊂ [d] is picked by agent i at iteration t. The coordinate set Ωt needs to be known by
all agents before (41). This can be achieved with low communication overhead, e.g., by forming a
spanning tree on the graph G and broadcasting the required indices in Ωt to all agents; see [54].
Set pt as the maximum desirable cardinality of Ωt,i , agent i chooses the coordinate set using one of
the following two schemes:
• (Random coordinate) Each agent selects Ωt,i by picking pt coordinates uniformly (with replacement) from [d].
• (Extreme coordinate) Each agent selects Ωt,i as the pt largest magnitude coordinates of the
vector ∇fi (θ̄ti ).
For the random coordinate selection scheme, the following lemma shows that the gradient
approximation error can be controlled at a desirable rate with an appropriate choice of pt . Let
ξt := (1 − (1 − 1/d)pt N ), we have:
Lemma 3 Set  > 0 and `t = dCl + log(t)/ log |λ−1
2 (W )|e. Let pt ≥ C0 t for some C0 < ∞. With
2
probability at least 1 − π /6, the following holds for all θ ∈ C:
ξt−1 ∇it F

N
1 X
−
∇fi (θ̄ti )
N
i=1

for all t ≥ 1 and i ∈ [N ].
12

∞

 dplog(t2 /) 
=O
,
tN

(43)

The proof can be found in Appendix E. Note that the above is given in terms of ξt−1 ∇it F instead of
∇it F . However, the result remains relevant as the LO (7a) in the DeFW algorithm is scale invariant,
i.e., arg mina∈C h∇it F , ai = arg mina∈C hα∇it F , ai for any α > 0. In other words, performing the
FW stepPwith ∇it F is equivalent to doing so with ξt−1 ∇it F . As ξt−1 ∇it F is an O(1/t) approximation
j
to N −1 N
j=1 ∇fj (θ̄t ), Assumption 2 is satisfied with ∆dt = O(1/t). Lastly, we conclude that
Corollary 2 The sparsified DeFW algorithm using random coordinate selection, i.e., with line 3 &
4 in Algorithm 1 replaced by (22) & (41), respectively, generates iterates that satisfy the guarantees
in Theorem 1 (with high probability). Under strong convexity and interior optimal point assumption,
the communication complexity is O(N · (1/δ) · log(1/δ)) to reach a δ-optimal solution to (38).
In the above, the first statement is a consequence of Lemma 3.
√ The second statement can be verified
by noting that reaching a δ-optimal solution requires O(1/ δ) iterations and the communication
cost is O(N t log t) at iteration t, as the agents exchange an O(N t)-sparse vector for Θ(log t) times.

5

Numerical Experiments

We perform numerical experiments to verify our theoretical findings on the DeFW algorithm. The
following discussions will focus on the two applications described in Section 4 using synthetic and
real data. To simulate the decentralized optimization setting, we artificially construct a network
of N = 50 agents, where the underlying communication network G is an Erdos-Renyi graph with
connectivity of 0.1. For the AC steps (22), (28) & (41), the doubly stochastic matrix W is calculated
according to the Metropolis-Hastings rule in [55].

5.1

Decentralized Matrix Completion

This section considers the decentralized matrix completion problem, where the goal is to predict
missing entries of an unknown matrix through corrupted partial measurements. We consider two
datasets — the first dataset is synthetically generated where the unknown
matrix θtrue is rank-K
P
> /K where y , x have
y
x
and has dimensions of m1 × m2 ; the matrix is generated as θtrue = K
i
i
i
i
i=1
i.i.d. N (0, 1) entries and different settings of m1 , m2 , K will be experimented. The second dataset is
the movielens100k dataset [56]. The unknown matrix θtrue records the movie ratings of m1 = 943
users on m2 = 1682 movies; and a total of 105 entries in θtrue are available as integers ranging from
1 to 5. The datasets are divided into training and testing sets and the mean square error (MSE)
on the testing set is evaluated as:
P
2
(44)
MSE = |Ωtest |−1 (k,l)∈Ωtest [θtrue ]k,l − [θ̂]k,l ,
where θ̂ denotes the estimated θ produced by the algorithm.
For the synthetic dataset, the training (testing) set contains 20% (80%) entries which are selected
randomly. For movielens100k, the training (testing) set contains 80 × 103 (20 × 103 ) entries. The
training data of the two datasets are equally partitioned into N = 50 parts; for movielens100k,
each agent holds 1600 entries. We evaluate the performance of the proposed consensus-based DeFW
algorithm applied to square loss and negated Gaussian loss, as described in Section 4.1. Unless
otherwise specified, we fix the number of AC rounds applied at ` = 1 such that the agents only
exchange information once per iteration. As the negated Gaussian loss is non-convex, we set the
13

10-1
100

Test MSE

Objective value / Consensus Error

101

10-1
10-2
10-3

Sq. Loss Obj.

10-4 1
10

10-2

Obj. (Sq., DPG)
Obj. (Gau., Cen.)
Obj. (Sq., Cen.)
Obj. (Gau., DeFW)
Obj. (Sq., DeFW)
Consensus Err (Gau.)
Consensus Err (Sq.)
Duality (Gau., DeFW)

102

103

Iteration number

104

101

4000

6000

DPG w/ Sq. Loss
Gau. Loss (Cen.)
Sq. Loss (Cen.)
Gau. Loss (DeFW)
Sq. Loss (DeFW)
Qing et al.

102

103

8000

10000

Iteration number

104

101
100
10-1
10-2 0

DPG
DeFW
2000

Iteration number

Figure 1: Results on noiseless synthetic data with m1 = 100, m2 = 250 and rank K = 5. (TopLeft) Objective value and consensus error of θ̄ti against iteration number t, the objective values are
evaluated by F (θ̄t ). (Top-Right) Worst-case MSE (among agents) against iteration number on the
testing set. (Bottom) Objective value (sq. loss) against iteration number t for DeFW and DPG.
The legend ‘Gau.’, ‘Sq.’ denote the consensus-based DeFW algorithm applied to (33) with the
negated Gaussian and square loss, respectively.
step size as γt = t−0.75 . The centralized FW algorithm for both losses will also be compared (cf. (7));
as well as the decentralized algorithm
√ in [45] (labeled as ‘Qing et al.’) and the DPG algorithm [15]
with step size set to αt = 0.1N/( t + 1) applied to square loss.
Our first example considers the noiseless synthetic dataset of problem dimension m1 = 100, m2 =
250, K = 5. The results are shown in Fig. 1. Here, for the DeFW/DPG algorithms, we set the
trace-norm radius to R = 1.2kθtrue kσ,1 ; and the algorithm in [45] is supplied with the true rank K
of θtrue . Notice that for this set of data, the minimum of (33) can be achieved by θ = θtrue ∈ C
with a zero objective value. From the top-left plot, for the DeFW algorithm applied to the convex
square loss function, we observe an O(1/t2 ) trend for the objective values, corroborating with our
analysis in Theorem 1; for the non-convex negated Gaussian loss function, the objective value and
the FW/duality gap gt also decay with t, the latter indicates the convergence to a stationary point.
Moreover, the consensus error of θ̄ti for DeFW applied to the two objective functions decay at the

14

Objective value

700
600

0.25

10-1

0.20

30
10

100

500

10-2
10-3

400
0

50

104

Obj. (Sq., DPG)
Obj. (Gau., Cen.)
103
Obj. (Sq., Cen.)
Obj. (Gau., DeFW)
102
Obj. (Sq., DeFW)
Consensus Err (Gau.) 1
Consensus Err (Sq.) 10
Duality (Gau., DeFW)

Consensus Err/Duality gap
Test MSE

800

0.15
0.10

10-4

0.050

10-5
1000 2000 3000 4000 5000

Iteration number

DPG w/ Sq. Loss
Gau. Loss (Cen.)
Sq. Loss (Cen.)
Gau. Loss (DeFW)
Square Loss (DeFW)
Qing et al.

1000 2000 3000 4000 5000

Iteration number

Figure 2: Results on sparse-noise contaminated synthetic data with m1 = 100, m2 = 250 and rank
K = 5. (Left) Objective value and consensus error of θ̄ti against the DeFW iteration number t.
Notice that the consensus error (in purple and yellow) / duality gap (in black) are plotted in a
logarithmic scale (cf. the right y-axis) while the objective values are plotted in a linear scale; (Right)
MSE against the DeFW iteration number t on the testing set.
rate predicted by Lemma 1. On the other hand, the top-right plot compares mean square error
(MSE) of the predicted matrix θ for the testing set. Here, we also compare the result with the
algorithm in [45]. We observe that the MSE performance of the DeFW algorithms approach their
centralized counterpart as the iteration number grows, yet the algorithm in [45] achieves the best
performance in this setting, notice that the true rank of θtrue is provided to this algorithm. From
the bottom plot, the DPG method applied to square loss function converges at a relatively fast
rate in the beginning, but was overtaken by DeFW as the iteration number grows. It is worth
mentioning that the DeFW algorithms have a consistently better MSE performance than DPG.
The second example considers adding noise to the observations for the same synthetic data case
in Fig. 1. In particular, we adopt the same setting as the previous example but include a sparse
noise in the observations — here, each Zk,l = pk,l · Z̃k,l where pk,l is Bernoulli with P (pk,l = 1) = 0.2
and Z̃k,l ∼ N (0, 5) (cf. (32)). The convergence results are compared in Fig. 2. For the left plot,
we observe similar convergence behaviors for the DeFW algorithms applied to different objective
functions as in the previous example. On the right plot, we observe that the DeFW algorithm
based on negated Gaussian loss achieves the lowest MSE, demonstrating its robustness to outlier
noise. We also see that the algorithm in [45] performs poorly on this dataset.
Another interesting discovery is that the algorithm in [45] seems to fail when the rank of θtrue is
high, even when the true rank is known and the observations are noiseless. In Fig. 3, we show the
MSE against iteration number of the algorithms when the synthetic data is noiseless and generated
with m1 = 100, m2 = 250, K = 10. As seen, [45] fails to produce a low MSE, while DeFW offers a
reasonable performance.
The next example evaluates the objective value and test MSE on synthetic, noiseless data
against the average runtime per agent. We focus on comparing the DeFW and DPG algorithms.
15

DPG w/ Sq. Loss
Gaussian Loss (Cen.)
Square Loss (Cen.)
Gaussian Loss (DeFW)
Square Loss (DeFW)
Qing et al.

Test MSE

0.20
0.15
0.10
0.05
0

1000

2000

3000

Iteration number

4000

5000

102
101

Test MSE

Objective value

Figure 3: Convergence of test MSE against iteration number on the testing set on noise-free synthetic data with m1 = 100, m2 = 250 and rank K = 10.

100
10-1
10-2 0

Sq. loss, DPG
Sq. loss, DeFW
50 100 150

Running Time (s)

200

0.30
0.25
0.20
0.15
0.10
0.05
0.000

Sq. loss, DPG
Sq. loss, DeFW
Gau. loss, DeFW

50

100

150

Running Time (s)

200

Figure 4: Results on noiseless synthetic data with m1 = 200, m2 = 1000 and rank K = 5. (Left)
Objective value against running time. (Right) Worst-case MSE (among agents) against running
time.
In Fig. 4, DeFW demonstrates a significant advantage over DPG since the former does not require
the projection computation. In fact, the average running time per iteration of DeFW is five times
faster than DPG. We also expect the complexity advantages to widen as the problem size grows.
Lastly, we consider the dataset movielens100k. We set R = 105 and focus on the test MSE
evaluated against the iteration number for the proposed DeFW algorithm. The numerical results
are presented in Fig. 5, where we also compare the case when we apply multiple (` = 1, 3) rounds of
AC updates per iteration to speed up the algorithm. The left plot in Fig. 5 considers the noiseless
scenario. As seen, the proposed DeFW algorithm applied on different loss functions converge to a
reasonable MSE that is attained by the centralized FW algorithm. We see that the DeFW with
negated Gaussian loss has a slower convergence compared to the square loss which is possibly
attributed to the non-convexity of the loss function. Moreover, the algorithms achieve much faster
convergence if we allow ` = 3 AC rounds of network information exchange per iteration. The right
plot in Fig. 5 considers when the observations are contaminated with a sparse noise of the same
model as Fig. 2. We observe that the negated Gaussian loss implementations attain the best MSE
as the non-convex loss is more robust against the sparse noise. Interestingly, the DeFW algorithm
with ` = 3 AC rounds has even outperformed its centralized counterpart. We suspect that this is
caused by the DeFW algorithm converging to a different local minima for the non-convex problem.

16

100

3.5

10-1

Duality / Consensus Error

4.0

Test MSE

3.0
2.5
2.0
1.5
1.0
0

2000 4000 6000 8000 10000

Iteration number

10-3
10-4
10-5
10-6 0
100

3.5

10-1

Duality / Consensus Error

4.0

3.0

Test MSE

10-2

2.5
2.0
1.5
1.0
0

2000 4000 6000 8000 10000

Iteration number

Gau. Loss (Cen.)
Sq. Loss (Cen.)
Gau. Loss (DeFW, 1AC)
Sq. Loss (DeFW, 1AC)

2000 4000 6000 8000 10000

Iteration Number

10-2
10-3
10-4
10-5
10-6 0

Gau. Loss (DeFW., 3AC)
Sq. Loss (DeFW, 3AC)
Duality gap (1AC)
Duality gap (3AC)

2000 4000 6000 8000 10000

Iteration Number

Consensus Err. (Gau., 1AC)
Consensus Err. (Gau., 3AC)
Consensus Err. (Sq., 1AC)
Consensus Err. (Sq., 3AC)

Figure 5: Convergence of the DeFW algorithm on movielens100k. (Top) Noiseless observations;
(Bottom) sparse-noise contaminated observations. Note that the duality gap and consensus error
are drawn in a logarithmic scale in the right plots.

5.2

Communication-efficient LASSO

This section conducts numerical experiments on the decentralized sparse learning problem. We
focus on the sparsified DeFW algorithm in Section 4.2 that has better communication efficiency.
We evaluate the performance on both synthetic and benchmark data. For the synthetic data, we
randomly generate each Ai as a (m = 20)×(d = 10000) matrix with N (0, 1) elements (cf. (37)) and
θtrue is a random sparse vector with kθtrue k0 = 50 such that the non-zero elements are also N (0, 1).
The observation noise zi has a variance of σ 2 = 0.01. For benchmark data, we test our method on

17

105

103
102
101
100

DeFW (extreme)
DeFW (rand)
DPG
PG-EXTRA
BHT

105

Objective value

104

Objective value

106

DeFW (extreme)
DeFW (rand)
DPG
PG-EXTRA
BHT

104
103
102
101

200

400

600

800

Iteration number

1000

100 4
10

105

106

Communication Cost

107

Figure 6: Convergence of the objective value on LASSO with synthetic dataset. (Left) against the
iteration number. (Right) against the communication cost (i.e., total number of values transmitted/received in the network during AC updates). In the legend, ‘DeFW (extreme)’ refers to the
extreme coordinate selection and ‘DeFW (rand)’ refers to the random coordinate selection scheme.
sparco7 [57], which is a commonly used dataset for benchmarking sparse recovery algorithms. For
sparco7, we have Ai ∈ R12×2560 as the local measurement matrix and θtrue is a sparse vector with
kθtrue k0 = 20.
The sparsified DeFW algorithm is implemented with pt = d2 + αcomm · te, `t = dlog(t) + 1e with
extreme or random coordinate selection. We compare the algorithms of PG-EXTRA [16] (with
fixed step size α = 1/d), DPG [15] (with step size αt = 1/t) and BHT [7]. DeFW, PG-EXTRA
and DPG are set to solve the convex problem (38) with R = 1.1kθtrue k1 . BHT is a communication
efficient decentralized version of IHT and is supplied with the true sparsity level in our simulations.
The first example in Fig. 6 shows the convergence of the algorithms on the synthetic data, where
we compare the objective value against the number of iterations and the communication cost, i.e.,
total number of values sent during the distributed optimization. We set αcomm = 0.05 for the DeFW
algorithms. From the left plot, we observe that DeFW and PG-EXTRA algorithms have similar
iteration complexity while ‘DeFW (rand)’ seems to have the fastest convergence. Meanwhile, BHT
demands a high number of iterations for convergence. On the other hand, in the right plot, the
DeFW algorithms demonstrate the best communication efficiency at low accuracy, while they lose
to BHT at higher accuracy. Lastly, ‘DeFW (extreme)’ achieves a better accuracy at the beginning
(i.e., less communication cost paid) but is overtaken by ‘DeFW (rand)’ as the communication cost
grows.
We then compare the performance on sparco7, where we show the convergence of objective
value against the communication cost in Fig. 7. We set αcomm = 0.025 for the sparsified DeFW
algorithms. At low accuracy, the DeFW algorithms offer the best communication cost-accuracy
trade-off, i.e., it performs the best at an accuracy of above ∼ 10−2 . Moreover, ‘DeFW (extreme)’
seems to be perform better than ‘DeFW (rand)’ in this example. Nevertheless, the BHT algorithm
18

Objective value

10-1
10-2
10-3
104

DeFW (extreme)
DeFW (rand)
DPG
PG-EXTRA
BHT

105
106
Communication Cost

Figure 7: Convergence of the objective value against the communication cost on LASSO with
sparco7 dataset. In the legend, ‘DeFW (extreme)’ refers to the extreme coordinate selection and
‘DeFW (rand)’ refers to the random coordinate selection scheme.
achieves the best performance when the communication cost paid is above 3 × 105 . Lastly, we
comment that although BHT has the lowest communication cost at high accuracy, its computational
complexity is high as the former requires a large number of iterations to reach a reasonable accuracy
(cf. left plot of Fig. 6). The sparsified DeFW offers a better balance of the communication and
computation complexity.

6

Conclusions & Open Problems

In this paper, we have studied a decentralized projection-free algorithm for constrained optimization, which we called the DeFW algorithm. Importantly, we showed that the DeFW algorithm
converges for both convex and non-convex loss functions and the respective convergence rates are
analyzed. The efficacy of the proposed algorithm is demonstrated through tackling two problems related to machine learning, with the advantages over previous state-of-the-art demonstrated through
numerical experiments. Future directions of study include developing an asynchronous version of
the DeFW algorithm.

7

Acknowledgement

The authors would like to thank the anonymous reviewers for providing constructive comments on
our paper.

A

Proof of Theorem 1

The proof of Theorem 1 follows from our recent analysis on online/stochastic FW algorithm [39].
Using line 5 of Algorithm 1, we observe that:
P
i
θ̄t+1 = θ̄t + γt (N −1 N
(45)
i=1 at − θ̄t ) .

19

Define ht := F (θ̄t ) − F (θ ? ) where θ ? is an optimal solution to (1). From the L-smoothness of F
and the boundedness of C, we have:
ht+1

N
γt X i
Lρ̄2
≤ ht +
hat − θ̄t , ∇F (θ̄t )i + γt2
,
N
2

(46)

i=1

where ρ̄ was defined in (5). Observe the following chain for the inner product: for each i ∈ [N ], we
have
hait − θ̄t , ∇F (θ̄t )i ≤ hait − θ̄t , ∇it F i + ρ̄k∇it F − ∇F (θ̄t )k2
≤ ha − θ̄t , ∇it F i + ρ̄ · k∇it F − ∇F (θ̄t )k2 , ∀ a ∈ C

(47)

≤ ha − θ̄t , ∇F (θ̄t )i + 2ρ̄ · k∇it F − ∇F (θ̄t )k2 , ∀ a ∈ C,
and used the fact ait ∈ arg mina∈C ha, ∇it F i
where we have added and subtracted ∇it F in the first inequality;
P
i
in the second inequality. Recalling that ∇t F = N −1 N
i=1 ∇fi (θ̄t ),
k∇it F − ∇F (θ̄t )k2
≤ k∇it F − ∇t F k2 + k∇t F − ∇F (θ̄t )k2
P
i
≤ ∆dt + N −1 N
i=1 k∇fi (θ̄t ) − ∇fi (θ̄t )k2
P
i
≤ ∆dt + L · N −1 N
i=1 kθ̄t − θ̄t k2

(48)

≤ ∆dt + L · ∆pt ,
where the third inequality is due to the L-smoothness of {fi }N
i=1 . Recalling that ∆pt = Cp /t,
∆dt = Cg /t and substituting the results above into the inequality (46) implies:
ht+1 ≤ ht + γt hāt − θ̄t , ∇F (θ̄t )i + γt2

Cg + LCp
Lρ̄2
+ 2ρ̄γt
,
2
t

(49)

where āt ∈ C is the minimizer of the linear optimization (7a) using ∇F (θ̄t ), i.e.,
āt ∈ arg minha, ∇F (θ̄t )i .
a∈C

(50)

Case 1: When F is convex, we observe
hāt − θ̄t , ∇F (θ̄t )i ≤ hθ ? − θ̄t , ∇F (θ̄t )i ≤ −ht ,

(51)

where the first inequality is due to the optimality of āt and the last inequality stems from the
convexity of F . Plugging the above into (49) yields
ht+1 ≤ (1 − γt )ht + γt2

2ρ̄(Cg + LCp )
Lρ̄2
+ γt
.
2
t

(52)

As γt = 2/(t + 1), from a high-level point of view, the above inequality behaves similarly to
ht+1 ≤ (1 − (1/t))ht + O(1/t2 ). Consequently, applying [58, Lemma 4] yields a O(1/t) convergence
rate for ht . In fact, this is a deterministic version of the case analyzed by [39, Theorem 10]. In
particular, setting α = 1, K = 2 in [39, (56)] and using an induction argument yield
ht ≤ 2 · (4ρ̄(Cg + LCp ) + Lρ̄2 )/(t + 1), ∀ t ≥ 1 .
20

(53)

Case 2: For the case when F is µ-strongly convex and θ ? lies in the interior of C with distance
δ > 0 (cf. (6)). Using [39, Lemma 6], we have
p
hθ̄t − āt , ∇F (θ̄t )i ≥ 2µδ 2 ht .
(54)
Plugging the above into (49) gives
ht+1 ≤

p
p p
2ρ̄(Cg + LCp )
Lρ̄2
ht ( ht − γt 2µδ 2 ) + γt2
+ γt
.
2
t

(55)

Compared to the case analyzed in (52), when ht is decreased, the decrement in ht+1 is increased,
leading to a faster convergence. This is a deterministic version of the case analyzed in [39, Theorem 7]. Setting α = 1, K = 2 in [39, (48)] and using an induction argument yields
ht ≤

B
B.1

(4ρ̄(Cg + LCp ) + Lρ̄2 )2
9
·
, ∀t≥1.
2
2δ µ
(t + 1)2

(56)

Proof of Theorem 2
Convergence rate

Let us recall the definition of the FW gap:
gt := max h∇F (θ̄t ), θ̄t − θi = h∇F (θ̄t ), θ̄t − āt i ,
θ∈C

(57)

where we have used the definition of āt in (50) from the previous proof. For simplicity, we shall
assume that T is an even integer in the following.
From the L-smoothness of F , we have:
F (θ̄t+1 ) ≤ F (θ̄t ) + h∇F (θ̄t ), θ̄t+1 − θ̄t i +

L
kθ̄t+1 − θ̄t k22 .
2

(58)

Observe that:
θ̄t+1 − θ̄t = N −1

PN

t
i=1 γt (ai

− θ̄ti ) .

(59)

As ait , θ̄ti ∈ C, we have kθ̄t+1 − θ̄t k2 ≤ γt ρ̄. Using (47) and (48) from the previous proof of
Theorem 1, the inequality (58) can be bounded as:
F (θ̄t+1 ) ≤ F (θ̄t ) − γt h∇F (θ̄t ), θ̄t − āt i
+ 2γt ρ̄ · (∆dt + L · ∆pt ) + γt2 Lρ̄2 /2
= F (θ̄t ) − γt gt + 2γt ρ̄ · (∆dt + L · ∆pt ) +

(60)

Lρ̄2
γt2
2

.

From the definition, we observe that gt ≥ 0. Now, summing the two sides of (60) from t = T /2 + 1
to t = T gives:
T
X

γt gt ≤

t=T /2+1

+

T
X



F (θ̄t ) − F (θ̄t+1 )



t=T /2+1
T
X

t=T /2+1



(61)

Lρ̄2 
2γt ρ̄ · (∆dt + L · ∆pt ) + γt2
.
2
21

Canceling duplicated terms in the first term of the right hand side above gives:
T
X

γt gt ≤ F (θ̄T /2+1 ) − F (θ̄T +1 )

t=T /2+1

(62)

T
X

+

Lρ̄2 
.
2γt ρ̄ · (∆dt + L · ∆pt ) + γt2
2

t=T /2+1

As gt , γt ≥ 0, we can lower bound the left hand side as:
T
X



γt gt ≥

min
t∈[T /2+1,T ]

t=T /2+1

 
gt ·

T
X


γt ,

(63)

t=T /2+1

and observe that for all T ≥ 6 and α ∈ (0, 1),
T
X

γt ≥

t=T /2+1

 2 1−α 
T 1−α 
· 1−
= Ω(T 1−α ) .
1−α
3

(64)

Define the constant C := Lρ̄2 /2 + 2ρ̄(Cg + LCp ). When α ≥ 0.5, using the fact that γt = t−α ,
∆pt = Cp /tα , ∆dt = Cg /tα , the right hand side of (62) is bounded above by:
G·ρ+C ·

PT

−2α
t=T /2+1 t

≤ G · ρ + C · log 2 ,

(65)

note that the series is converging as wePare summing from t = T /2 + 1 to t = T . Dividing the
above term by the lower bound (64) to Tt=T /2+1 γt yields (16).
On the other hand, when α < 0.5, we notice that
T
X

t−2α ≤

t=T /2+1

Z

T

t−2α dt =

T /2

21−2α − 1  T 1−2α
.
1 − 2α
2

(66)

Therefore, the right hand side of (62) is bounded above by
Gρ + C

T
X
t=T /2+1


1 − (1/2)1−2α  1−2α
·T
.
t−2α ≤ Gρ + C
1 − 2α

Dividing the above term by the lower bound (64) to

B.2

PT

t=T /2+1 γt

(67)

yields (17).

Convergence to stationary point of (1)

Recall that the set of stationary points to (1) is defined as:
C ? := {θ̄ ∈ C : maxθ∈C h∇F (θ̄), θ̄ − θi = 0} .
We state the following Nurminskii’s sufficient condition:

22

(68)

Theorem 3 [59, Theorem 1] Consider a sequence {θ̄t }t≥1 in a compact set C. Suppose that the
following hold5 :
A.1 limt→∞ kθ̄t+1 − θ̄t k = 0.
A.2 Let θ be a limit point of {θ̄t }t≥1 and {θst }t≥1 be a subsequence that converges to θ. If θ ∈
/ C?,
then for any t and some sufficiently small  > 0, there exists a finite s such that kθ̄s − θ̄st k > 
and s > st .
A.3 Let θ be a limit point of {θ̄t }t≥1 and {θst }t≥1 be a subsequence that converges to θ. If θ ∈
/ C?,
then for any t and some sufficiently small  > 0, we can define
τt := min s s.t. kθ̄s − θ̄st k > 
s>st

(69)

where τt is finite. Also, there exists a continuous function W (θ̄) that takes a finite number
of values in C ? with
lim sup W (θ̄τt ) < lim W (θ̄st ) .
(70)
t→∞

t→∞

Then the sequence {W (θ̄t )}t≥1 converges and the limit points of the sequence {θ̄t }t≥1 belongs to the
set C ? .
We apply the above theorem to prove that every limit point of {θ̄t }t≥1 are in C ? . First, A.1 can
be easily verified since
N
γt X i
γt ρ̄
kθ̄t+1 − θ̄t k ≤
(71)
kat − θ̄t k ≤
N
N
i=1

and we have γt → 0 as t → ∞.
As C is compact, there exists a convergent subsequence {θ̄st }t≥1 of the sequence of iterates
generated by the DeFW algorithm. Let θ be the limit point of {θ̄st }t≥1 and θ ∈
/ C ? . We shall verify
A.2 by contradiction. In particular, fix a sufficiently small  > 0 and assume that the following
holds:
kθ̄s − θ̄st k ≤ , ∀ s > st , ∀ t ≥ 1 .
(72)
As {θ̄st }t≥1 converges to θ, the assumption (72) implies that for some sufficiently large t and any
s > st , we have θ̄s ∈ B2 (θ), i.e., the ball of radius 2 centered at θ.
Since θ ∈
/ C ? , the following holds for some δ > 0,
h∇F (θ̄s ), θ − θ̄s i ≤ −δ < 0, ∀ θ ∈ C, ∀s > st .

(73)

In particular, we have h∇F (θ̄s ), ās − θ̄s i ≤ −δ as we recall that ās = arg mina∈C h∇F (θ̄s ), ai.
On the other hand, from (60) and using Assumptions 1-2, it holds true for all t ≥ 1 that:
F (θ̄t+1 ) − F (θ̄t ) ≤ γt · h∇F (θ̄t ), āt − θ̄t i
+ γt · O(t−α ) + γt2 Lρ̄2 /2 .
5

(74)

To give a clearer presentation, we have rephrased conditions A.2 and A.3 from the original Nurminskii’s conditions.

23

To arrive at a contradiction, we let s > st and sum up the two sides of (74) from t = st to t = s.
Consider the following chain of inequality:
F (θ̄s ) − F (θ̄st ) ≤

s
X

γ` (∇F (θ̄` ), ā` − θ̄` i + O(`−α ))

`=st

≤ −δ

s
X

γ` +

`=st

s
X

(75)
−α

γ` O(`

),

`=st

where the first inequality is due to the fact that γ`2 Lρ̄2 /2 = γ` O(`−α ) and the second inequality is
due to (73). Rearranging terms in (75), we have
F (θ̄s ) − F (θ̄st ) −

s
X

C ·`

−2α

`=st

≤ −δ

s
X

`−α ,

(76)

`=st

P
for somePC < ∞. As 1 ≥ α > 0.5, we have lims→∞ s`=st `−2α < ∞ on the left hand side and
lims→∞ s`=st `−α → +∞ on the right hand side. Letting s → ∞ on the both side of (76) implies
lim F (θ̄s ) − F (θ̄st ) < −∞ ,

(77)

s→∞

This leads to a contradiction to (73) since F (θ) is bounded over C. We conclude that A.2 holds for
the DeFW algorithm.
The remaining task is to verify A.3. We notice that the indices τt in (69) are well defined since
A.2 holds. Take W (θ) = F (θ) and notice that the image F (C ? ) is a finite set (cf. Assumption 3).
By the definition of τt , we have θ̄s ∈ B (θ̄st ) for all st ≤ s ≤ τt − 1. Again for some sufficiently
large t, we have θ̄s ∈ B (θ̄st ) ⊆ B2 (θ) and the inequality (75) holds for s = τt − 1. This gives:
F (θ̄τt ) − F (θ̄st ) ≤

τX
t −1

γ` · (−δ + O(`−α )) .

(78)

`=st

On the other hand, we have θ̄τt ∈
/ B (θ̄st ) and thus
 < kθ̄τt − θ̄st k ≤

τX
t −1
`=st

γ`

N
X
ai

`

i=1

N

− θ̄` ≤ ρ̄

τX
t −1

γ` .

(79)

`=st

P t −1
The above implies that τ`=s
γ` > /ρ̄ > 0. Considering (78) again, observe that O(`−α ) decays
t
to zero, for some sufficiently large t, we have −δ + O(`−α ) ≤ −δ 0 < 0 if ` ≥ st . Therefore, (78)
leads to
τX
t −1
δ0
F (θ̄τt ) − F (θ̄st ) ≤ −δ 0
<0.
(80)
γ` < −
ρ̄
`=st

Taking the limit t → ∞ on both sides leads to (70). The proof for the convergence to stationary
point in Theorem 2 is completed by applying Theorem 3.

24

C

Proof of Lemma 1

For simplicity, we shall drop the dependence of α in the constant t0 (α). It suffices to show that for
all t ≥ 1,
v
uN
uX
√
Cp
t
(81)
kθ̄ti − θ̄t k22 ≤ α , Cp = (t0 )α · N ρ̄ .
t
i=1

i
We observe that for t = 1 to t = t0 , the above inequality is true since
qPθ̄t , θ̄t ∈ C and the diameter
N
α
i
2
of C is bounded by ρ̄. For the induction step, let us assume that
i=1 kθ̄t − θ̄t k ≤ Cp /t for
some t ≥ t0 . Observe that
i
θt+1
= (1 − t−α )θ̄ti + t−α ait .
(82)
P
i
Denote ãt = N −1 N
i=1 at and using Fact 1, we observe that,
N
X

i
kθ̄t+1
− θ̄t+1 k22 ≤

i=1

|λ2 (W )|2 ·

N
X

(83)
k(1 −

t−α )(θ̄tj

− θ̄t ) +

t−α (ajt

− ãt )k22 ,

j=1

where we have used the fact θ̄t+1 = (1 − t−α )θ̄t + t−α ãt . The right hand side in the above can be
bounded by
N
X

k(1 − t−α )(θ̄tj − θ̄t ) + t−α (ajt − ãt )k22

j=1

≤

N
X

kθ̄tj − θ̄t k22 + t−2α ρ̄2 + 2ρ̄t−α kθ̄tj − θ̄t k2



j=1

(84)

v
uN
uX j
√
−2α
2
2
−α
≤t
(Cp + N ρ̄ ) + 2ρ̄t
Nt
kθ̄t − θ̄t k22
j=1

≤ t−2α (Cp +

√

 (t )α + 1
2
0
N ρ̄)2 ≤
·
C
,
p
(t0 )α · tα

P
where we have used the boundedness of C in the first inequality, the norm equivalence N
j=1 |cj | ≤
q
√
PN 2
N
j=1 cj in the second inequality and the induction hypothesis in the third and fourth inequalities. Consequently, from (23), we observe that for all t ≥ t0 ,
|λ2 (W )| ·

(t0 )α + 1
1
≤
,
α
α
(t0 ) · t
(t + 1)α

(85)

and the induction step is completed. Finally, Lemma 1 is proven by observing that (81) implies
(25).

25

D

Proof of Lemma 2

We prove the first condition (29) with a simple induction. This condition is obviously true for the
base step t = 1. For induction step, suppose that (29) is true up to some t, then
N
X

∇it+1 F =

i=1

N
X

(∇it F − ∇fi (θ̄ti )) +

N
X

i
∇fi (θ̄t+1
).

(86)

i=1

i=1

Note that the first term on the right hand
is zero due
hypothesis. Thus, the
P side
PNto the induction
i F = N −1
i ) for all t ≥ 1.
induction step is completed and N −1 N
∇
∇f
(
θ̄
i t
i=1 t
i=1
Then, we prove the second condition
(30).
For
simplicity,
we
drop the dependence of α in the
P
i F . It suffices to prove:
constant t0 (α). Recall ∇t F := N −1 N
∇
i=1 t
v
uN
uX
√
Cg
t
(87)
k∇it F − ∇t F k22 ≤ α , Cg = 2 N (t0 )α (2Cp + ρ̄)L
t
i=1

for all t ≥ 1 using induction. For t = 1 to t = t0 , the inequality can be
qeasily proven using the
PN
i
2
boundedness of the gradients. For the induction step, we suppose that
i=1 k∇t F − ∇t F k2 ≤
i
i ) − ∇f (θ̄ i ). We observe that
:= ∇fi (θ̄t+1
Cg /tα for some t ≥ t0 . Define the slack variable δft+1
i t
P
j
N
i
i
i
i
∇t+1 F = δft+1 + ∇t F and ∇t+1 F = j=1 Wij ∇t+1 F , thus applying Fact 1 yields
N
X

k∇it+1 F − ∇t+1 F k22 ≤

i=1

|λ2 (W )|2 ·

N
X

(88)
i
− ∇t+1 F k22 ,
k∇it F + δft+1

i=1

Similarly, define δFt+1 := ∇t+1 F − ∇t F = N −1
right hand side of (88) as
N
X

PN

i
i=1 δft+1

and observe that we can bound the

i
k∇it F + δft+1
− ∇t+1 F k22

i=1

≤

N 
X

(89)

i
− δFt+1 k22
k∇it F − ∇t F k22 + kδft+1

i=1
i
+ 2 · kδft+1
− δFt+1 k2 · k∇it F − ∇t F k2



where the first inequality is obtained by expanding the squared `2 norm and applying CauchySchwartz inequality.
Observe that for all i ∈ [N ], we have the following chain:
i
i
i
kδft+1
k2 = k∇fi (θ̄t+1
) − ∇fi (θ̄ti )k2 ≤ Lkθ̄t+1
− θ̄ti k2

PN
j
j
j
i
≤L
j=1 Wij (θt+1 − θ̄t ) + (θ̄t − θ̄t )
2


PN
≤ L j=1 Wij t−α ρ̄ + 2Cp t−α = (2Cp + ρ̄)Lt−α ,

26

(90)

where the last inequality is due to the convexity of `2 norm, the update rule in line 5 of Algorithm 1
and the results from Lemma 1. Using the triangular inequality, we observe that
 i
P
j
i
kδft+1
− δFt+1 k2 = 1 − N1 δt+1
+ N1 j6=i δt+1
2
 i
P
j
≤ 1 − N1 kδt+1
k2 + N1 j6=i kδt+1
k2
(91)
1
≤2 1−
(2Cp + ρ̄)Lt−α ≤ 2(2Cp + ρ̄)Lt−α .
N
Finally, applying the induction hypothesis, the right hand side of Eq. (89) can be bounded by
N
X

i
− ∇t+1 F k22
k∇it F + δft+1

i=1


≤ t−2α Cg2 + 4N (2Cp + ρ̄)2 L2
√ qPN
−α
i
2
+ t 4L(2Cp + ρ̄) N
i=1 k∇t F − ∇t F k2
2
√
2  (t0 )α + 1
≤ t−2α · Cg + 2L N (2Cp + ρ̄) ≤
·
C
,
g
(t0 )α · tα
√ qPN
PN
i
i
2
where we have used the fact that i=1 k∇t F − ∇t F k2 ≤ N
i=1 k∇t F − ∇t F k2 in the first
2
inequality. Invoking (23), we can upper bound the right hand side of (88) by Cg /(t + 1)2α for
all t ≥ t0 . Taking square root on both sides of the inequality completes the induction step.
Consequently, (30) can be implied by (87).

E

Proof of Lemma 3

Applying triangular inequality on the error vector yields:
ξt−1 ∇it F

N
1 X
∇fj (θ̄tj )
−
N
j=1

≤

ξt−1

·

∇it F

∞

N
1 X
−
∇fj (θ̄tj )
N

1Ωt

j=1

+

N

1 X
∇fj (θ̄tj )
N

(ξt−1 1Ωt − 1)

j=1

(92)

∞

∞

,

where 1 denotes the all-one vector. For the first term in the right hand side of (92), observe that
∇it F is obtained by applying the AC updates on the sparsified local gradients ∇fi (θ̄ti ) 1Ωt for
`t = dCl + log(t)/ log |λ−1
2 (W )|e rounds, applying Fact 1 yields the following for all i ∈ [N ]:
∇it F −

N
1 X
∇fj (θ̄tj )
N

1Ωt

j=1

≤ |λ2 (W )|`t · (∇fi (θ̄ti ) −

∞

N
1 X
∇fj (θ̄tj ))
N
j=1

≤ |λ2 (W )|Cl · B/t ,
27

(93)
1Ωt

∞

for some B < ∞ since the gradients are bounded.

P
For the second term in the right hand side of (92), we first apply the inequality k N −1 N
∇fi (θ̄ti )
i=1
P
−1
i
(ξt−1 1Ωt − 1)k∞ ≤ kN −1 N
i=1 ∇fi (θ̄t )k∞ k(ξt 1Ωt − 1)k∞ from [60]. Now, the probability that coordinate k is included is given by:
P (k ∈ Ωt ) = 1 − P

N
\
i=1


1
k∈
/ Ωt,i = 1 − (1 − )pt N = ξt ,
d

(94)

and that E[1Ωt ] = ξt 1. Then, observing that each element in ξt−1 1Ωt is bounded in [0, ξt−1 ] and
applying the Hoefding’s inequality [61], the following holds true for all x > 0:

2 −2
P kξt−1 1Ωt − 1k∞ ≥ x ≤ 2d · e−2x /ξt ,

(95)

where we have applied
p a union bound argument to take care of the `∞ -norm.
Setting x = ξt−1 (log(2dt2 ) − log )/2 and applying another union bound show that with probability at least 1 − (π 2 /6), the following holds for all t ≥ 1:
N
1 X
∇fi (θ̄ti )
N

(ξt−1 1Ωt − 1)

i=1

≤

ξt−1

N
1 X
∇fi (θ̄ti )
N
i=1

r
∞

∞

(96)
log(2dt2 /)
,
2

As d  0, we have ξt−1 ≈ d/(pt N ). Recalling pt ≥ C0 t yields the desired result in Lemma 3.

References
[1] J. Lafond, H.-T. Wai, and E. Moulines, “D-FW: Communication Efficient Distributed Algorithms for High-dimensional Sparse Optimization,” in Proc ICASSP, Mar 2016.
[2] H.-T. Wai, A. Scaglione, J. Lafond, and E. Moulines, “A projection-free decentralized algorithm for non-convex optimization,” in Proc GlobalSIP, December 2016.
[3] V. Cevher, S. Becker, and M. Schmidt, “Convex Optimization for Big Data: Scalable, randomized, and parallel algorithms for big data analytics,” IEEE Signal Process. Mag., vol. 31,
no. 5, pp. 32–43, Sep. 2014.
[4] A. H. Sayed, S.-Y. Tu, J. Chen, X. Zhao, and Z. J. Towfic, “Diffusion strategies for adaptation
and learning over networks: an examination of distributed strategies and network behavior,”
IEEE Signal Process. Mag., vol. 30, no. 3, pp. 155–171, May 2013.
[5] Z. Liu and L. Vandenberghe, “Interior-point method for nuclear norm approximation with
application to system identification,” SIAM J. Matrix Anal. Appl., vol. 31, no. 3, pp. 1235–
1256, 2010.
[6] E. J. Candès and B. Recht, “Exact matrix completion via convex optimization,” Found. Comput. Math., vol. 9, no. 6, pp. 717–772, 2009.
28

[7] C. Ravazzi, S. M. Fosson, and E. Magli, “Randomized algorithms for distributed nonlinear
optimization under sparsity constraints,” IEEE Trans. on Signal Process., vol. 64, no. 6, pp.
1420–1434, Mar 2016.
[8] S. Patterson, Y. C. Eldar, and I. Keidar, “Distributed compressed sensing for static and timevarying networks,” IEEE Trans. on Signal Process., vol. 62, no. 19, pp. 4931–4946, July 2014.
[9] J. Tsitsiklis, “Problems in decentralized decision making and computation,” Ph.D. dissertation,
Dept. of Electrical Engineering and Computer Science, M.I.T., Boston, MA, 1984.
[10] A. G. Dimakis, S. Kar, J. M. F. Moura, M. G. Rabbat, and A. Scaglione, “Gossip Algorithms
for Distributed Signal Processing,” Proc. IEEE, vol. 98, no. 11, pp. 1847–1864, Nov. 2010.
[11] P. Bianchi and J. Jakubowicz, “Convergence of a multi-agent projected stochastic gradient
algorithm for non-convex optimization,” IEEE Trans. Autom. Control, vol. 58, no. 2, pp.
391–405, Feb 2013.
[12] I.-A. Chen, “Fast distributed first-order methods,” Master’s thesis, MIT, 2012.
[13] G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” CoRR, vol.
abs/1605.07112, May 2016.
[14] B. Johansson, T. Keviczky, M. Johansson, and K. H. Johansson, “Subgradient methods and
consensus algorithms for solving convex optimization problems,” in Proc. CDC, Dec 2008, pp.
4185–4190.
[15] S. Ram, A. Nedić, and V. Veeravalli, “Distributed stochastic subgradient projection algorithms
for convex optimization,” Journal of Optimization Theory and Applications, vol. 147, no. 3,
pp. 516–545, 2010.
[16] W. Shi, Q. Ling, G. Wu, and W. Yin, “A proximal gradient algorithm for decentralized
composite optimization,” IEEE Trans. on Signal Process., vol. 63, no. 22, pp. 6013–6023,
Nov 2015.
[17] D. Jakovetic, J. Xavier, and J. M. F. Moura, “Fast distributed gradient methods,” IEEE
Trans. Autom. Control, vol. 59, no. 5, pp. 1131–1146, May 2014.
[18] A. Nedić, A. Olshevsky, and W. Shi, “Achieving geometric convergence for distributed optimization over time-varying graphs,” CoRR, vol. abs/1607.03218, July 2016.
[19] X. Li and A. Scaglione, “Convergence and applications of a gossip based gauss newton algorithm,” IEEE Trans. on Signal Process., vol. 61, no. 21, pp. 5231–5246, Nov 2013.
[20] D. Varagnolo, F. Zanella, A. Cenedese, G. Pillonetto, and L. Schenato, “Newton-raphson
consensus for distributed convex optimization,” IEEE Trans. Autom. Control, vol. 61, no. 4,
pp. 994–1009, April 2016.
[21] T.-H. Chang, A. Nedic, and A. Scaglione, “Distributed constrained optimization by consensusbased primal-dual perturbation method,” IEEE Trans. Autom. Control, vol. 59, no. 6, pp.
1524–1538, June 2014.

29

[22] J. Duchi, A. Agarwal, and M. J. Wainwright, “Dual averaging for distributed optimization:
Convergence analysis and network scaling,” IEEE Trans. Autom. Control, vol. 57, no. 3, pp.
592–606, March 2012.
[23] E. Wei and A. Ozdaglar, “On the o(1/k) convergence of asynchronous distributed alternating
direction method of multipliers,” CoRR, vol. abs/1307.8254, July 2013.
[24] A. Simonetto and H. Jamali-Rad, “Primal recovery from consensus-based dual decomposition
for distributed convex optimization,” JOTA, vol. 168, no. 1, pp. 172–197, 2016.
[25] M. Hong, “Decomposing linearly constrained nonconvex problems by a proximal primal dual
approach: Algorithms, convergence, and applications,” CoRR, vol. abs/1604.00543, Apr 2016.
[26] Y. Yang, G. Scutari, D. P. Palomar, and M. Pesavento, “A parallel stochastic approximation
method for nonconvex multi-agent optimization problems,” CoRR, vol. abs/1410.5076, Oct
2014.
[27] P. D. Lorenzo and G. Scutari, “Next: In-network nonconvex optimization,” IEEE Trans. on
Signal and Info. Process. over Networks, 2016.
[28] H.-T. Wai and A. Scaglione, “Consensus on state and time: Decentralized regression with
asynchronous sampling,” IEEE Trans. on Signal Process., vol. 63, no. 11, pp. 2972–2985, June
2015.
[29] H.-T. Wai, T.-H. Chang, and A. Scaglione, “A consensus-based decentralized algorithm for
non-convex optimization with application to dictionary learning,” in Proc ICASSP, Apr 2015,
pp. 3546–3550.
[30] M. Frank and P. Wolfe, “An algorithm for quadratic programming,” Naval Res. Logis. Quart.,
1956.
[31] Z. Wu and K. Teo, “A conditional gradient method for an optimal control problem involving
a class of nonlinear second-order hyperbolic partial differential equations,” Journal of Mathematical Analysis and Applications, vol. 91, no. 2, pp. 376 – 393, 1983.
[32] M. Jaggi and M. Sulovsky, “A simple algorithm for nuclear norm regularized problems,” in
ICML, June 2010.
[33] A. Joulin, K. Tang, and L. Fei-Fei, “Efficient image and video co-localization with frank-wolfe
algorithm,” in ECCV, Sept 2014.
[34] L. Zhang, V. Kekatos, and G. B. Giannakis, “Scalable electric vehicle charging protocols,”
CoRR, vol. abs/1510.00403v2, Oct 2016.
[35] M. Fukushima, “A modified frank-wolfe algorithm for solving the traffic assignment problem,”
Transportation Research Part B: Methodological, vol. 18, no. 2, pp. 169–177, April 1984.
[36] M. Jaggi, “Revisiting Frank-Wolfe: Projection-free sparse convex optimization,” in ICML,
June 2013.

30

[37] S. Ghosh and H. Lam, “Computing worst-case input models in stochastic simulation,” CoRR,
vol. abs/1507.05609, July 2015.
[38] S. Lacoste-Julien, “Convergence rate of Frank-Wolfe for non-convex objectives,” CoRR, vol.
abs/1607.00345, July 2016.
[39] J. Lafond, H.-T. Wai, and E. Moulines, “On the online Frank-Wolfe algorithms for convex and
non-convex optimizations,” CoRR, vol. abs/1510.01171v2, Aug 2016.
[40] S. Ghadimi and G. Lan, “Accelerated gradient methods for nonconvex nonlinear and stochastic
programming,” Mathematical Programming, vol. 156, no. 1, pp. 59–99, Feb 2015.
[41] J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra, “Efficient projections onto the `1 -ball
for learning in high dimensions,” in ICML, July 2008.
[42] G. H. Golub and C. F. van Loan, Matrix computations, 4th ed.
Press, Baltimore, MD, 2013.

Johns Hopkins University

[43] A. Defazio, F. Bach, and S. Lacoste-Julien, “SAGA: A fast incremental gradient method with
support for non-strongly convex composite objectives,” in NIPS, Dec 2014.
[44] A. Scaglione, R. Pagliari, and H. Krim, “The decentralized estimation of the sample covariance,” in Proc. Asilomar, Nov. 2008, pp. 1722–1726.
[45] Q. Ling, Y. Xu, W. Yin, and Z. Wen, “Decentralized low-rank matrix completion,” in Proc
ICASSP, Mar 2012.
[46] L. Mackey, A. Talwalkar, and M. I. Jordan, “Distributed matrix completion and robust factorization,” Journal of Machine Learning Research, vol. 16, pp. 913–960, 2015.
[47] H.-F. Yu, C.-J. Hsieh, S. Si, and I. Dhillon, “Scalable coordinate descent approaches to parallel
matrix factorization for recommender systems,” in ICDM. IEEE, 2012, pp. 765–774.
[48] B. Recht and C. Ré, “Parallel stochastic gradient algorithms for large-scale matrix completion,”
Mathematical Programming Computation, vol. 5, no. 2, pp. 201–226, 2013.
[49] V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky, “Sparse and low-rank matrix
decompositions,” in Proc. Allerton, 2009, pp. 962–967.
[50] G. H. Mohimani, M. Babaie-Zadeh, and C. Jutten, “Fast Sparse Representation Based on
Smoothed L0 Norm,” in ICA, ser. Lecture Notes in Computer Science. Springer, Sep. 2007,
pp. 389–396.
[51] L. Bako, “Identification of switched linear systems via sparse optimization,” Automatica,
vol. 47, no. 4, pp. 668 – 677, 2011.
[52] T. Blumensath and M. E. Davies, “Iterative hard thresholding for compressed sensing,” CoRR,
vol. abs/0805.0510, May 2008.
[53] M. E. Yildiz and A. Scaglione, “Coding with side information for rate-constrained consensus,”
IEEE Trans. on Signal Process., vol. 56, no. 8, pp. 3753–3764, Aug 2008.
31

[54] H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations, and Advanced
Topics. Wiley, 2004.
[55] L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” Systems & Control
Letters, vol. 53, no. 1, pp. 65–78, Sep. 2004.
[56] F. M. Harper and J. A. Konstan, “The movielens datasets: History and context,” ACM TiiS,
Jan 2015.
[57] E. v. Berg, M. P. Friedlander, G. Hennenfent, F. Herrmann, R. Saab, and Ö. Yılmaz, “Sparco:
A testing framework for sparse reconstruction,” Dept. Computer Science, University of British
Columbia, Vancouver, Tech. Rep. TR-2007-20, October 2007.
[58] B. P. Polyak, Introduction to Optimization.

Optimization Software, Inc., 1987.

[59] E. A. Nirminskii, “Convergence conditions for nonlinear programming algorithms,” Cybernetics, no. 6, pp. 79–81, Nov 1972.
[60] R. A. Horn and C. R. Johnson, Topics in matrix analysis. Cambridge: Cambridge University
Press, 1994, corrected reprint of the 1991 original.
[61] P. Massart, Concentration Inequalities and Model Selection.

32

Springer, 2003.

