# Anytime Minibatch with Delayed Gradients

Haider Al-Lawati, and Stark Draper This work was presented in part at the
Annual Conference on Information Sciences and Systems, Baltimore, MD, USA,
March 2019 [1] and at IEEE International Conference on Acoustics, Speech, and
Signal Processing, Barcelona, Spain, May 2020 [2].
This work was supported by Huawei Technologies Canada, the Natural Science and
Engineering Research Council (NSERC) of Canada through a Discovery Research
Grant, and the Omani Government Postgraduate Scholarship. The authors are with
Electrical and Computer Engineering department, University of Toronto,
Toronto, Canada (email<EMAIL_ADDRESS>starkdraper@utoronto.ca). Copyright (c) 2020 IEEE. Personal use of this
material is permitted. However, permission to use this material for any other
purposes must be obtained from the IEEE by sending a request to pubs-
<EMAIL_ADDRESS>
###### Abstract

Distributed optimization is widely deployed in practice to solve a broad range
of problems. In a typical asynchronous scheme, workers calculate gradients
with respect to out-of-date optimization parameters while the master uses
stale (i.e., delayed) gradients to update the parameters. While using stale
gradients can slow the convergence, asynchronous methods speed up the overall
optimization with respect to wall clock time by allowing more frequent updates
and reducing idling times. In this paper, we present a variable per-epoch
minibatch scheme called Anytime Minibatch with Delayed Gradients (AMB-DG). In
AMB-DG, workers compute gradients in epochs of a fixed time while the master
uses stale gradients to update the optimization parameters. We analyze AMB-DG
in terms of its regret bound and convergence rate. We prove that for convex
smooth objective functions, AMB-DG achieves the optimal regret bound and
convergence rate. We compare the performance of AMB-DG with that of Anytime
Minibatch (AMB) which is similar to AMB-DG but does not use stale gradients.
In AMB, workers stay idle after each gradient transmission to the master until
they receive the updated parameters from the master while in AMB-DG workers
never idle. We also extend AMB-DG to the fully distributed setting. We compare
AMB-DG with AMB when the communication delay is long and observe that AMB-DG
converges faster than AMB in wall clock time. We also compare the performance
of AMB-DG with the state-of-the-art fixed minibatch approach that uses delayed
gradients. We run our experiments on a real distributed system and observe
that AMB-DG converges more than two times.

##  I Introduction

Distributed stochastic optimization has become an important tool in solving
large-scale problems such as those found in modern machine learning
applications. Traditionally, such problems have been solved using gradient-
based methods in a serial manner on a single compute node. However, training
deep neural networks using large datasets with millions of data points in a
reasonable amount of time often requires parallelizing across multiple
machines [3, 4, 5, 6]. Furthermore, in many online learning systems, such as
search engines, data (e.g., queries) arrive at rates that a single node cannot
handle or process in real time [7]. Although training deep networks using a
single GPU is possible, in many large-scale training and online learning
problems, multiple nodes are deployed in parallel to cooperatively execute the
desired tasks.

In the past decade, a large body of work has proposed and analyzed various
schemes to parallelize stochastic optimization and online learning problems
[3, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]. A common approach is
to use a network of nodes arranged according to a _hub-and-spoke_ topology. In
this topology, a central node, known as the _master_ , keeps track of and
updates the optimization parameters while the other nodes, known as _workers_
, calculate the gradients of the objective function with respect to individual
data points and submit these gradients to the master.

Distributed optimization methods can be categorized as synchronous or
asynchronous. In synchronous methods, the master waits for all workers to
submit their results before updating the optimization parameters. As a result,
the speed of the computation in synchronous methods is limited by the speed of
the slowest workers known as “stragglers” [20, 21, 22]. To alleviate the
straggler effect, asynchronous methods have been proposed in which the master
does not wait for all workers. Instead, the master updates the optimization
parameters using “stale” (i.e., delayed) gradients.

Recently, we introduced a novel synchronous technique called _Anytime
Minibatch_ (AMB) in [13]. Our main idea was to fix the per-epoch compute time
across all workers rather than fixing the job size as is typical. Since
workers progress at different rates, fixing the compute time results in a
variable amount of work being completed by each worker in each epoch. A
drawback of AMB is that when workers submit their results to the master, they
idle while waiting to receive back the updated optimization parameters. When
this wait time is long, the wall time convergence can be greatly prolonged. To
alleviate this deficiency, in this paper we propose _Anytime Minibatch with
Delayed Gradients_ (AMB-DG). In AMB-DG, workers keep processing data points
and calculate gradients at all times while the master updates the parameters
using delayed gradients. We analyze the performance of AMB-DG for a convex
smooth objective function under the assumption of fixed gradient staleness.
Under these assumptions, we prove that the expected regret bound attained is
$O(\sqrt{{m}})$ where $m$ is the number of samples observed across all nodes.
This bound is well-known to be the optimal regret bound achievable by
gradient-based methods on arbitrary convex objective functions [7]. We also
show that under the same assumptions the expected convergence rate (i.e.,
optimality gap) achieved is $O(1/\sqrt{m})$. Our theoretical derivations show
that asymptotically in the number of data points observed, the impact of the
fixed delay on convergence is negligible for smooth convex loss functions. We
compare the performance of AMB-DG with that of AMB and observe that under long
communication delays AMB-DG converges faster than AMB in terms of wall clock
time. We also implement AMB-DG on the SciNet high performance computing
platform and compare the performance of AMB-DG with existing asynchronous
delayed-gradient-based methods. AMB-DG converges almost $2$ times faster in
our examples.

The remainder of the paper is organized as follows. In Sec. II, we review the
literature. In Sec. III, we present the system model and the algorithmic
description. The convergence analysis and theorems are presented in Sec. IV.
Detailed proofs are deferred to Appendix A. In Sec. VI, we present numerical
results illustrating the performance of AMB-DG. Finally, Sec. VII summarizes
and concludes the paper.

##  II Related Work

Asynchronous distributed optimization has been studied at least since the
seminal work of Tsitsiklis et al. [23]. In recent years, asynchronous schemes
have played a key role in solving large-scale machine learning and online
optimization problems. For instance, Google’s _distbelif_ [10] was one of the
earliest implementation of asynchronous distributed optimization for large-
scale training in machine learning. In general, the literature pertaining to
asynchronous distributed optimization and online learning focuses on two
aspects: algorithmic development and convergence analysis.

Developing schemes for asynchronous distributed optimization has been an
active area of research in recent years. Examples of such algorithms include
[6, 12, 15, 24]. In [24], 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 [15], 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 [25] 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
[26, 27, 28] and gradient sparsification (i.e., randomly dropping out
coordinates of the gradient and amplifying the rest) [29].

In another thread of works, convergence analyses of existing asynchronous
methods have been developed. In [8], the authors analyze the convergence of
distributed optimization of smooth convex loss functions using delayed
gradients under the assumption of bounded gradient delay. They prove that the
effect of gradient delay is negligible asymptotically in the number of
processed data points and that the optimal rate is achievable. In [30], the
convergence analysis is extended to general regularized convex cost functions.
In [17], the authors study the convergence of stochastic gradient methods for
nonconvex objective functions and establish an ergodic convergence rate of
${\cal O}(1/\sqrt{T})$, where $T$ is the number of iterations.

##  III AMB-DG Scheme

In this section, we introduce AMB-DG. We first introduce the system model and
then describe the algorithm. The pseudocode of the scheme is found in Appendix
C.

###  III-A System Model

In this paper we study a synchronized network consisting of a master and $n$
workers. Processing proceeds in epochs, each of duration $T_{p}$ seconds.
Epochs are indexed by $t\in\mathbb{Z}_{+}$. The $t$-th epoch therefore ends at
time $tT_{p}$. At the end of epoch $t$ workers synchronously and in parallel
transmit messages to the master. Worker $i$ transmits message $m_{i}(t)$. All
worker-to-master transmissions take $\tfrac{1}{2}T_{c}$ second. Based on its
current state and the $n$ messages received, the master updates its estimate
of the optimization parameters. The $t$-th update of the optimization
parameter is denoted by $w(t+1)$. We assume the master’s update occurs
instantaneously. Therefore the master’s $t$-th update occurs at time
$tT_{p}+\tfrac{1}{2}T_{c}$. The master then broadcasts its $t$-th parameter
update to all workers. This is done in parallel and all messages take
$\tfrac{1}{2}T_{c}$ second to reach each worker. Therefore, each worker
receives $w(t+1)$ at time $tT_{p}+T_{c}$. Naturally, depending on the relative
durations of $T_{p}$ and $T_{c}$ the workers will be basing their calculation
on more or less stale information. The ratio $\tau=\lceil
T_{c}/T_{p}\rceil\in\mathbb{Z_{+}}$ plays an important role in the ensuing
derivation. We term this ratio the “staleness parameter”. Note that $T_{p}$
and $T_{c}$ are both deterministic; hence $\tau$ is deterministic, too. The
staleness parameter, $\tau$, represents the number of updates the master makes
to the optimization parameter from the time when it calculates and broadcasts
$w(t)$ until it receives gradients with respect to the same $w(t)$.

The above description is diagrammed in Fig. 1. At the core of our interest in
this system is the fact that workers may be operating at different computing
speeds and therefore may process different amounts of data in each processing
epoch. In epoch $t$ worker $i$ processes $b_{i}(t)$ data points. These data
are indexed as $x_{i}(t,s)$ where $s\in[b_{i}(t)]$. The total data processed
in epoch $t$ is denoted $b(t)=\sum_{i=1}^{n}b_{i}(t)$. In Fig. 1 the variable-
sized mini-batches are indicated by the different heights of the bar plots
associated with each worker. Fig. 1 illustrates a system with three workers.

Fig. 1: AMB-DG system model

###  III-B Algorithmic Description

Our objective is to solve the following optimization problem

$\underset{w\in\mathcal{{W}}}{\text{{minimize\,}}}F(w)\text{ {\it{\rm where}}
}F(w):=\mathbb{E}_{P}\big{[}f(w,x)\big{]}.$ (1)

In (1) $f:\mathcal{W}\times\mathcal{X}\rightarrow\mathbb{R}$ and the
expectation is taken with respect to some (unknown) distribution $P$ over the
set $\mathcal{X}\subseteq\mathbb{R}^{d}$. In particular, we are interested in
solving for $w^{*}={\rm argmin}_{w\in{\cal W}}F(w)$.

The algorithm we study in the context of the above system model is dual
averaging [31, 32]. We first describe the distributed dual averaging without
stale gradients (i.e., when $T_{c}=0$). Then, we explain the delayed-gradient-
based variant.

Dual averaging is an iterative gradient-based algorithm. In each epoch $t$,
the system updates two parameters: the primal variable (a.k.a. the
optimization parameter) $w(t)$ and the dual variable $z(t)$. In the
distributed implementation of this algorithm, the master tracks and updates
these parameters while workers calculate the gradients. The system initializes
$z(1)=0\in\mathbb{R}^{d}$ and $w(1)={\rm argmin}_{w\in{\cal W}}\psi(w)$ where
$\psi(w)$ is a proximal function.

Next, we introduce the gradient computation and parameter update phases of
AMB-DG algorithm. First in the absence of gradient staleness, i.e., when
$T_{c}=0$, then we explain how to extend the algorithm to cater for stale
gradients.

#### Gradients computation

In each epoch $t$, worker $i$ calculates $b_{i}(t)$ gradients of $f(w,x)$ with
respect to the optimization parameters $w(t)$ and data points
$\\{x_{i}(t,s)\\},s\in[b_{i}(t)]$. The sum of gradients calculated by worker
$i$ at the end of epoch $t$ is

$g_{i}(t)=\sum_{s=1}^{b_{i}(t)}\nabla_{w}f\big{(}w(t),x_{i}(t,s)\big{)},$ (2)

