text:
\section{Introduction}
We consider a cloud server and a set of $M$ mobile devices (workers) collected in ${\cal M}:=\{1,\ldots,M\}$.
Each device $m$ has its local dataset $\{\xi_n,\,n\in {\cal N}_m\}$, which defines the loss function of device $m$ as
\begin{align}
{\cal L}_m(\theta)\!:=\!\sum_{n\in{\cal N}_m}\!\ell(\theta;\xi_n),\quad m\in{\cal M}
\end{align}
where $\theta\in \mathbb{R}^p$ is the sought vector (e.g., parameters of a prediction model) and $\xi_n$ is a data sample.
For example, in linear regression, $\ell(\theta;\xi_n)$ is the square loss;
and, in deep learning, $\ell(\theta;\xi_n)$ is the loss function of a neural network, and $\theta$ concatenates the weights.
The goal is to solve %
\begin{align}\label{eqn: problem}
	\min_{\theta\in \mathbb{R}^p}~{\cal L}(\theta)~~~{\rm with}~~~{\cal L}(\theta):=\sum_{m\in{\cal M}}{\cal L}_m(\theta).
\end{align}
Problem \eqref{eqn: problem} also arises in a number of areas, such as
multi-agent optimization \citep{nedic2009}, distributed signal processing \citep{msechu2011tsp}, and distributed machine learning \citep{dean2012}.
While our algorithms can be applied to other settings, we focus on the federated learning setting.
In this case, for bandwidth and privacy concerns, local data $\{\xi_n, n\in{\cal N}_m\}$ at each worker $m$ are not uploaded to the server, and collaboration is needed through communication between the server and workers.

\begin{figure}[t]
\centering
\includegraphics[width=8cm]{lasg.pdf}
  \caption{Generic LASG implementation.}
\label{fig:lasg-diag}
\end{figure}

To solve \eqref{eqn: problem}, we can in principle apply the distributed version of stochastic gradient descent (SGD) method.
In this case, at iteration $k$, the server broadcasts the current model $\theta^k$ to \emph{all} the workers; each worker $m$ computes $\nabla  \ell(\theta^k; \xi_m^k)$ using a randomly selected sample or a minibatch of samples $\{\xi_m^k\}\subseteq\{\xi_n, n\in{\cal N}_m\}$, and then uploads it to the server; and once receiving stochastic gradients from all workers, the server updates the model parameters via
\begin{flalign}	\label{eqn:SGDiteration}
& {\rm \textbf{SGD}}\qquad\qquad\qquad\qquad\qquad\qquad\qquad \theta^{k+1}=\theta^k-\eta_k\sum\limits_{m\in{\cal M}} \nabla  \ell(\theta^k; \xi_m^k) &
\end{flalign}
where $\eta_k>0$ is the (possibly) time-varying stepsize used at iteration $k$.
When $\nabla  \ell(\theta^k; \xi_m^k)$ is an unbiased gradient estimator of $\mathcal{L}_m(\theta)$, the convergence of SGD update \eqref{eqn:SGDiteration} is guaranteed \citep{bottou2016}.
To implement \eqref{eqn:SGDiteration}, however, the server has to communicate with \emph{all} workers to obtain fresh $\{\nabla \ell(\theta^k; \xi_m^k) \}$.
This prevents the efficient implementation of SGD in scenarios where communication between the server and the workers is costly \citep{mcmahan2017}, since latency will degrade the overall performance.
Therefore, \emph{our goal} is to find the parameter $\theta$ that minimizes \eqref{eqn: problem} with minimal communication overhead.

\subsection{Our approach}
This paper puts forward a class of new stochastic optimization methods that can considerably reduce the redundant or less informative communication of SGD.
The key motivation is that during the distributed learning process, not all communication rounds between the server and the worker are equally important. So a natural solution is to use a condition that decides whether to communicate or not. In this case, if some workers are not communicating, the server uses their stale gradients so that stale gradients replace skipped fresh gradients.

Analogous to the distributed implementation of SGD \eqref{eqn:SGDiteration}, our new approaches also aggregate the stochastic gradients from all workers, but in a fairly lazy manner. Hence, we term our algorithms as \textbf{L}azily \textbf{A}ggregated \textbf{S}tochastic \textbf{G}radient (\textbf{LASG}). LASG has the following generic update
\begin{align}\label{eqn:LASGiteration}
\theta^{k+1} = \theta^k-\eta_k\!\!\!\sum\limits_{m\in{\cal M}\backslash{\cal M}^k} \!\!\!\nabla \ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})
-\eta_k\!\!\!\sum\limits_{m\in{\cal M}^k}\!\!\! \nabla\ell(\theta^k;\xi_m^k)
\end{align}
or equivalently (see also Figure \ref{fig:lasg-diag})
 \begin{flalign}\label{eqn:LASGiteration2}
&{\rm \textbf{Generic LASG}}\qquad\qquad\qquad\qquad  \theta^{k+1} = \theta^k-\eta_k\nabla^k\quad{\rm with}\quad\nabla^k\!=\!\nabla^{k-1}+\sum\limits_{m\in{\cal M}^k}\delta_m^k&
\end{flalign}
where $\delta_m^k := \nabla \ell(\theta^k;\xi_m^k)-\nabla \ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})$ is the stochastic gradient innovation, $\tau_m^k\geq 0$ is the staleness of the gradient from worker $m$ used by $k$-iteration, and ${\cal M}^k$ is the subset of workers uploading $\delta_m^k$ at iteration $k$. The stalenesses $\{\tau_m^k\}$ are controlled by the selection of subset ${\cal M}^k$: at iteration $k$, if worker $m\notin {\cal M}^k$, the server increases the staleness by $\tau_m^{k+1} = \tau_m^{k} + 1$; otherwise, worker $m$ uploads the stochastic gradient, and the server resets $\tau_m^{k+1}=1$.

Clearly, selection of subset ${\cal M}^k$ is critical in LASG. However, the challenges are 1) the importance of each communication round is dynamic, thus a fixed or nonadaptive condition is ineffective; and 2) the condition needs to be checked either at server or at worker locally and efficiently.

To overcome these challenges, we develop two types of adaptive conditions based on message innovations. They can be chosen under different \emph{communication}, \emph{computation} and \emph{memory} requirements.
The first type is adopted by each worker (WK), and the second one by the server (PS).

\noindent\textbf{LASG-WK}: At iteration $k$, the server broadcasts $\theta^k$ to all workers; every worker computes $\nabla \ell(\theta^k;\xi_m^k)$, and checks if it belongs to ${\cal M}^k$; only the workers in ${\cal M}^k$ upload $\delta^k_m$; the server updates via \eqref{eqn:LASGiteration2}.

\noindent\textbf{LASG-PS}: At iteration $k$, the server decides ${\cal M}^k$ and sends $\theta^k$ to workers in ${\cal M}^k$; each worker $m\!\in\!{\cal M}^k$ computes $\nabla \ell(\theta^k;\xi_m^k)$ and uploads $\delta^k_m$; the rest of workers do nothing; the server updates via \eqref{eqn:LASGiteration2};

With detailed description of LASG rules deferred to Section \ref{sec.LASG}, the contributions of this paper are listed as follows.

{\bf 1)} We introduce a class of novel (quantized) stochastic optimization approaches that
reuses stale stochastic gradients to reduce redundant communication.

{\bf 2)} We establish convergence of our proposed algorithms in strongly convex and nonconvex settings even when the datasets are non-i.i.d. across workers. The convergence rates match those of SGD in the respective settings.

{\bf 3)} We confirm performance gains of our novel distributed
algorithms over some alternatives using extensive numerical tests on logistic regression and neural network training.

\subsection{Related work}
Communication-efficient distributed learning methods have gained popularity recently \citep{Nedic2018,jordan2018}. Most popular methods belong to two categories: c1) reduce the number of bits per communication
round; and, c2) save the number of communication
rounds.
For c1), methods are centered around the ideas of \emph{quantization} and \emph{sparsification}.

\noindent\textbf{Quantization} has been successfully applied to several engineering tasks employing wireless sensor networks \citep{msechu2011tsp}. In the context of distributed machine learning, a 1-bit and multi-bits quantization methods have been developed in \citep{seide20141, bernstein2018icml,alistarh2017qsgd,magnusson2019maintaining}. Other variants of quantized gradient schemes include error compensation \citep{wu2018error}, variance-reduced quantization \citep{zhang2017zipml}, and quantization to a ternary vector \citep{wen2017terngrad}.

\noindent\textbf{Sparsification} amounts to transmitting only gradient coordinates with large enough magnitudes exceeding a certain threshold~\citep{strom2015scalable, aji2017sparse}.
To avoid losing information of skipping communication, small gradient components will be accumulated and then transmitted when they are large enough \citep{lin2017deep,stich2018nips,alistarh2018}. Recently, randomized sparsification approaches have also been developed in \citep{wangni2018gradient,wang2018atomo}.

However, both quantization and sparsification aim to resolve c1).
For exchanging messages, e.g., the $p$-dimensional $\theta$ or its gradient, other latencies (initiating communication links, queueing, and propagating the message) are at least comparable to the message size-dependent transmission latency \citep{peterson2007}. This motivates c2) reducing the number of communication rounds.

\noindent\textbf{Periodic communication.}
In contrast to the gradient compression schemes, schemes that reduce the number of communication rounds have also been developed, including the periodic averaging techniques, e.g., local stochastic gradient descent (a.k.a. local SGD) \citep{lin2018don,stich2019local,wang2018coop,yu2019icml,yu2019aaai}.
In local SGD, workers are allowed to perform local model updates independently and the resultant models are averaged periodically. In this way communication frequency is reduced.
The caveat is that most local SGD methods have performance guarantee in the \emph{homogeneous} settings, where the data are independent and identically distributed over all workers. However, this assumption rarely holds in federated learning \citep{mcmahan2017}.

\noindent\textbf{Intermittent communication.}
Different from periodic communication used in local SGD, adaptive uploading techniques have been studied in e.g., lazily aggregated gradient (LAG) approaches \citep{chen2018lag,sun2019}.
LAG is tailored for the \emph{heterogeneous} learning settings, and has provable performance gain when the data distributions vary across workers.
Models in LAG are updated at the server, and workers only adaptively upload information that is determined to be informative enough. Unfortunately, while the original LAG has good performance in the deterministic settings (e.g., with full gradient), its performance is significantly degraded in the stochastic settings. Recent efforts have been made towards adaptive uploading in stochastic settings \citep{li2019csgd}, but the proposed scheme therein requires an exponentially increasing batch size, which is not favorable in practice. In contrast, the LASG approaches can be viewed as the stochastic counterparts of the LAG, and our adaptive communication rules are new and tailored for SGD, which do not require the increasing batch size.

\section{Why LAG does not work well with SGD?}
Our LASG approaches are closely related to the recently developed LAG method \citep{chen2018lag}.
In this section, we revisit LAG and provide insights why it does not work well in stochastic settings.

\begin{figure}[t]
\centering
\includegraphics[width=.5\textwidth]{toyexample.pdf}
  \caption{Number of uploads in per epoch (10 iterations) under stochastic LAG-WK and LASG-WK2.}
  \label{toyexample}
\end{figure}

Because not every communication round is equally important during the learning process, LAG only admits useful communication, and otherwise, reuses stale information.
Instead of communicating with all $M$ workers as SGD in \eqref{eqn:SGDiteration}, the direct (or ``naive") stochastic version of LAG (specifically LAG-WK) selects the subset of workers ${\cal M}^k$ to obtain their \emph{fresh} stochastic gradients $\nabla{\cal L}_m\big(\theta^k;\xi_m^k\big)$, $m\in{\cal M}^k$.
The \textbf{direct stochastic LAG} also follows the generic update \eqref{eqn:LASGiteration}, but it selects ${\cal M}^k$ as: if worker $m$ finds the innovation of the fresh stochastic gradient $\nabla \ell(\theta^k;\xi_m^k)$ is small such that it satisfies (with pre-defined $\{c_d\geq0\}$)
{\begin{align}\label{eqn:LAGrule}
\Big\|\nabla \ell(\theta^k;\xi_m^k)-\nabla \ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})\Big\|^2
\!\leq\frac{1}{M^2}\sum\limits_{d=1}^Dc_d\big\|\theta^{k+1-d}-\theta^{k-d}\big\|^2\!
\end{align}}
then we reuse the old gradient, $m\in{\cal M}\backslash{\cal M}^k$, and increase the staleness by $\tau_m^{k+1} = \tau_m^{k} + 1$; otherwise, worker $m$ uploads the stochastic gradient, and resets $\tau_m^{k+1}=1$.

In the deterministic setting, LAG condition \eqref{eqn:LAGrule} is motivated by the elegant \emph{``larger descent per upload"} rationale, and has proved to be effective \citep{chen2018lag}.
Nevertheless, the observation here is that the two stochastic gradients \eqref{eqn:LAGrule} are evaluated on two different iterates ($\theta^k$ and $\theta^{k-\tau_m^k}$) and two different samples ($\xi_m^k$ and $\xi_m^{k-\tau_m^k}$) thus two different loss functions. This is in contrast to the original LAG condition in \citep{chen2018lag} where the gradient innovation is evaluated on the same function. This subtle difference leads to significant degradation in performance.

Figure \ref{toyexample} compares the stochastic LAG and one of our new algorithms LASG-WK2 (introduced later), and demonstrates that the stochastic LAG is not effective in saving communication --- when $c_d$ is set to be small (e.g., 0.4), \eqref{eqn:LAGrule} almost never satisfies; and when $c_d$ is set to be large (e.g., 4), \eqref{eqn:LAGrule} satisfies initially, but stops satisfying later. This can be explained by expanding the left-hand-side (LHS) of \eqref{eqn:LAGrule} by (see the supplemental material for the deduction)
\begin{subequations}\label{eqn:variance-wk}
\begin{align}
\mathbb{E}\left[\|\nabla\ell(\theta^k;\xi_m^k)-\nabla\ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})\|^2\right]
\geq \,&\frac{1}{2}\mathbb{E}\Big[\big\|\nabla\ell(\theta^k;\xi_m^k)-\nabla{\cal L}_m(\theta^k)\big\|^2\Big]\label{eqn:wk-rq1}\\
+\,&\frac{1}{2}\mathbb{E}\Big[\big[\big\|\nabla\ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})-\nabla{\cal L}_m(\theta^{k-\tau_m^k})\big\|^2\big]\Big]\label{eqn:wk-rq2}\\
-\,&\mathbb{E}[\|\nabla{\cal L}_m(\theta^k)-\nabla{\cal L}_m(\theta^{k-\tau_m^k})\|^2]. \label{eqn:wk-rq3}
\end{align}
\end{subequations}
Even if the iterate $\theta^k$ converges, e.g., $\theta^k\rightarrow \theta^*$, and thus the right-hand-side (RHS) of \eqref{eqn:LAGrule} $\big\|\theta^{k+1-d}\!-\!\theta^{k-d}\big\|^2\!\rightarrow\! 0$, the LHS of \eqref{eqn:LAGrule} does not, because the gradient variance appearing in \eqref{eqn:wk-rq1} and \eqref{eqn:wk-rq2} does not vanish yet the gradient difference at the same function \eqref{eqn:wk-rq3} diminishes.

