\section{System model and algorithm}
\label{sec.algOutline}
In this section we outline our computation and optimization model and step through the three phases of the AMB algorithm. The pseudo code of the algorithm is provided in App.~\ref{app.algorithm}. We defer discussion of detailed mathematical assumptions and analytical results to Sec.~\ref{sec.analysis}.

We suppose a computing system that consists of $n$ compute nodes. Each node
corresponds to a vertex in a connected and undirected graph $G(V,E)$ that represents the inter-node communication structure.
The vertex set $V$ satisfies $|V| = n$ and the edge set $E$ tells us
which nodes can communicate directly. Let $\mathcal N_i =
\{j \in V: (i,j) \in E, i \neq j\}$ denote the neighborhood of node $i$.

The
collaborative objective of the nodes is to find the parameter vector
$w \in W \subseteq \mathbb{R}^d$ that solves
\begin{equation}
	w^\ast = \arg \min_{w \in W} F(w) \ \ \ \ {\rm where} \ \ \ \ F(w):= \mathbb E_x[f(w,x)]. \label{eq.expSoln}
\end{equation}
The expectation $\mathbb E_x[\cdot]$ is computed with respect to an unknown probability distribution $Q$ over a set $X \subseteq \mathbb{R}^d$. Because the distribution is unknown, the nodes must approximate the solution in (\ref{eq.expSoln}) using data points drawn in an independent and identically distributed (i.i.d.) manner from $Q$.

AMB uses dual averaging~\cite{Nesterov:2009,dekel2012optimal} as its optimization workhorse and averaging consensus~\cite{nokleby17,tsianos2016efficient} to facilitate collaboration among nodes. It proceeds in epochs consisting of three phases: \emph{compute}, in which nodes compute local minibatches; \emph{consensus}, in which nodes average their dual variables together; and \emph{update}, in which nodes take a dual averaging step with respect to the consensus-averaged dual variables. We let $t$ index each epoch, and each node $i$ has a primal variable $w_i(t) \in \mathbb{R}^d$ and dual variable $z_i(t) \in \mathbb{R}^d$. At the start of the first epoch, $t=1$, we initialize all primal variables to the same value $w(1)$ as
\begin{align}
	w_i(1)= w(1) = \arg \min_{w\in W} h(w),
\end{align}
and all dual variables to zero, i.e., $z_i(1) = 0 \in \mathbb{R}^d$. In here, $h:W\to \mathbb R$ is a $1$-strongly convex function.

{\bf Compute Phase: } All workers are given $T$ \emph{fixed time} to compute their local minibatches. During each epoch, each node is able to compute $b_i(t)$ gradients of $f(w,x)$, evaluated at $w_i(t)$ where the data samples $x_i(t,s)$ are drawn i.i.d. from $Q$. At the end of epoch $t$, each node $i$ computes its local minibatch gradient:
\begin{equation}
\label{eqn:mini.batch}
	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).
\end{equation}
As we fix the compute time, the local minibatch size $b_i(t)$ is a random variable. Let $b(t) := \sum_{i=1}^n b_i(t)$ be the \emph{global} minibatch size aggregated over all nodes. This contrasts with traditional approaches in which the minibatch is fixed. 
In Sec. \ref{sec.analysis} we provide a convergence analysis that accounts for the variability in the amount of work completed by each node. In Sec. \ref{sec.shiftExpDist}, we presents a wall time analysis based on random local minibatch sizes.

{\bf Consensus Phase: } Between computational epochs each node is given a fixed amount of time, $T_c$, to communicate with neighboring nodes. The objective of this phase is for each node to get (an approximation of) the following quantity:
\begin{align}
	\frac{1}{b(t)}\sum_{i=1}^{n}b_i(t)[z_i(t)+g_{i}(t)] & =
        \frac{1}{b(t)}\sum_{i=1}^{n}b_i(t)z_i(t) + \frac{1}{b(t)}
        \sum_{i=1}^{n} \sum_{s=1}^{b_i(t)} \nabla_w
        f\big(w_i(t),x_i(t,s)\big) \nonumber \\ & := \bar{z}(t) + g(t). \label{eq.idealConsensus}
\end{align}
The first term, $\bar{z}(t)$, is the weighted average of the previous
dual variables. The second, $g(t)$, is the average of all
gradients computed in epoch $t$.

The nodes compute this quantity approximately via several synchronous rounds of average consensus. Each node waits until it hears from all neighbors before starting a consensus round. As we have fixed communication time $T_c$, the number of consensus rounds $r_i(t)$ varies across workers and epochs due to random network delays. Let $P$ be a positive semi-definite, doubly-stochastic matrix (i.e., all entries of $P$ are non-negative and all row- and column-sums are one) that is consistent with the graph $G$ (i.e., $P_{i,j} > 0$ only if $i
= j$ or if $(i,j) \in E$). At the start of the consensus phase, each node $i$ shares its message $m_i^{(0)} =
nb_i(t)[z_i(t)+g_{i}(t)]$ with its neighboring nodes. Let $[r]$ stand for $[r] \in \{1,\ldots r\}$. Then, in consensus iteration $k
\in [r_i(t)]$ node $i$ computes its update as
\begin{equation*}
m_i^{(k)} = \sum_{j=1}^n P_{i,j} m_j^{(k-1)} = \sum_{j=1}^n (P_{i,j})^k m_j^{(0)}.
\end{equation*}

As long as $G$ is connected and the second-largest eigenvalue of $P$ is strictly less than unity, the iterations are guaranteed to converge to the true average. For finite $r_i(t)$, each node will have an error in its
approximation. Instead of~(\ref{eq.idealConsensus}), at the end of
the rounds of consensus, node $i$ will have
\begin{align}
	\label{eqn:DA2}
	z_i(t+1) = \bar{z}(t)+g(t)+\xi_i(t),
\end{align}
where $\xi_i(t)$ is the error. We use $\mathcal D^{(r_i(t))}\big(\{y_j\}_{j \in V},i\big)$ to denote the distributed
averaging affected by $r_i(t)$ rounds of consensus. Thus,
\begin{align}
	\label{eqn:DA1}
	z_i(t+1)=\frac{1}{b(t)}\mathcal{D}^{(r_i(t))}\Big(\Big\{nb_j(t)\big[z_j(t)+g_{j}(t)\big]\Big]\Big\}_{j \in V},i\Big)=\frac{1}{b(t)} m_i^{(r_i(t))}.
\end{align}
We note that the updated dual variable $z_i(t+1)$ is a normalized
version of the distributed average solution, normalized by
$b(t)=\sum_{i=1}^{n}b_i(t)$.

{\bf Update Phase: } After distributed averaging of dual variables, each node updates its primal
variable as
\begin{align}\label{eqn:primal.variable}
	w_i(t+1) = \arg \min_{w \in W} \Big\{\big\langle w,z_i(t+1)\big\rangle+\beta(t+1) h(w)\Big\};
\end{align}
where $\langle\cdot,\cdot\rangle$ denotes the standard inner product. As will be discussed further in our analysis, in this paper we assume
$h:W\to \mathbb R$ to be a 1-strongly convex function and $\beta(t)$
to be a sequence of positive non-decreasing parameters, i.e.,
$\beta(t)\leq \beta(t+1)$. We also work in Euclidean space where
$h(w)=\|w\|^2$ is a typical choice.
{"config": "arxiv", "file": "2006.05752/sysModAlg.tex"}