where the $x_{i}(t,s)$ are sampled by worker $i$ in epoch $t$ in an
independent and identically distributed (i.i.d.) manner from $P$. At the end
of each gradient computation epoch, each worker $i$ sends message
$m_{i}(t):=\big{(}g_{i}(t),b_{i}(t)$$\big{)}$ to the master and proceeds
immediately to the next epoch.

#### Parameters update

The master calculates the average of the received gradients
$g(t)=\frac{1}{b(t)}\sum_{i=1}^{n}g_{i}(t)$, and updates $z(t)$ and $w(t)$
using the following dual averaging update rules

$z(t+1)=z(t)+g(t),$ (3)

$w(t+1)=\arg\min_{w\in\mathcal{W}}\Big{\\{}\big{\langle}z(t+1),w\big{\rangle}+\frac{1}{\alpha(t+1)}\psi(w)\Big{\\}},$
(4)

where $\alpha(t)$ is a nonincreasing sequence of _step sizes_. Since we work
in the Euclidean space, a typical choice of $\psi(w)$ is $\lVert w\rVert^{2}$.
The master broadcasts $w(t+1)$ to all workers immediately. The workers use the
updated optimization parameter to calculate the next set of gradients.

#### Stale gradients

Next, we consider the case when $T_{c}\neq 0$. To simplify our analysis, we
assume that $T_{c}$ is an integer multiple of $T_{p}$ so that
$\tau=T_{c}/T_{p}.$ This is possible by choosing the appropriate $T_{p}$. Note
that for short communication delay or when $T_{c}$ is smaller than $T_{p}$,
$\tau\leq 1$. In this case, we can use AMB instead of AMB-DG as workers’ idle
time between two consecutive epochs is relatively small and the benefits of
using non-stale gradients can result in faster convergence despite the short
intermittent idle times. In our analysis, we are interested in operating in
the large communication delay regimes. Large communication delay has been
observed to be a major bottleneck in large scale distributed computing. In
this situation, slow epoch-wise convergence due to delayed gradients is
compensated by a faster rate of parameters update. Furthermore, since $\lceil
T_{c}/T_{p}\rceil\geq T_{c}/T_{p}$ with equality if and only if $T_{c}$ is an
integer multiple of $T_{p}$, setting $T_{p}$ such $T_{c}$ is an integer
multiple of $T_{p}$ ensures that workers will immediately use the new
information; i.e., a new compute epoch starts as soon as updated parameters
arrive. Also, since we are interested in a large communication delay regime,
such a choice of $T_{p}$ is not very limiting.

We assume the use of a non-blocking communication protocol. That is, after
each gradient computation epoch ends, workers send their messages to the
master and immediately start a new round of computation while communication
proceeds in the background. Note that workers receive the first update from
the master at time $T_{p}+T_{c}=(\tau+1)T_{p}$. Hence, worker $i$ uses $w(1)$
to calculate gradients $g_{i}(t)$ for epochs $1\leq t\leq\tau+1$. In other
words,

$g_{i}(t)=\sum_{s=1}^{b_{i}(t)}\nabla_{w}f\big{(}w(1),x_{i}(t,s)\big{)}.$

On the other hand, since workers receive $w(t+1)$ at time
$tT_{p}+T_{c}=(t+\tau+1)T_{p}$, then for epochs $t\geq\tau+2$, each worker $i$
calculates $g_{i}(t)$ as

$g_{i}(t)=\sum_{s=1}^{b_{i}(t)}\nabla_{w}f\big{(}w(t-\tau),x_{i}(t,s)\big{)}.$

Therefore, the master calculates $g(t)$ as

$g(t)=\sum_{i=1}^{n}\sum_{s=1}^{b_{i}(t)}\nabla_{w}f(w(t-\tau),x_{i}(t,s)),$
(5)

where for $t-\tau\leq 0$, $w(t-\tau):=w(1)$, the initial value.

Figure 1 illustrates the delayed gradient model when the communication time
$T_{c}=3T_{p}$. Workers calculate gradients with respect to $w(1)$ in the
first four epochs and send their messages to the master at times $tT_{p}$ for
$t=1,2,3,4$. The master uses $z(2)=g(1)=\sum_{i=1}^{n}g_{i}(1)$ to calculate
$w(2)$ and broadcasts it to all workers while it uses delayed gradients
$g(2)$, which are calculated with respect to $w(1)$, to update $z(3)$ before
calculating $w(3)$. Worker $i$ receives $w(2)$ at time $4T_{p}$ and uses it to
calculate $g_{i}(5)$. The master uses $g_{i}(5)$ in turn to calculate $z(6)$
and hence $w(6)$ at time $5T_{p}+\tfrac{1}{2}T_{c}$. Since $T_{c}=3T_{p}$, the
staleness parameter in this example is $\tau=3$. Observe that the master
calculates $w(6)$ using gradients calculated with respect to $w(2)$ instead of
$w(5)$, so gradient staleness $5-2=3=\tau$. Except for the first $\tau+1=4$
epochs, the master calculates $w(t)$ for $t\geq\tau+2=5$ using gradients
calculated with respect to $w(t-\tau)=w(t-3)$.

We note that although we use dual averaging as an algorithmic workhorse, AMB-
DG can be implemented using other gradient-based algorithms as well. The
motivation behind using dual averaging stems from the following. Dual
averaging has been shown to asymptotically achieve optimal regret bound when
applied in distributed optimization using delayed gradients and fixed
minibatch size [8]. Furthermore, in [13], we proved that when using dual
averaging in a synchronous distributed setting with variable minibatch per
epoch with no gradient staleness, we can achieve optimal regret bound
asymptotically. Hence, we anticipate that using dual averaging with delayed
gradients and variable minibatch per epoch could yield the desired convergence
rate.

##  IV Convergence Results

In this section, we develop convergence results for AMB-DG in terms of
expected regret and expected convergence rate. The latter is also known as the
optimality gap. Regret is the standard metric of performance measurement in
the online learning literature while optimality gap is the standard metric in
stochastic optimization. Let $R(T)$ and $G(T)$, respectively, denote the
regret and the optimality gap after $T$ epochs (i.e., parameters updates).
Then,

$R(T)=\sum_{t=1}^{T}\Big{[}f\big{(}w(t+1),x(t+1)\big{)}-f(w^{*},x(t+1))\Big{]},$
(6)

while

$G(T)=F(\hat{w}(T))-F(w^{*}),$ (7)

where $w^{*}={\rm argmin}_{w\in{\cal W}}F(w)$ and
$\hat{w}(T)=\frac{1}{T}\sum_{t=1}^{T}w(t+1)$ is the time-average of the
optimization variable over the $T$ epochs.

Before turning to our performance analysis, we first state the main
assumptions used in our derivations.

###  IV-A Preliminaries

As was stated in Sec. III, we are interested in solving the online stochastic
optimization problem of (1). We assume that the feasible set $\mathcal{W}$ is
closed and convex and that an optimal solution, $w^{*}\in{\cal W}$, exists. We
assume that $f(w,x)$ is differentiable and convex in $w$ for every $x$. Hence,
$F(w)$ is also convex and differentiable and the gradient of the objective
function is $\nabla F(w):=\mathbb{E}_{P}\big{[}\nabla f(w,x)\big{]}$. We
assume that $F(w)$ and $\nabla f(w,x)$ are both Lipschitz continuous with
parameters $J$ and $L$, respectively. In other words,

$\lvert F(w_{1})-F(w_{2})\rvert\leq J\,\,\lVert w_{1}-w_{2}\rVert\quad\forall
w_{1},w_{2}\in\mathcal{W},$ (8)

and for all $w_{1},w_{2}\in{\cal W}$ and for all $x\in{\cal X}$

$\lVert\nabla f(w_{1},x)-\nabla f(w_{2},x)\rVert\leq L\lVert
w_{1}-w_{2}\rVert$ (9)

where $\lVert.\rVert$ is the $l_{2}$ norm. The smoothness property in (9)
implies that

$f(w_{2},x)\leq f(w_{1},x)+\langle\nabla
f(w_{1},x),w_{2}-w_{1}\rangle+\frac{L}{2}\lVert w_{1}-w_{2}\rVert^{2}.$ (10)

We also assume the following variance bound, for all
$w\in\mathcal{W},\mathbb{E}_{x}\big{[}\big{\lVert}\nabla f(w,x)-\nabla
F(w)\big{\rVert}^{2}\big{]}\leq\sigma^{2}$, for some $\sigma\geq 0$.
Furthermore, the proximal function, $\psi(w)$, in the primal variable update
rule (4) is $1$-strongly convex. This means that $\psi$ satisfies

$\psi(w_{2})\geq\psi(w_{1})+\langle g,w_{2}-w_{1}\rangle+\frac{1}{2}\lVert
w_{2}-w_{1}\rVert^{2}$ (11)

for all $w_{1},w_{2}\in\mathcal{W}$ and for all $g\in\partial\psi(w)$ where
$\partial\psi(w)$ is the set of sub-gradients defined as
$\partial\psi(w):=\left\\{g\in\mathbb{R}^{d}|\psi(w_{2})\geq\psi(w_{1})+\langle
g,w_{2}-w_{1}\rangle,\forall\,w_{2}\in\text{dom}(\psi)\right\\}$ .

Furthermore, for the optimal solution, $w^{*}$, we assume that
$\psi(w^{*})\leq C^{2}/2$ and that for all $w\in\mathcal{W},$
$D_{\psi}(w^{*},w)\leq C^{2}$, for some $C\in\mathbb{R}$. In these
definitions, $D_{\psi}(w^{*},w)$ is the Bregman divergence between $w^{*}$ and
$w$ defined as

$D_{\psi}(w^{*},w):=\psi(w^{*})-\psi(w)-\big{\langle}\nabla\psi(w),w^{*}-w\big{\rangle}.$
(12)

###  IV-B Regret and Convergence Analysis

We analyze the performance of AMB-DG in terms of the regret achieved after $T$
epochs. The $b_{i}(t)$ are modeled as i.i.d. random variables. Let $\bar{b}$
be the expected minibatch per epoch. That is, $\mathbb{E}[b(t)]=\bar{b}$. Then
$\mathbb{E}[b(t)]=\mathbb{E}\big{[}\sum_{i=1}^{n}b_{i}(t)\big{]}=n\bar{b}$.
Therefore, $\mathbb{E}[b_{i}(t)]=\bar{b}/n$ for all $i\in[n]$ and for all
$t\in[T]$. Furthermore, assume that $b(t)\geq\hat{b}$. Let $m$ be the expected
total number of samples observed from epoch $1$ to $T$, i.e.,

$m=\mathbb{E}\Big{[}\sum_{t=1}^{T}b(t)\Big{]}=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}[b_{i}(t)]=T\bar{b}.$
(13)

We assume that all gradients received are delayed by $\tau$ steps where $\tau$
is a nonnegative integer.

$\displaystyle\mathbb{E}\big{[}R(T)\big{]}\coloneqq\mathbb{E}\bigg{[}\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{s=1}^{b_{i}(t)}\Big{[}f$
$\displaystyle(w(t+1),x_{i}(t+1,s))$
$\displaystyle-f(w^{*},x_{i}(t+1,s))\Big{]}\bigg{]}.$ (14)

We next state the main theoretical results of our work. The theorem bounds the
expected regret and the corollary bounds the optimality gap.

######  Theorem IV.1.

Assume that the master receives a set of gradients over $T$ epochs during
which the expected number of data points workers sample from $P$ in an i.i.d.
manner is $m$. Let $\hat{b}\neq 0$ and $\bar{b}$ be as defined above. Choosing
$\alpha(t)^{-1}=L+\sqrt{(t+\tau)/\bar{b}}$, the expected regret for AMB-DG
with deterministic common gradient delay $\tau$ across all master-worker links
in each epoch is