Therefore, the key insight here is that the non-diminishing variance of stochastic gradients makes the direct implementation of the LAG rule \eqref{eqn:LAGrule} ineffective eventually.

 \begin{table*}[t]
\centering
 \begin{tabular}[t]{ c || c | c ||c |c|| c |c  }
 \hline\hline \textbf{Metric} &\multicolumn{2}{|c||}{\textbf{Communication}}& \multicolumn{2}{|c||}{\textbf{Computation}}& \multicolumn{2}{|c}{\textbf{Memory}}\\
\hline \!\textbf{Algorithm}\!&\textbf{PS$\rightarrow$WK}~$m$\!\!&\!\textbf{WK} $m$ $\rightarrow$\textbf{PS}\!& ~~~\textbf{PS}~~~&\textbf{WK}~$m$& ~~~\textbf{PS}~~~&\textbf{WK}~$m$\\ \hline \hline
\textbf{Sync SGD} & always &  always & \eqref{eqn:SGDiteration} & \eqref{eqn:SGDiteration} &  ${\cal O}(p)$& $/$ \\ \hline
     \textbf{LASG-WK1} & always &\!\!\!only if $m\!\in\!{\cal M}^k$\!\!\!  & \!\!\! \eqref{eqn:LASGiteration2}\!\! & \!\! \eqref{eqn:workerrule1} &  \!\!\!\! ${\cal O}(p)$\!\!\!& \!\!\!\!${\cal O}(p)$\!\!\!\!  \\\hline
    \textbf{LASG-WK2} & always & \!\!\!only if $m\!\in\!{\cal M}^k$\!\!\! & \eqref{eqn:LASGiteration2}  &\!\!\!$\eqref{eqn:workerrule2}$\!\!\!&  ${\cal O}(p)$&\!\!\!\!\! ${\cal O}(p)$\!\!\!\!\\ \hline
    \textbf{LASG-PS} & only if $m\!\in\!{\cal M}^k$ & \!\!\!only if $m\!\in\!{\cal M}^k$\!\!\! & \eqref{eqn:LASGiteration2},\eqref{eqn:serverrule}  & \!\!only if $m\!\in\!{\cal M}^k$ \!\!\!&  ${\cal O}(Mp)$&\!\!\!${\cal O}(p)$\!\!\\ \hline
        \textbf{LASG-PSE} & only if $m\!\in\!{\cal M}^k$ & \!\!\!only if $m\!\in\!{\cal M}^k$\!\!\! & \eqref{eqn:LASGiteration2},\eqref{eqn:eserversule}  & \!\!only if $m\!\in\!{\cal M}^k$ \!\!\!&  ${\cal O}(Mp)$ &\!\!\!${\cal O}(p)$\!\!\!\\ \hline\hline
    \end{tabular}
\caption{A comparison of communication, computation and memory requirements.
\textbf{PS} denotes the parameter server, \textbf{WK} denotes the worker,
\textbf{PS$\rightarrow$WK $m$} is the download from the server to the worker $m$, and \textbf{WK} $m$ $\rightarrow$ \textbf{PS} is the upload from the worker $m$ to the server.}
\label{tab:3algcomp}
\end{table*}

\section{LASG: Lazily Aggregated Stochastic Gradient Approach}\label{sec.LASG}
In this section, we formally develop our LASG method, and present the intuition
behind its design.

While the updates of stochastic LAG and LASG \eqref{eqn:LASGiteration} look identical, the choice of ${\cal M}^k$ in them is very different.
To overcome the limitations of LAG in stochastic settings, the key of the LASG design is to \textbf{reduce the variance of the innovation measure} appeared in the adaptive condition.

Towards this goal, we develop two types of LASG rules to select ${\cal M}^k$.
The first type is adopted by each worker that uses the gradient difference as the innovation measure but a \emph{variance-reduced} gradient difference; and the second one by the parameter server that uses the model difference as the innovation measure, but uses a sequence of \emph{diminishing stepsizes} to control variance.

\begin{table*}[t]
\centering
    \begin{tabular}{c c}
    \hspace{-0.2cm}
\begin{minipage}[t]{7.8cm}
  \vspace{0pt}
\begin{algorithm}[H]
\caption{LASG-WK1}\label{alg: LASG-WK1}
    \begin{algorithmic}[1]
    \State{\textbf{Input:} Delay counter $\{\tau_m^0\}$,  stepsizes $\{\eta_k\}$, max delay $D$.}
        \For{$k=0,1,\ldots, K-1$}
            \State{Server broadcasts $\theta^k$ to all workers.}
            \State{All workers save $\tilde{\theta}=\theta^k$ if $k \mod D=0$.}
            \ParFor{ Worker $m=1,2,\ldots, M$}
            \State{Compute $\nabla \ell(\theta^k;\xi_m^k)$ and $\nabla \ell(\tilde{\theta};\xi_m^k)$.}
            \State{Check condition \eqref{eqn:workerrule1} with stored $\tilde{\delta}_m^{k-\tau_m^{k}}$.}

                \If{\eqref{eqn:workerrule1} is violated, or, $k\mod D=0$}
                \State{Upload $\delta_m^k$.}
               \qquad\quad\Comment{$\tau_m^{k+1}=1$
                \Else
                \State{Upload nothing.}\quad\Comment{$\tau_m^{k+1} = \tau_m^{k} + 1$}
                \EndIf

            \EndParFor
            \State{Server updates via \eqref{eqn:LASGiteration}.}
        \EndFor
    \end{algorithmic}
  \end{algorithm}
\end{minipage}
\begin{minipage}[t]{7.8cm}
  \vspace{0pt}
  \begin{algorithm}[H]
\caption{LASG-WK2}
\label{alg: LASG-WK2}
    \begin{algorithmic}[1]
        \State{\textbf{Input:} Delay counter $\{\tau_m^0\}$,  stepsizes $\{\eta_k\}$, max delay $D$.}
        \For{$k=0,1,\ldots, K-1$}
            \State{Server broadcasts $\theta^k$ to all workers.}
            \ParFor{ Worker $m=1,2,\ldots, M$}
            \State{Compute $\nabla \ell(\theta^k;\xi_m^k)$ and $\nabla \ell(\theta^{k-\tau_m^k}_m;\xi_m^k)$.}
            \State{Check condition \eqref{eqn:workerrule2}.}
                \If{\eqref{eqn:workerrule2} is violated, or, $\tau_m^k\geq D$}
                \State{Upload $\delta_m^k$. \qquad\qquad~~~~\Comment{$\tau_m^{k+1}=1$}}
                \Else
                \State{Upload nothing.}\qquad~\Comment{$\tau_m^{k+1} = \tau_m^{k} + 1$}
                \EndIf

            \EndParFor
            \State{Server updates via \eqref{eqn:LASGiteration}.}
        \EndFor
    \end{algorithmic}
\end{algorithm}
\end{minipage}
   \end{tabular}
   \caption{A comparison of LASG-WK1 and LASG-WK2.}
\end{table*}

\subsection{Worker LASG: save communication uploads}\label{subsec.wk}
We first introduce two LASG variants that use variance-reduced rules to check gradient innovation at the worker side.
The first one that we term \textbf{LASG-WK1} will reuse the old gradient of worker $m$ at iteration $k$ if it satisfies
\begin{equation}\label{eqn:workerrule1}
\left\|\tilde{\delta}_m^k-\tilde{\delta}_m^{k-\tau_m^k}\right\|^2\leq\frac{1}{M^2}\sum\limits_{d=1}^Dc_d\left\|\theta^{k+1-d}-\theta^{k-d}\right\|^2
\end{equation}
where $\tilde{\delta}_m^k := \nabla \ell(\theta^k;\xi_m^k)-\nabla \ell(\tilde{\theta};\xi_m^k)$ is the stochastic gradient difference at a common sample $\xi_m^k$, $\tilde{\delta}_m^{k-\tau_m^k} := \nabla \ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})-\nabla \ell(\tilde{\theta};\xi_m^{k-\tau_m^k})$ is the stochastic gradient difference at a common sample $\xi_m^{k-\tau_m^k}$,
and $\tilde{\theta}$ is a snapshot of the previous iterate that will be updated every $D$ iterations.
If \eqref{eqn:workerrule1} is satisfied, the staleness increases by $\tau_m^{k+1} = \tau_m^{k} + 1$; otherwise, worker $m$ uploads the fresh stochastic gradient, and resets staleness as $\tau_m^{k+1}=1$.

The rationale of \eqref{eqn:workerrule1} follows next.
In contrast to the non-vanishing variance in the LAG-WK rule (see \eqref{eqn:variance-wk}),
the LASG-WK1 rule \eqref{eqn:workerrule1} reduces its inherent variance.
To see this, we can decompose the LHS of \eqref{eqn:workerrule1} as the difference of two \emph{variance reduced} stochastic gradients at iteration $k$ and $k-\tau_m^k$.
Using the stochastic gradient in SVRG as an example \citep{johnson2013accelerating},
the innovation can be written as
\begin{align*}
\tilde{\delta}_m^k-\tilde{\delta}_m^{k-\tau_m^k}=\left(\nabla\ell(\theta^k;\xi_m^k)-\nabla\ell(\tilde{\theta};\xi_m^k)+\nabla{\cal L}_m(\tilde{\theta})\right)
-\left(\nabla\ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})-\nabla\ell(\tilde{\theta};\xi_m^{k-\tau_m^k})+\nabla{\cal L}_m(\tilde{\theta})\right).
\end{align*}
Define the minimizer of \eqref{eqn: problem} as $\theta^{\star}$ and assume that $\nabla\ell(\theta;\xi_m)$ is $\bar{L}$-Lipschitz continuous for any $\xi_m$.
The expectation of the LHS of \eqref{eqn:workerrule1} can be \emph{upper-bounded} by
\begin{align}\label{eqn:variance-wk1}
\mathbb{E}\left[\big\|\tilde{\delta}_m^k-\tilde{\delta}_m^{k-\tau_m^k}\big\|^2\right]\leq8\bar{L}(\mathbb{E}{\cal L}(\theta^k)-{\cal L}(\theta^{\star}))
+8\bar{L}(\mathbb{E}{\cal L}(\theta^{k-\tau_m^k})-{\cal L}(\theta^{\star}))\!+\!16\bar{L}(\mathbb{E}{\cal L}(\tilde{\theta})-{\cal L}(\theta^{\star})).
\end{align}
If the iterate $\theta^k$ converges, e.g., $\theta^k, \theta^{k-\tau_m^k}, \tilde{\theta}\rightarrow \theta^*$, the RHS of \eqref{eqn:variance-wk1} diminishes, and thus the LHS of \eqref{eqn:workerrule1} diminishes. This is in contrast to the stochastic LAG-WK rule in \eqref{eqn:variance-wk} that is \emph{lower-bounded} by a non-diminishing value.

In addition to \eqref{eqn:workerrule1}, the second rule that we term \textbf{LASG-WK2} reuses the old gradient of worker $m$ if it satisfies
\begin{equation}\label{eqn:workerrule2}
\!\left\|\nabla \ell(\theta^k;\xi_m^k)-\!\nabla \ell(\theta^{k-\tau_m^k}_m\!;\xi_m^k)\right\|^2\!\leq\!\frac{1}{M^2}\!\sum\limits_{d=1}^D\!c_d\left\|\theta^{k+1-d}\!\!-\theta^{k-d}\right\|^2\!\!.
\end{equation}
If \eqref{eqn:workerrule2} is satisfied, the server will use the stale stochastic gradient $\nabla \ell(\theta^{k-\tau_m^k}_m;\xi_m^{k-\tau_m^k})$ for worker $m$, and the staleness increases by $\tau_m^{k+1} = \tau_m^{k} + 1$; otherwise, worker $m$ uploads the fresh stochastic gradient, and resets the staleness as $\tau_m^{k+1}=1$. Notice that different from the naive LAG-WK \eqref{eqn:LAGrule}, the LASG condition \eqref{eqn:workerrule2} is evaluated at two different iterates but on the same sample $\xi_m^k$.

Similar to LASG-WK1, the LASG-WK2 rule \eqref{eqn:workerrule2} also reduces its inherent variance, since the LHS of \eqref{eqn:workerrule2} can be written as the difference between a \emph{variance reduced} stochastic gradient and a \emph{deterministic} gradient, that is
\begin{align}\label{eqn:variance-wk2}
    \nabla\ell(\theta^k;\xi_m^k)-\nabla\ell(\theta^{k-\tau_m^k};\xi_m^k)=\big(\nabla\ell(\theta^k;\xi_m^k)
    -\nabla\ell(\theta^{k-\tau_m^k};\xi_m^k)+\nabla{\cal L}_m(\theta^{k-\tau_m^k})\big)-\nabla{\cal L}_m(\theta^{k-\tau_m^k}).
\end{align}
With derivations deferred to the supplementary document, similar to \eqref{eqn:variance-wk1} we can also conclude that
$\mathbb{E}[\|\nabla\ell(\theta^k;\xi_m^k)-\nabla\ell(\theta^{k-\tau_m^k};\xi_m^k)\|^2]\rightarrow 0$ as the iterate $\theta^k\rightarrow \theta^{\star}$.

\subsection{Server LASG: save up/downloads and calculations}\label{subsec.ps}
Besides the worker-side conditions, we next introduce two LASG variants that use variance-reduced rules to check model innovation at the server side, both of which do not even need to broadcast the current models. The rationale is that if the model difference is small, the gradient difference used in Section \ref{subsec.wk} is likely to be small.

