Asynchronous Distributed Optimization with Stochastic Delays
  We study asynchronous finite sum minimization in a distributed-data setting
with a central parameter server. While asynchrony is well understood in
parallel settings where the data is accessible by all machines -- e.g.,
modifications of variance-reduced gradient algorithms like SAGA work well --
little is known for the distributed-data setting. We develop an algorithm
ADSAGA based on SAGA for the distributed-data setting, in which the data is
partitioned between many machines. We show that with $m$ machines, under a
natural stochastic delay model with an mean delay of $m$, ADSAGA converges in
$\tilde{O}\left(\left(n + \sqrt{m}\kappa\right)\log(1/\epsilon)\right)$
iterations, where $n$ is the number of component functions, and $\kappa$ is a
condition number. This complexity sits squarely between the complexity
$\tilde{O}\left(\left(n + \kappa\right)\log(1/\epsilon)\right)$ of SAGA
\textit{without delays} and the complexity $\tilde{O}\left(\left(n +
m\kappa\right)\log(1/\epsilon)\right)$ of parallel asynchronous algorithms
where the delays are \textit{arbitrary} (but bounded by $O(m)$), and the data
is accessible by all. Existing asynchronous algorithms with distributed-data
setting and arbitrary delays have only been shown to converge in
$\tilde{O}(n^2\kappa\log(1/\epsilon))$ iterations. We empirically compare on
least-squares problems the iteration complexity and wallclock performance of
ADSAGA to existing parallel and distributed algorithms, including synchronous
minibatch algorithms. Our results demonstrate the wallclock advantage of
variance-reduced asynchronous approaches over SGD or synchronous approaches.