$\displaystyle\mathbb{E}\big{[}R(T)\big{]}\leq\bar{b}\frac{C^{2}}{2}\Big{(}L+\sqrt{(T+1+\tau)/\bar{b}}\Big{)}$
$\displaystyle+2\tau JC\bar{b}$
$\displaystyle+\,2LJ^{2}(\tau+1)^{2}\bar{b}^{2}\big{(}1+\log T$
$\displaystyle\big{)}+\frac{\bar{b}}{\hat{b}}\sigma^{2}\sqrt{m}.$ (15)

In both Theorem IV.1 and Corollary IV.2, next, $J$ and $L$ are, respectively,
the Lipschitz constants of $F(w)$ and $\nabla f(w,x)$, $\sigma^{2}$ is the
bound on the variance of $\nabla f(w,x)$ and $C$ is a constant that satisfies
that for all $w\in\mathcal{W},$ the Bregman divergence $D_{\psi}(w^{*},w)\leq
C^{2}$.

Let $\hat{w}(T)$ be the average of the optimization variable over $T$ epochs,
i.e.,

$\hat{w}(T)=\frac{1}{T}\sum_{t=1}^{T}w(t+1).$ (16)

Using $\hat{w}(T)$ the expected optimality gap is

$\mathbb{E}\Big{[}G(T)\Big{]}\coloneqq\mathbb{E}\bigg{[}F\Big{(}\frac{1}{T}\sum_{t=1}^{T}w(t+1)\Big{)}-F(w^{*})\bigg{]}.$
(17)

Using the results from Theorem IV.1 and the definition of the conditional
expectation of the optimality gap in (17), we develop the following corollary
on the upper bound of the expected optimality gap achieved by AMB-DG.

######  Corollary IV.2.

The expected optimality gap for the AMB-DG scheme is

$\displaystyle\mathbb{E}\Big{[}G(T)\Big{]}\leq$
$\displaystyle\bar{b}\bigg{(}\frac{C^{2}}{2m}\Big{(}L+\sqrt{(T+1+\tau)/\bar{b}}\Big{)}+\frac{2\tau
JC}{m}$ $\displaystyle+2LJ^{2}\frac{(\tau+1)^{2}\bar{b}\big{(}1+\log
T\big{)}}{m}+\frac{\sigma^{2}}{\hat{b}\sqrt{m}}\bigg{)}.$ (18)

The proofs for Theorem IV.1 and Corollary IV.2 are provided in Appendix A. The
proof techniques exploits the convexity of $F$ and the Lipschitz continuity of
$\nabla F$ to bound $F(w(t+1))-F(w^{*})$. We define the error term
$e(t)=\nabla F(w(t))-g(t)$ and use dual averaging and some results from [8] to
further bound $\mbox{$F(w(t+1))$}-\mbox{$F(w^{*})$}$. The choice of a
nonincreasing sequence of the learning rates $\big{\\{}\alpha(t)\big{\\}}$ for
$t\in[T]$ helps achieve the optimal regret and optimality gap bounds.

###  IV-C Discussion

Our results in Theorem IV.1 and Corollary IV.2 can be interpreted as follows.
As long as gradient staleness $\tau\leq\mathcal{O}\big{(}m^{1/4}\big{)},$ then
the expected regret $\mathbb{E}[R(T)]\leq\mathcal{O}\big{(}\sqrt{m}\big{)}$
and the convergence rate
$\mathbb{E}\big{[}G(T)\big{]}\leq\mathcal{O}\big{(}1/\sqrt{m}\big{)}$. These
are the optimal achievable bounds for each metric. We highlight that in AMB-
DG, we can control the gradient staleness by choosing the appropriate fixed
computation time, $T_{p}$. Since in AMB-DG $\tau=\lceil T_{c}/T_{p}\rceil$, if
we choose $T_{p}$ such that $\lceil
T_{c}/T_{p}\rceil\leq\mathcal{O}\big{(}m^{1/4}\big{)}$, we can guarantee
$\tau\leq\mathcal{O}(m^{1/4})$. Unlike other existing schemes such as those in
[15, 12], the gradient staleness does not depend on the number of workers. It
only depends on the ratio of $T_{c}$ to $T_{p}$. Hence, AMB-DG can scale to
larger cluster sizes without experiencing the performance degradation that can
result from larger staleness due to larger cluster.

The regret bound in (15) and the optimality gap bound in (18) depend on
$\bar{b}$, $\hat{b}$ and the ratio $\bar{b}/\hat{b}$. In a real system, these
parameters would be determined by the characteristics of the workers and their
computing speeds. They further depend on the fixed processing time $T_{p}$. As
might be expected, in our experiments on a real distributed system we observe
that $\bar{b}$ and $\hat{b}$ scale linearly with $T_{p}$. In addition, we
observe that the ratio $\bar{b}/\hat{b}$ is typically bounded by some small
constant. Therefore, both bounds in (15) and (18) are asymptotically dominated
by $m$.

Since $\hat{b}\leq\bar{b}$ with equality if and only if $b(t)=\bar{b}$ for all
$t\in[T]$, the regret bound is minimized when the system observes the same
number of data points in each epoch. This is achieved if there are no
stragglers. Hence, the analysis reveals the penalty incurred due to
stragglers. However, this penalty becomes negligible asymptotically in $m$.
Similarly, the dominant term in the convergence rate bound in (18) is scaled
by $\bar{b}/\hat{b}\geq 1$. When there are no stragglers, that dominant term
is minimized. Hence, the ratio $\bar{b}/\hat{b}$ reflects the impact the
stragglers can have on the convergence rate. This impact diminishes as $m$
gets larger.

##  V Extension to the Fully Decentralized Setting

The previous analysis assume that the time required by the master to aggregate
gradients and update parameters is negligible. In practice, the time spent by
the master to aggregate gradients increases with the number of the workers.
The added delay can be accounted for an increase in the effective
communication time that each worker node experiences. For this reason it can
be difficult to scale the hub-and-spoke model to large networks of nodes.

In contrast, the fully decentralized setting, in which no master node exists,
scales well to large network size avoiding significant increases in
communication time. In this setting, each node communicates with its
neighboring nodes using distributed averaging protocols [33]. During
communication, workers exchange information (e.g., primal and dual variables)
with their neighbors a few times and calculate a weighted-average of the
received information to achieve consensus. If perfect consensus is achieved,
then each worker ends up with the same value which corresponds to the average
of the information prior to communication across all workers. In theory,
achieving perfect consensus may require infinite number of information
exchange. Since this is not possible in practice as workers exchange
information a few times, workers often end up with imperfect consensus.

The model we analyze to investigate the decentralized realization of AMB-DG
consists of two-way noiseless communication channel between certain pairs of
workers. We represent these connections as a graph ${\cal G}(E,V)$ in which
each worker $i\in V$ is a vertex in the graph. Each edge represented two
neighbour nodes, i.e., if workers $i$ and $j$ can communicate with each other
then $(i,j)\in E$. Furthermore, the graph is undirected since if worker $i$
can send to worker $j$, then also worker $j$ can send to worker $i$. This
means that edge $(i,j)$ is the same as the edge $(j,i)$. We assume that
communication time between all connected pairs is equal. Let $Q$ be a matrix
that is positive semi-definite and doubly stochastic (i.e., all columns and
rows sum to $1$) such that $Q_{ij}>0$ if $i=j$ or $(i,j)\in E$, otherwise
$Q_{ij}=0$. The entries of $Q$ are the weights that workers use to scale the
messages received from their neighbours so that nodes can eventually calculate
the average of their messages. $Q$ is sometimes referred to as communication
matrix.

###  V-A AMB-DG Algorithm in the Masterless Setting

The version of the decentralized AMB-DG we analyze is similar to the one
explained in Sec. III. The main difference is that instead of master-worker
communication, we have inter-node communication using a distributed averaging
protocol. This is similar to the model we analyzed for the AMB scheme in [13].

#### Gradient Computation

This step is the same as in the hub-and-spoke setting. Each worker computes
gradients for $T_{p}$ seconds. Due to imperfect consensus, in each epoch,
workers calculate gradients with respect to different optimization parameters.
Let $w_{i}(t)$ be the optimization parameter at worker $i$ in the $t$-th
epoch. The resulting sum of the gradients computed by worker $i$ in epoch $t$
is

$g_{i}(t)=\frac{1}{b_{i}(t)}\sum_{s=1}^{b_{i}(t)}\nabla_{w}f\big{(}w_{i}(t),x_{i}(t,s)\big{)}.$
(19)

#### Consensus Phase

The consensus phase starts immediately after the gradient computation epoch.
At the end of this phase, each worker updates its own optimization parameter.
In each consensus phase, workers spend $T_{c}$ seconds to exchange information
over $r$ rounds of consensus. In the $t$-th phase, worker $i$ begins by
sending message $m_{i}^{(0)}(t)=nb_{i}(t)(z_{i}(t)+g_{i}(t))$. After $k$
rounds of consensus, where $k\in[r]$, worker $i$ has the message

$m_{i}^{(k)}(t)=\sum_{j=1}^{n}Q_{ij}m_{j}^{(k-1)}(t)=\sum_{j=1}^{n}(Q_{ij})^{k}m_{i}^{(0)}(t).$
(20)

For a large enough number of iterations, $r$, and if the graph is connected
and the second largest eigenvalue of $Q$ is strictly less than one, then the
consensus rounds converge to $m_{i}^{(r)}(t)=b(t)[\bar{z}(t)+g(t)]$, where
$\bar{z}(t):=\frac{1}{b(t)}\sum_{i=1}^{n}b_{i}(t)z_{i}(t)$,
$g(t)=\frac{1}{b(t)}\sum_{i=1}^{n}g_{i}(t)$. We note that if the number of
iteration per consensus round increases, then the duration of each consensus
phase becomes larger. In other words, as $r$ increases, $T_{c}$ increases.
This means that if $r$ is too large, then gradient staleness, $\tau$, also
increases since $\tau$ increases with $T_{c}$. We highlight that in the
master-worker setup the communication phases can overlap as can be seen in
Fig.1. In the fully distributed setting, we also allow such an overlap. To
manage multiple messages, each worker $i$ sends the index of the epoch, $t$,
to its neighbours when sending message $m_{i}^{(r)}(t)$.

#### Parameters Update

Worker $i$ updates its dual variable after $r$ rounds of consensus according
to

$z_{i}(t+1)=\frac{1}{b(t)}m_{i}^{(r)}(t)=\bar{z_{i}}(t)+g(t).$ (21)

However, often having a large number of consensus rounds may not be practical
and workers complete a small number of rounds. Therefore, the actual dual
variable update contains an additive error term and can be expressed as

$z_{i}^{(r)}(t+1)=\bar{z_{i}}(t)+g(t)+\epsilon_{i}(t)$ (22)

where the superscript $r$ in $z_{i}^{(r)}$ denotes the number of consensus
rounds and $\epsilon_{i}(t)$ is the consensus error at worker $i$. The
optimization parameter $w_{i}(t)$ is updated according to (4). Let $z(t)$
denote the dual variable with perfect consensus. According to Lemma 1 from our
previous work [13], let $\delta\geq 0$ and $\lambda_{2}(Q)$ be the second
largest eigenvalue of $Q$, then

$\lVert z_{i}^{(r)}(t+1)-z(t+1)\rVert\leq\delta$ (23)

if the number of consensus rounds per worker in each consensus phase satisfies