The first one that we term \textbf{LASG-PS} will reuse the old gradient of worker $m$, given that the old parameter that worker $m$ used for computing the last stochastic gradient satisfies
\begin{equation}\label{eqn:serverrule}
L_m^2\left\|\theta^{k}-\theta^{k-\tau_m^k}\right\|^2\leq\frac{1}{M^2}\sum\limits_{d=1}^Dc_d\left\|\theta^{k+1-d}-\theta^{k-d}\right\|^2
\end{equation}
where $L_m$ is the smoothness constant of $\mathcal{L}_m(\theta)$. Condition \eqref{eqn:serverrule} can be checked at the server side without computing new gradients if the server stores $\{\theta^{k-\tau_m^k}\}$ that all workers used for computing the most recent stochastic gradients.

The LHS of \eqref{eqn:serverrule} can be \emph{upper-bounded} in expectation by
\begin{align}\label{eqn:variance-server}
\mathbb{E}\left[\big\|\theta^{k}-\theta^{k-\tau_m^k}\big\|^2\right]&\leq 2D \sum_{d=1}^{D}\mathbb{E}\left[\big\|\theta^{k-d}-\theta^{k-d-\tau_m^{k-d}}\big\|^2\right]\eta_{k-D}^2 \nonumber\\
&+2D \sum_{d=1}^{D}\mathbb{E}\left\|\nabla \mathcal{L}(\theta^{k-d})\right\|^2\eta_{k-D}^2+D^2 \left(\sum_{m\in {\cal M}}\sigma_m^2\right)\eta_{k-D}^2.
\end{align}
If the iterate $\theta^k$ does not diverge so that $\left\|\nabla \mathcal{L}(\theta^k)\right\|^2$ is bounded, then the diminishing stepsizes $\{\eta_k\}$ ensure that the second and third terms in the RHS of \eqref{eqn:variance-server} vanish. Using mathematical induction, the LHS of \eqref{eqn:serverrule} also diminishes. Therefore, similar to the variance-reduced gradient difference used in LASG-WK, the diminishing stepsizes can also make the LASG-PS condition effective asymptotically.

\begin{table*}[t]
\centering
\vspace{-0.9cm}
\begin{tabular}{c c}
\hspace{-0.5cm}
\begin{minipage}[t]{7.8cm}
\begin{algorithm}[H]
\caption{LASG-PS}
\label{alg: LASG-PS}
    \begin{algorithmic}[1]
  \State{\textbf{Input:} $\theta^0$, delay counter $\{\tau_m^0\}$, smoothness contants $\{L_m\}$, stepsizes $\{\eta_k\}$, maximum delay $D$.}
        \For{$k=0,1,\ldots, K-1$}
            \ParFor{ Worker $m=1,2,\ldots, M$}
            \State{Server checks condition \eqref{eqn:serverrule}.}
                \If{\eqref{eqn:serverrule} is violated or $\tau_m^k\geq D$} %
                \State{Server sends $\theta^k$ to worker $m$}
                \State{Worker $m$ computes $\nabla \ell(\theta^k;\xi_m^k)$.}
                \State{Worker $m$ uploads $\delta_m^k$.} \quad~~\Comment{$\tau_m^{k+1}=1$}
                \Else
                \State{No action.} \qquad\qquad~~\Comment{$\tau_m^{k+1} = \tau_m^{k} + 1$}
                \EndIf
            \EndParFor
            \State{Server updates via \eqref{eqn:LASGiteration}.}
        \EndFor
    \end{algorithmic}
\end{algorithm}
\end{minipage}
\begin{minipage}[t]{7.8cm}
\begin{algorithm}[H]
\caption{LASG-PSE}
\label{alg: LASG-PSE}
    \begin{algorithmic}[1]
  \State{\textbf{Input:} $\theta^0$, delay counter $\{\tau_m^0\}$, smoothness estimates $\{\hat{L}_m^0\}$, stepsizes $\{\eta_k\}$, maximum delay $D$.}
        \For{$k=0,1,\ldots, K-1$}
            \ParFor{ Worker $m=1,2,\ldots, M$}
            \State{Server checks condition \eqref{eqn:eserversule}.}
                \If{\eqref{eqn:eserversule} is violated or $\tau_m^k\geq D$} %
                \State{Server sends $\theta^k$ to worker $m$.}
                \State{Worker $m$ computes $\nabla \ell(\theta^k;\xi_m^k)$.}
                \State{Worker $m$ uploads $\delta_m^k$.} \quad~~\Comment{$\tau_m^{k+1}=1$}
                \State{Worker $m$ uploads $\hat{L}_m^{k+1}$ in \eqref{eqn:Lmestimate}.
                \Else
                \State{No action.} \qquad\qquad~~\Comment{$\tau_m^{k+1} = \tau_m^{k} + 1$}
                \EndIf
            \EndParFor
            \State{Server updates via \eqref{eqn:LASGiteration}.}
        \EndFor
    \end{algorithmic}
\end{algorithm}
\end{minipage}
\end{tabular}
\vspace{0.1cm}
\caption{A comparison of LASG-PS and LASG-PSE.}
\end{table*}

In many problems, however, $L_m$ is not always available, or, hard to compute. To resolve this issue, we develop LASG-PSE, a variation of LASG-PS that estimates $L_m$ ``on-the-fly.''
With $\hat{L}_m^k$ denoting the estimate of $L_m$, \textbf{LASG-PSE} will reuse the old gradient of worker $m$ if it satisfies
\begin{equation}\label{eqn:eserversule}
 (\hat{L}_m^k)^2\|\theta^{k}-\theta^{k-\tau_m^k}\|^2\leq\frac{1}{M^2}\sum\limits_{d=1}^Dc_d\|\theta^{k+1-d}-\theta^{k-d}\|^2
\end{equation}
where the estimated constant $\hat{L}_m^k$ is updated iteratively via
\begin{equation}\label{eqn:Lmestimate}
\!\!\hat{L}_m^{k+1}=\max\left\{\hat{L}_m^k, \frac{\|\nabla\ell(\theta^{k};\xi_m^k)-\nabla\ell(\theta^{k-\tau_m^k};\xi_m^k)\|}{\|\theta^{k}-\theta^{k-\tau_m^k}\|}\right\}.
\end{equation}

We summarize LASG-PS and LASG-PSE in Algorithms \ref{alg: LASG-PS} and \ref{alg: LASG-PSE}, and compare our four LASG variants in Table \ref{tab:3algcomp}.

\noindent\textbf{Comparison of all LASG variants.}
Comparing WK conditions with PS conditions in Table \ref{tab:3algcomp}, LASG-PS and LASG-PSE need \emph{extra memory} at the server side but save both \emph{local computation and download communication}, while LASG-WK1 and LASG-WK2 save only upload communication.
Between the two WK conditions, LASG-WK1 is more conservative as LASG-WK1 measures the change of gradients at two model states for both new and old data samples but LASG-WK2 measures only the change of gradient at the new sample.
Between the two PS conditions, LASG-PSE is more flexible since it does not require the knowledge of local smoothness $L_m$.
Given specific communication, computation, and memory requirements, we can flexibly choose different LASG.

\subsection{Quantized LASG: Further save communication bits}
The four LASG variants save the number of communication rounds.
To further reduce communication bits per round, we combine LASG with various quantization mechanisms. With the stochastic gradient $\nabla \ell(\theta;\xi)$, we define the gradient under a quantization operator ${\cal Q}$ as
\begin{equation}
Q(\theta;\xi)	:={\cal Q}\left(\nabla \ell(\theta;\xi)\right).
\end{equation}

We adopt the stochastic quantization scheme in \citep{alistarh2017qsgd} and develop the quantized LASG as
\begin{align*}
\theta^{k+1} \!=\! \theta^k\!-\!\eta_k\!\!\!\!\!\sum\limits_{m\in{\cal M}\backslash{\cal M}^k} \!\!\!\!\! Q(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})-\eta_k\!\!\!\!\sum\limits_{m\in{\cal M}^k}\!\!\!Q(\theta^k;\xi_m^k)
\end{align*}
where ${\cal M}^k$ is determined by one out of four rules \eqref{eqn:workerrule1}-\eqref{eqn:eserversule}.
We term the quantized LASG as LAQSG.

\section{Convergence Analysis}
In this section we present the convergence results of LASG-WK1, LASG-WK2 and LASG-PS in both the nonconvex and strongly convex cases, and the convergence results of LAQSG in the nonconvex case.
Due to the technical reasons, we leave the analysis of LASG-PSE for future work, but it empirically has very impressive performance.

First, we make some basic assumptions, which are standard in analyzing SGD and its variants \citep{ghadimi2013stochastic, johnson2013accelerating,alistarh2017qsgd}.
\begin{assumption}\label{assump:smoothness}
The loss function $\mathcal{L}$ is smooth with $L>0$.
\end{assumption}
\begin{assumption}\label{assump:gradientestimator}
The samples $\xi_m^1,\xi_m^2,\ldots$ are independent, and the stochastic gradient $\nabla\ell(\theta;\xi_m^k)$ satisfies
\begin{align}
    &\mathbb{E}_{\xi_m^k} \nabla\ell(\theta;\xi_m^k) = \nabla\mathcal{L}_m(\theta),\\
    &\mathbb{E}_{\xi_m^k} \left[\|\nabla\ell(\theta;\xi_m^k)-\nabla\mathcal{L}_m(\theta)\|^2\right]\leq\sigma_m^2. \label{eqn:boundedvariance}
\end{align}
\end{assumption}
For LASG-PS, we require an extra smoothness assumption.
\begin{assumption}\label{assump:localsmoothness}
The local gradient $\nabla\mathcal{L}_m$ is $L_m$-Lipschitz continuous, i.e. for any $\theta_1,\theta_2\in\mathbb{R}^p$, we have
\begin{equation}
    \|\nabla\mathcal{L}_m(\theta_1)-\nabla\mathcal{L}_m(\theta_2)\|\leq L_m\|\theta_1-\theta_2\|.
\end{equation}
\end{assumption}

With these assumptions, LASG will yield descent of $\mathcal{L}(\theta^k)$.
\begin{lemma}\label{lemma:lossdescent}
Under Assumptions \ref{assump:smoothness}, \ref{assump:gradientestimator} and \ref{assump:localsmoothness}, $\{\theta^k\}$ generated by Algorithms \ref{alg: LASG-WK1}, \ref{alg: LASG-WK2} and \ref{alg: LASG-PS} satisfy
\begin{align}\label{eqn:lossdescent}
    \mathbb{E}\mathcal{L}(\theta^{k+1})&\leq\mathbb{E}\mathcal{L}(\theta^k)-\left(\eta_k-L\eta_k^2\right)\mathbb{E}\left[\|\nabla\mathcal{L}(\theta^k)\|^2\right]\nonumber\\
    &+\sum\limits_{d=1}^D\Big(\big(\eta_k+\frac{1}{2L}\big)c_d+\frac{\sqrt{M}L}{12}\Big)\mathbb{E}\left[\|\theta^{k+1-d}-\theta^{k-d}\|^2\right]+L\eta_k^2\left(\frac{9}{2}+6\sqrt{M}D\right)\sum\limits_{m=1}^M\sigma_m^2.
\end{align}
\end{lemma}
\vspace{-0.15cm}
Note that all the terms on the right hand side of the inequality \eqref{eqn:lossdescent} show up in SGD analysis except $\|\theta^{k+1-d}\!-\!\theta^{k-d}\|^2$, which exists due to stale information.
To deal with this term, we introduce the following Lyapunov function:
\begin{equation}
\label{eqn:Lyapunov}
    V^k:=\mathbb{E}\mathcal{L}(\theta^k)-\mathcal{L}(\theta^{\star})+\sum\limits_{d=1}^{D}\gamma_d\mathbb{E}\left[\|\theta^{k+1-d}-\theta^{k-d}\|^2\right]
\end{equation}
where $\{\gamma_d\}_{d=1}^D$ are constants to be determined later. The following lemma is a direct application of Lemma \ref{lemma:lossdescent}.

\begin{lemma}\label{lemma:lyapunovdescent}
Under Assumptions \ref{assump:smoothness} and \ref{assump:gradientestimator}, there exist constants $\{A_d^k\}_{d=1}^D $, $B_0^k$ and $B_1^k$ such that
\begin{align}\label{descent}
    \mathbb{E} V^{k+1}-\mathbb{E} V^k\leq -B_0^k\mathbb{E}\left[\|\nabla\mathcal{L}(\theta^{k})\|^2\right]+B_1^k\sum\limits_{m=1}^M\sigma_m^2-\sum\limits_{d=1}^DA_d^k\mathbb{E}\left[\|\theta^{k+1-d}-\theta^{k-d}\|^2\right].
\end{align}
\end{lemma}
The constants $\{A_d^k\}_{d=1}^D$, $B_0^k$ and $B_1^k$ depend on stepsize $\eta_k$, $\gamma$ and $\{c_d\}_{d=1}^D$. Their expressions are specified in the supplementary materials. By choosing proper $\eta_k$ and $c_d$, we are able to ensure the convergence of LASG.

We first present the convergence in nonconvex case.
\begin{theorem}\label{thm:nonconvex}
{\normalfont \textsf{(nonconvex)}} Under Assumptions \ref{assump:smoothness}, \ref{assump:gradientestimator} (for Algorithm \ref{alg: LASG-PS} also Assumption \ref{assump:localsmoothness}), if $\eta_k=\eta={\cal O}(\frac{1}{\sqrt{K}})$ with $c_{\eta}>0$, and $c_d\leq\min\{\frac{1}{12D\eta^2},\frac{\sqrt{M}L^2}{18}\}$, then $\{\theta^k\}$ generated by Algorithms \ref{alg: LASG-WK1}-\ref{alg: LASG-PS} satisfy
\begin{equation}
    \frac{1}{K}\sum\limits_{k=0}^{K-1}\mathbb{E}\left[\|\nabla\mathcal{L}(\theta^k)\|^2\right]=O\left({1}/{\sqrt{K}}\right)

\end{equation}
\end{theorem}

