Developing schemes for asynchronous distributed optimization has been
an active area of research in recent years. Examples of such algorithms
include [1]}, [2]}, [3]}, [4]}.
In [4]}, the authors study parallel optimization
with sparse data. They propose an asynchronous dual averaging approach
termed AsyncDA. In AsyncDA, the master keeps and updates the dual
variable while each worker keeps its own primal optimization variable.
Asynchronous methods use stale gradients, as was mentioned earlier.
While asynchronous schemes can tolerate gradient staleness, large
staleness can slow convergence. This is known as the stale gradient
problem. For instance, in [3]}, gradient staleness
scales linearly in the number of workers. Thus using larger network
may have an undesirable impact on convergence. To limit the negative
impact of staleness, the authors in [7]} propose
a stale-gradient-based scheme and control the staleness in a spoke-and-hub
setting by forcing fast workers to wait for slow ones. One of the
challenges encountered in distributed optimization is dealing with
the communication load. When the number of workers increases, worker-master
communication may become a bottleneck. To reduce the communication
load and alleviate the bottleneck, techniques that compress the information
before transmission have been proposed and analyzed such as gradient
quantization [8]}, [9]}, [10]}
and gradient sparsification (i.e., randomly dropping out coordinates
of the gradient and amplifying the rest) [11]}.