$r\geq\left\lceil\frac{\log(2\sqrt{n}(1+2J/\delta)}{1-\lambda_{2}(Q)}\right\rceil$
(24)

where $J$ is the Lipschitz parameter of the objective function $F(w)$.

###  V-B Convergence Results

The convergence analysis for the fully distributed case is similar to the one
we developed in Sec. IV for the hub-and-spoke. The only exception is that we
must account for the consensus error. In addition, the optimization parameter
$w(t)$ in the regret in (14) is replaced with $w_{i}(t)$.

######  Theorem V.1.

Assume that the workers process gradients over $T$ epochs during which the
expected number of data points workers sample from $P$ in an i.i.d. manner is
$m$. Let $\hat{b}\neq 0$ and $\bar{b}$ be as defined in Sec. IV. Choosing
$\alpha(t)^{-1}=L+\sqrt{(t+\tau)/\bar{b}}$, the expected regret for AMB-DG in
the fully decentralized setting with deterministic common gradient delay
$\tau$ for all links in each epoch is

$\displaystyle\mathbb{E}[R(T)]\leq\frac{\bar{b}}{\alpha(T+1)}\psi(w^{*})+2\tau
JC\bar{b}\,+$ $\displaystyle 2LJ^{2}(\tau+1)^{2}\big{(}1+\log
T\big{)}\bar{b}^{2}+\sigma^{2}\frac{\bar{b}}{\hat{b}}\sqrt{m}$
$\displaystyle+2J\delta\bar{b}^{3/2}\sqrt{m}.$ (25)

The proof of Theorem V.1 is provided in Appendix B. The regret bound in (25)
is similar to the one obtained in (15). The only difference is that (25) has
an extra term related to the consensus error (i.e., the term with $\delta$).
If workers achieve perfect consensus, then $\delta=0$ and thus (25) reduces to
(15). In contrast, if the communication time per consensus iteration is long
and workers are forced to keep $r$ small, then $\delta$ will be large and
hence the regret bound is larger.

##  VI Numerical Results

In this section we demonstrate the performance of AMB-DG and compare it to
other schemes. We evaluate the performance in two ways. First, we solve a
linear regression problem using a synthetic dataset. We model the per-node
compute time using the shifted exponential distribution. We compare the
performance of AMB-DG with that of AMB under the assumption of long
communication delays. Furthermore, we compare the performance of AMB-DG with a
fixed minibatch delayed-gradient-based scheme called $K$-batch async [34, 17].
$K$-batch async is a suitable baseline to compare AMB-DG with since both
schemes ensure that workers never idle. Hence, they both use stale gradients.
Moreover, both schemes exploit all jobs completed by all workers. In $K$-batch
async, in each epoch each worker calculates $\tilde{b}/K$ gradients and
submits their sum to the master. Here $\tilde{b}$ is the per-epoch fixed
minibatch size and $K$ is an integer that divides $\tilde{b}$. The master
updates the parameter $w$ after receiving $K$ messages from the workers. These
$K$ messages need not be from distinct workers. Faster workers can contribute
more messages. Second, we compare the performance of AMB-DG with that of
$K$-batch async when training a neural network to classify images from the
CIFAR-10 dataset [35]. We run these neural network experiments on SciNet which
is an academic high performance computing cluster. All experiments are
repeated $10$ times and the average performance is reported. We note that the
purpose of these experiments is to compare the performance of our approach
that is based on fixing the compute time with the that of the state-of-the-art
approach that uses a fixed minibatch per epoch. Methods that speed up
convergence when using delayed gradients such as those found in [36] and [37]
can also be applied to AMB-DG.

###  VI-A Linear regression

####  VI-A1 Dataset

For the linear regression problem we generate the global optimizer vector
$w^{*}\in\mathbb{R}^{d}$ from the multivariate Gaussian ${\cal N}({\bf 0,{\bf
I})}$. In each compute epoch, $t$, worker $i$ receives a stream of a sequence
of inputs of the form $(\zeta(t,s),y_{i}(t,s))$. If the $i$-th node observes
$b_{i}(t)$ data points in epoch $t$ then $1\leq s\leq b_{i}(t)$. The data
points $\zeta_{i}(t,s),y_{i}(t,s)$ are generated as following. First, we
generate $\xi_{i}(t,s)\in\mathbb{R}^{d}$ in an i.i.d. manner according to
Gaussian ${\cal N}(\mathbf{0},\mathbf{I})$. Then the labels $y_{i}(t,s)$ are
defined as $y_{i}(t,s)=\zeta_{i}(t,s)^{T}w^{*}+\epsilon_{i}(t,s)$, where $T$
denotes the transpose operation and the $\epsilon_{i}(t,s)$ are i.i.d. zero-
mean Gaussian noise samples with variance $\sigma^{2}$. In our simulations, we
choose $d=10^{4}$ and $\sigma^{2}=10^{-3}$.

####  VI-A2 Objective function

The objective function the system is designed to minimize is

$F(w)=\sum_{t}\sum_{i=1}^{n}\sum_{s=1}^{b_{i}(t)}\big{[}\zeta_{i}(t,s)^{T}w-y_{i}(t,s)\big{]}^{2}.$
(26)

We assume that the system initializes the optimization variable to the all-
zero vector $w(1)=0$. In each worker’s compute epoch $t$, the worker
calculates gradients $g_{i}(t)$ according to

$g_{i}(t)=\sum_{s=1}^{b_{i}(t)}\Big{[}\zeta_{i}(t,s)^{T}w(t)-y_{i}(t,s)\Big{]}\zeta_{i}(t,s).$
(27)

The error rate achieved in the $t$-th epoch is calculated as

${\rm Err}(t)=\frac{\lVert A[w(t)-w^{*}]\rVert^{2}}{\lVert Aw^{*}\rVert^{2}}$
(28)

where $A$ is an $N\times d$ matrix whose rows are i.i.d. ${\cal
N}(\mathbf{0},\mathbf{I})$ and $\lVert.\rVert$ is the $l_{2}$ norm. We choose
$N=250000$. Since $w(1)=0$, the initial error rate is always ${\rm Err}(1)=1$.

####  VI-A3 Shifted exponential model

To evaluate performance versus wall clock time, we model the time that each
node takes to calculate a fixed local minibatch of size $b$ as random variable
that follows a shifted exponential distribution. Exponential and shifted
exponential distributions are widely used in the literature to model variable
compute times [34, 16]. We use $T_{i}(t)$ to denote the time taken by worker
$i$ to calculate $b$ gradients in the $t$-th epoch. The probability density
function of $T_{i}(t)$ is

$f_{T_{i}}(\tau)=\lambda e^{-\lambda(\tau-\xi)},\,\,\tau\geq\xi\geq 0$ (29)

where $\xi$ is the minimum duration a single worker takes to calculates $b$
gradients while $\lambda^{-1}+\xi$ is the expected time to calculate $b$
gradients.

Conditioned on $T_{i}(t)$, the worker is assumed to make linear progress
through the dataset, i.e., it takes $kT_{i}(t)/b$ to calculate $k$ gradients
(note that $k\geq b$ is allowed). In our simulations, we choose $\lambda=2/3$
and $\xi=1$. Per our model, in both AMB and AMB-DG, node $i$ is given a fixed
time $T_{p}$ to compute $b_{i}(t)$ gradients in epoch $t$. Per our assumptions
above, $b_{i}(t)=bT_{p}/T_{i}(t)$, for some fixed $b\leq\mathbb{E}[b_{i}(t)]$.
In our simulations, we assume a network of $n=10$ workers and that
$T_{p}=2.5$. We choose $b=60$ to ensure that the expected minibatch per epoch
is $\mathbb{E}[b(t)]\geq nb=600$. This lower bound is according to Theorem 7
of [13]. Moreover, in our examples, we set $T_{c}=10$.

####  VI-A4 Performance evaluation of AMB-DG vs. AMB

Figure 2 compares the performance of AMB-DG with that of AMB. The two plots in
Fig. 2 compare the performance of each scheme with respect to the number of
epochs as well as wall clock time.

Figure 2a shows that the per-epoch performance of AMB is better than that of
AMB-DG. This is expected since AMB uses “fresh” gradients to update the
optimization parameter in each epoch whereas AMB-DG uses stale ones. However,
when comparing the performance against the wall clock time, we observe in Fig.
2b that AMB-DG is almost three times faster than AMB. In particular, AMB-DG
achieves an error rate of $0.35$ at $55$ ${\rm s}$ whereas AMB takes about
$182$ ${\rm s}$ to achieve the same error rate. We highlight that (akin to
AMB) the gradients in the first epoch of AMB-DG do not suffer from stalenesss
since they are calculated with respected $w(1)$. Therefore, both schemes
achieve similar error rates after the first epoch. In AMB-DG, gradient
staleness increases gradually until the fifth epoch from which point $\tau=4$.
This higher staleness explains why, as can be observed in Fig.2a, AMB-DG
achieves higher per-epoch error rates especially from the fifth epoch onward.

The comparison above highlights one of the shortcomings of AMB. During
communications, AMB workers stay idle. This can slow convergence when the
communication time is long. On the other hand, AMB-DG exploits the
communication time to process additional gradients which, albeit being stale,
help improve convergence speed. The improvement becomes especially pronounced
when communication delays are long. Note that in AMB, except for the first
update, the master updates the optimization parameters every
$T_{p}+T_{c}=12.5$ ${\rm s}$ whereas in AMB-DG the parameters are updated
every $T_{p}=2.5$ ${\rm s}$. The first update in both schemes takes place
after $T_{p}+\frac{1}{2}T_{c}=7.5$ ${\rm s}$. Hence, the epoch duration in AMB
is larger than that in AMB-DG. As the communication time is increased, this
difference in epoch durations increases. Conversely, as the communication time
approaches zero, the epoch duration in both schemes become identical. In this
limiting case, the gradient delay in AMB-DG goes to $\tau=0$ which means that
AMB-DG reduces to AMB.

(a) Per-epoch performance. (b) Wall clock time performance.

Fig. 2: Performance of AMB versus AMB-DG.

####  VI-A5 Performance comparison of AMB-DG with $K$-batch async

In this experiment we again model the time that takes worker $i$ to calculate
$b=60$ gradients in the $t$-th epoch according to the same shifted exponential
distribution in (29). We set $\lambda=2/3$ and $\xi=1$ as before. We run the
simulations for $n=10$ workers and let $T_{c}=10$. For AMB-DG, we set
$T_{p}=2.5$. Thus, the expected minibatch per epoch in AMB-DG is roughly
$600$. For the $K$-batch async, each worker computes $60$ gradients per epoch
and we set $K=10$. Hence, the master updates the optimization parameters
whenever it receives $\tilde{b}=600$ gradients. Fig. 3 illustrates that AMB-DG
achieves faster convergence when compared to $K$-batch async. For instance,
the error rate achieved by AMB-DG after almost $30$ ${\rm s}$ is achieved by
$K$-Batch Async at around $47$ ${\rm s}$ meaning that AMB-DG is over $1.5$
times faster than K-Batch Async. Observe that the first update takes a long
time due to the long communication delay. This impacts both schemes. If we
ignore this initial shared delay and re-scale time, AMB-DG becomes about $1.7$
times faster than $K$-Batch Async.

Fig. 3: AMB-DG vs $K$-batch async.

To gain further insights into why AMB-DG outperforms $K$-batch async, we look
at the distribution of gradient staleness in both cases. As explained in Sec.
III, the gradient staleness suffered by AMB-DG after the first few epochs is
$\tau=T_{c}/T_{p}=4$. On the other hand, the distribution of gradient
staleness experienced by $K$-batch async as depicted in Figure 4 shows that
almost $80\%$ of the gradients received by the master are delayed by five or
more steps. Therefore, although the average per-epoch minibatch size and the
average per-update time in both schemes are similar, AMB-DG suffers less
staleness when compared to $K$-batch async and thus converges faster.

Fig. 4: Gradient staleness distribution in $K$-batch async.

###  VI-B CIFAR-10 Image Classification

Although our analysis assumed convex smooth objective functions, we complement
our work by presenting results for a nonconvex image classification problem.
We train a neural network to classify CIFAR-10 images. We work with the neural
network architecture of [38] that consists of $14$ layers: $9$ convolutional
layers followed by $5$ fully connected layers. The loss function that we
optimize is the cross-entropy function. We run our experiments on the SciNet
using $n=4$ workers and a master node. Each node in the SciNet cluster is
equipped with a total of 40 Intel Skylake CPU cores and 202 GB of memory.
Since we use a high performance computing platform, the inter-node
communication time is much smaller than the per-epoch compute time. Therefore,
we artificially delay communication to mimic operating environments in which
communication time is long. We induce $T_{c}=10$ ${\rm s}$ while we choose
$T_{p}=10$ ${\rm s}$ for AMB-DG. For $K$-batch async, we set $b=60$ and $K=4$.
The per-epoch minibatch size is in $K$-batch async is $240$ which is
approximately the same as the average minibatch per epoch in AMB-DG. Figure 5
compares the performance of both schemes when $T_{c}=10$. It illustrates that
AMB-DG achieves a lower training loss and higher testing accuracy than that
achieved by $K$-batch async when the neural network is trained for the same
duration. In particular, the training loss achieved by AMB-DG after $4$ hours
is achieved by $K$-batch async after almost $7.5$ hours showing that AMB-DG is
about $1.9$ times faster than $K$-batch async. Similarly, the testing accuracy
achieved by $K$-batch async after about $7.5$ hours is already achieved by
AMB-DG after only $4$ hours. We remind the reader that the reported
performance is an average of $10$ experiments and that the purpose of these
experiments is to compare the wall-clock performance of our approach to the
existing fixed minibatch approach. The aim is not to build a deep learning
model that achieves higher training error or testing accuracy than the
existing best in class so, for example, we did not implement dropout or data
augmentation in our simulations.

(a) Training error. (b) Testing accuracy.

Fig. 5: AMB-DG vs. $K$-Batch Async for CIFAR-10 with induced $T_{c}=10$ sec.

###  VI-C Variable Minibatches of AMB-DG in a Real Distributed System

In our analysis in Sec. IV, we observe that the regret depends on several
parameters that are system specific. These are the minimum per-epoch minibatch
$\hat{b}$ and the average minibatch $\bar{b}$. To understand how these
parameters scale in real distributed systems, we ran our algorithm on SciNet
using the MNIST dataset [39] for several values of the processing time,
$T_{p}$, ranging from $200$ ${\rm\mu s}$ to $2000$ ${\rm\mu s}$. For each
choice of $T_{p}$, we ran the algorithm for $200$ epochs and recorded the
minimum $\hat{b}$ and the average $\bar{b}$ minibatches across these $200$
epochs. Fig. 6 shows that these parameters scale almost linearly with $T_{p}$.
Hence, for a given $T_{p}$, these parameters are bounded and thus the regret
bound in (15) and the convergence rate in (18) are dominated by $m$
asymptotically as discussed in Sec. IV-C. Furthermore, the ratio
$\bar{b}/\hat{b}$ is observed to be bounded above by $\gamma<1.1$ as can be
read from the right y-axis in Fig. 6.

Fig. 6: $\hat{b},\bar{b}$ and $\bar{b}/\hat{b}$ of AMB-DG.

##  VII Conclusion

In this paper, we present the Anytime Minibatch with Delayed Gradients (AMB-
DG) algorithm. AMB-DG is a variable-minibatch scheme for online distributed
stochastic optimization. In AMB-DG, workers are given a fixed compute time to
calculate as many gradients as they can before submitting the sum of the
computed gradients, along with their local minibatch size, to the master.
Following each submission, workers continue to calculate gradients using the
existing optimization parameters, without waiting for updates from the master.
As a result, the master uses stale gradients to update the optimization
parameters. Our theoretical analysis shows that for smooth convex objective
functions, AMB-DG achieves the optimal regret bound of ${\cal O}(\sqrt{m})$
and the optimal convergence rate of ${\cal O}(1/\sqrt{m})$, where $m$ is the
total number of samples observed by the entire system and that the impact of
gradient delay is negligible asymptotically in the number of samples observed,
$m$. We compare AMB-DG with AMB under long communication delay setting when
solving a linear regression problem and observe that AMB-DG outperforms AMB in
terms of wall clock time convergence. We also compare the performance of AMB-
DG with that of $K$-batch async algorithm for the same linear regression
problem and observe that AMB-DG achieves lower staleness and faster
convergence in wall clock time. We also implement AMB-DG and $K$-batch async
on a real distributed system to train a neural network using the CIFAR-10
dataset. We observe that AMB-DG is almost $2$ times faster.

In our analysis we assumed fixed communication delay. As a future extension of
this work, one can consider a more interesting regime of operation in which
the communication time is random. Furthermore, this paper analyzed AMB-DG for
the master-worker distributed setting. AMB-DG can be extended to a fully
decentralized setup and its performance and convergence can be analyzed as in
[13].

##  VIII Acknowledgement

We thank Jason Lam and Zhenhua Hu of Huawei Technologies Canada and Tharindu
Adikari from the University of Toronto for technical discussions. We thank
Compute Canada for providing their high performance computing platform to run
our experiments throughout this project.

## References

  * [1] H. Al-Lawati, N. Ferdinand, and S. C. Draper, “Anytime minibatch with stale gradients,” in _Proc. of Conf. on Inf. Sciences and Sys._ , Mar. 2019, pp. 1–5.
  * [2] H. Al-Lawati and S. C. Draper, “Anytime minibatch with delayed gradients: System performance and convergence analysis,” in _Proc. of Int. Conf. on Acoustics, Speech, and Sig. Proc._ , 2020.
  * [3] J. Chen, R. Monga, S. Bengio, and R. Jozefowicz, “Revisiting distributed synchronous SGD,” in _Proc. of Int. Conf. on Learning and Representations_ , 2016.
  * [4] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in _Advances in Neural Inf. Process. Sys._ , 2012, pp. 1097–1105.
  * [5] K. Simonyan and A. Zisserman., “Very deep convolutional networks for large-scale image recognition,” in _Proc. of Int. Conf. on Learning and Representations_ , 2015.
  * [6] M. A. Zinkevich, M. Weimer, A. Smola, and L. Li, “Parallelized stochastic gradient descent,” in _Advances in Neural Inf. Process. Sys._ , 2010, pp. 2595–2603.
  * [7] O. Dekel, R. Gilad-Bachrach, O. Shamir, and L. Xiao, “Optimal distributed online prediction using mini-batches,” _Journal of Machine Learning Research_ , pp. 165–202, Jan. 2012.
  * [8] A. Agarwal and J. C. Duchi, “Distributed delayed stochastic optimization,” in _Advances in Neural Inf. Process. Sys._ , 2011, pp. 873–881.
  * [9] L. Bottou and Y. L. Cun, “Large scale online learning,” in _Advances in Neural Inf. Process. Sys._ , 2004, pp. 217–224.
  * [10] J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, Q. V. Le, and A. Y. Ng, “Large scale distributed deep networks,” in _Advances in Neural Inf. Process. Sys._ , 2012, pp. 1223–1231.
  * [11] J. C. Duchi, A. Agarwal, and M. J. Wainwright, “Dual averaging for distributed optimization: Convergence analysis and network scaling,” _IEEE Trans. on Automatic Cont._ , pp. 592–606, Mar. 2012.
  * [12] N. Feng, B. Recht, C. Re, and S. J. Wright, “Hogwild: A lock-free approach to parallelizing stochastic gradient descent,” in _Advances in Neural Inf. Process. Sys._ , 2011, pp. 693–701.
  * [13] N. Ferdinand, H. Al-Lawati, S. C. Draper, and M. Nokleby, “Anytime minibatch: Exploiting stragglers in online distributed optimization,” in _Proc. of Int. Conf. on Learning Representations_ , 2019.
  * [14] P. Jain, S. M. Kakade, R. Kidambi, P. Netrapalli, and A. Sidford, “Accelerating stochastic gradient descent for least squares regression,” _ArXiv e-prints_ , Apr. 2017.
  * [15] M. Zinkevich, J. Langford, and A. J. Smola, “Slow learners are fast,” in _Advances in Neural Inf. Process. Sys._ , 2009, pp. 2331–2339.
  * [16] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding up distributed machine learning using codes,” _IEEE Trans. on Inf. Theory_ , pp. 1514–1529, Mar. 2018.
  * [17] X. Lian, Y. Huang, Y. Li, and J. Liu, “Asynchronous parallel stochastic gradient for nonconvex optimization,” in _Advances in Neural Inf. Process. Sys._ , 2015, pp. 2737–2745.
  * [18] M. Nokleby and W. U. Bajwa, “Distributed mirror descent for stochastic learning over rate-limited networks,” in _Proc. of IEEE Int. Workshop on Comp.Advances in Multi-Sensor Adaptive Process._ , Dec. 2017, pp. 1–5.
  * [19] I. T. Konstantinos and M. G. Rabbat, “Efficient distributed online prediction and stochastic optimization with approximate distributed averaging,” _IEEE Trans. Signal and Inf. Process. Nets_ , pp. 489–506, 2016.
  * [20] J. Dean and L. A. Barroso, “The tail at scale,” _Communications of the ACM_ , pp. 74–80, 2013.
  * [21] P. Garraghan, X. Ouyang, R. Yang, D. McKee, and J. Xu, “Straggler root-cause and impact analysis for massive-scale virtualized cloud datacenters,” _IEEE Trans. on Services Computing_ , pp. 91–104, Jan. 2019.
  * [22] M. Zaharia, A. Konwinski, A. D. Joseph, R. Katz, and I. Stoica, “Improving mapreduce performance in heterogeneous environments,” in _Proc. of USENIX Conf. on Operating Sys. Design and Imp._ , 2008.
  * [23] J. Tsitsiklis, D. Bertsekas, and M. Athans, “Distributed asynchronous deterministic and stochastic gradient optimization algorithms,” _IEEE Trans. on Automatic Cont._ , pp. 803–812, Sep. 1986.
  * [24] J. Duchi, M. I. Jordan, and B. McMahan, “Estimation, optimization, and parallelism when data is sparse,” in _Advances in Neural Inf. Process. Sys._ , 2013, pp. 2832–2840.
  * [25] Q. Ho, J. Cipar, H. Cui, S. Lee, J. K. Kim, P. B. Gibbons, G. A. Gibson, G. Ganger, and E. P. Xing, “More effective distributed ml via a stale synchronous parallel parameter server,” in _Advances in Neural Inf. Process. Sys._ , 2013, pp. 1223–1231.
  * [26] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, “QSGD: Communication-efficient SGD via gradient quantization and encoding,” in _Advances in Neural Inf. Process. Sys._ , 2017.
  * [27] T. Chen, G. Giannakis, T. Sun, and W. Yin, “LAG: Lazily aggregated gradient for communication-efficient distributed learning,” in _Advances in Neural Inf. Process. Sys._ , 2018, pp. 5050–5060.
  * [28] J. Bernstein, Y.-X. Wang, K. Azizzadenesheli, and A. Anandkumar, “signSGD: Compressed optimisation for non-convex problems,” in _Proc. of Machine Learning Research_ , 2018, pp. 560–569.
  * [29] J. Wangni, J. Wang, J. Liu, and T. Zhang, “Gradient sparsification for communication-efficient distributed optimization,” in _Advances in Neural Inf. Process. Sys._ , 2018, pp. 1299–1309.
  * [30] H. R. Feyzmahdavian, A. Aytekin, and M. Johansson, “An asynchronous mini-batch algorithm for regularized stochastic optimization,” _IEEE Trans. on Automatic Cont._ , pp. 3740–3754, Dec. 2016.
  * [31] Y. Nesterov, “Primal-dual subgradient methods for convex problems,” _Math. Program._ , pp. 221–259, Apr. 2009.
  * [32] L. Xiao, “Dual averaging method for regularized stochastic learning and online optimization,” in _Advances in Neural Inf. Process. Sys._ , 2009, pp. 2116–2124.
  * [33] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Analysis and optimization of randomized gossip algorithms,” in _Proc. of IEEE Conf. on Decision and Cont._ , Dec. 2004, pp. 5310–5315.
  * [34] S. Dutta, G. Joshi, S. Ghosh, P. Dube, and P. Nagpurkar, “Slow and stale gradients can win the race: Error-runtime trade-offs in distributed SGD,” in _Proc. of Int. Conf. on Artificial Intelligence and Statistics_ , 2018, pp. 803–812.
  * [35] A. Krizhevsky, V. Nair, and G. Hinton, “The CIFAR-10 dataset,” _online: http://www. cs. toronto. edu/kriz/cifar. html_ , vol. 55, 2014.
  * [36] S. Zheng, Q. Meng, T. Wang, W. Chen, N. Yu, Z. Ma, and T. Liu, “Asynchronous stochastic gradient descent with delay compensation,” in _Proc. of the Int. Conf. on Machine Learning_ , 2017.
  * [37] W. Zhang, S. Gupta, X. Lian, and J. Liu, “Staleness-aware async-SGD for distributed deep learning,” in _Proc. of Int. Joint Conf. on Artificial Intelligence_ , 2016.
  * [38] C. Park. CIFAR10 image classification with tensorflow. [Online]. Available: https://github.com/deep-diver/CIFAR10-img-classification-tensorflow/
  * [39] Y. LeCun and C. Cortes, “MNIST handwritten digit database,” 2010. [Online]. Available: http://yann.lecun.com/exdb/mnist/

##  Appendix A AMB-DG Convergence Proofs

###  A-A Proof of Theorem IV.1

The proof of Theorem IV.1 uses the convexity and Lipschitz smoothness
properties of $F(w)$ and $f(w,x)$. We also use the following three lemmas to
prove some intermediate results. Lemma A.1 is from [31] and Lemmas A.2 and A.3
are from [8].

######  Lemma A.1.

If $x^{+}=\arg\min_{u\in{\cal X}}\langle z,u\rangle+A\psi(u)$, then for any
$x,z\in\mathcal{X}$

$\langle z,x\rangle+A\psi(x)\geq\langle
z,x^{+}\rangle+A\psi(x^{+})+AD_{\psi}(x,x^{+}),$

where $D_{\psi}(x,x^{+})$ is the Bregman divergence between $x$ and $x^{+}$.

######  Lemma A.2.

Let the assumptions of Sec. IV-A hold. Then for any sequence $w(t)$,

$\displaystyle\sum_{t=1}^{T}\big{\langle}\nabla F(w(t))-\nabla F(w(t-\tau)),$
$\displaystyle w(t+1)-w^{*}\big{\rangle}$
$\displaystyle\leq\frac{L}{2}\sum_{t=1}^{T}\big{\lVert}w(t-\tau)$
$\displaystyle-w(t+1)\big{\rVert}^{2}+2\tau JC.$

Consequently, if $\mathbb{E}\big{[}\lVert w(t)-w(t+1)\rVert^{2}\big{]}\leq
4J^{2}\kappa(t)^{2}$ for a nonincreasing sequence $\kappa(t)$,

$\displaystyle\mathbb{E}\Bigg{[}\sum_{t=1}^{T}\big{\langle}\nabla
F(w(t))-\nabla F(w(t-\tau))$ $\displaystyle,w(t+1)-w^{*}\big{\rangle}\Bigg{]}$
$\displaystyle\leq 2LJ^{2}(\tau+1)^{2}$
$\displaystyle\sum_{t=1}^{T}\kappa(t-\tau)^{2}+2\tau JC.$

######  Lemma A.3.

Let the assumptions of Sec.IV-A hold. Let $\alpha(t)^{-1}=L+\eta(t)$ for
$\eta(t)>0$ and $L\geq 0$. Then $\mathbb{E}\Big{[}\lVert
w(t)-w(t+1)\rVert^{2}\Big{]}\leq\frac{4J^{2}}{\eta(t)^{2}}$.

The convergence of our scheme is impacted by the following two factors. First,
gradients are calculated with respect to $f(w,x)$ rather than $F(w)$.
Furthermore, in each epoch $t$, the master receives the gradients $g(t)$ which
are delayed by $\tau$ steps. We define the error term $e(t)$.

$e(t):=\nabla F(w(t))-g(t)$ (30)

First, we look at $F(w(t))-F(w^{*})$ and develop some bounds.

$\displaystyle F(w(t))-F(w^{*})$ $\displaystyle\leq\big{\langle}\nabla
F(w(t)),w(t)-w^{*}\big{\rangle}$ $\displaystyle=\langle\nabla F(w(t)),$
$\displaystyle w(t+1)-w^{*}\rangle$ (31) $\displaystyle+\langle\nabla
F(w(t)),w(t)-w(t+1)\rangle$ (32) $\displaystyle\leq\langle\nabla F(w(t)),$
$\displaystyle w(t+1)-w^{*}\rangle+F(w(t))$ $\displaystyle-F$
$\displaystyle(w(t+1))+\frac{L}{2}\big{\lVert}w(t)-w(t+1)\big{\rVert}^{2},$
(33)

where (31) follows from the convexity of $F$ and (33) from the $L$-Lipschitz
continuity of $\nabla F$, cf., (10).

From (30), $\nabla F(w(t))=e(t)+g(t)$. Substituting this in (33) and
rearranging, we get a bound for $F(w(t+1))-F(w^{*})$.

$\displaystyle F(w(t+1))-F(w^{*})$ $\displaystyle\leq\langle
e(t)+g(t),w(t+1)-w^{*}\rangle$
$\displaystyle+\frac{L}{2}\big{\lVert}w(t)-w(t+1)\big{\rVert}^{2}$ (34)
$\displaystyle=\langle e(t),w(t+1)-$ $\displaystyle w^{*}\rangle+\langle
g(t),w(t+1)-w^{*}\rangle$
$\displaystyle+\frac{L}{2}\big{\lVert}w(t)-w(t+1)\big{\rVert}^{2}$ (35)
$\displaystyle=\langle z(t+1)-z(t),$ $\displaystyle w(t+1)-w^{*}\rangle$
$\displaystyle+\langle e(t),w(t+1)$
$\displaystyle-w^{*}\rangle+\frac{L}{2}\big{\lVert}w(t)-w(t+1)\big{\rVert}^{2}$
(36) $\displaystyle=\langle z(t+1),w(t+$ $\displaystyle
1)-w^{*}\rangle-\langle z(t),w(t+1)-w^{*}\rangle$ $\displaystyle+\langle
e(t),w(t+1)$
$\displaystyle-w^{*}\rangle+\frac{L}{2}\big{\lVert}w(t)-w(t+1)\big{\lVert}^{2},$
(37)

where (36) follows by observing that $g(t)=z(t+1)-z(t)$ from (3).

Recall that $w(t)=\arg\min_{w\in{\cal W}}\left\\{\langle
z(t),w\rangle+\alpha(t)^{-1}\psi(w)\right\\}$ according to (4). We apply Lemma
A.1 to (37) where we replace $x^{+}$, $x$, $z$ and, $A$ from Lemma A.1 with
$w(t)$, $w(t+1)$, $z(t)$, and $\alpha(t)^{-1}$, respectively, and re-arrange
to get

$\displaystyle-\langle z(t),w(t+1)-w^{*}\rangle\leq$ $\displaystyle-\langle
z(t),w(t)-w^{*}\rangle$ $\displaystyle+\frac{1}{\alpha(t)}$
$\displaystyle\big{[}\psi(w(t+1))-\psi(w(t))\big{]}$
$\displaystyle-\frac{1}{\alpha(t)}D_{\psi}\big{(}w(t+1),w(t)\big{)}.$ (38)

Substitute (38) in (37) yields

$\displaystyle F(w(t+1))-F(w^{*})\leq$ $\displaystyle\langle
z(t+1),w(t+1)-w^{*}\rangle$ $\displaystyle-\langle z(t),w(t)-w^{*}\rangle$
$\displaystyle+\frac{1}{\alpha(t)}\big{[}\psi(w(t+1))-\psi(w(t))\big{]}$
$\displaystyle+\langle e(t),w(t+1)-$ $\displaystyle
w^{*}\rangle-\frac{1}{\alpha(t)}D_{\psi}\big{(}w(t+1),w(t)\big{)}$
$\displaystyle+\frac{L}{2}\lVert w(t)-w(t+1)\rVert^{2}.$ (39)

Since $\alpha(t)$ is a sequence of positive nonincreasing step sizes, define a
positive nondecreasing sequence $\eta(t)$ such that
$\alpha(t)^{-1}=L+\eta(t)$. As will be seen later, $\eta(t)$ will subsequently
be optimized to achieve the desired regret bound. Typically, $\eta(t)$ is set
proportional to $\sqrt{t+\tau}$. Substituting $L+\eta(t)$ for $\alpha(t)^{-1}$
and observing that $\frac{1}{2}\lVert w(t)-w(t+1)\rVert^{2}\leq
D_{\psi}\big{(}w(t+1),w(t)\big{)}$ since $\psi(x)$ is strongly convex, and
then noticing that the $LD_{\psi}(w(t+1),w(t))$ term cancels. Equation (39)
then becomes

$\displaystyle F(w(t+1))-F(w^{*})\leq$ $\displaystyle\langle
z(t+1),w(t+1)-w^{*}$ $\displaystyle\rangle-\langle z(t),w(t)-w^{*}\rangle$
$\displaystyle+\langle e(t),w(t+1)-w^{*}\rangle$
$\displaystyle+\frac{1}{\alpha(t)}\big{[}\psi(w(t+1))-\psi(w(t))\big{]}$
$\displaystyle-\eta(t)D_{\psi}\big{(}w(t+1),w(t)\big{)}.$ (40)

Now we sum both sides of (40) from $t=1$ to $t=T$ and note that the term
$\langle z(1),w(1)-w^{*}\rangle=0$ since $z(1)=0$ to get

$\displaystyle\sum_{t=1}^{T}F\big{(}w(t+1)\big{)}-F(w^{*})$
$\displaystyle\leq$ $\displaystyle\big{\langle}z(T+1),w(T+1)-w^{*}$
$\displaystyle\big{\rangle}+\frac{\psi(w(T+1))}{\alpha(T)}$
$\displaystyle-\frac{\psi(w(1))}{\alpha(1)}+\sum_{t=2}^{T}\psi(w(t))$
$\displaystyle\Big{[}\frac{1}{\alpha(t-1)}-\frac{1}{\alpha(t)}\Big{]}$
$\displaystyle-\sum_{t=1}^{T}\eta(t)D_{\psi}\big{(}w(t+1),w(t$
$\displaystyle)\big{)}+\sum_{t=1}^{T}\langle e(t),w(t+1)-w^{*}\rangle$ (41)
$\displaystyle\leq\big{\langle}z(T+1),w(T+1)-$ $\displaystyle
w^{*}\big{\rangle}+\frac{\psi(w(T+1))}{\alpha(T+1)}$
$\displaystyle-\sum_{t=1}^{T}\eta(t)D_{\psi}\big{(}w(t+1),w(t$
$\displaystyle)\big{)}+\sum_{t=1}^{T}\langle e(t),w(t+1)-w^{*}\rangle$ (42)
$\displaystyle\leq\frac{\psi(w^{*})}{\alpha(T+1)}-\sum_{t=1}^{T}\eta(t)D_{\psi}$
$\displaystyle\big{(}w(t+1),w(t)\big{)}$ $\displaystyle+$
$\displaystyle\sum_{t=1}^{T}\langle e(t),w(t+1)-w^{*}\rangle$ (43)

where (42) follows from the facts that
$\frac{1}{\alpha(t-1)}-\frac{1}{\alpha(t)}\leq 0$ (and hence
$\alpha(T)\geq\alpha(T+1)$) and $\psi(w)\leavevmode\nobreak\
\geq\leavevmode\nobreak\ 0$ so we can drop the negative term
$-\frac{\psi(w(1))}{\alpha(1)}$. Equation (43) follows from that
$\big{\langle}z(T+1),w(T+1)-w^{*}\rangle+\frac{\psi(w(T+1))}{\alpha(T+1)}\leq\frac{\psi(w^{*})}{\alpha(T+1)}$.
To see this, observe that according to dual average rule
$w(T+1)=\arg\min_{w\in\mathcal{W}}\Big{\\{}\big{\langle}z(T+1),w\big{\rangle}+\frac{1}{\alpha(T+1)}\psi(w)\Big{\\}}$.
So, if we substitute $w^{*}$ for $w(T+1)$ in the first two term on the right
hand side of (42), the expression will be larger. This substitution eliminates
the inner product term and we get (43).

Next, we look at the last term in (43); i.e., $\sum_{t=1}^{T}\langle
e(t),w(t+1)-w^{*}\rangle$.

$\displaystyle\sum_{t=1}^{T}\langle e(t),w(t+1)-w^{*}\rangle=$
$\displaystyle\sum_{t=1}^{T}\langle\nabla F(w(t))-\nabla F(w(t$
$\displaystyle-\tau)),w(t+1)-w^{*}\rangle$
$\displaystyle+\sum_{t=1}^{T}\langle\nabla F(w(t-\tau))$
$\displaystyle-g(t),w(t+1)-w^{*}\rangle.$ (44)

Using Lemma A.2, and noting that from Lemma A.3 that $\mathbb{E}\Big{[}\lVert
w(t)-w(t+1)\rVert^{2}\Big{]}\leq\frac{4J^{2}}{\eta(t)^{2}}$, we can bound the
expected value of the first term on the right hand side of (44) as

$\displaystyle\mathbb{E}\Bigg{[}\sum_{t=1}^{T}$ $\displaystyle\langle\nabla
F(w(t))-\nabla F(w(t-\tau)),w(t+1)-w^{*}\rangle\Bigg{]}$ $\displaystyle\leq
2\tau JC+2LJ^{2}(\tau+1)^{2}\sum_{t=1}^{T}\frac{1}{\eta(t-\tau)^{2}},$ (45)

where the nonincreasing sequence $\kappa(t)$ in Lemma A.2 is replaced by
$\frac{1}{\eta(t)}$ since $\eta(t)$ is nondecreasing.

Now, we look at the second term in (44)

$\displaystyle\langle\nabla F(w(t-\tau))-g(t),w(t+1)-w^{*}\rangle$
$\displaystyle=\langle\nabla F(w(t-\tau))-g(t),w(t)-w^{*}\rangle$
$\displaystyle+\langle\nabla F(w(t-\tau))-g(t),$ $\displaystyle
w(t+1)-w(t)\rangle$ (46) $\displaystyle\leq\langle\nabla
F(w(t-\tau))-g(t),w(t)-w^{*}\rangle$ $\displaystyle+$
$\displaystyle\frac{1}{2\eta(t)}\big{\lVert}\nabla
F(w(t-\tau))-g(t)\big{\rVert}^{2}+\frac{\eta(t)}{2}$ $\displaystyle\lVert
w(t+1)-w(t)\rVert^{2}.$ (47)

The last inequality follows from the Fenchel-Young inequality which states
that for every $u,v\in\mathbb{R}^{n}$ given a real valued convex function
$h(u)$ and its convex conjugate $h^{*}(u)$, the inner product $\langle
u,v\rangle\leq h(u)+h^{*}(v)$. In (47), we let $u=\nabla F(w(t-\tau))-g(t)$,
$v=w(t+1)-w(t)$, $h(u)=\frac{\eta(t)}{2}\lVert u\rVert^{2}$ and
$h^{*}(v)=\frac{1}{2\eta(t)}\lVert v\rVert^{2}$. Note that conditioned on
$g(1),g(2),...,g(t-1)$, $w(t)$ is not random and hence $w(t)$ does not depend
on $\nabla F(w(t-\tau))-g(t)$. Furthermore, since by definition $\nabla
F(w)=\mathbb{E}\big{[}\nabla f(w,x)\big{]}$, then $\mathbb{E}\big{[}\nabla
F(w(t-\tau))-g(t)\big{]}=0$. Hence, the first term on the right hand side of
(47) has zero expectation. Due to the bounded variance assumption, and
assuming that the master receives $b(t)$ gradients in epoch $t$,

$\displaystyle\mathbb{E}\Big{[}\big{\lVert}\nabla
F(w(t-\tau))-g(t)\big{\rVert}^{2}\big{|}b(t)\Big{]}$ $\displaystyle=$
$\displaystyle\mathbb{E}\Big{[}\big{\lVert}\nabla
F(w(t-\tau))-\frac{1}{b(t)}\sum_{i=1}^{n}\sum_{s=1}^{b_{i}(t)}$
$\displaystyle\big{[}f(w(t-\tau),x_{i}(t,s))\big{]}\big{\rVert}^{2}\big{|}b(t)\Big{]}$
$\displaystyle\leq$ $\displaystyle\frac{\sigma^{2}}{b(t)}.$

The bound above follows from the fact that $x_{i}(t,s)$ are sampled i.i.d, so
the cross terms have zero expectation. Taking the expected value of (47)
conditioned on $b(t)$

$\displaystyle\mathbb{E}\Bigg{[}\langle\nabla
F(w(t-\tau))-g(t),w(t+1)-w^{*}\rangle\big{|}b(t)\Bigg{]}$
$\displaystyle\leq\frac{1}{2\eta(t)}\frac{\sigma^{2}}{b(t)}+\frac{\eta(t)}{2}\mathbb{E}\Big{[}\big{\lVert}w(t+1)$
$\displaystyle\big{\rVert}^{2}\Big{]}.$ (48)

Taking the expectation on both sides in (44) conditioned on ${\cal B}_{{\rm
tot}}:=\big{\\{}b(t),t\in[T]\big{\\}}$ and substituting (45) and (48),

$\displaystyle\sum_{t=1}^{T}\mathbb{E}\Big{[}\langle
e(t),w(t+1)-w^{*}\rangle\big{|}{\cal B}_{{\rm tot}}\Big{]}$ $\displaystyle\leq
2\tau JC+$ $\displaystyle
2LJ^{2}(\tau+1)^{2}\sum_{t=1}^{T}\frac{1}{\eta(t-\tau)^{2}}$
$\displaystyle+\frac{\sigma^{2}}{2}\sum_{t=1}^{T}\frac{1}{\eta(t)b(t)}$
$\displaystyle+\sum_{t=1}^{T}\frac{\eta(t)}{2}\mathbb{E}\Big{[}\lVert w(t+$
$\displaystyle 1)-w(t)\rVert^{2}\Big{]}.$ (49)

Substituting this into (43) after taking the conditional expectation given
${\cal B}_{{\rm tot}}$ and observing that the term
$-\eta(t)D_{\psi}(w(t+1),w(t))$ in (43) is upper bounded by
$-\frac{\eta(t)}{2}\lVert w(t+1)-w(t)\rVert^{2}$ since $\frac{1}{2}\lVert
w(t+1)-w(t)\rVert^{2}\leq D_{\psi}(w(t+1),w(t))$. This then cancels the last
term in (49), and we have

$\displaystyle\mathbb{E}\Big{[}\sum_{t=1}^{T}F\big{(}w(t+1)\big{)}-F(w^{*})\Big{]}$
$\displaystyle=\mathbb{E}\bigg{[}\mathbb{E}\Big{[}\sum_{t=1}^{T}F\big{(}w(t+1)\big{)}-F$
$\displaystyle(w^{*})\big{|}{\cal B}_{{\rm tot}}\Big{]}\bigg{]}$ (50)
$\displaystyle\leq\frac{1}{\alpha(T+1)}\psi(w^{*})+2\tau JC$
$\displaystyle+2LJ^{2}(\tau+1)^{2}\sum_{t=1}^{T}\frac{1}{\eta(t-\tau)^{2}}$
$\displaystyle+\frac{\sigma^{2}}{2}\mathbb{E}\bigg{[}\sum_{t=1}^{T}\frac{1}{\eta(t)b(t)}\bigg{]}.$
(51)

Let $\eta(t)=\sqrt{(t+\tau)/\bar{b}}$ and recalling that,
$\mathbb{E}[1/b(t)]\leq 1/\hat{b}$ and $m=T\bar{b}$, then

$\displaystyle\sum_{t=1}^{T}\frac{1}{\eta(t)\hat{b}}=\sum_{t=1}^{T}\frac{\sqrt{\bar{b}}}{\hat{b}\sqrt{t+\tau}}$
$\displaystyle\leq\frac{\sqrt{\bar{b}}}{\hat{b}}\sum_{t=1}^{T}\frac{1}{\sqrt{t+1}}$
$\displaystyle\leq$ $\displaystyle
2\frac{\sqrt{\bar{b}}\sqrt{T}}{\hat{b}}=\frac{2\sqrt{m}}{\hat{b}},$ (52)

and,

$\sum_{t=1}^{T}\frac{\bar{b}}{\eta(t-\tau)^{2}}=\bar{b}\sum_{t=1}^{T}\frac{1}{t}\leq\bar{b}\big{[}1+\log{\big{(}T\big{)}}\big{]}.$
(53)

The expected regret after $T$ epochs is

$\displaystyle\mathbb{E}\big{[}R(T)\big{]}=\mathbb{E}\bigg{[}\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{s=1}^{b_{i}(t)}f(w$
$\displaystyle(t+1),x_{i}(t+1,s))$ $\displaystyle-$ $\displaystyle
f(w^{*},x_{i}(t+1,s))\bigg{]}$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\bigg{[}\sum_{s=1}^{b_{i}(t)}f(w(t+1),x_{i}$
$\displaystyle(t+1,s))$ $\displaystyle-$ $\displaystyle
f(w^{*},x_{i}(t+1,s))\bigg{]}$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\sum_{s=1}^{b_{i}(t)}f(w(t+1)$
$\displaystyle,x_{i}(t+1,s))$ $\displaystyle-f(w^{*}$
$\displaystyle,x_{i}(t+1,s))\big{|}b_{i}(t)\bigg{]}\bigg{]}$