Next we present the convergence results under the following strong convexity assumption on ${\cal L}(\theta)$.
\begin{assumption}\label{assump:strongconvexity}
The overall loss $\mathcal{L}(\theta)$ is $\mu$-strongly convex
\end{assumption}
Parallel to the sublinear convergence of SGD in the
strongly convex case, e.g., \citep{rakhlin2011making}, LASG algorithms achieve the $O(1/K)$ order of convergence.
\begin{theorem}\label{thm:stronglyconvex}
{\normalfont \textsf{(strongly convex)}} Under Assumption \ref{assump:smoothness},\ref{assump:gradientestimator},\ref{assump:strongconvexity} (for Algorithm \ref{alg: LASG-PS} only, also Assumption \ref{assump:localsmoothness}), if $\eta_k=\frac{2}{\mu(k+K_0)}$ for a given constant $K_0$, and $c_d\leq\min\{\frac{1}{24D\eta_0^2},\frac{\sqrt{M}L^2}{18}\}$, then $\theta^K$ generated by Algorithms \ref{alg: LASG-WK1}, \ref{alg: LASG-WK2} and \ref{alg: LASG-PS} satisfies
\begin{equation}
    \mathbb{E}\mathcal{L}(\theta^K)-\mathcal{L}(\theta^{\star})=O\left({1}/{K}\right)
\end{equation}
\end{theorem}

For the convergence of LAQSG algorithms, we make the following additional assumption that guarantees the bounded variance of the quantized stochastic gradient.
\begin{assumption}\label{assump:boundedgradient}
The gradient is bounded as $\mathbb{E}_{\xi_m}\left[\|\nabla\ell(\theta;\!\xi_m)\|^2\right]\!\leq\! B$ for any $\theta \in \mathbb{R}^p$.
\end{assumption}
Based on this assumption, we have the following result.
\begin{theorem}\label{thm:LAQSG}
{\normalfont \textsf{(LAQSG)}} Under Assumptions \ref{assump:smoothness}, \ref{assump:gradientestimator}, \ref{assump:boundedgradient} (also Assumption \ref{assump:localsmoothness} for Algorithm \ref{alg: LASG-PS}), if $\eta_k\!=\!\eta\!={\cal O}(\frac{1}{\sqrt{K}})$, $c_d\leq\min\{\frac{1}{16D\eta^2},\frac{\sqrt{M}L^2}{24}\}$ where $c_{\eta}>0$ is a constant, then $\{\theta^k\}$ generated by quantized Algorithms \ref{alg: LASG-WK1} - \ref{alg: LASG-PS} satisfy
\begin{equation}
    \frac{1}{K}\sum\limits_{k=0}^{K-1}\mathbb{E}\left[\|\nabla \mathcal{L}(\theta^{k})\|^2\right]=O\left({1}/{\sqrt{K}}\right).

\end{equation}
\end{theorem}

\begin{figure*}[t]
\centering

 \hspace*{-3ex}
    \includegraphics[width=.35\textwidth]{covtype_iter.pdf}
    \hspace*{-4ex}
    \includegraphics[width=.35\textwidth]{covtype_comm.pdf}
    \hspace*{-4ex}
    \includegraphics[width=.35\textwidth]{covtype_bits.pdf}

    \caption{Logistic regression on \textit{covtype} dataset in the heterogeneous setting}
    \label{fig:covtype}

\end{figure*}

\begin{figure*}[t]
\centering
 \hspace*{-3ex}
    \includegraphics[width=.35\textwidth]{nn_mnist_loss.pdf}
    \hspace*{-4ex}
    \includegraphics[width=.35\textwidth]{nn_mnist_comm.pdf}
    \hspace*{-4ex}
    \includegraphics[width=.35\textwidth]{nn_mnist_bits.pdf}
    \caption{Training Neural network on \textit{mnist} dataset in the heterogeneous setting.}
    \label{fig:NNmnist}
\end{figure*}

\begin{figure*}[t]
\centering
 \begin{subfigure}[b]{0.5\textwidth}
\centering
\includegraphics[width=1\textwidth]{mnist_loss_seed.pdf}
\caption{Training loss on \textit{mnist} dataset.}
    \label{fig:mnist_train_seed}
    \end{subfigure}%
 \begin{subfigure}[b]{0.5\textwidth}
\centering
\includegraphics[width=1\textwidth]{mnist_test_seed.pdf}
\caption{Training loss on \textit{mnist} dataset.}
    \label{fig:mnist_test_seed}
    \end{subfigure}%
 \caption{Simulations on \textit{mnist} dataset averaged over 30 trials.}
\end{figure*}

\begin{figure*}[t]
\centering
 \begin{subfigure}[b]{0.5\textwidth}
\centering
\includegraphics[width=1\textwidth]{imagenet_train.pdf}
\caption{Training loss on \textit{tiny imagenet} dataset.}
    \label{fig:imagenet_train}
    \end{subfigure}%
 \begin{subfigure}[b]{0.5\textwidth}
\centering
\includegraphics[width=1\textwidth]{imagenet_test.pdf}
\caption{Testing accuracy on \textit{tiny imagenet} dataset.}
    \label{fig:imagenet_test}
    \end{subfigure}%
 \caption{Simulations on \textit{tiny imagenet} dataset.}
\end{figure*}

\begin{table*}[t]
 \vspace{-0.2cm}
\centering
\resizebox{\textwidth}{!}{
\begin{tabular}{c||c|c|c|c|c|c|c||c|c|c|c|c}
\hline
\multirow{2}{*}{Algorithm} & \multirow{2}{*}{SGD} & \multirow{2}{*}{\!\!\!LAG-WK\!\!\!} & \multicolumn{4}{|c|}{LASG} &\multirow{2}{*}{\!\!\!local SGD\!\!\!} &\multirow{2}{*}{QSGD} & \multicolumn{4}{|c}{LAQSG}\\ \cline{4-7}\cline{10-13}
                     &                      &                         & WK1 & WK2 & PS & PSE
&                           &                      & WK1 & WK2 & PS & PSE \\ \hline\hline
ijcnn1(LR)&0.4383& 0.3317 & {\bf 0.2311} & {\bf 0.2308} & 0.2736  & 0.2356   & 0.2554 & 0.4382 & {\bf 0.2307} & 0.2316    & 0.2722  & 0.2356\\ \hline
mnist(LR) &0.4214& 0.4074 & 0.1826 & {\bf 0.1281} & 0.2950  & 0.1681 & 0.2189 & 0.4228 & {\bf 0.1486} & {\bf 0.1342}    & 0.2839  & 0.1572\\ \hline
covtype(LR)&0.6772&0.6727 & 0.5604 &{\bf 0.5523}& 0.6467 & 0.5985 & 0.6288 & 0.6772 &{\bf 0.5537}&{\bf 0.5477}& 0.6456 & 0.5914 \\ \hline
mnist(NN)&0.1544&0.1457&0.1063 &{\bf 0.0510} & ---& {\bf 0.0421} & 0.1178 & 0.2492 & 0.2327 & 0.1564 &--- &{\bf 0.1046}\\ \hline
\end{tabular}}
\caption{Loss after $10^3$ and $10^4$ communication rounds for logistic regression (LR) and neural network (NN) in heterogeneous setting.}
\label{table: 1}
\end{table*}

\begin{table*}[t]
    \vspace{0.2cm}
\centering
\resizebox{\textwidth}{!}{
\begin{tabular}{c||c|c|c|c|c|c|c||c|c|c|c|c}
\hline
\multirow{2}{*}{Algorithm} & \multirow{2}{*}{SGD} & \multirow{2}{*}{\!\!\!LAG-WK\!\!\!} & \multicolumn{4}{|c|}{LASG} &\multirow{2}{*}{\!\!\!local SGD\!\!\!} &\multirow{2}{*}{QSGD} & \multicolumn{4}{|c}{LAQSG}\\ \cline{4-7}\cline{10-13}
                     &                      &                         & WK1 & WK2 & PS & PSE
&                           &                      & WK1 & WK2 & PS & PSE \\ \hline\hline
ijcnn1(LR)&0.6356& 0.3672 & 0.3050 & 0.3037 & 0.3378 & 0.3053 & 0.3226 & 0.4597 & {\bf 0.2370} & {\bf 0.2363} & 0.2798 & {\bf 0.2411}\\ \hline
mnist(LR)&0.6989& 0.6762 & 0.5081 & 0.3859 & 0.6653 & 0.4029 & 0.6125 & 0.5690 & {\bf 0.1916} & {\bf 0.1681} & 0.4215 & {\bf 0.2071} \\ \hline
covtype(LR)&0.6837&0.6806 & 0.5770 & 0.5650 & 0.6620 & 0.6178 & 0.6483 & 0.6469 & {\bf 0.5273} & {\bf 0.5277} & 0.5930 & {\bf 0.5488} \\ \hline
mnist(NN)&0.3042&0.2792&0.2157 & 0.1159 &---&{\bf 0.0814}& 0.2472 & 0.2011 & 0.1602 &{\bf 0.1104} &---&{\bf 0.0764} \\ \hline
\end{tabular}}
\caption{Loss after $10^5$, $10^6$, $10^6$ bits of uploads for LR on ijcnn1, mnist, covtype,  and $10^8$ for NN in heterogeneous setting.}
\label{table: 2}
\end{table*}

\section{Simulations}
Numerical tests have been conducted on both logistic regression and neural network models.

We benchmark LA(Q)SG with SGD, LAG-WK, local SGD and QSGD. For local SGD \citep{lin2018don}, workers perform SGD independently to update local $\{\theta_m\}_{m=1}^M$, and $\{\theta_m\}_{m=1}^M$ then are averaged over all workers every $H$ iterations. In simulations, we did a grid search for SGD learning rates.
We consider the heterogeneous setting where data with same labels are unevenly assigned to $M$ workers.

\noindent\textbf{Logistic regression on ijcnn1, MNIST and covtype.}
The data are distributed across $M=10$ workers for ijcnn1, MNIST (with digits 3, 5) and $M=20$ for Covtype. For each worker, the batch size is selected to be 0.01 of the local data size for ijcnn1, MNIST and  0.001 for Covtype. The $\ell_2$-regularization parameter is set to be $10^{-5}$. We choose stepsize $\eta=0.1$. For all LASG algorithms, $D=100$ and $c_d=0.1/\eta^2/M^2$ for $d=1,2,\ldots 10$ and $c_d=0$ for $d=11,\ldots 100$. For local-SGD, the communication period is $H=50, 10, 20$ iterations for ijcnn1, MNIST, Covtype respectively. This is optimized to save communication as much as possible without largely affecting the convergence speed. For quantization methods, we perform 4-bit stochastic quantization \citep{alistarh2017qsgd}. Numerical results are reported in Figure \ref{fig:covtype} and in Tables \ref{table: 1}, \ref{table: 2}.
Performance averaged over multiple trails has also been reported in Figures \ref{fig:mnist_train_seed} and \ref{fig:mnist_test_seed}.
Supplementary materials have additional tests in Figures \ref{fig:ijcnn1_u}-\ref{fig:covtype_u} and Tables \ref{table: 3} and \ref{table: 4}.

\noindent\textbf{Neural network.}
We train a convolutional neural network with two convolution-ELU-maxpooling layers (ELU is a smoothed ReLU) followed by two fully-connected layers for 10 classes classification on MNIST. The data are distributed on $M=10$ workers. We choose stepsize $\eta=0.05$. Since the objective function is nonsmooth ($L_m$ is not available), LASG-PS is not considered in this test. For all LASG algorithms, we set $D=50$, $c_d=0.1/\eta^2/M^2$ for $d=1,2,\ldots 10$ and $c_d=0$ for $d=11,\ldots 50$.
For local-SGD, we set the communication period to be 4. For all quantization methods, we perform 8-bit stochastic quantization. Numerical results are reported in Figure \ref{fig:NNmnist} and listed in Tables \ref{table: 1} and \ref{table: 2}. Additional results can be found in Figures \ref{fig:NNmnist_u}-\ref{fig:NNmnist_test} and Tables \ref{table: 3}, \ref{table: 4} in the supplementary materials.

All algorithms have been tested on the popular \emph{tiny imagenet} dataset using the Resnet18 model initialized by weights pretrained on ImageNet1000; see the accuracy versus total time (communication and computation) in Figures \ref{fig:imagenet_train} and \ref{fig:imagenet_test}. For training loss, LASG-WK1 and -WK2 require much less total time than SGD and local SGD with $H=2$, but slightly more than local SGD with $H=4$ and $6$. However, as shown in Figure \ref{fig:imagenet_test}, local SGD with larger communication period sacrifices the testing accuracy by 3-4\%.

\begin{figure}[h]
\centering
\includegraphics[width=.45\textwidth]{covtype_grad.pdf}
\caption{Logistic regression on \textit{covtype} dataset in the heterogeneous setting.}
\label{fig:covtype_grad}
\end{figure}

In our numerical tests, all LASG algorithms achieve the same iteration complexity as SGD and outperform local-SGD in most cases.
Compared with SGD, LASG-WK2 and LASG-PSE reduce the number of communication rounds by around one order of magnitude for neural network training and even more for logistic regression. LASG-WK1 also reduce the communication by more than one order of magnitude for logistic regression.
Based on the results of LAG-WK and QSGD, it is evident that the selection rules \eqref{eqn:workerrule1}, \eqref{eqn:workerrule2} and \eqref{eqn:eserversule} of LASG-WK1, LASG-WK2 and LASG-PSE achieve more significant improvement in terms of saving communication and bits than the selection rule \eqref{eqn:LAGrule} of LAG-WK and stochastic quantization strategy of QSGD.

Although the performance of LASG-PS is not as impressive as other LASG algorithms in saving communication, it considerably saves local computation compared with other algorithms except LASG-PSE as shown in Figure \ref{fig:covtype_grad}. Moreover, LASG-PSE has performance gains in both saving communication and local computation.
The performance of LAQSG validates that the LASG algorithms can be easily equipped with stochastic quantization with additional benefits from quantization.

\section{Conclusions}
In this paper, we developed a class of LASG methods as communication-efficient variants of SGD.
LASG methods leverage a set of adaptive communication rules to detect and then skip less informative or redundant communication rounds between the server and workers during distributed learning.
To further reduce communication bandwidth, the quantized version of LASG is also presented.
Both LASG and their quantized version are simple to implement, and have convergence rate comparable to the original SGD. Extensions to nonsmooth and decentralized settings are also in our research agenda.

\vspace{3cm}

