A couple of months ago we (Kevin Scaman, Francis Bach, Yin Tat Lee, Laurent Massoulie and myself) uploaded a new paper on distributed convex optimization. We came up with a pretty clean picture for the optimal oracle complexity of this setting, which I will describe below. I should note that there are hundreds of papers on this topic, but the point of the post is to show our simple cute calculations and not to survey the immense literature on distributed optimization, see the paper itself for a number of pointers to other recent works.
Distributed optimization setting
Let 
be an undirected graph on 
vertices (
) and with diameter 
. We will think of the nodes in 
as the computing units. To each vertex 
there is an associated convex function 
. For machine learning applications one can think that each computing unit has access to a “private” dataset, and 
represents the fit of the model corresponding to 
on this dataset (say measured on least squares loss, or logistic loss for example). The goal will be to find in a distributed way the optimal “consensus” point:
The distributed processing protocol is as follows: asynchronously/in parallel, each node 
can (i) compute a (local) gradient 
in time 
, and (ii) communicate a vector in 
to its neighbors in
in time 
. We denote by 
the local model (essentially its guess for 
) of node
at time 
. We aim to characterize the smallest time 
such that one can guarantee that all nodes
satisfy 
where 
.
We focus on the case where 
is 
-smooth and 
-strongly convex (
is the condition number), which is arguably the most challenging case since one expects linear convergence (i.e., the scaling of
in 
should be 
) which a priori makes the interaction of optimization error and communication error potentially delicate (one key finding is that in fact it is not delicate!). Also, having in mind applications outside of large-scale machine learning (such as “federated” learning), we will make no assumptions about the functions at different vertices relate to each other.
A trivial answer
Recall that Nesterov’s accelerated gradient descent solves the serial problem in time 
. Trivially one can distribute a step of Nesterov’s accelerated gradient descent in time 
(simply designate a master node at the beginning, and everybody sends its local gradient to the master node in time
). Thus we arrive at the upper bound 
using a trivial (centralized) algorithm. We now show (slightly informally, see the paper for proper definitions) that this in fact optimal!
First let us recall the lower bound proof in the serial case (see for example Theorem 3.15 here). The idea is to introduce the function 
where 
is the Laplacian of the path graph on 
, or in other words
First it is easy to see that this function is indeed 
-smooth and 
-strongly convex. The key point is that, for any algorithm starting at 
and such that each iteration stays in the linear span of the previously computed gradients (a very natural assumption) then
In words one can say that each gradient calculation “discovers” a new edge of the path graph involved in the definition of 
. Concluding the serial proof is then just a matter of brute force calculations.
Now let us move to the distributed setting, and consider two vertices 
and
that realize the diameter of
. The idea goes as follows: let 
(respectively 
) be the Laplacian of even edges of the path graph on 
(respectively the odd edges), that is
Now define 
, 
, and 
for any 
. The key observation is that node
does not “know” about the even edges until it receives a message from
and vice versa. Thus it fairly easy to show that in this case one has:
which effectively amounts to a slowdown by a factor 
compared to the serial case and proves the lower bound 
.
Not so fast!
One can say that the algorithm proposed above defeats a bit the purpose of the distributed setting. Indeed the centralized communication protocol it relies on is not robust to various real-life issues such as machine failures, time-varying graphs, edges with different latency, etc. An elegant and practical solution is to restrict communication to be gossip-like. That is local computations have now to be communicated via matrix multiplication with a walk matrix 
which we define as satisfying the following three conditions: (i) 
, (ii) 
, and (iii) 
. Let us briefly discuss these conditions: (i) simply means that if 
represents real values stored at the vertices, then 
can be calculated with a distributed communication protocol; (ii) says that if there is consensus (that is all vertices hold the same value) then no communication occurs with this matrix multiplication; and (iii) will turn out to be natural in a just a moment for our algorithm based on duality. A prominent example of a walk matrix would be the (normalized) Laplacian of
We denote by 
the inverse condition number of
on 
(that is the ratio of the smallest non-zero eigvenvalue of
to its largest eigenvalue), also known as the spectral gap of
when
is the Laplacian. Notice that
naturally controls the number of gossip steps to reach consensus, in the sense that gossip steps corresponds to gradient descent steps on 
, which will converge in 
steps. Doing an “accelerated gossip” (also known as Chebyshev gossiping) one could thus hope to essentially replace the diameter
by 
. Notice that this is hopeful thinking because in the centralized model
steps gets you to an exact consensus, while in the gossip model one only reaches an
-approximate consensus and errors might compound. In fact with a bit of graph theory one can immediately see that simply replacing
by
is too good to be true: there are graphs (namely expanders) where
is of order 
while
is of order of a constant, and thus an upper bound of the form (say) 
would violate our previous lower bound by a factor 
.
To save the day we will make extra assumptions, namely that each local function 
has condition number 
and that in addition to computing local gradient the vertices can also compute local gradients of the Fenchel dual functions 
. The latter assumption can be removed at the expense of extra logarithmic factors but we will ignore this point here (see the paper for some hints as well as further discussion on this point). For the former assumption we note that the lower bound proof given above completely breaks under this assumption. However one can save the construction for some specific graphs (finding the correct generalization to arbitrary graphs is one of our open problems). For example imagine a line graph, and cluster the vertices into three groups, the first third, the middle, and the last third. Then one could distribute the even part of the Laplacian on
in the first group, and the odd part on the last group, as well as distribute the Euclidean norm evenly among all vertices. This construction verifies that each vertex function has condition number 
and furthermore the rest of the argument still goes through. Interestingly in this case one also has 
and thus this proves that for the line graph one has 
for gossip algorithms. We will now show a matching upper bound (which holds for arbitrary graphs).
Dual algorithm
For 
(which we think of as a set of column vectors, one for each vertex 
), denote 
for the 
column and let 
. We are interested in minimizing 
under the constraint that all columns are equal, which can be written as 
. By definition of the Fenchel dual 
and a simple change of variable one has:
Next observe that gradient ascent on 
can be written as
and with the notation 
this is simply 
. Crucially 
exactly corresponds to gossiping the local conjugate gradients (which are also the local models) 
. In other words we only have to understand the condition number of the function 
. The beauty of all of this is that this condition number is precisely 
(i.e. it naturally combines the condition number of the vertex functions with the “condition number” of the graph). Thus by accelerating gradient ascent we arrive at a time complexity of 
(recall that a gossip step takes time
). We call the corresponding algorithm SSDA (Single-Step Dual Accelerated). One can improve it slightly in the case of low communication cost by doing multiple rounds of communication between two gradient computations (essentially replacing
by 
). We call the corresponding algorithm MSDA (Multi-Step Dual Accelerated) and its attains the optimal (in the worst case over graphs) complexity of 
.