$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\bigg{[}\sum_{s=1}^{b_{i}(t)}\mathbb{E}\Big{[}F(w(t+1)$
$\displaystyle-F(w^{*})\Big{]}\bigg{]}$ (54)
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\Big{[}b_{i}(t)\mathbb{E}\Big{[}F(w(t+1)$
$\displaystyle-F(w^{*})\Big{]}\Big{]}$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\Big{[}b_{i}(t)\Big{]}\mathbb{E}\Big{[}F(w(t+1$
$\displaystyle)-F(w^{*})\Big{]}$ (55)
$\displaystyle\leq\sum_{t=1}^{T}\sum_{i=1}^{n}\frac{\bar{b}}{n}\mathbb{E}\Big{[}F(w(t+1)-F$
$\displaystyle(w^{*})\Big{]}$ (56)

where equation (54) follows from the fact that
$\mathbb{E}[f(w(t),x(t))]=\mathbb{E}[\mathbb{E}[f(w(t),x(t))\lvert
w(t)]]=\mathbb{E}[F(w(t))]$.

Substituting (52), (53), and (51) in (56), we get

$\displaystyle\mathbb{E}\big{[}R(T)\big{]}\leq$
$\displaystyle\frac{\bar{b}}{\alpha(T+1)}\psi(w^{*})+2\tau JC\bar{b}\,+$
$\displaystyle 2LJ^{2}(\tau+1)^{2}\big{(}1+\log
T\big{)}\bar{b}^{2}+\sigma^{2}\frac{\bar{b}}{\hat{b}}\sqrt{m}.$ (57)

Finally, the bound in (15) of Theorem IV.1 is obtained from (57) by observing
that $\psi(w^{*})\leq C^{2}/2$ and $\alpha(t)^{-1}=L+\sqrt{(t+\tau)/\bar{b}}$.
Hence, $1/\alpha(T+1)=L+\sqrt{(T+1+\tau)/\bar{b}}$ since $\bar{b}=m/T$.

###  A-B Proof of Corollary IV.2

Let $\hat{w}(T)=\frac{1}{T}\sum_{t=1}^{T}w(t+1)$, then the expected optimality
gap can be bounded by

$\displaystyle\mathbb{E}\big{[}G(T)\big{]}$
$\displaystyle=\mathbb{E}\big{[}F(\hat{w}(T))\big{]}-F(w)$ (58)
$\displaystyle=\mathbb{E}\Bigg{[}F\bigg{(}$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}w(t+1)\bigg{)}\Bigg{]}-F(w^{*})$ (59)
$\displaystyle\leq\mathbb{E}\Bigg{[}\frac{1}{T}$
$\displaystyle\sum_{t=1}^{T}F\big{(}w(t+1)\big{)}\Bigg{]}-F(w^{*})$ (60)
$\displaystyle=\mathbb{E}\Bigg{[}\frac{\bar{b}}{m}$
$\displaystyle\sum_{t=1}^{T}\Big{(}F\big{(}w(t+1)\big{)}-F(w^{*})\Big{)}\Bigg{]}$
(61) $\displaystyle=\frac{\bar{b}}{m}\mathbb{E}\Bigg{[}$
$\displaystyle\sum_{t=1}^{T}\Big{(}F\big{(}w(t+1)\big{)}-F(w^{*})\Big{)}\Bigg{]}$
(62) $\displaystyle\leq\,\,\,\bar{b}\Bigg{(}$
$\displaystyle\frac{C^{2}}{2m}\Big{(}L+\sqrt{(T+1+\tau)/\bar{b}}\Big{)}+\frac{2\tau
JC}{m}+$ $\displaystyle\frac{2LJ^{2}(\tau+1)^{2}\bar{b}\big{(}1+\log
T\big{)}}{m}+\frac{\sigma^{2}}{\hat{b}\sqrt{m}}\Bigg{)}.$ (63)

where (60) follows from the convexity of $F(w)$ and (63) follows from Theorem
IV.1.

##  Appendix B Proof of Theorem V.1

Define the sample path ${\cal B}_{{\rm tot}}=\\{b_{i}(t),i\in[n],t\in[T]\\}$.
Then conditioned on this sample path, the expected regret is given by

$\displaystyle\mathbb{E}\big{[}R(T)\lvert{\cal B_{{\rm tot}}}\big{]}=$
$\displaystyle\mathbb{E}\bigg{[}\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{s=1}^{b_{i}(t)}f($
$\displaystyle w_{i}(t+1),x_{i}(t+1,s))$
$\displaystyle-f(w^{*},x_{i}(t+1,s))\Big{\lvert}{\cal B}_{{\rm tot}}\bigg{]}$
(64)
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\bigg{[}\sum_{s=1}^{b_{i}(t)}$
$\displaystyle F(w_{i}(t+1))-F(w^{*})\bigg{]}$ (65)
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\bigg{[}\sum_{s=1}^{b_{i}(t)}$
$\displaystyle F(w(t+1))-F(w^{*})$
$\displaystyle+F(w_{i}(t+1))-F(w(t+1)\bigg{]}$ (66)
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\bigg{[}\sum_{s=1}^{b_{i}(t)}$
$\displaystyle F(w(t+1))-F(w^{*})\bigg{]}+$
$\displaystyle\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{s=1}^{b_{i}(t)}$
$\displaystyle\mathbb{E}\Big{[}F(w_{i}(t+1))-F(w(t+1))\Big{]}$ (67)
$\displaystyle\leq\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\bigg{[}\sum_{s=1}^{b_{i}(t)}$
$\displaystyle F(w(t+1))-F(w^{*})\bigg{]}+$
$\displaystyle\sum_{t=1}^{T}\sum_{i=1}^{n}$
$\displaystyle\sum_{s=1}^{b_{i}(t)}J\mathbb{E}\Big{[}\lVert
w_{i}(t+1)-w(t+1)\rVert\Big{]}$ (68)

where (68) follows from the Lipschitz continuity assumption (8). To bound the
the term $\lVert w_{i}(t+1)-w(t+1)\rVert$ above we use Lemma 2 from [19] which
states that for all $i\in[n]$ and all $t\in[T],$

$\lVert w_{i}(t+1)-w(t+1)\rVert\leq\alpha(t+1)\lVert
z_{i}^{(r)}(t+1)-z(t+1)\rVert.$ (69)

Substituting (23) and (69) in (68), we get

$\displaystyle\mathbb{E}\big{[}R(T)\lvert{\cal B_{{\rm
tot}}}\big{]}\leq\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\bigg{[}\sum_{s=1}^{b_{i}(t)}$
$\displaystyle F(w(t+1))-F(w^{*})\bigg{]}$ $\displaystyle+\sum_{t=1}^{T}$
$\displaystyle\sum_{i=1}^{n}\sum_{s=1}^{b_{i}(t)}J\delta\alpha(t+1)$ (70)
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\bigg{[}\sum_{s=1}^{b_{i}(t)}$
$\displaystyle F(w(t+1))-F(w^{*})\bigg{]}$ $\displaystyle+$
$\displaystyle\sum_{t=1}^{T}J\delta b(t)\alpha(t+1).$ (71)

Since
$\mathbb{E}\big{[}R(T)\big{]}=\mathbb{E}\big{[}\mathbb{E}\big{[}R(T)\lvert{\cal
B_{{\rm tot}}}\big{]}\big{]}$, then the expected regret is

$\displaystyle\mathbb{E}\big{[}R(T)\big{]}\leq\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\sum_{s=1}^{b_{i}(t)}$
$\displaystyle F(w(t+1))-F(w^{*})\bigg{]}\bigg{]}$ $\displaystyle+$
$\displaystyle J\delta\bar{b}\sum_{t=1}^{T}\alpha(t+1).$ (72)

We look at the second term $\sum_{t=1}^{T}J\delta\bar{b}\alpha(t+1)$ and
observe that $\alpha(t+1)\leq 1/\sqrt{(t+\tau)/\bar{b}}$. Thus,

$\displaystyle J\delta\bar{b}\sum_{t=1}^{T}\alpha(t+1)\leq$ $\displaystyle
J\delta\bar{b}\sum_{t=1}^{T}\frac{1}{\sqrt{(t+\tau)/\bar{b}}}$ (73)
$\displaystyle=$ $\displaystyle
j\delta\bar{b}^{3/2}\sum_{t=1}^{T}\frac{1}{\sqrt{(t+\tau)}}$ (74)
$\displaystyle\leq$ $\displaystyle 2J\delta\bar{b}^{3/2}\sqrt{m}.$ (75)

The first term in (72) is the expected regret for the hub-and-spoke case so we
can substitute its bound from (57). Thus, we have

$\displaystyle\mathbb{E}\big{[}R(T)\big{]}\leq\frac{\bar{b}}{\alpha(T+1)}$
$\displaystyle\psi(w^{*})+2\tau JC\bar{b}\,+$ $\displaystyle
2LJ^{2}(\tau+1)^{2}\big{(}1+$ $\displaystyle\log
T\big{)}\bar{b}^{2}+\sigma^{2}\frac{\bar{b}}{\hat{b}}\sqrt{m}+2J\delta\bar{b}^{3/2}\sqrt{m}.$
(76)

##  Appendix C AMB-DG Pseudocode

In this section, we present pseudocode for AMB-DG. Algorithm 1 details the
process at the workers while Algorithm 2 shows the AMB-DG steps at the master.
In Algorithm 1, line 2 is about parameter initialization at the workers. Lines
4-11 correspond to the gradient compute phase. Line 12 is related to worker-
to-master communication while in lines 8-10 and 13-15, workers receive the
update from the master and update their local versions of the optimization
parameters. On the other hand, in Algorithm 2, lines 3-7 are related to
worker-to-master communication in which the master receives messages from the
workers. Lines 8-10, correspond to the parameter update phase while line 12
represent the communication from the master to all workers.

1:for all $t=1,2,...$ do

2: initialize $g_{i}(t)=0,b_{i}(t)=0,s=0$

3: $T_{0}=\texttt{current\\_time}$

4: while $\texttt{current\\_time}\leq T_{p}-T_{0}$ do

5: sample i.i.d input data $x_{i}(t,s)$ from $P$

6: calculate $g_{i}(t)=g_{i}(t)+\nabla f(w(t),x_{i}(t,s))$

7: $b_{i}(t)$++, $s$++.

8: end while

9: send $g_{i}(t)$, $b_{i}(t)$ to the master

10: if received updated parameter $\tilde{w}$ from master then

11: set $w(t)=\tilde{w}$

12: end if

13:end for

Algorithm 1 AMB-DG Algorithm (Worker Node)

1:for all $t=1,2,\cdots$ do

2: initialize $b(t)=0,g(t)=0$.

3: for all $i=1,2,\cdots,n$ do

4: receive $b_{i}(t),g_{i}(t)$ from worker $i$

5: $b(t)$ += $b_{i}(t)$

6: $g(t)$ += $g_{i}(t)$

7: end for

8: $z(t+1)=z(t)+\frac{1}{b(t)}g(t)$

9: $w(t+1)=\arg\min_{w\in\mathcal{W}}\big{\\{}\langle
w,z(t+1)\rangle+\frac{1}{\alpha(t+1)}\psi(w)\big{\\}}$

10: send $w(t+1)$ to all workers

11:end for

Algorithm 2 AMB-DG Algorithm (Master Node) |  Haider Al-Lawati (Student Member, IEEE) received his B.Sc.E and M.Sc. degrees both in Engineering and Mathematics from Queen’s University, Kingston, Canada in 2005 and 2007, respectively. He is currently a Ph.D. candidate at the Electrical and Computer Engnieering department at the University of Toronoto. Between 2008 and 2015, he worked in the telecom industry as an RF planning engineer, a project manager and a head of a department working on various mobile technologies such as GSM, WCDMA, LTE and WiMAX. Throughout his academic and industrial careers, Mr. Al-Lawati received a number of scholarships and awards. His current research interests include distributed computing, distributed optimization, and machine learning.
---|---
|  Stark C. Draper (Senior Member, IEEE) received the M.S. and Ph.D. degrees
from the Massachusetts Institute of Technology (MIT), and the B.S. and B.A.
degrees in electrical engineering and in history from Stanford University. He
is a Professor of Electrical and Computer Engineering with the University of
Toronto (UofT) and was an Associate Professor with the University of
Wisconsin, Madison. As a Research Scientist he has worked with the Mitsubishi
Electric Research Labs (MERL), Disney’s Boston Research Lab, Arraycomm Inc.,
the C. S. Draper Laboratory, and Ktaadn Inc. He completed Postdocs with the
UofT and at the University of California, Berkeley. His research interests
include information theory, optimization, error-correction coding, security,
and the application of tools and perspectives from these fields in
communications, computing, learning, and astronomy. Prof. Draper is a
recipient of the NSERC Discovery Award, the NSF CAREER Award, the 2010 MERL
President’s Award, and teaching awards from the UofT, the University of
Wisconsin, and MIT. He received an Intel Graduate Fellowship, Stanford’s
Frederick E. Terman Engineering Scholastic Award, and a U.S. State Department
Fulbright Fellowship. He spent the 2019–2020 academic year on sabbatical at
the Chinese University of Hong Kong, Shenzhen, and visiting the Canada-France-
Hawaii Telescope (CFHT) in Hawai’i, USA. He chairs the Machine Intelligence
major at UofT, is a member of the IEEE Information Theory Society Board of
Governors, and serves as the Faculty of Applied Science and Engineering
representative on the UofT Governing Council.
---|---