\section{Introduction}
We consider a cloud server and a set of $M$ mobile devices (workers) collected in ${\cal M}:=\{1,\ldots,M\}$.
Each device $m$ has its local dataset $\{\xi_n,\,n\in {\cal N}_m\}$, which defines the loss function of device $m$ as
\begin{align}
{\cal L}_m(\theta)\!:=\!\sum_{n\in{\cal N}_m}\!\ell(\theta;\xi_n),\quad m\in{\cal M}
\end{align}
where $\theta\in \mathbb{R}^p$ is the sought vector (e.g., parameters of a prediction model) and $\xi_n$ is a data sample.
For example, in linear regression, $\ell(\theta;\xi_n)$ is the square loss;
and, in deep learning, $\ell(\theta;\xi_n)$ is the loss function of a neural network, and $\theta$ concatenates the weights.
The goal is to solve %
\begin{align}\label{eqn: problem}
	\min_{\theta\in \mathbb{R}^p}~{\cal L}(\theta)~~~{\rm with}~~~{\cal L}(\theta):=\sum_{m\in{\cal M}}{\cal L}_m(\theta).
\end{align}
Problem \eqref{eqn: problem} also arises in a number of areas, such as
multi-agent optimization \citep{nedic2009}, distributed signal processing \citep{msechu2011tsp}, and distributed machine learning \citep{dean2012}.
While our algorithms can be applied to other settings, we focus on the federated learning setting.
In this case, for bandwidth and privacy concerns, local data $\{\xi_n, n\in{\cal N}_m\}$ at each worker $m$ are not uploaded to the server, and collaboration is needed through communication between the server and workers.

\begin{figure}[t]
\centering
\includegraphics[width=8cm]{lasg.pdf}
  \caption{Generic LASG implementation.}
\label{fig:lasg-diag}
\end{figure}

To solve \eqref{eqn: problem}, we can in principle apply the distributed version of stochastic gradient descent (SGD) method.
In this case, at iteration $k$, the server broadcasts the current model $\theta^k$ to \emph{all} the workers; each worker $m$ computes $\nabla  \ell(\theta^k; \xi_m^k)$ using a randomly selected sample or a minibatch of samples $\{\xi_m^k\}\subseteq\{\xi_n, n\in{\cal N}_m\}$, and then uploads it to the server; and once receiving stochastic gradients from all workers, the server updates the model parameters via
\begin{flalign}	\label{eqn:SGDiteration}
& {\rm \textbf{SGD}}\qquad\qquad\qquad\qquad\qquad\qquad\qquad \theta^{k+1}=\theta^k-\eta_k\sum\limits_{m\in{\cal M}} \nabla  \ell(\theta^k; \xi_m^k) &
\end{flalign}
where $\eta_k>0$ is the (possibly) time-varying stepsize used at iteration $k$.
When $\nabla  \ell(\theta^k; \xi_m^k)$ is an unbiased gradient estimator of $\mathcal{L}_m(\theta)$, the convergence of SGD update \eqref{eqn:SGDiteration} is guaranteed \citep{bottou2016}.
To implement \eqref{eqn:SGDiteration}, however, the server has to communicate with \emph{all} workers to obtain fresh $\{\nabla \ell(\theta^k; \xi_m^k) \}$.
This prevents the efficient implementation of SGD in scenarios where communication between the server and the workers is costly \citep{mcmahan2017}, since latency will degrade the overall performance.
Therefore, \emph{our goal} is to find the parameter $\theta$ that minimizes \eqref{eqn: problem} with minimal communication overhead.

\subsection{Our approach}
This paper puts forward a class of new stochastic optimization methods that can considerably reduce the redundant or less informative communication of SGD.
The key motivation is that during the distributed learning process, not all communication rounds between the server and the worker are equally important. So a natural solution is to use a condition that decides whether to communicate or not. In this case, if some workers are not communicating, the server uses their stale gradients so that stale gradients replace skipped fresh gradients.

Analogous to the distributed implementation of SGD \eqref{eqn:SGDiteration}, our new approaches also aggregate the stochastic gradients from all workers, but in a fairly lazy manner. Hence, we term our algorithms as \textbf{L}azily \textbf{A}ggregated \textbf{S}tochastic \textbf{G}radient (\textbf{LASG}). LASG has the following generic update
\begin{align}\label{eqn:LASGiteration}
\theta^{k+1} = \theta^k-\eta_k\!\!\!\sum\limits_{m\in{\cal M}\backslash{\cal M}^k} \!\!\!\nabla \ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})
-\eta_k\!\!\!\sum\limits_{m\in{\cal M}^k}\!\!\! \nabla\ell(\theta^k;\xi_m^k)
\end{align}
or equivalently (see also Figure \ref{fig:lasg-diag})
 \begin{flalign}\label{eqn:LASGiteration2}
&{\rm \textbf{Generic LASG}}\qquad\qquad\qquad\qquad  \theta^{k+1} = \theta^k-\eta_k\nabla^k\quad{\rm with}\quad\nabla^k\!=\!\nabla^{k-1}+\sum\limits_{m\in{\cal M}^k}\delta_m^k&
\end{flalign}
where $\delta_m^k := \nabla \ell(\theta^k;\xi_m^k)-\nabla \ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})$ is the stochastic gradient innovation, $\tau_m^k\geq 0$ is the staleness of the gradient from worker $m$ used by $k$-iteration, and ${\cal M}^k$ is the subset of workers uploading $\delta_m^k$ at iteration $k$. The stalenesses $\{\tau_m^k\}$ are controlled by the selection of subset ${\cal M}^k$: at iteration $k$, if worker $m\notin {\cal M}^k$, the server increases the staleness by $\tau_m^{k+1} = \tau_m^{k} + 1$; otherwise, worker $m$ uploads the stochastic gradient, and the server resets $\tau_m^{k+1}=1$.

Clearly, selection of subset ${\cal M}^k$ is critical in LASG. However, the challenges are 1) the importance of each communication round is dynamic, thus a fixed or nonadaptive condition is ineffective; and 2) the condition needs to be checked either at server or at worker locally and efficiently.

To overcome these challenges, we develop two types of adaptive conditions based on message innovations. They can be chosen under different \emph{communication}, \emph{computation} and \emph{memory} requirements.
The first type is adopted by each worker (WK), and the second one by the server (PS).

\noindent\textbf{LASG-WK}: At iteration $k$, the server broadcasts $\theta^k$ to all workers; every worker computes $\nabla \ell(\theta^k;\xi_m^k)$, and checks if it belongs to ${\cal M}^k$; only the workers in ${\cal M}^k$ upload $\delta^k_m$; the server updates via \eqref{eqn:LASGiteration2}.

\noindent\textbf{LASG-PS}: At iteration $k$, the server decides ${\cal M}^k$ and sends $\theta^k$ to workers in ${\cal M}^k$; each worker $m\!\in\!{\cal M}^k$ computes $\nabla \ell(\theta^k;\xi_m^k)$ and uploads $\delta^k_m$; the rest of workers do nothing; the server updates via \eqref{eqn:LASGiteration2};

With detailed description of LASG rules deferred to Section \ref{sec.LASG}, the contributions of this paper are listed as follows.

{\bf 1)} We introduce a class of novel (quantized) stochastic optimization approaches that
reuses stale stochastic gradients to reduce redundant communication.

{\bf 2)} We establish convergence of our proposed algorithms in strongly convex and nonconvex settings even when the datasets are non-i.i.d. across workers. The convergence rates match those of SGD in the respective settings.

{\bf 3)} We confirm performance gains of our novel distributed
algorithms over some alternatives using extensive numerical tests on logistic regression and neural network training.

\subsection{Related work}
Communication-efficient distributed learning methods have gained popularity recently \citep{Nedic2018,jordan2018}. Most popular methods belong to two categories: c1) reduce the number of bits per communication
round; and, c2) save the number of communication
rounds.
For c1), methods are centered around the ideas of \emph{quantization} and \emph{sparsification}.

\noindent\textbf{Quantization} has been successfully applied to several engineering tasks employing wireless sensor networks \citep{msechu2011tsp}. In the context of distributed machine learning, a 1-bit and multi-bits quantization methods have been developed in \citep{seide20141, bernstein2018icml,alistarh2017qsgd,magnusson2019maintaining}. Other variants of quantized gradient schemes include error compensation \citep{wu2018error}, variance-reduced quantization \citep{zhang2017zipml}, and quantization to a ternary vector \citep{wen2017terngrad}.

\noindent\textbf{Sparsification} amounts to transmitting only gradient coordinates with large enough magnitudes exceeding a certain threshold~\citep{strom2015scalable, aji2017sparse}.
To avoid losing information of skipping communication, small gradient components will be accumulated and then transmitted when they are large enough \citep{lin2017deep,stich2018nips,alistarh2018}. Recently, randomized sparsification approaches have also been developed in \citep{wangni2018gradient,wang2018atomo}.

However, both quantization and sparsification aim to resolve c1).
For exchanging messages, e.g., the $p$-dimensional $\theta$ or its gradient, other latencies (initiating communication links, queueing, and propagating the message) are at least comparable to the message size-dependent transmission latency \citep{peterson2007}. This motivates c2) reducing the number of communication rounds.

\noindent\textbf{Periodic communication.}
In contrast to the gradient compression schemes, schemes that reduce the number of communication rounds have also been developed, including the periodic averaging techniques, e.g., local stochastic gradient descent (a.k.a. local SGD) \citep{lin2018don,stich2019local,wang2018coop,yu2019icml,yu2019aaai}.
In local SGD, workers are allowed to perform local model updates independently and the resultant models are averaged periodically. In this way communication frequency is reduced.
The caveat is that most local SGD methods have performance guarantee in the \emph{homogeneous} settings, where the data are independent and identically distributed over all workers. However, this assumption rarely holds in federated learning \citep{mcmahan2017}.

\noindent\textbf{Intermittent communication.}
Different from periodic communication used in local SGD, adaptive uploading techniques have been studied in e.g., lazily aggregated gradient (LAG) approaches \citep{chen2018lag,sun2019}.
LAG is tailored for the \emph{heterogeneous} learning settings, and has provable performance gain when the data distributions vary across workers.
Models in LAG are updated at the server, and workers only adaptively upload information that is determined to be informative enough. Unfortunately, while the original LAG has good performance in the deterministic settings (e.g., with full gradient), its performance is significantly degraded in the stochastic settings. Recent efforts have been made towards adaptive uploading in stochastic settings \citep{li2019csgd}, but the proposed scheme therein requires an exponentially increasing batch size, which is not favorable in practice. In contrast, the LASG approaches can be viewed as the stochastic counterparts of the LAG, and our adaptive communication rules are new and tailored for SGD, which do not require the increasing batch size.

\section{Why LAG does not work well with SGD?}
Our LASG approaches are closely related to the recently developed LAG method \citep{chen2018lag}.
In this section, we revisit LAG and provide insights why it does not work well in stochastic settings.

\begin{figure}[t]
\centering
\includegraphics[width=.5\textwidth]{toyexample.pdf}
  \caption{Number of uploads in per epoch (10 iterations) under stochastic LAG-WK and LASG-WK2.}
  \label{toyexample}
\end{figure}

Because not every communication round is equally important during the learning process, LAG only admits useful communication, and otherwise, reuses stale information.
Instead of communicating with all $M$ workers as SGD in \eqref{eqn:SGDiteration}, the direct (or ``naive") stochastic version of LAG (specifically LAG-WK) selects the subset of workers ${\cal M}^k$ to obtain their \emph{fresh} stochastic gradients $\nabla{\cal L}_m\big(\theta^k;\xi_m^k\big)$, $m\in{\cal M}^k$.
The \textbf{direct stochastic LAG} also follows the generic update \eqref{eqn:LASGiteration}, but it selects ${\cal M}^k$ as: if worker $m$ finds the innovation of the fresh stochastic gradient $\nabla \ell(\theta^k;\xi_m^k)$ is small such that it satisfies (with pre-defined $\{c_d\geq0\}$)
{\begin{align}\label{eqn:LAGrule}
\Big\|\nabla \ell(\theta^k;\xi_m^k)-\nabla \ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})\Big\|^2
\!\leq\frac{1}{M^2}\sum\limits_{d=1}^Dc_d\big\|\theta^{k+1-d}-\theta^{k-d}\big\|^2\!
\end{align}}
then we reuse the old gradient, $m\in{\cal M}\backslash{\cal M}^k$, and increase the staleness by $\tau_m^{k+1} = \tau_m^{k} + 1$; otherwise, worker $m$ uploads the stochastic gradient, and resets $\tau_m^{k+1}=1$.

In the deterministic setting, LAG condition \eqref{eqn:LAGrule} is motivated by the elegant \emph{``larger descent per upload"} rationale, and has proved to be effective \citep{chen2018lag}.
Nevertheless, the observation here is that the two stochastic gradients \eqref{eqn:LAGrule} are evaluated on two different iterates ($\theta^k$ and $\theta^{k-\tau_m^k}$) and two different samples ($\xi_m^k$ and $\xi_m^{k-\tau_m^k}$) thus two different loss functions. This is in contrast to the original LAG condition in \citep{chen2018lag} where the gradient innovation is evaluated on the same function. This subtle difference leads to significant degradation in performance.

Figure \ref{toyexample} compares the stochastic LAG and one of our new algorithms LASG-WK2 (introduced later), and demonstrates that the stochastic LAG is not effective in saving communication --- when $c_d$ is set to be small (e.g., 0.4), \eqref{eqn:LAGrule} almost never satisfies; and when $c_d$ is set to be large (e.g., 4), \eqref{eqn:LAGrule} satisfies initially, but stops satisfying later. This can be explained by expanding the left-hand-side (LHS) of \eqref{eqn:LAGrule} by (see the supplemental material for the deduction)
\begin{subequations}\label{eqn:variance-wk}
\begin{align}
\mathbb{E}\left[\|\nabla\ell(\theta^k;\xi_m^k)-\nabla\ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})\|^2\right]
\geq \,&\frac{1}{2}\mathbb{E}\Big[\big\|\nabla\ell(\theta^k;\xi_m^k)-\nabla{\cal L}_m(\theta^k)\big\|^2\Big]\label{eqn:wk-rq1}\\
+\,&\frac{1}{2}\mathbb{E}\Big[\big[\big\|\nabla\ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})-\nabla{\cal L}_m(\theta^{k-\tau_m^k})\big\|^2\big]\Big]\label{eqn:wk-rq2}\\
-\,&\mathbb{E}[\|\nabla{\cal L}_m(\theta^k)-\nabla{\cal L}_m(\theta^{k-\tau_m^k})\|^2]. \label{eqn:wk-rq3}
\end{align}
\end{subequations}
Even if the iterate $\theta^k$ converges, e.g., $\theta^k\rightarrow \theta^*$, and thus the right-hand-side (RHS) of \eqref{eqn:LAGrule} $\big\|\theta^{k+1-d}\!-\!\theta^{k-d}\big\|^2\!\rightarrow\! 0$, the LHS of \eqref{eqn:LAGrule} does not, because the gradient variance appearing in \eqref{eqn:wk-rq1} and \eqref{eqn:wk-rq2} does not vanish yet the gradient difference at the same function \eqref{eqn:wk-rq3} diminishes.

Therefore, the key insight here is that the non-diminishing variance of stochastic gradients makes the direct implementation of the LAG rule \eqref{eqn:LAGrule} ineffective eventually.

 \begin{table*}[t]
\centering
 \begin{tabular}[t]{ c || c | c ||c |c|| c |c  }
 \hline\hline \textbf{Metric} &\multicolumn{2}{|c||}{\textbf{Communication}}& \multicolumn{2}{|c||}{\textbf{Computation}}& \multicolumn{2}{|c}{\textbf{Memory}}\\
\hline \!\textbf{Algorithm}\!&\textbf{PS$\rightarrow$WK}~$m$\!\!&\!\textbf{WK} $m$ $\rightarrow$\textbf{PS}\!& ~~~\textbf{PS}~~~&\textbf{WK}~$m$& ~~~\textbf{PS}~~~&\textbf{WK}~$m$\\ \hline \hline
\textbf{Sync SGD} & always &  always & \eqref{eqn:SGDiteration} & \eqref{eqn:SGDiteration} &  ${\cal O}(p)$& $/$ \\ \hline
     \textbf{LASG-WK1} & always &\!\!\!only if $m\!\in\!{\cal M}^k$\!\!\!  & \!\!\! \eqref{eqn:LASGiteration2}\!\! & \!\! \eqref{eqn:workerrule1} &  \!\!\!\! ${\cal O}(p)$\!\!\!& \!\!\!\!${\cal O}(p)$\!\!\!\!  \\\hline
    \textbf{LASG-WK2} & always & \!\!\!only if $m\!\in\!{\cal M}^k$\!\!\! & \eqref{eqn:LASGiteration2}  &\!\!\!$\eqref{eqn:workerrule2}$\!\!\!&  ${\cal O}(p)$&\!\!\!\!\! ${\cal O}(p)$\!\!\!\!\\ \hline
    \textbf{LASG-PS} & only if $m\!\in\!{\cal M}^k$ & \!\!\!only if $m\!\in\!{\cal M}^k$\!\!\! & \eqref{eqn:LASGiteration2},\eqref{eqn:serverrule}  & \!\!only if $m\!\in\!{\cal M}^k$ \!\!\!&  ${\cal O}(Mp)$&\!\!\!${\cal O}(p)$\!\!\\ \hline
        \textbf{LASG-PSE} & only if $m\!\in\!{\cal M}^k$ & \!\!\!only if $m\!\in\!{\cal M}^k$\!\!\! & \eqref{eqn:LASGiteration2},\eqref{eqn:eserversule}  & \!\!only if $m\!\in\!{\cal M}^k$ \!\!\!&  ${\cal O}(Mp)$ &\!\!\!${\cal O}(p)$\!\!\!\\ \hline\hline
    \end{tabular}
\caption{A comparison of communication, computation and memory requirements.
\textbf{PS} denotes the parameter server, \textbf{WK} denotes the worker,
\textbf{PS$\rightarrow$WK $m$} is the download from the server to the worker $m$, and \textbf{WK} $m$ $\rightarrow$ \textbf{PS} is the upload from the worker $m$ to the server.}
\label{tab:3algcomp}
\end{table*}

\section{LASG: Lazily Aggregated Stochastic Gradient Approach}\label{sec.LASG}
In this section, we formally develop our LASG method, and present the intuition
behind its design.

While the updates of stochastic LAG and LASG \eqref{eqn:LASGiteration} look identical, the choice of ${\cal M}^k$ in them is very different.
To overcome the limitations of LAG in stochastic settings, the key of the LASG design is to \textbf{reduce the variance of the innovation measure} appeared in the adaptive condition.

Towards this goal, we develop two types of LASG rules to select ${\cal M}^k$.
The first type is adopted by each worker that uses the gradient difference as the innovation measure but a \emph{variance-reduced} gradient difference; and the second one by the parameter server that uses the model difference as the innovation measure, but uses a sequence of \emph{diminishing stepsizes} to control variance.

\begin{table*}[t]
\centering
    \begin{tabular}{c c}
    \hspace{-0.2cm}
\begin{minipage}[t]{7.8cm}
  \vspace{0pt}
\begin{algorithm}[H]
\caption{LASG-WK1}\label{alg: LASG-WK1}
    \begin{algorithmic}[1]
    \State{\textbf{Input:} Delay counter $\{\tau_m^0\}$,  stepsizes $\{\eta_k\}$, max delay $D$.}
        \For{$k=0,1,\ldots, K-1$}
            \State{Server broadcasts $\theta^k$ to all workers.}
            \State{All workers save $\tilde{\theta}=\theta^k$ if $k \mod D=0$.}
            \ParFor{ Worker $m=1,2,\ldots, M$}
            \State{Compute $\nabla \ell(\theta^k;\xi_m^k)$ and $\nabla \ell(\tilde{\theta};\xi_m^k)$.}
            \State{Check condition \eqref{eqn:workerrule1} with stored $\tilde{\delta}_m^{k-\tau_m^{k}}$.}

                \If{\eqref{eqn:workerrule1} is violated, or, $k\mod D=0$}
                \State{Upload $\delta_m^k$.}
               \qquad\quad\Comment{$\tau_m^{k+1}=1$
                \Else
                \State{Upload nothing.}\quad\Comment{$\tau_m^{k+1} = \tau_m^{k} + 1$}
                \EndIf

            \EndParFor
            \State{Server updates via \eqref{eqn:LASGiteration}.}
        \EndFor
    \end{algorithmic}
  \end{algorithm}
\end{minipage}
\begin{minipage}[t]{7.8cm}
  \vspace{0pt}
  \begin{algorithm}[H]
\caption{LASG-WK2}
\label{alg: LASG-WK2}
    \begin{algorithmic}[1]
        \State{\textbf{Input:} Delay counter $\{\tau_m^0\}$,  stepsizes $\{\eta_k\}$, max delay $D$.}
        \For{$k=0,1,\ldots, K-1$}
            \State{Server broadcasts $\theta^k$ to all workers.}
            \ParFor{ Worker $m=1,2,\ldots, M$}
            \State{Compute $\nabla \ell(\theta^k;\xi_m^k)$ and $\nabla \ell(\theta^{k-\tau_m^k}_m;\xi_m^k)$.}
            \State{Check condition \eqref{eqn:workerrule2}.}
                \If{\eqref{eqn:workerrule2} is violated, or, $\tau_m^k\geq D$}
                \State{Upload $\delta_m^k$. \qquad\qquad~~~~\Comment{$\tau_m^{k+1}=1$}}
                \Else
                \State{Upload nothing.}\qquad~\Comment{$\tau_m^{k+1} = \tau_m^{k} + 1$}
                \EndIf

            \EndParFor
            \State{Server updates via \eqref{eqn:LASGiteration}.}
        \EndFor
    \end{algorithmic}
\end{algorithm}
\end{minipage}
   \end{tabular}
   \caption{A comparison of LASG-WK1 and LASG-WK2.}
\end{table*}

\subsection{Worker LASG: save communication uploads}\label{subsec.wk}
We first introduce two LASG variants that use variance-reduced rules to check gradient innovation at the worker side.
The first one that we term \textbf{LASG-WK1} will reuse the old gradient of worker $m$ at iteration $k$ if it satisfies
\begin{equation}\label{eqn:workerrule1}
\left\|\tilde{\delta}_m^k-\tilde{\delta}_m^{k-\tau_m^k}\right\|^2\leq\frac{1}{M^2}\sum\limits_{d=1}^Dc_d\left\|\theta^{k+1-d}-\theta^{k-d}\right\|^2
\end{equation}
where $\tilde{\delta}_m^k := \nabla \ell(\theta^k;\xi_m^k)-\nabla \ell(\tilde{\theta};\xi_m^k)$ is the stochastic gradient difference at a common sample $\xi_m^k$, $\tilde{\delta}_m^{k-\tau_m^k} := \nabla \ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})-\nabla \ell(\tilde{\theta};\xi_m^{k-\tau_m^k})$ is the stochastic gradient difference at a common sample $\xi_m^{k-\tau_m^k}$,
and $\tilde{\theta}$ is a snapshot of the previous iterate that will be updated every $D$ iterations.
If \eqref{eqn:workerrule1} is satisfied, the staleness increases by $\tau_m^{k+1} = \tau_m^{k} + 1$; otherwise, worker $m$ uploads the fresh stochastic gradient, and resets staleness as $\tau_m^{k+1}=1$.

The rationale of \eqref{eqn:workerrule1} follows next.
In contrast to the non-vanishing variance in the LAG-WK rule (see \eqref{eqn:variance-wk}),
the LASG-WK1 rule \eqref{eqn:workerrule1} reduces its inherent variance.
To see this, we can decompose the LHS of \eqref{eqn:workerrule1} as the difference of two \emph{variance reduced} stochastic gradients at iteration $k$ and $k-\tau_m^k$.
Using the stochastic gradient in SVRG as an example \citep{johnson2013accelerating},
the innovation can be written as
\begin{align*}
\tilde{\delta}_m^k-\tilde{\delta}_m^{k-\tau_m^k}=\left(\nabla\ell(\theta^k;\xi_m^k)-\nabla\ell(\tilde{\theta};\xi_m^k)+\nabla{\cal L}_m(\tilde{\theta})\right)
-\left(\nabla\ell(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})-\nabla\ell(\tilde{\theta};\xi_m^{k-\tau_m^k})+\nabla{\cal L}_m(\tilde{\theta})\right).
\end{align*}
Define the minimizer of \eqref{eqn: problem} as $\theta^{\star}$ and assume that $\nabla\ell(\theta;\xi_m)$ is $\bar{L}$-Lipschitz continuous for any $\xi_m$.
The expectation of the LHS of \eqref{eqn:workerrule1} can be \emph{upper-bounded} by
\begin{align}\label{eqn:variance-wk1}
\mathbb{E}\left[\big\|\tilde{\delta}_m^k-\tilde{\delta}_m^{k-\tau_m^k}\big\|^2\right]\leq8\bar{L}(\mathbb{E}{\cal L}(\theta^k)-{\cal L}(\theta^{\star}))
+8\bar{L}(\mathbb{E}{\cal L}(\theta^{k-\tau_m^k})-{\cal L}(\theta^{\star}))\!+\!16\bar{L}(\mathbb{E}{\cal L}(\tilde{\theta})-{\cal L}(\theta^{\star})).
\end{align}
If the iterate $\theta^k$ converges, e.g., $\theta^k, \theta^{k-\tau_m^k}, \tilde{\theta}\rightarrow \theta^*$, the RHS of \eqref{eqn:variance-wk1} diminishes, and thus the LHS of \eqref{eqn:workerrule1} diminishes. This is in contrast to the stochastic LAG-WK rule in \eqref{eqn:variance-wk} that is \emph{lower-bounded} by a non-diminishing value.

In addition to \eqref{eqn:workerrule1}, the second rule that we term \textbf{LASG-WK2} reuses the old gradient of worker $m$ if it satisfies
\begin{equation}\label{eqn:workerrule2}
\!\left\|\nabla \ell(\theta^k;\xi_m^k)-\!\nabla \ell(\theta^{k-\tau_m^k}_m\!;\xi_m^k)\right\|^2\!\leq\!\frac{1}{M^2}\!\sum\limits_{d=1}^D\!c_d\left\|\theta^{k+1-d}\!\!-\theta^{k-d}\right\|^2\!\!.
\end{equation}
If \eqref{eqn:workerrule2} is satisfied, the server will use the stale stochastic gradient $\nabla \ell(\theta^{k-\tau_m^k}_m;\xi_m^{k-\tau_m^k})$ for worker $m$, and the staleness increases by $\tau_m^{k+1} = \tau_m^{k} + 1$; otherwise, worker $m$ uploads the fresh stochastic gradient, and resets the staleness as $\tau_m^{k+1}=1$. Notice that different from the naive LAG-WK \eqref{eqn:LAGrule}, the LASG condition \eqref{eqn:workerrule2} is evaluated at two different iterates but on the same sample $\xi_m^k$.

Similar to LASG-WK1, the LASG-WK2 rule \eqref{eqn:workerrule2} also reduces its inherent variance, since the LHS of \eqref{eqn:workerrule2} can be written as the difference between a \emph{variance reduced} stochastic gradient and a \emph{deterministic} gradient, that is
\begin{align}\label{eqn:variance-wk2}
    \nabla\ell(\theta^k;\xi_m^k)-\nabla\ell(\theta^{k-\tau_m^k};\xi_m^k)=\big(\nabla\ell(\theta^k;\xi_m^k)
    -\nabla\ell(\theta^{k-\tau_m^k};\xi_m^k)+\nabla{\cal L}_m(\theta^{k-\tau_m^k})\big)-\nabla{\cal L}_m(\theta^{k-\tau_m^k}).
\end{align}
With derivations deferred to the supplementary document, similar to \eqref{eqn:variance-wk1} we can also conclude that
$\mathbb{E}[\|\nabla\ell(\theta^k;\xi_m^k)-\nabla\ell(\theta^{k-\tau_m^k};\xi_m^k)\|^2]\rightarrow 0$ as the iterate $\theta^k\rightarrow \theta^{\star}$.

\subsection{Server LASG: save up/downloads and calculations}\label{subsec.ps}
Besides the worker-side conditions, we next introduce two LASG variants that use variance-reduced rules to check model innovation at the server side, both of which do not even need to broadcast the current models. The rationale is that if the model difference is small, the gradient difference used in Section \ref{subsec.wk} is likely to be small.

The first one that we term \textbf{LASG-PS} will reuse the old gradient of worker $m$, given that the old parameter that worker $m$ used for computing the last stochastic gradient satisfies
\begin{equation}\label{eqn:serverrule}
L_m^2\left\|\theta^{k}-\theta^{k-\tau_m^k}\right\|^2\leq\frac{1}{M^2}\sum\limits_{d=1}^Dc_d\left\|\theta^{k+1-d}-\theta^{k-d}\right\|^2
\end{equation}
where $L_m$ is the smoothness constant of $\mathcal{L}_m(\theta)$. Condition \eqref{eqn:serverrule} can be checked at the server side without computing new gradients if the server stores $\{\theta^{k-\tau_m^k}\}$ that all workers used for computing the most recent stochastic gradients.

The LHS of \eqref{eqn:serverrule} can be \emph{upper-bounded} in expectation by
\begin{align}\label{eqn:variance-server}
\mathbb{E}\left[\big\|\theta^{k}-\theta^{k-\tau_m^k}\big\|^2\right]&\leq 2D \sum_{d=1}^{D}\mathbb{E}\left[\big\|\theta^{k-d}-\theta^{k-d-\tau_m^{k-d}}\big\|^2\right]\eta_{k-D}^2 \nonumber\\
&+2D \sum_{d=1}^{D}\mathbb{E}\left\|\nabla \mathcal{L}(\theta^{k-d})\right\|^2\eta_{k-D}^2+D^2 \left(\sum_{m\in {\cal M}}\sigma_m^2\right)\eta_{k-D}^2.
\end{align}
If the iterate $\theta^k$ does not diverge so that $\left\|\nabla \mathcal{L}(\theta^k)\right\|^2$ is bounded, then the diminishing stepsizes $\{\eta_k\}$ ensure that the second and third terms in the RHS of \eqref{eqn:variance-server} vanish. Using mathematical induction, the LHS of \eqref{eqn:serverrule} also diminishes. Therefore, similar to the variance-reduced gradient difference used in LASG-WK, the diminishing stepsizes can also make the LASG-PS condition effective asymptotically.

\begin{table*}[t]
\centering
\vspace{-0.9cm}
\begin{tabular}{c c}
\hspace{-0.5cm}
\begin{minipage}[t]{7.8cm}
\begin{algorithm}[H]
\caption{LASG-PS}
\label{alg: LASG-PS}
    \begin{algorithmic}[1]
  \State{\textbf{Input:} $\theta^0$, delay counter $\{\tau_m^0\}$, smoothness contants $\{L_m\}$, stepsizes $\{\eta_k\}$, maximum delay $D$.}
        \For{$k=0,1,\ldots, K-1$}
            \ParFor{ Worker $m=1,2,\ldots, M$}
            \State{Server checks condition \eqref{eqn:serverrule}.}
                \If{\eqref{eqn:serverrule} is violated or $\tau_m^k\geq D$} %
                \State{Server sends $\theta^k$ to worker $m$}
                \State{Worker $m$ computes $\nabla \ell(\theta^k;\xi_m^k)$.}
                \State{Worker $m$ uploads $\delta_m^k$.} \quad~~\Comment{$\tau_m^{k+1}=1$}
                \Else
                \State{No action.} \qquad\qquad~~\Comment{$\tau_m^{k+1} = \tau_m^{k} + 1$}
                \EndIf
            \EndParFor
            \State{Server updates via \eqref{eqn:LASGiteration}.}
        \EndFor
    \end{algorithmic}
\end{algorithm}
\end{minipage}
\begin{minipage}[t]{7.8cm}
\begin{algorithm}[H]
\caption{LASG-PSE}
\label{alg: LASG-PSE}
    \begin{algorithmic}[1]
  \State{\textbf{Input:} $\theta^0$, delay counter $\{\tau_m^0\}$, smoothness estimates $\{\hat{L}_m^0\}$, stepsizes $\{\eta_k\}$, maximum delay $D$.}
        \For{$k=0,1,\ldots, K-1$}
            \ParFor{ Worker $m=1,2,\ldots, M$}
            \State{Server checks condition \eqref{eqn:eserversule}.}
                \If{\eqref{eqn:eserversule} is violated or $\tau_m^k\geq D$} %
                \State{Server sends $\theta^k$ to worker $m$.}
                \State{Worker $m$ computes $\nabla \ell(\theta^k;\xi_m^k)$.}
                \State{Worker $m$ uploads $\delta_m^k$.} \quad~~\Comment{$\tau_m^{k+1}=1$}
                \State{Worker $m$ uploads $\hat{L}_m^{k+1}$ in \eqref{eqn:Lmestimate}.
                \Else
                \State{No action.} \qquad\qquad~~\Comment{$\tau_m^{k+1} = \tau_m^{k} + 1$}
                \EndIf
            \EndParFor
            \State{Server updates via \eqref{eqn:LASGiteration}.}
        \EndFor
    \end{algorithmic}
\end{algorithm}
\end{minipage}
\end{tabular}
\vspace{0.1cm}
\caption{A comparison of LASG-PS and LASG-PSE.}
\end{table*}

In many problems, however, $L_m$ is not always available, or, hard to compute. To resolve this issue, we develop LASG-PSE, a variation of LASG-PS that estimates $L_m$ ``on-the-fly.''
With $\hat{L}_m^k$ denoting the estimate of $L_m$, \textbf{LASG-PSE} will reuse the old gradient of worker $m$ if it satisfies
\begin{equation}\label{eqn:eserversule}
 (\hat{L}_m^k)^2\|\theta^{k}-\theta^{k-\tau_m^k}\|^2\leq\frac{1}{M^2}\sum\limits_{d=1}^Dc_d\|\theta^{k+1-d}-\theta^{k-d}\|^2
\end{equation}
where the estimated constant $\hat{L}_m^k$ is updated iteratively via
\begin{equation}\label{eqn:Lmestimate}
\!\!\hat{L}_m^{k+1}=\max\left\{\hat{L}_m^k, \frac{\|\nabla\ell(\theta^{k};\xi_m^k)-\nabla\ell(\theta^{k-\tau_m^k};\xi_m^k)\|}{\|\theta^{k}-\theta^{k-\tau_m^k}\|}\right\}.
\end{equation}

We summarize LASG-PS and LASG-PSE in Algorithms \ref{alg: LASG-PS} and \ref{alg: LASG-PSE}, and compare our four LASG variants in Table \ref{tab:3algcomp}.

\noindent\textbf{Comparison of all LASG variants.}
Comparing WK conditions with PS conditions in Table \ref{tab:3algcomp}, LASG-PS and LASG-PSE need \emph{extra memory} at the server side but save both \emph{local computation and download communication}, while LASG-WK1 and LASG-WK2 save only upload communication.
Between the two WK conditions, LASG-WK1 is more conservative as LASG-WK1 measures the change of gradients at two model states for both new and old data samples but LASG-WK2 measures only the change of gradient at the new sample.
Between the two PS conditions, LASG-PSE is more flexible since it does not require the knowledge of local smoothness $L_m$.
Given specific communication, computation, and memory requirements, we can flexibly choose different LASG.

\subsection{Quantized LASG: Further save communication bits}
The four LASG variants save the number of communication rounds.
To further reduce communication bits per round, we combine LASG with various quantization mechanisms. With the stochastic gradient $\nabla \ell(\theta;\xi)$, we define the gradient under a quantization operator ${\cal Q}$ as
\begin{equation}
Q(\theta;\xi)	:={\cal Q}\left(\nabla \ell(\theta;\xi)\right).
\end{equation}

We adopt the stochastic quantization scheme in \citep{alistarh2017qsgd} and develop the quantized LASG as
\begin{align*}
\theta^{k+1} \!=\! \theta^k\!-\!\eta_k\!\!\!\!\!\sum\limits_{m\in{\cal M}\backslash{\cal M}^k} \!\!\!\!\! Q(\theta^{k-\tau_m^k};\xi_m^{k-\tau_m^k})-\eta_k\!\!\!\!\sum\limits_{m\in{\cal M}^k}\!\!\!Q(\theta^k;\xi_m^k)
\end{align*}
where ${\cal M}^k$ is determined by one out of four rules \eqref{eqn:workerrule1}-\eqref{eqn:eserversule}.
We term the quantized LASG as LAQSG.

\section{Convergence Analysis}
In this section we present the convergence results of LASG-WK1, LASG-WK2 and LASG-PS in both the nonconvex and strongly convex cases, and the convergence results of LAQSG in the nonconvex case.
Due to the technical reasons, we leave the analysis of LASG-PSE for future work, but it empirically has very impressive performance.

First, we make some basic assumptions, which are standard in analyzing SGD and its variants \citep{ghadimi2013stochastic, johnson2013accelerating,alistarh2017qsgd}.
\begin{assumption}\label{assump:smoothness}
The loss function $\mathcal{L}$ is smooth with $L>0$.
\end{assumption}
\begin{assumption}\label{assump:gradientestimator}
The samples $\xi_m^1,\xi_m^2,\ldots$ are independent, and the stochastic gradient $\nabla\ell(\theta;\xi_m^k)$ satisfies
\begin{align}
    &\mathbb{E}_{\xi_m^k} \nabla\ell(\theta;\xi_m^k) = \nabla\mathcal{L}_m(\theta),\\
    &\mathbb{E}_{\xi_m^k} \left[\|\nabla\ell(\theta;\xi_m^k)-\nabla\mathcal{L}_m(\theta)\|^2\right]\leq\sigma_m^2. \label{eqn:boundedvariance}
\end{align}
\end{assumption}
For LASG-PS, we require an extra smoothness assumption.
\begin{assumption}\label{assump:localsmoothness}
The local gradient $\nabla\mathcal{L}_m$ is $L_m$-Lipschitz continuous, i.e. for any $\theta_1,\theta_2\in\mathbb{R}^p$, we have
\begin{equation}
    \|\nabla\mathcal{L}_m(\theta_1)-\nabla\mathcal{L}_m(\theta_2)\|\leq L_m\|\theta_1-\theta_2\|.
\end{equation}
\end{assumption}

With these assumptions, LASG will yield descent of $\mathcal{L}(\theta^k)$.
\begin{lemma}\label{lemma:lossdescent}
Under Assumptions \ref{assump:smoothness}, \ref{assump:gradientestimator} and \ref{assump:localsmoothness}, $\{\theta^k\}$ generated by Algorithms \ref{alg: LASG-WK1}, \ref{alg: LASG-WK2} and \ref{alg: LASG-PS} satisfy
\begin{align}\label{eqn:lossdescent}
    \mathbb{E}\mathcal{L}(\theta^{k+1})&\leq\mathbb{E}\mathcal{L}(\theta^k)-\left(\eta_k-L\eta_k^2\right)\mathbb{E}\left[\|\nabla\mathcal{L}(\theta^k)\|^2\right]\nonumber\\
    &+\sum\limits_{d=1}^D\Big(\big(\eta_k+\frac{1}{2L}\big)c_d+\frac{\sqrt{M}L}{12}\Big)\mathbb{E}\left[\|\theta^{k+1-d}-\theta^{k-d}\|^2\right]+L\eta_k^2\left(\frac{9}{2}+6\sqrt{M}D\right)\sum\limits_{m=1}^M\sigma_m^2.
\end{align}
\end{lemma}
\vspace{-0.15cm}
Note that all the terms on the right hand side of the inequality \eqref{eqn:lossdescent} show up in SGD analysis except $\|\theta^{k+1-d}\!-\!\theta^{k-d}\|^2$, which exists due to stale information.
To deal with this term, we introduce the following Lyapunov function:
\begin{equation}
\label{eqn:Lyapunov}
    V^k:=\mathbb{E}\mathcal{L}(\theta^k)-\mathcal{L}(\theta^{\star})+\sum\limits_{d=1}^{D}\gamma_d\mathbb{E}\left[\|\theta^{k+1-d}-\theta^{k-d}\|^2\right]
\end{equation}
where $\{\gamma_d\}_{d=1}^D$ are constants to be determined later. The following lemma is a direct application of Lemma \ref{lemma:lossdescent}.

\begin{lemma}\label{lemma:lyapunovdescent}
Under Assumptions \ref{assump:smoothness} and \ref{assump:gradientestimator}, there exist constants $\{A_d^k\}_{d=1}^D $, $B_0^k$ and $B_1^k$ such that
\begin{align}\label{descent}
    \mathbb{E} V^{k+1}-\mathbb{E} V^k\leq -B_0^k\mathbb{E}\left[\|\nabla\mathcal{L}(\theta^{k})\|^2\right]+B_1^k\sum\limits_{m=1}^M\sigma_m^2-\sum\limits_{d=1}^DA_d^k\mathbb{E}\left[\|\theta^{k+1-d}-\theta^{k-d}\|^2\right].
\end{align}
\end{lemma}
The constants $\{A_d^k\}_{d=1}^D$, $B_0^k$ and $B_1^k$ depend on stepsize $\eta_k$, $\gamma$ and $\{c_d\}_{d=1}^D$. Their expressions are specified in the supplementary materials. By choosing proper $\eta_k$ and $c_d$, we are able to ensure the convergence of LASG.

We first present the convergence in nonconvex case.
\begin{theorem}\label{thm:nonconvex}
{\normalfont \textsf{(nonconvex)}} Under Assumptions \ref{assump:smoothness}, \ref{assump:gradientestimator} (for Algorithm \ref{alg: LASG-PS} also Assumption \ref{assump:localsmoothness}), if $\eta_k=\eta={\cal O}(\frac{1}{\sqrt{K}})$ with $c_{\eta}>0$, and $c_d\leq\min\{\frac{1}{12D\eta^2},\frac{\sqrt{M}L^2}{18}\}$, then $\{\theta^k\}$ generated by Algorithms \ref{alg: LASG-WK1}-\ref{alg: LASG-PS} satisfy
\begin{equation}
    \frac{1}{K}\sum\limits_{k=0}^{K-1}\mathbb{E}\left[\|\nabla\mathcal{L}(\theta^k)\|^2\right]=O\left({1}/{\sqrt{K}}\right)

\end{equation}
\end{theorem}

Next we present the convergence results under the following strong convexity assumption on ${\cal L}(\theta)$.
\begin{assumption}\label{assump:strongconvexity}
The overall loss $\mathcal{L}(\theta)$ is $\mu$-strongly convex
\end{assumption}
Parallel to the sublinear convergence of SGD in the
strongly convex case, e.g., \citep{rakhlin2011making}, LASG algorithms achieve the $O(1/K)$ order of convergence.
\begin{theorem}\label{thm:stronglyconvex}
{\normalfont \textsf{(strongly convex)}} Under Assumption \ref{assump:smoothness},\ref{assump:gradientestimator},\ref{assump:strongconvexity} (for Algorithm \ref{alg: LASG-PS} only, also Assumption \ref{assump:localsmoothness}), if $\eta_k=\frac{2}{\mu(k+K_0)}$ for a given constant $K_0$, and $c_d\leq\min\{\frac{1}{24D\eta_0^2},\frac{\sqrt{M}L^2}{18}\}$, then $\theta^K$ generated by Algorithms \ref{alg: LASG-WK1}, \ref{alg: LASG-WK2} and \ref{alg: LASG-PS} satisfies
\begin{equation}
    \mathbb{E}\mathcal{L}(\theta^K)-\mathcal{L}(\theta^{\star})=O\left({1}/{K}\right)
\end{equation}
\end{theorem}

For the convergence of LAQSG algorithms, we make the following additional assumption that guarantees the bounded variance of the quantized stochastic gradient.
\begin{assumption}\label{assump:boundedgradient}
The gradient is bounded as $\mathbb{E}_{\xi_m}\left[\|\nabla\ell(\theta;\!\xi_m)\|^2\right]\!\leq\! B$ for any $\theta \in \mathbb{R}^p$.
\end{assumption}
Based on this assumption, we have the following result.
\begin{theorem}\label{thm:LAQSG}
{\normalfont \textsf{(LAQSG)}} Under Assumptions \ref{assump:smoothness}, \ref{assump:gradientestimator}, \ref{assump:boundedgradient} (also Assumption \ref{assump:localsmoothness} for Algorithm \ref{alg: LASG-PS}), if $\eta_k\!=\!\eta\!={\cal O}(\frac{1}{\sqrt{K}})$, $c_d\leq\min\{\frac{1}{16D\eta^2},\frac{\sqrt{M}L^2}{24}\}$ where $c_{\eta}>0$ is a constant, then $\{\theta^k\}$ generated by quantized Algorithms \ref{alg: LASG-WK1} - \ref{alg: LASG-PS} satisfy
\begin{equation}
    \frac{1}{K}\sum\limits_{k=0}^{K-1}\mathbb{E}\left[\|\nabla \mathcal{L}(\theta^{k})\|^2\right]=O\left({1}/{\sqrt{K}}\right).

\end{equation}
\end{theorem}

\begin{figure*}[t]
\centering

 \hspace*{-3ex}
    \includegraphics[width=.35\textwidth]{covtype_iter.pdf}
    \hspace*{-4ex}
    \includegraphics[width=.35\textwidth]{covtype_comm.pdf}
    \hspace*{-4ex}
    \includegraphics[width=.35\textwidth]{covtype_bits.pdf}

    \caption{Logistic regression on \textit{covtype} dataset in the heterogeneous setting}
    \label{fig:covtype}

\end{figure*}

\begin{figure*}[t]
\centering
 \hspace*{-3ex}
    \includegraphics[width=.35\textwidth]{nn_mnist_loss.pdf}
    \hspace*{-4ex}
    \includegraphics[width=.35\textwidth]{nn_mnist_comm.pdf}
    \hspace*{-4ex}
    \includegraphics[width=.35\textwidth]{nn_mnist_bits.pdf}
    \caption{Training Neural network on \textit{mnist} dataset in the heterogeneous setting.}
    \label{fig:NNmnist}
\end{figure*}

\begin{figure*}[t]
\centering
 \begin{subfigure}[b]{0.5\textwidth}
\centering
\includegraphics[width=1\textwidth]{mnist_loss_seed.pdf}
\caption{Training loss on \textit{mnist} dataset.}
    \label{fig:mnist_train_seed}
    \end{subfigure}%
 \begin{subfigure}[b]{0.5\textwidth}
\centering
\includegraphics[width=1\textwidth]{mnist_test_seed.pdf}
\caption{Training loss on \textit{mnist} dataset.}
    \label{fig:mnist_test_seed}
    \end{subfigure}%
 \caption{Simulations on \textit{mnist} dataset averaged over 30 trials.}
\end{figure*}

\begin{figure*}[t]
\centering
 \begin{subfigure}[b]{0.5\textwidth}
\centering
\includegraphics[width=1\textwidth]{imagenet_train.pdf}
\caption{Training loss on \textit{tiny imagenet} dataset.}
    \label{fig:imagenet_train}
    \end{subfigure}%
 \begin{subfigure}[b]{0.5\textwidth}
\centering
\includegraphics[width=1\textwidth]{imagenet_test.pdf}
\caption{Testing accuracy on \textit{tiny imagenet} dataset.}
    \label{fig:imagenet_test}
    \end{subfigure}%
 \caption{Simulations on \textit{tiny imagenet} dataset.}
\end{figure*}

\begin{table*}[t]
 \vspace{-0.2cm}
\centering
\resizebox{\textwidth}{!}{
\begin{tabular}{c||c|c|c|c|c|c|c||c|c|c|c|c}
\hline
\multirow{2}{*}{Algorithm} & \multirow{2}{*}{SGD} & \multirow{2}{*}{\!\!\!LAG-WK\!\!\!} & \multicolumn{4}{|c|}{LASG} &\multirow{2}{*}{\!\!\!local SGD\!\!\!} &\multirow{2}{*}{QSGD} & \multicolumn{4}{|c}{LAQSG}\\ \cline{4-7}\cline{10-13}
                     &                      &                         & WK1 & WK2 & PS & PSE
&                           &                      & WK1 & WK2 & PS & PSE \\ \hline\hline
ijcnn1(LR)&0.4383& 0.3317 & {\bf 0.2311} & {\bf 0.2308} & 0.2736  & 0.2356   & 0.2554 & 0.4382 & {\bf 0.2307} & 0.2316    & 0.2722  & 0.2356\\ \hline
mnist(LR) &0.4214& 0.4074 & 0.1826 & {\bf 0.1281} & 0.2950  & 0.1681 & 0.2189 & 0.4228 & {\bf 0.1486} & {\bf 0.1342}    & 0.2839  & 0.1572\\ \hline
covtype(LR)&0.6772&0.6727 & 0.5604 &{\bf 0.5523}& 0.6467 & 0.5985 & 0.6288 & 0.6772 &{\bf 0.5537}&{\bf 0.5477}& 0.6456 & 0.5914 \\ \hline
mnist(NN)&0.1544&0.1457&0.1063 &{\bf 0.0510} & ---& {\bf 0.0421} & 0.1178 & 0.2492 & 0.2327 & 0.1564 &--- &{\bf 0.1046}\\ \hline
\end{tabular}}
\caption{Loss after $10^3$ and $10^4$ communication rounds for logistic regression (LR) and neural network (NN) in heterogeneous setting.}
\label{table: 1}
\end{table*}

\begin{table*}[t]
    \vspace{0.2cm}
\centering
\resizebox{\textwidth}{!}{
\begin{tabular}{c||c|c|c|c|c|c|c||c|c|c|c|c}
\hline
\multirow{2}{*}{Algorithm} & \multirow{2}{*}{SGD} & \multirow{2}{*}{\!\!\!LAG-WK\!\!\!} & \multicolumn{4}{|c|}{LASG} &\multirow{2}{*}{\!\!\!local SGD\!\!\!} &\multirow{2}{*}{QSGD} & \multicolumn{4}{|c}{LAQSG}\\ \cline{4-7}\cline{10-13}
                     &                      &                         & WK1 & WK2 & PS & PSE
&                           &                      & WK1 & WK2 & PS & PSE \\ \hline\hline
ijcnn1(LR)&0.6356& 0.3672 & 0.3050 & 0.3037 & 0.3378 & 0.3053 & 0.3226 & 0.4597 & {\bf 0.2370} & {\bf 0.2363} & 0.2798 & {\bf 0.2411}\\ \hline
mnist(LR)&0.6989& 0.6762 & 0.5081 & 0.3859 & 0.6653 & 0.4029 & 0.6125 & 0.5690 & {\bf 0.1916} & {\bf 0.1681} & 0.4215 & {\bf 0.2071} \\ \hline
covtype(LR)&0.6837&0.6806 & 0.5770 & 0.5650 & 0.6620 & 0.6178 & 0.6483 & 0.6469 & {\bf 0.5273} & {\bf 0.5277} & 0.5930 & {\bf 0.5488} \\ \hline
mnist(NN)&0.3042&0.2792&0.2157 & 0.1159 &---&{\bf 0.0814}& 0.2472 & 0.2011 & 0.1602 &{\bf 0.1104} &---&{\bf 0.0764} \\ \hline
\end{tabular}}
\caption{Loss after $10^5$, $10^6$, $10^6$ bits of uploads for LR on ijcnn1, mnist, covtype,  and $10^8$ for NN in heterogeneous setting.}
\label{table: 2}
\end{table*}

\section{Simulations}
Numerical tests have been conducted on both logistic regression and neural network models.

We benchmark LA(Q)SG with SGD, LAG-WK, local SGD and QSGD. For local SGD \citep{lin2018don}, workers perform SGD independently to update local $\{\theta_m\}_{m=1}^M$, and $\{\theta_m\}_{m=1}^M$ then are averaged over all workers every $H$ iterations. In simulations, we did a grid search for SGD learning rates.
We consider the heterogeneous setting where data with same labels are unevenly assigned to $M$ workers.

\noindent\textbf{Logistic regression on ijcnn1, MNIST and covtype.}
The data are distributed across $M=10$ workers for ijcnn1, MNIST (with digits 3, 5) and $M=20$ for Covtype. For each worker, the batch size is selected to be 0.01 of the local data size for ijcnn1, MNIST and  0.001 for Covtype. The $\ell_2$-regularization parameter is set to be $10^{-5}$. We choose stepsize $\eta=0.1$. For all LASG algorithms, $D=100$ and $c_d=0.1/\eta^2/M^2$ for $d=1,2,\ldots 10$ and $c_d=0$ for $d=11,\ldots 100$. For local-SGD, the communication period is $H=50, 10, 20$ iterations for ijcnn1, MNIST, Covtype respectively. This is optimized to save communication as much as possible without largely affecting the convergence speed. For quantization methods, we perform 4-bit stochastic quantization \citep{alistarh2017qsgd}. Numerical results are reported in Figure \ref{fig:covtype} and in Tables \ref{table: 1}, \ref{table: 2}.
Performance averaged over multiple trails has also been reported in Figures \ref{fig:mnist_train_seed} and \ref{fig:mnist_test_seed}.
Supplementary materials have additional tests in Figures \ref{fig:ijcnn1_u}-\ref{fig:covtype_u} and Tables \ref{table: 3} and \ref{table: 4}.

\noindent\textbf{Neural network.}
We train a convolutional neural network with two convolution-ELU-maxpooling layers (ELU is a smoothed ReLU) followed by two fully-connected layers for 10 classes classification on MNIST. The data are distributed on $M=10$ workers. We choose stepsize $\eta=0.05$. Since the objective function is nonsmooth ($L_m$ is not available), LASG-PS is not considered in this test. For all LASG algorithms, we set $D=50$, $c_d=0.1/\eta^2/M^2$ for $d=1,2,\ldots 10$ and $c_d=0$ for $d=11,\ldots 50$.
For local-SGD, we set the communication period to be 4. For all quantization methods, we perform 8-bit stochastic quantization. Numerical results are reported in Figure \ref{fig:NNmnist} and listed in Tables \ref{table: 1} and \ref{table: 2}. Additional results can be found in Figures \ref{fig:NNmnist_u}-\ref{fig:NNmnist_test} and Tables \ref{table: 3}, \ref{table: 4} in the supplementary materials.

All algorithms have been tested on the popular \emph{tiny imagenet} dataset using the Resnet18 model initialized by weights pretrained on ImageNet1000; see the accuracy versus total time (communication and computation) in Figures \ref{fig:imagenet_train} and \ref{fig:imagenet_test}. For training loss, LASG-WK1 and -WK2 require much less total time than SGD and local SGD with $H=2$, but slightly more than local SGD with $H=4$ and $6$. However, as shown in Figure \ref{fig:imagenet_test}, local SGD with larger communication period sacrifices the testing accuracy by 3-4\%.

\begin{figure}[h]
\centering
\includegraphics[width=.45\textwidth]{covtype_grad.pdf}
\caption{Logistic regression on \textit{covtype} dataset in the heterogeneous setting.}
\label{fig:covtype_grad}
\end{figure}

In our numerical tests, all LASG algorithms achieve the same iteration complexity as SGD and outperform local-SGD in most cases.
Compared with SGD, LASG-WK2 and LASG-PSE reduce the number of communication rounds by around one order of magnitude for neural network training and even more for logistic regression. LASG-WK1 also reduce the communication by more than one order of magnitude for logistic regression.
Based on the results of LAG-WK and QSGD, it is evident that the selection rules \eqref{eqn:workerrule1}, \eqref{eqn:workerrule2} and \eqref{eqn:eserversule} of LASG-WK1, LASG-WK2 and LASG-PSE achieve more significant improvement in terms of saving communication and bits than the selection rule \eqref{eqn:LAGrule} of LAG-WK and stochastic quantization strategy of QSGD.

Although the performance of LASG-PS is not as impressive as other LASG algorithms in saving communication, it considerably saves local computation compared with other algorithms except LASG-PSE as shown in Figure \ref{fig:covtype_grad}. Moreover, LASG-PSE has performance gains in both saving communication and local computation.
The performance of LAQSG validates that the LASG algorithms can be easily equipped with stochastic quantization with additional benefits from quantization.

\section{Conclusions}
In this paper, we developed a class of LASG methods as communication-efficient variants of SGD.
LASG methods leverage a set of adaptive communication rules to detect and then skip less informative or redundant communication rounds between the server and workers during distributed learning.
To further reduce communication bandwidth, the quantized version of LASG is also presented.
Both LASG and their quantized version are simple to implement, and have convergence rate comparable to the original SGD. Extensions to nonsmooth and decentralized settings are also in our research agenda.

\vspace{3cm}

redpajama_set_name: RedPajamaArXiv