text:
\section{Introduction}
We study distributed optimization where the data are partitioned among $n$ worker nodes; the data are not necessarily identically distributed.
We seek to learn the model parameter (aka optimization variable) ${ \boldsymbol x} \in {\mathbb R}^d$ by solving the following distributed empirical risk minimization problem:
\begin{small}
	\begin{equation}
	\label{eq:goal}
	\min_{{ \boldsymbol x} \in {\mathbb R}^d} \ f({ \boldsymbol x}) :=
	\frac{1}{n} \sum_{k=1}^n f_k({ \boldsymbol x}),
	\end{equation}
\end{small}%
where $f_k({ \boldsymbol x}) := {\mathbb E}_{\xi \sim {\mathcal D}_k} \big[ F_{k} \left( { \boldsymbol x} ; \xi\right) \big]$ and ${\mathcal D}_k$ is the distribution of data on the $k$-th node with $k \in [n] := \{1, \cdots, n\}$.
Such a problem is traditionally solved under centralized optimization paradigms such as parameter servers \cite{li2014scaling}.
Federated Learning (FL), which often has a central parameter server, enables massive edge computing devices to jointly learn a centralized model while keeping all local data localized~\cite{konevcny2015federated,mcmahan2017communication,konevcny2017stochastic,li2019federated,sahu2019federated}.
As opposed to  centralized optimization, decentralized optimization lets every worker node collaborate only with their neighbors by exchanging information.
A typical decentralized algorithm works in this way: a node collects its neighbors' model parameters ${ \boldsymbol x}$, takes a weighted average, and then performs a (stochastic) gradient descent to update its local parameters~\cite{lian2017can}.
Decentralized optimization can outperform the centralized under specific settings \cite{lian2017can}.

Decentralized optimization, as well as the centralized, suffers from high communication costs.
The communication cost is the bottleneck of distributed optimization when the number of model parameters or the number of worker nodes are large.
It is well known that deep neural networks have a large number of parameters.
For example, ResNet-50 \cite{he2016deep} has 25 million parameters, so sending ${ \boldsymbol x}$ through a computer network can be expensive and time-consuming.
Due to modern big data and big models, a large number of worker nodes can be involved in distributed optimization, which further increases the communication cost.
The situation can be exacerbated if the worker nodes in distributed learning are remotely connected, which is the case in edge computing and other types of distributed learning.

In recent years, to directly save communication, many researchers let more local updates happen before each synchronization in centralized settings.
A typical and famous example is Local SGD~\cite{mcmahan2017communication,lin2018don,stich2018local,wang2018cooperative,wang2018adaptive}.
As its decentralized counterpart, Periodic Decentralized SGD (PD-SGD) alternates between a fixed number of local updates and one step of decentralized SGD~\cite{wang2018cooperative}.
However, its update scheme is too rigid to balance the trade-off between communication and computation efficiently~\cite{wang2019matcha}.
It is still unclear how to combine local updates and decentralized communications efficiently in decentralized and non-iid data settings.

\paragraph{Contributions.}
To answer the question, in the paper, we propose a meta algorithm termed as LD-SGD, which is able to incorporate arbitrary update schemes for decentralized optimization.
We provide an analytical framework, which sheds light on the relationship between convergence and update schemes.
We show that LD-SGD converges with a wide choice of communication patterns for non-convex stochastic optimization problems and non-identically independently distributed training data (i.e., ${\mathcal D}_1 , \cdots , {\mathcal D}_n$ are not the same).

We then specify two update schemes to illustrate the effectiveness of LD-SGD.
For the first scheme, we let LD-SGD alternate (i.e., $I_1$ steps of) multiple local updates and multiple (i.e., $I_2$ steps of) decentralized SGDs; see the illustration in Figure~\ref{fig:pdsgd}.
A reasonable choice of $I_2$ could better trade off the balance between communication and computation both theoretically and empirically.

We observe a phenomenon that more local computation (i.e., large $I_1/I_2$) often leads to a quick initial drop of loss function but higher final errors, while more communication (i.e., small $I_1/I_2$) often results in a lower error floor but higher communication cost.
Therefore, in the second scheme, we propose and analyze a decaying strategy that periodically halves $I_1$.
From our framework, we theoretically verify the efficiency of the strategy.

\begin{figure}[ht]
	\begin{center}
		\centerline{\includegraphics[width=0.7\columnwidth]{figures/pdsgd.pdf}}
		\caption{Illustration of how five nodes run a round of LD-SGD with the first scheme where $I_1=3$ and $I_2 =2$.
			Blue and red arrows respectively represent local gradient computation and communication among neighbor nodes.}
		\label{fig:pdsgd}
	\end{center}
	\vskip -0.2in
\end{figure}

\section{Related Work}

\paragraph{Federated optimization.}
The optimization problem implicit in FL is referred to as federated optimization, drawing a connection (and contrast) to distributed optimization.
Currently, the state-of-the-art algorithm in federated optimization is Federated Averaging (FedAvg) \cite{konevcny2016federated,mcmahan2017communication}, which is a centralized optimization method and is also referred to as Local SGD.
In every iteration of FedAvg, a small subset of nodes is activated, and it alternates between multiple local SGDs and sends updated parameters to the central server.
With perhaps unrealistic assumptions such as identical ${\mathcal D}_k$'s or all nodes activated, the convergence of FedAvg has been analyzed by \cite{zhou2017convergence,stich2018local,wang2018cooperative,yu2019parallel}.
\citet{li2019convergence} for the first time analyzed   FedAvg in more realistic federated setting (i.e., non-identical ${\mathcal D}_k$'s and partial activated nodes).
PD-SGD is an extension of FedAvg (or Local SGD) towards decentralized optimization~\cite{wang2018cooperative,haddadpour2019convergence}.
MATCHA~\cite{wang2019matcha} extends PD-SGD to a more federated setting by only activating a random subgraph of the network topology each round.
Our work can be viewed as an attempt to generalize FedAvg to decentralized settings.

\paragraph{Decentralized stochastic gradient descent (D-SGD).}
Decentralized (stochastic) algorithms were used as compromises when a powerful central server is not available.
They were studied as consensus optimization in the control community~\cite{ram2010asynchronous,yuan2016convergence,sirb2016consensus}.
\citet{lian2017can} justified the potential advantage of D-SGD over its centralized counterpart.
D-SGD not only reduces the communication cost but achieves the same linear speed-up as centralized counterparts when more nodes are available~\cite{lian2017can}.
This promising result pushes the research of distributed optimization from a sheer centralized mechanism to a more decentralized pattern~\cite{lan2017communication,tang2018d,koloskova2019decentralized,wang2019matcha,luo2019heterogeneity}.

\paragraph{Communication efficient algorithms.}
The current methodology towards communication-efficiency in distributed optimization could be divided into two categories.
The more direct approach is to reduce the size of the messages through gradient compression or sparsification \cite{seide2014bit,lin2017deep,zhang2017zipml,tang2018communication,wang2018atomo,horvath2019stochastic}.
An orthogonal one is to pay more local computation for less communication, e.g.,
one-shot aggregation \cite{zhang2013communication,zhang2015divide,lee2017communication,lin2017distributed,wang2019sharper}, primal-dual algorithms \cite{smith2016cocoa,smith2017federated,hong2018gradient} and distributed Newton methods
\cite{shamir2014communication,zhang2015disco,reddi2016aide,wang2018giant,mahajan2018efficient}.
Beyond them, a simple but powerful method is to reduce the communication frequency by allowing more local updates~\cite{zinkevich2010parallelized,stich2018local,lin2018don,you2018imagenet,wang2018cooperative}, which we focus on in this paper.

\paragraph{Most related work.}
Our work is most closely related with ones in~\cite{wang2018cooperative,wang2019matcha}. Specifically,
\citet{wang2018cooperative} proposed PD-SGD that can also combine decentralization and local updates.
However, they only considered the case of one step of decentralized SGD after a fixed number of local updates.
Moreover, they analyzed PD-SGD by assuming all worker nodes have access to the underlying distribution (hence data are identically distributed).
The algorithm shown in Figure~\ref{fig:pdsgd} is an extension of PD-SGD by introducing a new parameter (i.e., $I_2$) of controlling the length of decentralized SGDs.
$I_2$ helps us better balance the communication-computation trade-off.

MATCHA~\cite{wang2019matcha} makes communication happen only among a random small portion of worker nodes at each round\footnote{Specifically, they first decompose the network topology into joint matchings (or subgraphs), then randomly activates a small portion of matchings.}.
When no node is activated, local updates come in.
Consequently, the theory of MATCHA is formulated for random connection matrices (i.e., ${\bf W}_t$ in our case) and does not straightforwardly extend to a deterministic sequence of ${\bf W}_t$.
Our work mainly studies a deterministic sequence of ${\bf W}_t$ but could also extend to random sequences.

\section{Notation and Preliminaries}
\label{sec:notation}

\paragraph{Decentralized system.}

Conventionally, a decentralized system can be described by a graph ${\mathcal G} = ([n], {\bf W})$ where ${\bf W}$ is an $n\times n$ doubly stochastic matrix describing the weights of the edges. A nonzero entry $w_{ij}$ indicates that the $i$-th and $j$-th nodes are connected.

\begin{defi}
	We say a matrix ${\bf W}=[w_{ij}] \in {\mathbb R}^{n {\times} n}$ to be symmetric and doubly stochastic, if ${\bf W}$ is symmetric and each row of ${\bf W}$ is a probability distribution over the vertex set $[n]$, i.e., $w_{ij} \geq 0, {\bf W} = {\bf W}^\top$, and $ {\bf W} {\bf 1}_n ={\bf 1}_n$.
\end{defi}

\paragraph{Notation.}
Let ${ \boldsymbol x}^{(k)} \in {\mathbb R}^d$ be the optimization variable (aka model parameters in machine learning language) held by the $k$-th node.
The step is indicated by a subscript, e.g., ${ \boldsymbol x}_t^{(k)}$ is the parameter held by the $k$-th node in step $t$.
Note that at any time moment, ${ \boldsymbol x}^{(1)}, \cdots , { \boldsymbol x}^{(n)}$ may not be equal.
The concatenation of all the variables is
\[  {\bf X}  := \left[ { \boldsymbol x}^{(1)}, \cdots, { \boldsymbol x}^{(n)} \right] \in {\mathbb R}^{d {\times} n}. \]
The averaged variable is
$ \overline{{ \boldsymbol x}} := \frac{1}{n} \sum_{k=1}^n  { \boldsymbol x}^{(k)} = \frac{1}{n} {\bf X} {\bf 1}_n$.
The derivative of $F_k$ w.r.t.\ ${ \boldsymbol x}^{(k)}$ is $\nabla F_k ({ \boldsymbol x}^{(k)};\xi^{(k)}) \in {\mathbb R}^d$ and the concatenated gradient evaluated at ${\bf X}$ with datum $\xi$ is
\[{\bf G}( {\bf X}; \xi) := \left[ \nabla F_1({ \boldsymbol x}^{(1)};\xi^{(1)}), \cdots, \nabla F_n({ \boldsymbol x}^{(n)};\xi^{(n)})\right].\]
We denote the set of natural numbers by ${\mathbb{N}} = \{1,2, \cdots\}$.
We define $[n] : = \{1, 2, \cdots, n\}$ and $[s:t]$ means the interval between the positive integers $s$ and $t$, i.e., if $s\le t$, $[s:t] =  \{l \in {\mathbb{N}} :s \le l \le t\}$, otherwise $[s:t] = \emptyset$.
For any set ${\mathcal I}$ and real number $x$, we define ${\mathcal I} + x := \{ t = y + x: y \in {\mathcal I}  \}$.

\paragraph{Decentralized SGD (D-SGD).}
D-SGD works in the following way~\cite{bianchi2013performance,lan2017communication}.
At Step $t$, the $k$-th node randomly chooses a local datum $\xi_{t}^{(k)}$, and uses its current local variable ${ \boldsymbol x}_{t}^{(k)}$ to evaluate the stochastic gradient $\nabla F_k \big( { \boldsymbol x}_{t}^{(k)} ; \xi_t^{(k)}\big)$.
Then each node performs stochastic gradient descent (SGD) to obtain an intermediate variable ${ \boldsymbol x}_{t+\frac{1}{2}}^{(k)}$ and finally finishes the update by collecting and aggregating its neighbors' intermediate variables:
\begin{eqnarray}
{ \boldsymbol x}_{t+\frac{1}{2}}^{(k)}
& \longleftarrow & { \boldsymbol x}_{t}^{(k)} - \eta \nabla F_k \big( { \boldsymbol x}_{t}^{(k)} ; \xi_t^{(k)}\big), \label{eq:psgd1}\\
{ \boldsymbol x}_{t+1}^{(k)}
& \longleftarrow &  \sum_{l \in {\mathcal N}_k} w_{kl} { \boldsymbol x}_{t + \frac{1}{2}}^{(l)}, \label{eq:psgd2}
\end{eqnarray}
where ${\mathcal N}_k = \{ l \in [n] \, | \, w_{kl} > 0 \}$ contains the indices of the $k$-th node's neighbors.
In matrix form, this can be captured by
${\bf X}_{t+1} = ({\bf X}_t - \eta {\bf G}({\bf X}_t; \xi_t)) {\bf W}$.
Obviously, D-SGD requires $T$ communications per $T$ steps.

\begin{remark}
	The order of Step~\ref{eq:psgd1} and Step~\ref{eq:psgd2} in D-SGD can be exchanged .
	In this way, we first average the local variable with neighbors and then update the local stochastic gradient into the local variable.
	The update rule becomes
	${ \boldsymbol x}_{t+1}^{(k)}
	\longleftarrow   \sum_{l \in {\mathcal N}_k} w_{kl} { \boldsymbol x}_{t}^{(l)} - \eta \nabla F_k \big( { \boldsymbol x}_{t}^{(k)} ; \xi_t^{(k)} \big)$.
	The benefit is that the computation of stochastic gradients (i.e., $\nabla F_k \big( { \boldsymbol x}_{t}^{(k)} ; \xi_t^{(k)} \big)$) and communication (i.e., Step~\ref{eq:psgd2}) can be run in parallel.
	Our theory in Section~\ref{sec:convergence} is applicable to these cases.
\end{remark}

\section{Local Decentralized SGD (LD-SGD)}
In this section, we first propose LD-SGD which is able to incorporate arbitrary update schemes.
Then we present  convergence analysis for it.

\subsection{The Algorithm}

\begin{algorithm}[tb]
	\caption{Local Decentralized SGD (LD-SGD)}
	\label{alg:main}
	\begin{algorithmic}
		\STATE {\bfseries Input:} total steps $T$, step size $\eta$, communication set ${\mathcal I}_T$
		\FOR{$t=1$ {\bfseries to} $T$}
		\STATE ${\bf X}_{t+\frac{1}{2}} \gets {\bf X}_t - \eta {\bf G}({\bf X}_t;\xi_t)$
		\IF{$  t \in {\mathcal I}_T$}
		\STATE ${\bf X}_{t+1} \gets {\bf X}_{t+\frac{1}{2}}{\bf W}$  \RCOMMENT { Communication }
		\ELSE
		\STATE ${\bf X}_{t+1} \gets {\bf X}_{t+\frac{1}{2}}$ \RCOMMENT { Local updates }
		\ENDIF
		\ENDFOR
	\end{algorithmic}
\end{algorithm}

Algorithm~\ref{alg:main} summarizes the proposed LD-SGD algorithm.
It periodically performs multiple local updates and D-SGD.
Without local updates, LD-SGD would be the standard D-SGD algorithm.
Let ${\mathcal I}_T$ index the steps where decentralized SGD is performed.
Our theory allows for arbitrary ${\mathcal I}_T \subset [T]$.
We can write the resulting algorithm in matrix form:
\[
{\bf X}_{t+1} = ({\bf X}_{t} - {\bf G}({\bf X}_t; \xi_t)){\bf W}_t,
\]
where  ${\bf W}_t \in {\mathbb R}^{n \times n}$ is the connected matrix defined by
\begin{equation}
\label{eq:W_main}
{\bf W}_t = \left\{ \begin{array}{ll}
{\bf I}_n & \text{if} \ t  \notin {\mathcal I}_T,  \\
{\bf W} & \text{if} \ t  \in {\mathcal I}_T.
\end{array}\right.
\end{equation}
Here ${\bf W}$ is a prespecified doubly stochastic matrix.
Different choices of ${\mathcal I}_T$ give rise to different update schemes and then lead to different communication efficiency.
For example, when we choose ${\mathcal I}_T^0 = \{ t \in [T] : t \ \text{mod} \ I = 0  \} $ where $I$ is the communication interval, LD-SGD recovers the previous work PD-SGD~\cite{wang2018cooperative}.
Therefore, it is natural to explore how different ${\mathcal I}_T$ affects the convergence of LD-SGD.

\begin{remark}
	Actually, our framework can apply to any arbitrary deterministic doubly stochastic matrix sequence\footnote{In this way, we define ${\bf W}_t = {\bf W}^{(t)}$ for $t \in {\mathcal I}_T$ where $\{{\bf W}^{(t)}\}_{t=1}^T$ is the prescribed doubly stochastic matrix sequence. Each ${\bf W}^{(t)}$ can even be stochastic like the previous work~\cite{wang2019matcha}, as long as they are independent.
		For the latter case, one should modify the definition of $\rho_{s, t-1}$.}.
	But this will make it complicated to present the conclusion.
	For brevity, we use the same ${\bf W}$ to define ${\bf W}_t$ for $t \in {\mathcal I}_T$.
\end{remark}

\subsection{Convergence Analysis}
\label{sec:convergence}

\subsubsection{Assumptions}

In Eq.~\eqref{eq:goal}, we define $f_k({ \boldsymbol x}) := {\mathbb E}_{\xi \sim {\mathcal D}_k} \big[ F_{k} \left( { \boldsymbol x} ; \xi\right) \big]$ as the objective function of the $k$-th node.
Here, ${ \boldsymbol x} $ is the optimization variable and $\xi $ is a data sample.
Note that $f_k({ \boldsymbol x})$ captures the data distribution in the $k$-th node.
We make a standard assumption: $f_1 , \cdots , f_n$ are smooth.

\begin{assumption}[Smoothness]
	\label{asum:smooth}
	For all $k \in [n]$, $f_k$ is smooth with modulus $L$, i.e.,
	\[ \big\| \nabla f_k({ \boldsymbol x}) - \nabla f_k({\boldsymbol y}) \big\|
	\: \leq \: L \big\| { \boldsymbol x} - {\boldsymbol y} \big\|,
	\quad \forall \  { \boldsymbol x}, {\boldsymbol y} \in {\mathbb R}^d.  \]
\end{assumption}

We assume the stochastic gradients have bounded variance.
The assumption has been made by the prior work \cite{lian2017can,wang2018cooperative,tang2018d,tang2018communication}.

\begin{assumption}[Bounded variance]
	\label{asum:within-var}
	There exists some $\sigma > 0$ such that $\forall \ k \in [n]$,
	\[	{\mathbb E}_{\xi \sim {\mathcal D}_k} \big\| \nabla F_k({ \boldsymbol x};\xi) - \nabla f_k({ \boldsymbol x}) \big\|^2
	\: \leq \: \sigma^2,
	\quad \forall \ { \boldsymbol x} \in {\mathbb R}^d.\]
\end{assumption}

Recall from Eq.~\eqref{eq:goal} that $f({ \boldsymbol x}) = \frac{1}{n} \sum_{k=1}^n f_k({ \boldsymbol x})$ is the global objective function.
If the data distributions are not identical, that is, ${\mathcal D}_k \neq {\mathcal D}_l$ for $k \neq l$, then the global objective is not the same to the local objectives.
In this case, we define $\kappa$ to quantify the degree of non-iid.
If the data across nodes are iid, then $\kappa = 0$.

\begin{assumption}[Degree of non-iid]
	\label{asum:inter-var}
	There exists some $\kappa \ge 0$ such that
	\begin{equation*}
	\frac{1}{n}\sum_{k=1}^n \big\| \nabla f_k({ \boldsymbol x}) - \nabla f({ \boldsymbol x}) \big\|^2
	\: \leq \: \kappa^2,
	\quad \forall \ { \boldsymbol x} \in {\mathbb R}^d.
	\end{equation*}
\end{assumption}

Finally, we need to assume the nodes are well connected;
otherwise, the update in one node cannot be propagated to another node within a few iterations.
In the worst case, if the system is not fully connected, the algorithm will not converge.
We use $\rho = |\lambda_2|$ to quantify the connectivity where $\lambda_2$ is the second largest absolute eigenvalue of ${\bf W}$. A small $\rho$ indicates nice connectivity.
If the connection forms a complete graph, then ${\bf W} =\frac{1}{n} {\bf 1}_n {\bf 1}_n^\top$, and thus $\rho = 0$.

\begin{assumption}[Nice connectivity]
	\label{asum:W}
	The $n\times n$ connectivity matrix ${\bf W} $ is symmetric doubly stochastic.
	Denote its eigenvalues by $1 = |\lambda_1| > |\lambda_2| \ge \cdots \ge |\lambda_n| \ge 0$.
	We assume the spectral gap $1- \rho \in (0, 1]$ where $\rho = |\lambda_2| \in [0, 1)$.
\end{assumption}

\subsubsection{Main Results}

Recall that $\overline{{ \boldsymbol x}}_t = \frac{1}{n} \sum_{k=1}^n { \boldsymbol x}_t^{(k)} $ is defined as the averaged variable in the $t$-th iteration.
Note that the objective function $f({ \boldsymbol x})$ is often non-convex when neural networks are applied.
$\rho_{s, t-1}$ is very important in our theory because it captures the characteristics of each update scheme.
All the proof can be found in Appendix~\ref{append:PD-SGD}.

\begin{defi}
	\label{def:rho}
	For any $s < t$, define $\rho_{s, t-1} = \|\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}\|$ where $\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} = \prod_{l=s}^{t-1} {\bf W}_l$ with ${\bf W}_l$ given in~\eqref{eq:W_main}.
	Actually, we have $\rho_{s, t-1} = \rho^{|[s: t-1] \cap {\mathcal I}_T|}$, where $[s:t-1] = \{l \in {\mathbb{N}}: s \le l \le t-1\}$ and $\rho$ is defined in Assumption~\ref{asum:W}.
\end{defi}

\begin{theorem}[LD-SGD with any ${\mathcal I}_T$]
	\label{thm:PD-SGD}
	Let Assumptions~\ref{asum:smooth},~\ref{asum:within-var},~\ref{asum:inter-var},~\ref{asum:W} hold and the constants $L$, $\kappa$, $\sigma$, and $\rho$ be defined therein.
	Let $\Delta = f(\overline{{ \boldsymbol x}}_0) - \min_{{ \boldsymbol x} } f ({ \boldsymbol x} )$ be the initial error.
	For any fixed $T$, define
	\begin{gather*}
	A_T =\frac{1}{T}\sum_{t=1}^{T} \sum_{s=1}^{t-1} \rho^2_{s, t-1}, \\
	B_T = \frac{1}{T} \sum_{t=1}^{T} \left(\sum_{s=1}^{t-1} \rho_{s, t-1} \right)^2, \\
	C_T = \max_{s \in [T-1]} \sum_{t=s+1}^T  \rho_{s, t-1}  \left( \sum_{l=1}^{t-1}  \rho_{l, t-1} \right).
	\end{gather*}
	If the learning rate $\eta$ is small enough such that
	\begin{equation}
	\label{eq:lr}
	\eta \: < \: \min \bigg\{ \frac{1}{2L}, \; \frac{1}{4\sqrt{2}L \sqrt{C_T}} \bigg\} ,
	\end{equation}
	then
	\begin{align}
	\label{eq:main}
	&\frac{1}{T} \sum_{t=1}^{T} {\mathbb E} \big\|\nabla f (\overline{{ \boldsymbol x}}_t) \big\|^2  \nonumber \\
	&\: \leq \:
	{\underbrace{\frac{2\Delta}{\eta T} + \frac{\eta L\sigma^2}{n}}_{\text{fully sync SGD}}}  +
	{\underbrace{\vphantom{ \left(\frac{a^{0.3}}{b}\right) } 4\eta^2L^2 \left( A_T \sigma^2 +B_T\kappa^2 \right)}_{ \text{residual error}}} .
	\end{align}
\end{theorem}

\begin{corollary}
	\label{cor:computation}
	If we choose the learning rate as $\eta = \sqrt{\frac{n}{T}}$ in Theorem~\ref{thm:PD-SGD}, then when $T > 4L^2 n \max\{1,4C_T\} $, we have,
	\begin{equation}
	\label{eq:linear}
	\frac{1}{T} \sum_{t=1}^{T} {\mathbb E} \|\nabla f (\overline{{ \boldsymbol x}}_t ) \|^2
	\leq
	\frac{2 \Delta {+} L \sigma^2 }{\sqrt{n T}}
	{+} \frac{ 4nL^2  \left( A_T \sigma^2 {+} B_T\kappa^2 \right) }{ T }.
	\end{equation}
\end{corollary}

\paragraph{Sufficient condition for convergence.}
If the chosen ${\mathcal I}_T$ satisfies the sublinear condition that
\begin{equation}
\label{eq:sublinear}
A_T = o(T), \ B_T = o(T) \ \text{and} \ C_T = o(T),
\end{equation}
we thereby prove the convergence of LD-SGD with the update scheme ${\mathcal I}_T$ to a stationary point, e.g., a local minimum or saddle point.
However, not every update scheme satisfies~\eqref{eq:sublinear}.
For example, when ${\mathcal I}_T = \{T\}$, we have $\rho_{s, t-1}=1$ for all $s < t \le T$ and thus $A_T = \Theta(T), B_T = \Theta(T^2)$ and $C_T = \Theta(T^2)$.
But Theorem~\ref{thm:bound} shows that as long as $\text{gap}({\mathcal I}_T)$ is small enough, the sublinear condition holds.
So there is still a wide range of ${\mathcal I}_T$ that meets the condition.

\begin{defi}[Gap]
	\label{def:gap}
	For any set ${\mathcal I}_T = \{ e_1, \cdots, e_g \} \subset [T]$ with $e_i < e_{j}$ for $i < j$, the gap of ${\mathcal I}_T$ is defined as
	\[  \text{gap}({\mathcal I}_T) = \max_{i \in [g+1]} (e_i - e_{i-1}) \  \text{where} \ e_0 =0, e_{g+1}=T. \]
\end{defi}

\begin{theorem}
	\label{thm:bound}
	Let $A_T, B_T, C_T$ be defined in Theorem~\ref{thm:PD-SGD}. Then for any ${\mathcal I}_T$, we have
	\[ 	A_T \le \text{gap}({\mathcal I}_T) \frac{1+\rho^2}{1-\rho^2}, \
	\max\{ B_T, C_T \} \le  \frac{\text{gap}({\mathcal I}_T)^2}{(1-\rho)^2}. \]
\end{theorem}

\section{Two Proposed Update Schemes}
\label{sec:algo}
Before we move to the discussion of our results, we  first specify two classes of update schemes, both of which satisfy the sublinear condition~\eqref{eq:sublinear}.
The proposed update schemes  also deepen our understandings of the main results.

\subsection{Adding Multiple Decentralized SGDs}
One centralized average can synchronize all local models, while it often needs multiple decentralized communication to achieve global consensus.
Therefore, it is natural to introduce multiple decentralized SGDs (D-SGD) to ${\mathcal I}_T^0$.
In particular, we set
\[ {\mathcal I}_T^1 = \{ t \in [T]: t \ \text{mod} \ (I_1 + I_2)  \notin [I_1]  \},  \]
where $I_1, I_2$ are parameters that respectively control the length of local updates and D-SGD.

In this way, each worker node periodically alternates between two phases.
In the first phase, each node locally runs $I_1 \ (I_1 \geq 0)$ steps of SGD in parallel\footnote{That is to perform Step~\ref{eq:psgd1} for $I_1$ times.}.
In the second phase, each worker node runs $I_2 \ (I_2 \geq 1)$ steps of D-SGD.
As mentioned, D-SGD is a combination of Step~\ref{eq:psgd1} and Step~\ref{eq:psgd2}.
So communication only happens in the second phase; a worker node performs $\frac{I_2}{I_1 + I_2} T $ communication per $T$ steps.
Figure~\ref{fig:pdsgd} illustrates one round of LD-SGD with ${\mathcal I}_T^1$ when $I_1=3$ and $I_2=2$.
When LD-SGD is equipped with ${\mathcal I}_T^1$, the corresponding $A_T, B_T, C_T$ are $O(1)$ w.r.t.\ $T$.
The proof is provided in Appendix~\ref{append:scheme1}.

\begin{theorem}[LD-SGD with ${\mathcal I}_T^1$]
	\label{thm:scheme1}
	When we set ${\mathcal I}_T = {\mathcal I}_T^1$ for PD-SGD, under the same setting, Theorem~\ref{thm:PD-SGD} holds with
	\begin{gather*}
	A_T \le \frac{1}{2I}\left( \frac{1+\rho^{2I_2}}{1-\rho^{2I_2}} I_1^2 + \frac{1+\rho^2}{1-\rho^2} I_1 \right)  +  \frac{\rho^2}{1-\rho^2}, \\
	\max \left\{  B_T, C_T \right\}\le K^2, K= \frac{I_1}{1 - \rho^{I_2}} + \frac{\rho}{1-\rho}.
	\end{gather*}
	Therefore, LD-SGD converges with ${\mathcal I}_T^1$.
\end{theorem}

The introduction of $I_2$ extends the scope of previous framework: Cooperative SGD~\cite{wang2018cooperative}.
As a result, many existing algorithms become special cases when the period lengths $I_1, I_2$, and the connected matrix ${\bf W}$ are carefully determined.
As an evident example, we recover D-SGD by setting $I_1 = 0$ and $I_2 > 0$\footnote{We make a convention that $[0] = \emptyset$, so in this case ${\mathcal I}_T^1 = [T]$.} and the conventional PD-SGD by setting $I_1 > 0$ and $I_2 = 1$.
Another important example is Local SGD (or FedAvg) that periodically averages local model parameters in a centralized manner~\cite{zhou2017convergence,lin2018don,stich2018local,yu2019parallel}.
Local SGD is a case with $I_1 > 1$, $I_2 = 1$ and ${\bf W} = \frac{1}{n} {\bf 1}_n {\bf 1}_n^\top$.
We summarize examples and the comparison with their convergence results in Appendix~\ref{appen:discussion}.

\subsection{Decaying the Length of Local Updates}

\begin{figure}[ht]

	\begin{center}
		\centerline{\includegraphics[width=0.7\columnwidth]{figures/15_effi.pdf}}
		\caption{Training loss of LD-SGD with ${\mathcal I}_T^1$ v.s. the number of D-SGD.
			The experiment setting is the same as Section~\ref{sec:exp}.
			Since $I_1 + I_2 =15$, the larger $I_1$, the less number of D-SGD.
			It illustrates the trade-off between the convergence speed and final error.}
		\label{fig:speed-error}
	\end{center}
	\vskip -0.2in
\end{figure}

From Figure~\ref{fig:speed-error}, larger local computation ratio (i.e., $I_1/I_2$) converges faster but incurs a higher final error, while lower local computation ratio enjoys a smaller final error but sacrifices the convergence speed.
A similar phenomena is observed by an independent work~\cite{wang2018adaptive}, which finds that a faster initial drop of global loss often accompanies a higher final error.

To take the advantage of both cases, we are inspired to decay $I_1$ every $M$ rounds until $I_1$ vanishes.
In particular, we first define an ancillary set
\[  {\mathcal I}(I_1, I_2, M) = \{t \in [M(I_1+I_2)]: t \ \text{mod} \ (I_1+I_2) \notin [I_1] \}, \]
and then recursively define ${\mathcal J}_0 = {\mathcal I}(I_1, I_2, M)$ and
\[ {\mathcal J}_j ={\mathcal I}\left( \bigg\lfloor \frac{I_1}{2^j} \bigg\rfloor , I_2, M\right) + \max({\mathcal J}_{j-1}), 1 \le j \le J, \]
where $\max({\mathcal J}_{j-1})$ returns the maximum number collected in ${\mathcal J}_{j-1}$ and $J = \lceil \log_2 I_1 \rceil $.
Finally we set
\[  {\mathcal I}_T^2 =\cup_{j=0}^J {\mathcal J}_{j} \cup [\max({\mathcal J}_{J}):T].  \]
From the recursive definition, once $t \ge \max({\mathcal J}_{J})$, $I_1$ is reduced to zero and LD-SGD is reduced to D-SGD.

When LD-SGD is equipped with ${\mathcal I}_T^2$, the corresponding $A_T, B_T, C_T$ are $O(1)$ w.r.t. $T$.
The proof is provided in Appendix~\ref{append:scheme2}.

\begin{theorem}[LD-SGD with ${\mathcal I}_T^2$]
	\label{thm:scheme2}
	When we set ${\mathcal I}_T = {\mathcal I}_T^2$ for LD-SGD, under the same setting, for $T \ge \max({\mathcal J}_{J})$, Theorem~\ref{thm:PD-SGD} holds with
	\begin{gather*}
	A_T \le\frac{1}{T} \frac{I_1}{1{-}\rho^{2I_2}} \rho^{2(T {-}\max({\mathcal J}_{J}))} + (1{-}\frac{\max({\mathcal J}_{J})}{T}) \frac{\rho^2}{1{-}\rho^2}, \\
	B_T \le K \left[\frac{1}{T} \frac{I_1}{1{-}\rho^{I_2}} \rho^{T{-}\max({\mathcal J}_{J})} + (1{-}\frac{\max({\mathcal J}_{J})}{T}) \frac{\rho}{1-\rho}\right],\\
	C_T \le K^2,
	\end{gather*}
	where $K$ is the same in Theorem~\ref{thm:scheme1}.
	Therefore, LD-SGD converges with ${\mathcal I}_T^2$.
\end{theorem}

From experiments in Section~\ref{sec:exp}, the simple strategy empirically performs better than the PD-SGD.

\section{Discussion}
In this section, we will discuss some aspects of our main results (Theorem~\ref{thm:PD-SGD}) and shed light on advantages of proposed update schemes.

\paragraph{Error decomposition.}
From Theorem~\ref{thm:PD-SGD}, the upper bound~\eqref{eq:main} is decomposed into two parts.
The first part is exactly the same as the optimization error bound in parallel SGD~\cite{bottou2018optimization}.
The second part is termed as residual errors as it results from performing periodic local updates and reducing inter-node communication.
In previous literature, the application of local updates inevitably results the residual error~\cite{lan2017communication,stich2018local,wang2018cooperative,haddadpour19a,li2019convergence,yu2019linear}.

To go a step further towards the residual error, take LD-SGD with ${\mathcal I}_T^1$ for example.
From Theorem~\ref{thm:scheme1}, the residual error often grows with the length of local updates $I = I_1 + I_2$.
When data are independently and identical distributed
\footnote{This is also possible if all nodes have access to the entire data, e.g., the distributed system may shuffle data regularly so that each node actually optimizes the same loss function.} (i.e., $\kappa = 0$), \citet{wang2018cooperative} shows that the residual error of the conventional PD-SGD grows only linearly in $I$.
~\citet{haddadpour19a} achieves the similar linear dependence on $I$ but only requires each node draws samples from its local partitions.
When data are not identically distributed (i.e., $\kappa$ is strictly positive), both~\citet{yu2019parallel} and~\citet{zhou2017convergence} show that the residual error of Local SGD grows quadratically in $I$.
Theorem~\ref{thm:scheme1} shows that the residual error of LD-SGD with ${\mathcal I}_T^1$ is $O(I\sigma^2 + I^2 \kappa^2)$, where the linear dependence comes from the stochastic gradients and the quadratic dependence results from the heterogeneity.
The similar dependence is also established for centralized momentum SGD in~\cite{yu2019linear}.

\paragraph{On Linear Speedup.}
Assume ${\mathcal I}_T$ satisfies
\begin{equation}
\label{eq:speedup_condition}
A_T = O(\sqrt{T}) \ B_T = O(\sqrt{T}) \ \text{and} \ C_T = o(T).
\end{equation}
Note that Condition~\eqref{eq:speedup_condition} is sufficient for the sublinear condition~\eqref{eq:sublinear}.
From Corollary~\ref{cor:computation}, the convergence of LD-SGD with ${\mathcal I}_T$ will be dominated by the first term $O(\frac{1}{\sqrt{nT}})$, when the total step $T$ is sufficiently large.
So LD-SGD with ${\mathcal I}_T$ can achieve a linear speedup in terms of the number of worker nodes.
Both of ${\mathcal I}_T^1$ and ${\mathcal I}_T^2$ satisfy Condition~\eqref{eq:speedup_condition}.
Taking LD-SGD with ${\mathcal I}_T^1$ for example, we have
\begin{corollary}
	\label{cor:communication}
	In the setting of Theorem~\ref{thm:scheme1}, if we set $\eta =\sqrt{\frac{n}{T}}$ and choose $I_1, I_2$ to satisfy that $nK^2/T = 1/\sqrt{nT}$ then the bound of $\frac{1}{T} \sum_{t=1}^{T} {\mathbb E} \big\|\nabla f (\overline{{ \boldsymbol x}}_t) \big\|^2$ becomes
	\begin{equation*}
	\frac{2\Delta + L \sigma^2 + 4L^2(\sigma^2 + \kappa^2)}{\sqrt{nT}}.
	\end{equation*}
\end{corollary}

However, if ${\mathcal I}_T$ fails to meet~\eqref{eq:speedup_condition}, the second term $O(\frac{A_T+B_T}{T} \cdot n)$ will dominate.
As a result, more worker nodes may lead to slow convergence or even divergence.
As suggested by Theorem~\ref{thm:bound}, one way to make the first term dominate is to involve more communication.\footnote{By pigeonhole principle, we have $\text{gap}({\mathcal I}_T) \ge \frac{T}{|{\mathcal I}_T|+1}$. In order to reduce $\text{gap}({\mathcal I}_T)$, one must perform more communication.}

\paragraph{Communication Efficiency.}
LD-SGD with ${\mathcal I}_T$ needs only $|{\mathcal I}_T|$ communications per $T$ total steps.
To increase communication efficiency, we are motivated to reduce the size of ${\mathcal I}_T$ as much as possible.
However, as suggested by Theorem~\ref{thm:bound}, to guarantee convergence, we are required to make sure ${\mathcal I}_T$ is sufficiently large (so that $\text{gap}({\mathcal I}_T)$ will be small enough).
The trade-off between communication and convergence needs a careful design of update schemes.
The two proposed update schemes have their own way of balancing the trade-off.

For LD-SGD with ${\mathcal I}_T^1$, it only needs $\frac{I_2}{I} T$ communications per $T$ total steps where $I = I_1 + I_2$.
From Corollary~\ref{cor:communication}, to ensure $nK^2/T = 1/\sqrt{nT}$, we have $I_1 =  (T^{\frac{1}{4}} n^{-\frac{3}{4}} - \frac{\rho}{1-\rho})(1-\rho^{I_2})$.
Then the communication complexity of LD-SGD with ${\mathcal I}_T^1$ is
\[   \frac{I_2}{I_2 + (T^{\frac{1}{4}} n^{-\frac{3}{4}} - \frac{\rho}{1-\rho})(1-\rho^{I_2})} T = O(T^{\frac{3}{4}} n^{\frac{3}{4}}),  \]
which is an increasing function of $I_2$.
On the other hand, a large $I_2$ fastens convergence (since all bounds in Theorem~\ref{thm:scheme1} are decreasing in $I_2$).
Therefore, the introduction of $I_2$ allows more flexibility to balance the trade-off between communication and convergence.
From experiments, large $I_2$ often has higher communication efficiency.
Besides, similar to Local SGD which has $O(T^{\frac{3}{4}} n^{\frac{3}{4}})$ communication complexity in centralized settings~\cite{yu2019parallel}, LD-SGD with ${\mathcal I}_T^1$ also achieves that level.

For LD-SGD with ${\mathcal I}_T^2$, it has much faster convergence rate since from Theorem~\ref{thm:scheme2}, the bounds of $A_T$ and $B_T$ are much smaller than those of ${\mathcal I}_T^1$.
However, it needs $MI_2J + (T-\max({\mathcal J}_J))$ communications per $T$ total steps, which is more than that of ${\mathcal I}_T^1$.
To balance the trade-off, we can choose a reasonable $I_2$.
From experiments in Section~\ref{sec:exp}, ${\mathcal I}_T^2$ empirically performs better than the vanilla PD-SGD.

\paragraph{Effect of connectivity $\rho$.}
The connectivity is measured by $\rho$, the second largest absolute eigenvalue of ${\bf W}$.
The network connectivity $\rho$ has impact on the convergence rate via $\rho_{s, t-1}$.
Each update scheme corresponds to one way that $\rho_{s, t-1}$ depends on $\rho$.

Generally speaking, well-connectivity helps reduce residual errors and thus speed up convergence.
If the graph is nicely connected, in which case $\rho$ is close to zero, then the update in one node will be propagated to all the other nodes very soon, and the convergence is thereby fast.
As a result, the bounds in Theorem~\ref{thm:bound} are much smaller due to $\rho \approx 0$.
On the other hand, if the network connection is very sparse (in which case $\rho \approx 1$), $\rho$ will greatly slows convergence.
Take LD-SGD with ${\mathcal I}_T^1$ for example.
When $\rho \approx 1$, from Theorem~\ref{thm:scheme1}, the bound of $A_T \approx \frac{1}{1-\rho} \frac{I}{2I_2}$ and the bound of $B_T \approx (\frac{1}{1-\rho} \frac{I}{I_2})^2$, both of which can be extremely large.
Therefore, it needs more steps to converge.

\paragraph{Effect of variance $\sigma^2$ and $\kappa^2$.}
Undoubtedly, the existence of $\sigma^2$ and $\kappa^2$ negatively affects convergence.
The former is common in stochastic optimization due to the variance incurred by computing gradients.
The latter results from the nature of non-identical data distribution.
Non-iid data is very commonplace in Federated Learning.
The fact that $A_T \le B_T$ shows the impact of non-iid data is much stronger than that of stochastic gradients.

\section{Experiments}
\label{sec:exp}

\paragraph{Experiment setup.}
We evaluate LD-SGD with two proposed update schemes (${\mathcal I}_T^1$ and ${\mathcal I}_T^2$) using the CIFAR-10 dataset which has ten classes of natural images.
We set the number of worker nodes to $n=100$ and connect every node with 10 nodes.
The connection graph is sparse, and the second biggest eigenvalue is big: $\rho \approx 0.98$.
To make the objective functions $f_1, \cdots , f_n$ heterogeneity, we let each node contain samples random selected from two classes.
We build a small convolutional neural network (CNN) by adding the following layers one by one:
$\textsf{Conv} (32, 5\times 5)$
$\Rightarrow$
$\textsf{MaxPool} (2\times 2)$
$\Rightarrow$
$\textsf{Conv} (64, 5\times 5)$
$\Rightarrow$
$\textsf{MaxPool} (2\times 2)$
$\Rightarrow$
$\textsf{Dense} (512)$
$\Rightarrow$
\textsf{ReLU}
$\Rightarrow$
$\textsf{Dense} (128)$
$\Rightarrow$
\textsf{ReLU}
$\Rightarrow$
$\textsf{Dense} (10)$
$\Rightarrow$
\textsf{Softmax}.
There are totally $940,000$ trainable parameters.
We choose the best learning rate from $\{10^{-3}, 10^{-2}, 10^{-1}\}$.
We set $T=10,000$ and evaluate the averaged model every 10 global steps on the global loss~\eqref{eq:goal}.
If the abscissa axis is named as 'steps', we show global training loss v.s. total steps.
Otherwise for 'communication steps', each unit in the abscissa axis represents once communication.
In this way, we can measure the communication efficiency, i.e. how the global training loss decreases when a communication step (i.e., Step~\ref{eq:psgd1} and Step~\ref{eq:psgd2}) is performed.

\begin{figure}[!tb]

	\centering
	\minipage{0.5\textwidth}
	\centering
	\includegraphics[width=\textwidth]{figures/I1=10_global.pdf}
	\caption{Convergence of LD-SGD \\ with ${\mathcal I}_T^1$. }
	\label{fig:pdsgd_exp_convergence}
	\endminipage\hfill
	\minipage{0.5\textwidth}
	\centering
	\includegraphics[width=\textwidth]{figures/I1=10_effi.pdf}
	\caption{Communication efficiency of LD-SGD\\ with ${\mathcal I}_T^1$. }
	\label{fig:pdsgd_exp_communication}
	\endminipage
\end{figure}

\begin{figure}[!tb]

	\centering
	\minipage{0.5\textwidth}
	\centering
	\includegraphics[width=\columnwidth]{figures/decay_global.pdf}
	\caption{Convergence of LD-SGD \\ with ${\mathcal I}_T^2$. }
	\label{fig:pdsgd_decay_exp_converegence}
	\endminipage\hfill
	\minipage{0.5\textwidth}
	\centering
	\includegraphics[width=\columnwidth]{figures/decay_effi.pdf}
	\caption{Communication efficiency of LD-SGD  \\ with ${\mathcal I}_T^2$. }
	\label{fig:pdsgd_decay_exp_communication}
	\endminipage
\end{figure}

\paragraph{Convergence against computation.}
Figure~\ref{fig:pdsgd_exp_convergence} shows the convergence speed of ${\mathcal I}_T^1$ under different configurations.
When $I_1$ is fixed as 10, larger $I_2/I_1$ leads to faster convergence in terms of computation.
As an extreme, $I_1=0, I_2=1$ converges fastest (but requires the most communication).
What's more, larger $I_2/I_1$ has less final error.

\paragraph{Convergence against communication.}
Figure~\ref{fig:pdsgd_decay_exp_communication} shows the communication efficiency of ${\mathcal I}_T^1$ under different configurations.
For a fixed $I_1$, a big $I_1/I_2$ requires less communications (which precisely needs $\frac{I_2}{I_1 + I_2} T$ communications) and has a fast drop of the global loss (which we have also mentioned in Figure~\ref{fig:speed-error}).
However, as mentioned, large $I_1/I_2$ unfortunately incurs high level of final errors.
We speculate the reason is that at the beginning, the optimization parameters are far away from any stationary point, and more local updates will accelerate the move towards it.
When it is close enough to a good parameter region (e.g., the neighborhood of stationary points), more local updates inevitably increases the residual errors and thus deteriorates the ultimate loss level.
It is natural to combine the choice of parameters more organically; here is our motivation to propose a decay strategy ${\mathcal I}_T^2$ that gradually decreases $I_1$.

\paragraph{Decaying $I_1$.}
The above empirical observation suggests using a big $I_1$ in the beginning and a small $I_1$ in the end.
We decay $I_1$ by half every 200 rounds of communication, i.e., about 2000 steps initially.
As argued, the decaying strategy ${\mathcal I}_T^2$ helps reduce the final error.
From Figure~\ref{fig:pdsgd_decay_exp_converegence}, once we periodically reduces $I_1$, all choice of $I_2$ have a similar level of final errors.
Figure~\ref{fig:pdsgd_decay_exp_communication} shows that $I_1=10, I_2=1$ with the decay strategy is the most efficient method.
In practical, we can set $I_2$ a little bit higher (e.g., $5$) to take the advantage of fast convergence.

\section{Conclusion}
In this paper we have proposed a meta algorithm LD-SGD, which can be combined with any update scheme ${\mathcal I}_T$.
Our analytical framework has shown that with any ${\mathcal I}_T$ that has sufficiently small $\text{gap}({\mathcal I}_T)$, LD-SGD converges under the setting of stochastic non-convex optimization and non-identically distributed data.
We have also presented two novel update schemes, one adding multiple D-SGDs (denoted ${\mathcal I}_T^1$) and the other empirically reducing the length of local updates  (denoted by ${\mathcal I}_T^2$) .
Both the schemes help improve communication efficiency theoretically and empirically.
The framework we proposed might help researchers to design more efficient update schemes.

\bibliographystyle{named}

\section{Discussion on others' convergence results}
\label{appen:discussion}

As discussed in Section~\ref{sec:algo}, LD-SGD with the update scheme ${\mathcal I}_T^1$ incorporates many previous algorithms by setting $I_1, I_2$ and $\rho$ correspondingly.
Taking the difference between the update rule~\eqref{eq:pdsgd} and~\eqref{eq:new_update} into account, we could give convergence results for previous algorithms via Theorem~\ref{thm:PD-SGD} or Theorem~\ref{thm:PD-SGD-} (see Table~\ref{tab:algo_result}).
In this section, we compare the result obtained from our analytical framework with their original ones.

\begin{table}[htbp]
	\setlength{\tabcolsep}{0.3pt}
	\centering
	\caption{Convergence results of LD-SGD with ${\mathcal I}_T^1$.
	To recover previous algorithms, $I_1, I_2$ and $\rho$ (which is defined by Assumption~\ref{asum:W}) are determined as following.
	The result is directly obtained by combining the bounds derived in Theorem~\ref{thm:scheme1} with Theorem~\ref{thm:PD-SGD} or Theorem~\ref{thm:PD-SGD-}.
	In this table, $\Delta = f(\overline{{ \boldsymbol x}}_0) - \min_{{ \boldsymbol x} } f ({ \boldsymbol x} )$ is the initial error, $\eta$ the learning rate and $I = I_1 + I_2$.
	The result for D-SGD is obtained from Theorem~\ref{thm:PD-SGD-} while the rest from Theorem~\ref{thm:PD-SGD}.}
	\label{tab:algo_result}
	\begin{tabular}{ccccccc}
		\toprule
		Algorithms & ~~~~~$I_1$~~~~~ & ~~~~~$I_2$~~~~~
		& ~~~~~$\rho$~~~~~ &~~~~~$\sigma$~~~~~ &~~~~~$\kappa$~~~~~ &
		Convergence Rate \\
		\midrule
		SGD~\citep{bottou2018optimization}& 0 & 1 & $0$ & 0 & 0 &
		$\frac{2\Delta}{\eta T} + \frac{\eta L\sigma^2}{n}$ \\
		PR-SGD~\cite{yu2019parallel} & $ \geq 1$ & $1$ &  $0$ & $>0$&  $>0$ &
		$\frac{2\Delta}{\eta T} + \frac{\eta L\sigma^2}{n}  + 2\eta^2L^2\sigma^2 I_1 + 16\eta^2L^2\kappa^2 I_1^2$ \\
		D-SGD~\cite{lian2017can} & 0 & 1 & $[0, 1)$ & $>0$ & $>0$ &
		$\frac{2\Delta}{\eta T} + \frac{\eta L\sigma^2}{n} +  \frac{4\eta^2L^2\sigma^2}{1-\rho^2} + \frac{ 4\eta^2L^2\kappa^2}{(1-\rho)^2}$  \\
		DPA-SGD~\cite{wang2018cooperative}&$\geq 0$ & $1$ & $[0,1)$ & $>0$& 0 &
		$\frac{2\Delta}{\eta T} + \frac{\eta L\sigma^2}{n} + 2\eta^2L^2 \sigma^2(\frac{1+\rho^2}{1-\rho^2} I -1)$ \\
		\bottomrule
	\end{tabular}
\end{table}

\paragraph{Convergence for PR-SGD.}
PR-SGD~\cite{zhou2017convergence,yu2019parallel,yu2019linear} is the special case of LD-SGD when $I_2 =1$ and $\rho = 0$ (i.e., ${\bf W} = {\bf Q} = \frac{1}{n}{\bf 1}_n{\bf 1}_n^\top$).~\citet{yu2019parallel} derives its convergence (Theorem~\ref{thm:yu}) by requiring Assumption~\ref{asum:bound} which is definitely stronger than our Assumption~\ref{asum:inter-var}. Roughly speaking we always have bound $\kappa^2 \le 4G^2$ since $	\frac{1}{n}\sum_{k=1}^n \big\| \nabla f_k({ \boldsymbol x}) - \nabla f({ \boldsymbol x}) \big\|^2 \le \frac{2}{n} \sum_{k=1}^n \|  \nabla f_k({ \boldsymbol x}) \|^2 + 2 \|\nabla f({ \boldsymbol x})\|^2 \le 4G^2$. Then our bound matches theirs up to constant factors. Another interesting thing is in this case our bound only depends on $I_1 = I-1$ while~\citet{yu2019parallel}'s relies on $I$. Though they are the same asymptotically, our refined analysis shows that the step of model averaging doesn't account for the accumulation of residual errors.

\begin{assumption}(Bounded second moments)
	\label{asum:bound}
There are exist some $G > 0$ such that for all $k \in [n]$,
\[ {\mathbb E}_{\xi \sim {\mathcal D}_k} \|  \nabla F_k({ \boldsymbol x}; \xi)\|^2 \le G^2 \]
\end{assumption}

\begin{theorem}[\citet{yu2019parallel}]
	\label{thm:yu}
Let Assumption~\ref{asum:smooth},~\ref{asum:within-var} and~\ref{asum:bound} hold and $L, \sigma, G$ defined therein.
Let $\{{ \boldsymbol x}_t\}_{t=1}^T$ denote by the sequence obtained by PR-SGD and $\Delta = f(\overline{{ \boldsymbol x}}_0) - \min_{{ \boldsymbol x} } f ({ \boldsymbol x} )$ be the initial error.
If $0 < \eta  \le \frac{1}{L}$, then for all $T$, we have
\begin{equation*}
\frac{1}{T} \sum_{t=1}^{T} {\mathbb E} \big\|\nabla f (\overline{{ \boldsymbol x}}_t) \big\|^2
\: \leq \:
\frac{2\Delta}{\eta T} + \frac{\eta L\sigma^2}{n} +  4\eta^2 I^2 G^2L^2
\end{equation*}
\end{theorem}

\paragraph{Convergence for D-SGD.}
D-SGD~\cite{jiang2017collaborative,lian2017can} is the special case of LD-SGD where $I_1 =0, I_2=1$, $1  > \rho \ge 0$ and the communication-after update rule (introduced in Appendix~\ref{append:another_update}) is applied.
The original paper~\cite{lian2017can} provides an analysis for D-SGD, which we simplify and translate into Theorem~\ref{thm:lian} in our notation.
To guarantee convergence at a neighborhood of stationary points,~\cite{lian2017can} requires a smaller learning rate ${\mathcal O}(\frac{1-\rho}{\sqrt{n}L})$ than our ${\mathcal O}(\frac{1-\rho}{L})$.
By contrast their residual error is larger than ours up to a factor of ${\mathcal O}(n)$. They could achieve as similar bounds on residual errors as ours by shrinking the learning rate, but the convergence would be slowed down.

\begin{theorem}[\citet{lian2017can}]
	\label{thm:lian}
	Let Assumption~\ref{asum:smooth},~\ref{asum:within-var}, ~\ref{asum:inter-var} and~\ref{asum:W} hold and $L, \sigma, \kappa$ defined therein.
	Let $\{{ \boldsymbol x}_t\}_{t=1}^T$ denote by the sequence obtained by D-SGD and $\Delta = f(\overline{{ \boldsymbol x}}_0) - \min_{{ \boldsymbol x} } f ({ \boldsymbol x} )$ be the initial error.
	When the learning rate is small enough\footnote{In this way, their $D_2 \ge \frac{2}{3}$ and $D_1 \ge \frac{1}{4}$, and this result follows from replacing $D_1, D_2$ with these constant lower bounds.} such that $\eta \le \frac{1-\rho}{3\sqrt{6}L} \frac{1}{\sqrt{n}}$, then for all $T$, we have
	\begin{equation*}
	\frac{1}{T} \sum_{t=1}^{T} {\mathbb E} \big\|\nabla f (\overline{{ \boldsymbol x}}_t) \big\|^2
	\: \leq \:
	\frac{4\Delta}{\eta T} + \frac{2\eta L\sigma^2}{n} + n \left[ \frac{6\eta^2L^2\sigma^2 }{1-\rho^2} +  \frac{54\eta^2L^2\kappa^2 }{(1-\rho)^2} \right]
	\end{equation*}
\end{theorem}

\paragraph{Convergence for PD-SGD.}
 The PD-SGD is derived as a byproduct of the framework of Cooperative SGD (C-SGD) in~\cite{wang2018cooperative}.
 In that paper,~\citet{wang2018cooperative} terms PD-SGD as Decentralized Periodic Averaging SGD (PDA-SGD).
 In our paper, the PD-SGD (or DPA-SGD) is the case of LD-SGD with ${\mathcal I}_T^1$ when $I_2 = 1$ and $1 > \rho \ge 0$.
 We translate their original analysis into Theorem~\ref{thm:wang} for ease of comparison.

 First, our residual error is exactly the same with theirs up to constant factors. Second, they didn't consider the case when the data is non-identically distributed. Third, we allow more flexible communication pattern design by introducing parameters $I_2$.

 \begin{theorem}[\citet{wang2018cooperative}]
 	\label{thm:wang}
 	Let Assumption~\ref{asum:smooth},~\ref{asum:within-var} and~\ref{asum:W} hold and $L, \sigma$ defined therein.
 	Let $\{{ \boldsymbol x}_t\}_{t=1}^T$ denote by the sequence obtained by PD-SGD and $\Delta = f(\overline{{ \boldsymbol x}}_0) - \min_{{ \boldsymbol x} } f ({ \boldsymbol x} )$ be the initial error.
 	When the learning rate is small enough such that $\eta \le \min  \{  \frac{1}{2L}, \frac{1-\rho}{\sqrt{10}LI} \}$, then for all $T$, we have
 	\begin{equation*}
 	\frac{1}{T} \sum_{t=1}^{T} {\mathbb E} \big\|\nabla f (\overline{{ \boldsymbol x}}_t) \big\|^2
 	\: \leq \:
 	\frac{2\Delta}{\eta T} + \frac{\eta L\sigma^2}{n} + \eta^2L^2 \sigma^2(\frac{1+\rho^2}{1-\rho^2} I -1)
 	\end{equation*}
 \end{theorem}

\section{Proof of Main Result}
\label{append:PD-SGD}

\subsection{Additional notation}
\label{appen:add-nota-1}
In the proofs we will use the following notation.
Let ${\bf G}( {\bf X}; \xi)$ be defined in Section~\ref{sec:notation} previously. Let
\begin{align*}
\overline{{\bf g}}( {\bf X}; \xi) :=\frac{1}{n}{\bf G}({\bf X}; \xi) \, {\bf 1}_n= \frac{1}{n} \sum_{k=1}^n F_k({ \boldsymbol x}^{(k)};\xi^{(k)}) \in {\mathbb R}^{d }
\end{align*}
be the averaged gradient.
Recall from~\eqref{eq:goal} the definition $f_k({ \boldsymbol x}) := {\mathbb E}_{\xi \sim {\mathcal D}_k} \big[ F_{k} \left( { \boldsymbol x} ; \xi\right) \big]$.
We analogously define
\begin{align*}
\nabla f({\bf X}) &:= {\mathbb E} \big[ {\bf G}( {\bf X}; \xi) \big]= \left[ \nabla f_1({ \boldsymbol x}^{(1)}), \cdots, \nabla f_n({ \boldsymbol x}^{(n)})\right] \in {\mathbb R}^{d \times n},\\
\overline{\nabla f}({\bf X}) &:= {\mathbb E}  \big[ \overline{{\bf g}}( {\bf X}; \xi) \big] = \frac{1}{n}\nabla f({\bf X}) {\bf 1}_n = \frac{1}{n} \sum_{k=1}^n \nabla f_k({ \boldsymbol x}^{(k)})  \in {\mathbb R}^{d },\\
\nabla f( \overline{{ \boldsymbol x}} ) &:= \overline{\nabla f}( \overline{{ \boldsymbol x}} )  =  \frac{1}{n} \sum_{k=1}^n \nabla f_k(\overline{{ \boldsymbol x}})  \in {\mathbb R}^{d } .
\end{align*}
Let ${\bf Q} = \frac{1}{n}{\bf 1}_n {\bf 1}_n^\top $ and $\overline{{ \boldsymbol x}}_t = \frac{1}{n} \sum_{k=1}^n { \boldsymbol x}_t^{(k)}$.
Define the residual error as
\begin{equation}
\label{eq:v}
V_t = {\mathbb E}_{\xi} \frac{1}{n} \big\|{\bf X}_t({\bf I}-{\bf Q}) \big\|_F^2 ={\mathbb E}_{\xi} \frac{1}{n} \sum_{k=1}^n \big\| { \boldsymbol x}_t^{(k)} - \overline{{ \boldsymbol x}}_t \big\|^2 .
\end{equation}
where the expectation is taken with respect to all randomness of stochastic gradients or equivalently $\xi = (\xi_1, \cdots, \xi_t, \cdots)$ where $\xi_s = (\xi_s^{(1)}, \cdots, \xi_s^{(n)})^\top \in {\mathbb R}^n$. Except where noted, we will use notation ${\mathbb E}(\cdot)$ in stead of ${\mathbb E}_{\xi}(\cdot)$ for simplicity. Hence $V_t = \frac{1}{n} {\mathbb E} \sum_{k=1}^n \big\| { \boldsymbol x}_t^{(k)} - \overline{{ \boldsymbol x}}_t \big\|^2$.

As mentioned in Section~\ref{sec:notation}, LD-SGD with arbitrary update scheme can be equivalently written in matrix form which will be used repeatedly in the following convergence analysis. Specifically,
\begin{equation}
\label{eq:pdsgd}
{\bf X}_{t+1} = ({\bf X}_{t} - {\bf G}({\bf X}_t; \xi_t)){\bf W}_t
\end{equation}
where ${\bf X}_t \in {\mathbb R}^{d \times n}$ is the concatenation of $\{{ \boldsymbol x}_t^{(k)} \}_{k=1}^n$, ${\bf G}({\bf X}_t;\xi_t) \in {\mathbb R}^{d \times n}$ is the concatenated gradient evaluated at ${\bf X}_t$ with the sampled datum $\xi_t$, and ${\bf W}_t \in {\mathbb R}^{n \times n}$ is the connected matrix defined by
\begin{equation}
\label{eq:W}
{\bf W}_t = \left\{ \begin{array}{ll}
{\bf I}_n & \text{if} \ t  \notin {\mathcal I}_T ; \\
{\bf W} & \text{if} \ t  \in {\mathcal I}_T.
\end{array}\right.
\end{equation}

\subsection{Useful lemmas}

The main idea of proof is to express ${\bf X}_t$ in terms of gradients and then develop upper bound on residual errors.
The technique to bound residual errors can be found in~\cite{wang2018adaptive,wang2018cooperative,wang2019matcha,yu2019parallel,yu2019linear}.

\begin{lem}[One step recursion]
	\label{lem:one-step}
	Let Assumptions~\ref{asum:smooth} and~\ref{asum:within-var} hold and $L$ and $\sigma$ be defined therein.
	Let $\eta$ be the learning rate.
	Then the iterate obtained from the update rule~\eqref{eq:pdsgd} satisfies
	\begin{equation}
	\label{eq:one-step}

	{\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_{t+1}) \big]
	\: \leq \: {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_t) \big] - \frac{\eta}{2}(1-\eta L) {\mathbb E} \big\| \overline{\nabla f}({\bf X}_t) \big\|^2
	- \frac{\eta}{2} {\mathbb E} \big\| \nabla f (\overline{{ \boldsymbol x}}_t) \big\|^2 + \frac{L\sigma^2\eta^2 }{2n} + \frac{\eta L^2}{2} V_t,
	\end{equation}
	where the expectations  are taken with respect to all randomness in stochastic gradients.
\end{lem}

\begin{proof}
Recall that from the update rule~\eqref{eq:pdsgd} we have
\[ \overline{{ \boldsymbol x}}_{t+1} = \overline{{ \boldsymbol x}}_{t} - \eta \overline{{\bf g}}({\bf X}_t, \xi_t). \]
When Assumptions~\ref{asum:smooth} and~\ref{asum:within-var} hold,
it follows directly from Lemma 8 in~\cite{tang2018d} that
\begin{align*}
{\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_{t+1}) \big]
\: \leq \: {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_t) \big] - \frac{\eta}{2} {\mathbb E} \big\| \nabla f (\overline{{ \boldsymbol x}}_t) \big\|^2
&- \frac{\eta}{2}(1-\eta L) {\mathbb E} \big\| \overline{\nabla f}({\bf X}_t) \big\|^2
+ \frac{L\sigma^2\eta^2 }{2n} \\
&+ \frac{\eta}{2}  {\mathbb E} \big\| \nabla f(\overline{{ \boldsymbol x}}_t) - \overline{\nabla f}({\bf X}_t) \big\|^2.
\end{align*}

The conclusion then follows from
\begin{align*}
 {\mathbb E} \| \nabla f(\overline{{ \boldsymbol x}}_t) - \overline{\nabla f}({\bf X}_t)  \|^2
&= \frac{1}{n^2} {\mathbb E} \bigg\| \sum_{k=1}^n \left[  f_k \big(\overline{{ \boldsymbol x}}_t \big) -   f_k \big({ \boldsymbol x}_t^{(k)} \big) \right] \bigg\|^2\\
& \overset{(a)}{\le} \frac{1}{n} \sum_{k=1}^n {\mathbb E} \Big\|  f_k \big(\overline{{ \boldsymbol x}}_t \big) -   f_k \big({ \boldsymbol x}_t^{(k)} \big)  \Big\|^2\\
& \overset{(b)}{\le}  \frac{L^2}{n} \sum_{k=1}^n  {\mathbb E} \big\| { \boldsymbol x}_t^{(k)} - \overline{{ \boldsymbol x}}_t \big\|^2\\
& = L^2 V_t
\end{align*}
where (a) follows from Jensen's inequality, (b) follows from Assumption~\ref{asum:smooth},
and $V_t$ is defined in \eqref{eq:v}.
\end{proof}

\begin{lem}[Residual error decomposition]
	\label{lem:residual-decom}
	Let ${\bf X}_1 = { \boldsymbol x}_1 {\bf 1}_n^\top \in {\mathbb R}^{d\times n}$ be the initialization. If we apply the update rule~\eqref{eq:pdsgd}, then for any $t \ge 2$,
	\begin{equation}
	\label{eq:decomposition}
	{\bf X}_t({\bf I}_n-{\bf Q})= - \eta \sum_{s=1}^{t-1} {\bf G}({\bf X}_s;\xi_s) \left(  \mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q} \right)
	\end{equation}
	where $\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1}$ is defined in~\eqref{eq:Ph} and ${\bf W}_t$ is given in~\eqref{eq:W}.
	\begin{equation}
	\label{eq:Ph}
	\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} = \left\{
	\begin{array}{ll}
	{\bf I}_{n}   &\text{if} \ s \ge t \\
	\prod_{l=s}^{t-1} {\bf W}_l & \text{if} \ s < t.
	\end{array}
	\right.
	\end{equation}
\end{lem}

\begin{proof}[Proof]
	For convenience, we denote by ${\bf G}_t = {\bf G}({\bf X}_t; \xi_t) \in {\mathbb R}^{d \times n}$ the concatenation of stochastic gradients at iteration $t$. According to the update rule, we have
	\begin{align*}
	{\bf X}_t({\bf I}_n-{\bf Q}) &= ({\bf X}_{t-1} - \eta{\bf G}_{t-1}){\bf W}_{t-1}({\bf I}_n-{\bf Q})\\
	&\overset{(a)}{=} {\bf X}_{t-1}({\bf I}_n-{\bf Q}){\bf W}_{t-1} - \eta{\bf G}_{t-1}({\bf W}_{t-1} -{\bf Q})\\
	&\overset{(b)}{=} {\bf X}_{t-l}({\bf I}_n-{\bf Q}) \prod_{s=t-l}^{t-1} {\bf W}_{s} - \eta \sum_{s=t-l}^{t-1}  {\bf G}_s (\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q} ) \\
	&\overset{(c)}{=} {\bf X}_1({\bf I}_n-{\bf Q})\mbox{\boldmath$\Phi$\unboldmath}_{1, t-1} - \eta \sum_{s=1}^{t-1} {\bf G}_s \left(  \mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q} \right)
	\end{align*}
	where (a) follows from ${\bf W}_{t-1}{\bf Q} = {\bf Q} {\bf W}_{t-1}$; (b) results by iteratively expanding the expression of ${\bf X}_{s}$ from $s = t-1$ to $s = t- l+1$ and plugging in the definition of $\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1}$ in~\eqref{eq:W}; (c) follows simply by setting $l=t-1$. Finally, the conclusion follows from the initialization ${\bf X}_1 = { \boldsymbol x}_1 {\bf 1}_n^\top$ which implies ${\bf X}_1({\bf I}-{\bf Q})= {\bf 0}$.
\end{proof}

\begin{lem}[Gradient variance decomposition]
	\label{lem:grad-decom}
	Given any sequence of deterministic matrices $\{{\bf A}_s\}_{s =1}^t$, then for any $t \ge 1$,
	\begin{equation}
	\label{eq:grad-var}
	{\mathbb E}_{\xi} \bigg\| \sum_{s =1}^t  \left[ {\bf G} \big({\bf X}_s;\xi_s \big) - \nabla f \big({\bf X}_s \big) \right] {\bf A}_s \bigg\|_F^2
	=  	\sum_{s =1}^t  {\mathbb E}_{\xi_s}  \Big\|  \left[ {\bf G} \big({\bf X}_s;\xi_s \big) - \nabla f \big({\bf X}_s \big) \right] {\bf A}_s \Big\|_F^2 .
	\end{equation}
	where the expectation ${\mathbb E}_{\xi}(\cdot)$ is taken with respect to the randomness of $\xi = (\xi_1, \cdots, \xi_t, \cdots)$ and ${\mathbb E}_{\xi_s}(\cdot)$ is with respect to $\xi_s = (\xi_s^{(1)}, \cdots, \xi_s^{(n)})^\top \in {\mathbb R}^n$.
\end{lem}

\begin{proof}
\begin{align*}
{\mathbb E}_{\xi} &\bigg\| \sum_{s =1}^t  \left[ {\bf G} \big({\bf X}_s;\xi_s \big) - \nabla f \big({\bf X}_s \big) \right] {\bf A}_s \bigg\|_F^2
\: = \:  \sum_{s =1}^t  {\mathbb E}_{\xi_s} \Big\| \left[  {\bf G} \big({\bf X}_s;\xi_s \big) - \nabla f \big({\bf X}_s \big)  \right] {\bf A}_s \Big\|_F^2 \\
& + 2 \sum_{1 \le s < l \le t}  {\mathbb E}_{\xi_s, \xi_l} \Big[  \Big\langle \left[ {\bf G} \big({\bf X}_s;\xi_s \big) - \nabla f \big({\bf X}_s \big) \right] {\bf A}_s, \: \left[ {\bf G} \big({\bf X}_l;\xi_l \big) - \nabla f \big({\bf X}_l \big) \right] {\bf A}_l  \Big\rangle \Big]
\end{align*}
where the inner product of matrix is defined by $\langle {\bf A}, {\bf B} \rangle  =\text{tr}({\bf A} {\bf B}^\top)$.

Since different nodes work independently without interference, for $ s \neq l \in [t]$, $\xi_s$ is independent with $\xi_l$.
Let ${\mathcal F}_s = \sigma(\{\xi_l\}_{l=1}^s)$ be the $\sigma$-field generated by all the random variables until iteration $s$.
Then for any $1 \le s < l \le t$, we obtain
\begin{align*}
&{\mathbb E}_{\xi_s, \xi_l} \Big[ \Big\langle  \left( {\bf G}({\bf X}_s;\xi_s) - \nabla f({\bf X}_s) \right) {\bf A}_s, \: \left( {\bf G}({\bf X}_l;\xi_l) - \nabla f({\bf X}_l)\right) {\bf A}_l  \Big\rangle \Big] \\
&={\mathbb E}_{\xi_s} {\mathbb E}_{\xi_l} \Big[ \Big\langle  \left( {\bf G}({\bf X}_s;\xi_s) - \nabla f({\bf X}_s) \right) {\bf A}_s, \, \left( {\bf G}({\bf X}_l;\xi_l) - \nabla f({\bf X}_l)\right) {\bf A}_l  \Big\rangle \, \Big| \, {\mathcal F}_{l-1} \Big] \\
&\overset{(a)}{=}{\mathbb E}_{\xi_s}  \Big\{ \Big\langle  \left( {\bf G}({\bf X}_s;\xi_s) - \nabla f({\bf X}_s) \right) {\bf A}_s,
\: {\mathbb E}_{\xi_l} \big[ \left( {\bf G}({\bf X}_l;\xi_l) - \nabla f({\bf X}_l)\right) {\bf A}_l  \big| {\mathcal F}_{l-1} \big] \Big\rangle \Big\} \\
&\overset{(b)}{=}{\mathbb E}_{\xi_s}  \Big[ \Big\langle  {\bf G}({\bf X}_s;\xi_s) - \nabla f({\bf X}_s), \: {\bf 0} \Big\rangle \Big] = 0
\end{align*}
where (a) follows from the tower rule by noting that ${\bf X}_s$ and $\xi_s$ are both ${\mathcal F}_{l-1}$-measurable and (b) uses the fact that $\xi_l$ is independent with ${\mathcal F}_s (s < l)$ and  ${\bf G}({\bf X}_l;\xi_l)$ is a unbiased estimator of $\nabla f({\bf X}_l)$.
\end{proof}

\begin{lem}[Bound on second moments of gradients]
	\label{lem:grad-second}
	For any $n$ points: $\{ { \boldsymbol x}_t^{(k)}\}_{k=1}^n$, define ${\bf X}_t = \left[ { \boldsymbol x}_t^{(1)}, \cdots, { \boldsymbol x}_t^{(n)} \right]$ as their concatenation, then under Assumption~\ref{asum:smooth} and~\ref{asum:inter-var},
	\begin{equation}
	\label{eq:grad-second}
	\frac{1}{n} {\mathbb E} \big\| \nabla f({\bf X}_t)  \big\|_F^2
	\: \leq \: 8L^2 V_t + 4 \kappa^2  +  4 {\mathbb E} \big\| \overline{\nabla f}({\bf X}_t)  \big\|^2.
	\end{equation}
\end{lem}

\begin{proof}
By splitting $\nabla f({\bf X}_t)$ into four terms, we obtain
\begin{align*}
& {\mathbb E} \| \nabla f({\bf X}_t)  \|_F^2\\
=&{\mathbb E}  \| \nabla f({\bf X}_t)  - \nabla f(\overline{{ \boldsymbol x}}_t  {\bf 1}_n^\top)
+  \nabla f(\overline{{ \boldsymbol x}}_t  {\bf 1}_n^\top)  -  \nabla f(\overline{{ \boldsymbol x}}_t) {\bf 1}_n^\top  \\
& \quad +  \nabla f(\overline{{ \boldsymbol x}}_t) {\bf 1}_n^\top - \overline{\nabla f}({\bf X}_t){\bf 1}_n^\top
+ \overline{\nabla f}({\bf X}_t){\bf 1}_n^\top  \|_F^2 \\
\overset{(a)}{\le}
& 4{\mathbb E} \| \nabla f({\bf X}_t)  - \nabla f(\overline{{ \boldsymbol x}}_t  {\bf 1}_n^\top)\|_F^2
+ 4 {\mathbb E} \| \nabla f(\overline{{ \boldsymbol x}}_t  {\bf 1}_n^\top)  -  \nabla f(\overline{{ \boldsymbol x}}_t) {\bf 1}_n^\top  \|_F^2    \\
& \quad + 4{\mathbb E} \| \nabla f(\overline{{ \boldsymbol x}}_t) {\bf 1}_n^\top - \overline{\nabla f}({\bf X}_t){\bf 1}_n^\top \|_F^2 + 4 {\mathbb E} \| \overline{\nabla f}({\bf X}_t){\bf 1}_n^\top  \|_F^2 \\
\overset{(b)}{=}& 4L^2 n V_t +  4 {\mathbb E} \| \nabla f(\overline{{ \boldsymbol x}}_t  {\bf 1}_n^\top)  -  \nabla f(\overline{{ \boldsymbol x}}_t) {\bf 1}_n^\top \|_F^2  + 4L^2 n V_t + 4 n {\mathbb E}  \| \overline{\nabla f}({\bf X}_t)  \|^2\\
\overset{(c)}{=}&  8L^2 n V_t  + 4 n \kappa^2 +  4 n \| \overline{\nabla f}({\bf X}_t)  \|^2
\end{align*}
where (a) follows from the basic inequality $\| \sum_{i=1}^n {\bf A}_i \|_F^2 \le n \sum_{i=1}^n \|{\bf A}_i\|_F^2$; (b) follows from the smoothness of $\{f_k\}_{k=1}^n$ and $f = \frac{1}{n} \sum_{k=1}^n f_k$ (Assumption~\ref{asum:smooth}) and the definition of $V_t$ in~\eqref{eq:v}; (c) follows from Assumption~\ref{asum:inter-var} as a result of the fact $\|\nabla f(\overline{{ \boldsymbol x}}_t  {\bf 1}_n^\top)  -  \nabla f(\overline{{ \boldsymbol x}}_t) {\bf 1}_n^\top\|_F^2 = \sum_{k=1}^n \| \nabla f_k(\overline{{ \boldsymbol x}}_t) - \nabla f(\overline{{ \boldsymbol x}}_t) \|^2$.
\end{proof}

\begin{lem}[Bound on residual errors]
	\label{lem:residual-bound}
	Let $\rho_{s, t-1} = \|\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}\|$ where $\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1}$ is defined in~\eqref{eq:Ph}. Then the residual error can be upper bounded, i.e.,
	\[  V_t \le 2 \eta^2 U_t  \]
	where
	\begin{equation}
	\label{eq:U}
	U_t =
	 \sigma^2  \sum_{s=1}^{t-1} \rho^2_{s, t-1}
	+
	 \left( \sum_{s=1}^{t-1}  \rho_{s, t-1} \right) \left(  \sum_{s=1}^{t-1} \rho_{s, t-1} \left( 8L^2 V_s  + 4\kappa^2 +4 {\mathbb E} \| \overline{\nabla f}({\bf X}_s)  \|^2 \right) \right).
	\end{equation}
\end{lem}

\begin{proof}
Again we denote by ${\bf G}_t = {\bf G}({\bf X}_t; \xi_t)$ for simplicity. From Lemma~\ref{lem:residual-decom}, we can obtain a closed form of $V_t$. Then it follows that
\begin{align*}
n V_t  &= {\mathbb E} \| {\bf X}_{t}({\bf I} - {\bf Q}) \|_F^2 = \eta^2 {\mathbb E} \bigg\| \sum_{s=1}^{t-1} {\bf G}_s(\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q})\bigg\|_F^2 \\
&=\eta^2 {\mathbb E} \bigg\| \sum_{s=1}^{t-1} ({\bf G}_s - {\mathbb E} {\bf G}_s )(\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q})  +  \sum_{s=1}^{t-1} {\mathbb E} {\bf G}_s(\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}) \bigg\|_F^2 \\
&\overset{(a)}{\le} 2 \eta^2 {\mathbb E}\bigg\| \sum_{s=1}^{t-1} ({\bf G}_s - \nabla f ({\bf X}_s) )(\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q})\bigg\|_F^2
+ 2\eta^2 {\mathbb E} \bigg\|\sum_{s=1}^{t-1} \nabla f ({\bf X}_s)(\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}) \bigg\|_F^2\\
&\overset{(b)}{=} 2 \eta^2{\mathbb E} \sum_{s=1}^{t-1} \|({\bf G}_s - \nabla f ({\bf X}_s) )(\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q})\|_F^2
+ 2\eta^2 {\mathbb E} \bigg\|\sum_{s=1}^{t-1} \nabla f ({\bf X}_s)(\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}) \bigg\|_F^2\\
&\overset{(c)}{\le} 2 \eta^2 {\mathbb E} \sum_{s=1}^{t-1} \|({\bf G}_s - \nabla f ({\bf X}_s) )(\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q})\|_F^2
+ 2\eta^2 {\mathbb E} \left(  \sum_{s=1}^{t-1} \| \nabla f ({\bf X}_s)(\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}) \|_F  \right)^2 \\
&\overset{(d)}{\le} 2 \eta^2 {\mathbb E} \sum_{s=1}^{t-1} \|{\bf G}_s - \nabla f ({\bf X}_s) \|_F^2 \|\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}\|^2
+ 2\eta^2 {\mathbb E} \left(  \sum_{s=1}^{t-1} \| \nabla f ({\bf X}_s)\|_F \|(\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}) \| \right)^2 \\
&\overset{(e)}{=} 2 \eta^2 \sum_{s=1}^{t-1} \rho^2_{s, t-1}  {\mathbb E} \|{\bf G}_s - \nabla f ({\bf X}_s) \|_F^2   + 2\eta^2 {\mathbb E} \left(  \sum_{s=1}^{t-1} \rho_{s, t-1} \| \nabla f ({\bf X}_s)\|_F  \right)^2 \\
&\overset{(f)}{\le} 2 \eta^2 \sum_{s=1}^{t-1} \rho^2_{s, t-1} {\mathbb E}  \|{\bf G}_s - \nabla f ({\bf X}_s) \|_F^2   + 2\eta^2 \left( \sum_{s=1}^{t-1}  \rho_{s, t-1} \right) \left(  \sum_{s=1}^{t-1} \rho_{s, t-1}{\mathbb E}  \|  \nabla f ({\bf X}_s)\|_F^2 \right) \\
&\overset{(g)}{\le} 2 \eta^2 \sum_{s=1}^{t-1} \rho^2_{s, t-1} n \sigma^2   + 2\eta^2 \left( \sum_{s=1}^{t-1}  \rho_{s, t-1} \right) \left(  \sum_{s=1}^{t-1} \rho_{s, t-1} \left( 8L^2 n V_s  + 4 n \kappa^2 +  4 n{\mathbb E} \| \overline{\nabla f}({\bf X}_s)  \|^2 \right) \right) \\
&= 2n\eta^2 \left[   \sigma^2  \sum_{s=1}^{t-1} \rho^2_{s, t-1}
+  \left( \sum_{s=1}^{t-1}  \rho_{s, t-1} \right) \left(  \sum_{s=1}^{t-1} \rho_{s, t-1} \left( 8L^2 V_s  + 4 \kappa^2 + 4 {\mathbb E} \| \overline{\nabla f}({\bf X}_s)  \|^2 \right) \right)  \right] \\
&=2n\eta^2 U_t
\end{align*}
where (a) follows from the basic inequality $\| {\bf a} + {\bf b} \|^2 \le 2 (\|{\bf a}\|^2 + \|{\bf b}\|^2)$ and ${\mathbb E} {\bf G}_s = \nabla f({\bf X}_s)$; (b) follows from Lemma~\ref{lem:grad-decom}; (c) follows from the triangle inequality $\|\sum_{s=1}^{t-1}{\bf A}_s\|_F \le \sum_{s=1}^{t-1}\|{\bf A}_s\|_F$; (d) follows from the basic inequality $\|{\bf A}{\bf B}\|_F \le \|{\bf A}\|_F \|{\bf B}\|$ for any matrix ${\bf A}$ and ${\bf B}$; (e) directly follows from the notation $\rho_{s, t-1} = \|\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}\|$; (f) follows from the Cauchy inequality; (g) follows from Assumption~\ref{asum:within-var} and Lemma~\ref{lem:grad-second}.
\end{proof}

\begin{lem}[Bound on average residual error]
	\label{lem:residual-average}
	For any fix $T$, define
	\begin{equation}
	\label{eq:ABC}
	A_T =\frac{1}{T}\sum_{t=1}^{T} \sum_{s=1}^{t-1} \rho^2_{s, t-1}, \quad
	B_T = \frac{1}{T} \sum_{t=1}^{T} \left(\sum_{s=1}^{t-1} \rho_{s, t-1} \right)^2, \quad
	C_T = \max_{s \in [T-1]} \sum_{t=s+1}^T  \rho_{s, t-1}  \left( \sum_{l=1}^{t-1}  \rho_{l, t-1} \right).
	\end{equation}
	Assume the learning rate is so small that $16\eta^2L^2 C_T < 1$, then
	\begin{equation}
	\frac{1}{T}\sum_{t=1}^T V_t \le  \frac{2\eta^2}{1-16\eta^2L^2 C_T}\left[ A_T \sigma^2 + B_T \kappa^2 +  4C_T\frac{1}{T}\sum_{t=1}^{T}  {\mathbb E} \| \overline{\nabla f}({\bf X}_t)  \|^2  \right].
	\end{equation}
\end{lem}

\begin{proof}
	Denote by $Z_s = 8L^2 V_s  + 4 {\mathbb E} \| \overline{\nabla f}({\bf X}_s)  \|^2 $ for short. From Lemma~\ref{lem:residual-bound}, $V_t \le 2 \eta^2 U_t$, then
	\begin{equation}
	\label{eq:V<U}
	\frac{1}{T}\sum_{t=1}^T V_t \le 2 \eta^2 \cdot \frac{1}{T} \sum_{t=1}^{T}U_t
	\end{equation}
	and
	\begin{align}
	\label{eq:U_average_u}
	\frac{1}{T}\sum_{t=1}^{T}U_t
	&\overset{\eqref{eq:U}}{=}
	\frac{1}{T}\sum_{t=1}^{T} \left[
	\sigma^2  \sum_{s=1}^{t-1} \rho^2_{s, t-1}
	+  \left( \sum_{s=1}^{t-1}  \rho_{s, t-1} \right) \left(  \sum_{s=1}^{t-1} \rho_{s, t-1} \left( Z_s + 4 \kappa^2 \right) \right) \right] \nonumber \\
	&\overset{(a)}{=} \sigma^2 \frac{1}{T}\sum_{t=1}^{T} \sum_{s=1}^{t-1} \rho^2_{s, t-1}
	+ 4 \kappa^2 \frac{1}{T} \sum_{t=1}^{T} \left(\sum_{s=1}^{t-1} \rho_{s, t-1} \right)^2
	 + \frac{1}{T} \sum_{t=1}^T \left( \sum_{l=1}^{t-1}  \rho_{l, t-1} \right) \left( \sum_{s=1}^{t-1} \rho_{s, t-1} Z_s \right)  \nonumber \\
	&\overset{(b)}{=} \sigma^2 \frac{1}{T}\sum_{t=1}^{T} \sum_{s=1}^{t-1} \rho^2_{s, t-1}
	+ 4 \kappa^2 \frac{1}{T} \sum_{t=1}^{T} \left(\sum_{s=1}^{t-1} \rho_{s, t-1} \right)^2
	+ \frac{1}{T}\sum_{s=1}^{T-1} Z_s   \sum_{t=s+1}^T  \rho_{s, t-1}  \left( \sum_{l=1}^{t-1}  \rho_{l, t-1} \right)  \nonumber \\
	&\overset{(c)}{\le} \sigma^2 A_T + 4 \kappa^2  B_T
	+  C_T \frac{1}{T} \sum_{s=1}^{T-1} Z_s   \nonumber \\
	&\overset{(d)}{\le}\sigma^2 A_T + 4 \kappa^2  B_T
	+ 8 L^2 C_T  \frac{1}{T} \sum_{s=1}^{T-1} V_s + 4 C_T \frac{1}{T}\sum_{t=1}^{T}  {\mathbb E} \| \overline{\nabla f}({\bf X}_t)  \|^2 \nonumber  \\
	&\overset{(e)}{\le}\sigma^2 A_T + 4 \kappa^2  B_T
	+ 16 \eta^2 L^2 C_T  \frac{1}{T} \sum_{t=1}^{T} U_t + 4 C_T \frac{1}{T}\sum_{t=1}^{T}  {\mathbb E} \| \overline{\nabla f}({\bf X}_t)  \|^2
	\end{align}
	where (a) follows from rearrangement;
	(b) follows from the equality that
	\[ \sum_{t=1}^{T} \left( \sum_{s=1}^{t-1}  \rho_{s, t-1} \right) \left( \sum_{s=1}^{t-1} \rho_{s, t-1} Z_s \right)
	=  \sum_{t=1}^{T} \left( \sum_{l=1}^{t-1}  \rho_{l, t-1} \right)
	\left( \sum_{s=1}^{T-1} \rho_{s, t-1} Z_s 1_{ \{t > s \}} \right)
	=  \sum_{s=1}^{T-1} Z_s   \sum_{t=s+1}^T  \rho_{s, t-1}  \left( \sum_{l=1}^{t-1}  \rho_{l, t-1} \right);    \]
	(c) following from the notation~\eqref{eq:ABC};
	(d) follows from the definition of ${\bf Z}_s$;
	(e) follows from Lemma~\ref{lem:residual-bound}.

	By arranging~\eqref{eq:U_average_u} and assuming the learning rate is small enough such that $16\eta^2L^2 C_T < 1$, then we have
	\begin{equation}
	\label{eq:U_average_u_2}
	\frac{1}{T}\sum_{t=1}^T U_t \le \frac{1}{1-16\eta^2L^2 C_T}\left[ A_T \sigma^2 + B_T \kappa^2 +  4C_T\frac{1}{T}\sum_{t=1}^{T}  {\mathbb E} \| \overline{\nabla f}({\bf X}_t)  \|^2  \right].
	\end{equation}

	Our conclusion then follows by combining~\eqref{eq:V<U} and~\eqref{eq:U_average_u_2}.
\end{proof}

\begin{lem}[Computation of $\rho_{s, t-1}$]
	\label{lem:rho_compute}
	Define $\rho_{s, t-1} = 1$ for any $t \le s$ and $\rho_{s, t-1} =  \|\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}\|$ when $s < t$.
	Then $\rho_{s, t-1} = \prod_{l=s}^{t-1} \rho_l$ with $\rho_l = \rho$ if $l \in {\mathcal I}_T$, else $\rho_l = 1$, where $\rho$ is defined in Assumption~\ref{asum:W}.
	As a direct consequence, $\rho_{s, t-1} = \rho_{s, l-1} \rho_{l, t-1}$ for any $s\le l \le t$ and thus $\rho_{s, t-1} = \rho^{|[s:t-1] \cap {\mathcal I}_T|}$.
\end{lem}
\begin{proof}
By definition, we have $\rho_{s, t-1} = \|\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}\| = \|\prod_{l=s}^{t-1}{\bf W}_l -{\bf Q} \|$. Since for any positive integer $l$, ${\bf W}_l {\bf Q} = {\bf Q} {\bf W}_l$, then ${\bf W}_l$ and ${\bf Q}$ can be simultaneously diagonalized. From this it is easy to see that $ \|\prod_{l=s}^{t-1}{\bf W}_l -{\bf Q} \|= \prod_{l=s}^{t-1} \rho_l$ where $\rho_l$ is the second largest absolute eigenvalue of ${\bf W}_l$. Note that ${\bf W}_l$ is either ${\bf W}$ or ${\bf I}$ according to the value of $l$ as a result of the definition~\eqref{eq:W}.
Hence  $\rho_l = \rho$ if $l \in {\mathcal I}_T$, else $ = 1$.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:PD-SGD}}
\label{append:main_proof}

\begin{proof}
	From Lemma~\ref{lem:one-step}, it follows that
	\begin{align*}
	{\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_{t+1})  \big]
	\: \leq \: {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_t) \big]
	- \frac{\eta}{2}(1-\eta L) {\mathbb E} \big\| \overline{\nabla f}({\bf X}_t) \big\|^2
	- \frac{\eta}{2} {\mathbb E} \big\| \nabla f (\overline{{ \boldsymbol x}}_t) \big\|^2
	+ \frac{L\sigma^2\eta^2 }{2n}
	+ \frac{\eta L^2}{2} V_t.
	\end{align*}
	Note that the expectation is taken with respect to all randomness of stochastic gradients, i.e., $\xi = (\xi_1, \xi_2. \cdots)$.
	Arranging this inequality, we have
	\begin{equation}
	\label{eq:e1}
	{\mathbb E} \big\| \nabla f (\overline{{ \boldsymbol x}}_t) \big\|^2
	\: \leq \: \frac{2}{\eta} \Big\{ {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_t) \big] -  {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_{t+1}) \big] \Big\}
	- (1-\eta L) {\mathbb E} \big\| \overline{\nabla f}({\bf X}_t) \big\|^2 + \frac{L\sigma^2\eta}{n} + L^2 V_t.
	\end{equation}

	Then it follows that
	\begin{align*}
	\label{eq:e2}
	&\frac{1}{T} \sum_{t=1}^{T} {\mathbb E} \| \nabla f (\overline{{ \boldsymbol x}}_t)\|^2 \\
	& \overset{(a)}{\le} \frac{2}{\eta T} \Big\{ {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_1) \big] -  {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_{T+1}) \big] \Big\}
	+ \frac{L\sigma^2\eta}{n} +  \frac{L^2}{T} \sum_{t=1}^{T}V_t
	- \frac{1-\eta L }{T} \sum_{t=1}^{T}  {\mathbb E} \big\| \overline{\nabla f}({\bf X}_t) \big\|^2\\
	& \overset{(b)}{\le}
	\frac{2}{\eta T} \Big\{ {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_1) \big] -  {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_{T+1}) \big] \Big\}
	+ \frac{L\sigma^2\eta}{n}
	-  \frac{1-\eta L}{T} \sum_{t=1}^{T}  {\mathbb E} \big\| \overline{\nabla f}({\bf X}_t) \big\|^2 \\
	& \quad \quad  +
	\frac{2\eta^2L^2}{1-16\eta^2L^2 C_T}\left[ A_T \sigma^2 + B_T \kappa^2 +  4C_T\frac{1}{T}\sum_{t=1}^{T}  {\mathbb E} \| \overline{\nabla f}({\bf X}_t)  \|^2  \right]\\
	& \overset{(c)}{\le}
	\frac{2}{\eta T} \Big\{  {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_1) \big] -  {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_{T+1}) \big] \Big\}
	+ \frac{L\sigma^2\eta}{n} + 4\eta^2L^2A_T \sigma^2 + 4\eta^2L^2B_T\kappa^2  \\
	& \quad \quad- (1-\eta L - 16\eta^2L^2C_T)  \frac{1}{T} \sum_{t=1}^{T}  {\mathbb E} \| \overline{\nabla f}({\bf X}_t)\|^2\\
	&\overset{(d)}{\le}
	\frac{2}{\eta T} \Big\{ {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_1) \big] -  {\mathbb E} \big[ f(\overline{{ \boldsymbol x}}_{T+1}) \big] \Big\}
	+ \frac{L\sigma^2\eta}{n}
	+ 4\eta^2L^2A_T \sigma^2 + 4\eta^2L^2B_T\kappa^2
	\end{align*}
	where (a) follows by telescoping and averaging~\eqref{eq:e1};
	(b) follows from the upper bound of $\frac{1}{T} \sum_{t=1}^{T}V_t$ in Lemma~\ref{lem:residual-average};
	(c) follows from the choice of the learning rate $\eta$ which satisfies $ \frac{1}{1-16\eta^2L^2C_T} \le 2$ (since $16\eta^2L^2C_T \le \frac{1}{2}$ from~\eqref{eq:lr}) and rearrangement;
	(d) follows the requirement that the learning rate $\eta$ is small enough such that $ \eta L + 16\eta^2L^2C_T < 1$ (which is satisfied since $\eta L \le \frac{1}{2}$ and $16\eta^2L^2K^2 \le \frac{1}{2}$).
\end{proof}

\subsection{Proof of Theorem~\ref{thm:bound}}
For any prescribed ${\mathcal I}_T$, denote by $g = |{\mathcal I}_T|$ and ${\mathcal I}_T = \{ e_1, e_2, \cdots, e_g \}$ with $e_0 = 1 \le e_1 < e_2 < \cdots < e_g \le T=e_{g+1}$.
For short, we let $s_i = e_i-e_{i-1}$ for $i \in [g+1]$.
Therefore, $\text{gap}({\mathcal I}_T) = \max_{i\in[g+1]} s_i$ from Definition~\ref{def:gap} and $T = \sum_{l=0}^{g} s_{l+1}$.

Recall the definition in~\eqref{eq:ABC}:
\begin{equation*}
A_T =\frac{1}{T}\sum_{t=1}^{T} \sum_{s=1}^{t-1} \rho^2_{s, t-1},  \
B_T = \frac{1}{T} \sum_{t=1}^{T} \left(\sum_{s=1}^{t-1} \rho_{s, t-1} \right)^2,  \
C_T = \max_{s \in [T-1]} \sum_{t=s+1}^T  \rho_{s, t-1}  \left( \sum_{l=1}^{t-1}  \rho_{l, t-1} \right).
\end{equation*}
In this section, we will provide proof for the bound on $A_T, B_T$ and $C_T$ in terms of $\text{gap}({\mathcal I}_T)$ (Theorem~\ref{thm:bound}).

\begin{proof}
Recall that from Definition~\ref{def:rho} and Lemma~\ref{lem:rho_compute}, $\rho_{s, t-1} = \rho^{|[s: t-1] \cap {\mathcal I}_T|}$, where $[s:t-1] = \{l \in {\bf N}: s \le l \le t-1\}$ and $\rho$ is defined in Assumption~\ref{asum:W}.
For simplicity, let $\Delta = \text{gap}({\mathcal I}_T) = \max_{i\in[g]} s_i$.

Let's first have a glance at $\sum_{s=1}^{t-1} \rho_{s, t-1}$.
Without loss of generality, we assume $e_{l} <  t \le e_{l+1}$ for some $l \in [g]\cup\{0\}$.
There, we have
\begin{equation}
\label{eq:inter}
\sum_{s=1}^{t-1} \rho_{s, t-1} = \left( t-e_{l} -1 \right)  + \sum_{i=1}^{l} s_i \rho^{l+1-i}.
\end{equation}
As a direct result, for any $t$, $\sum_{s=1}^{t-1} \rho_{s, t-1} \le \Delta + \Delta \frac{\rho}{1-\rho} = \frac{\Delta}{1-\rho}$.
Similarly, by symmetry, we have for any $s < T$, $\sum_{t=s+1}^{T} \rho_{s, t-1}  \le \frac{\Delta}{1-\rho}$.
Therefore, we have
\[ B_T \le \left( \frac{\Delta}{1-\rho} \right)^2 \ \text{and} \
C_T \le  \left( \max_{s \in [T-1]} \sum_{t=s+1}^T  \rho_{s, t-1}\right)  \max_{t \in [T+1]}  \left( \sum_{l=1}^{t-1}  \rho_{l, t-1} \right) = \left( \frac{\Delta}{1-\rho} \right)^2.  \]

Finally, for $A_T$, by using~\eqref{eq:inter}, we have
\begin{align*}
A_T = \frac{1}{T}\sum_{t=1}^T\sum_{s=1}^{t-1} \rho_{s, t-1}
& =\frac{1}{T}\sum_{l=0}^{g} \sum_{t=e_l+1}^{e_{l+1}}\sum_{s=1}^{t-1} \rho_{s, t-1}
= \frac{1}{T}\sum_{l=0}^{g} \sum_{t=e_l+1}^{e_{l+1}} \left[ \left( t-e_{l} -1 \right)  + \sum_{i=1}^{l} s_i \rho^{l+1-i} \right] \\
&=\frac{1}{T}\sum_{l=0}^{g} \left[\frac{s_{l+1}(s_{l+1}-1) }{2} +  s_{l+1}\sum_{i=1}^{l} s_i \rho^{l+1-i} \right] \\
&\le \frac{1}{T}\sum_{l=0}^{g} s_{l+1} \left( \frac{\Delta -1}{2}  + \Delta\sum_{i=1}^{l}\rho^{l+1-i}  \right) \\
&\le \frac{\Delta -1}{2}  + \Delta\frac{\rho}{1-\rho} = \Delta \frac{1+\rho}{1-\rho} - \frac{1}{2}.
\end{align*}

\end{proof}

\section{Proof of LD-SGD with multiple D-SGDs}
\label{append:scheme1}

The task of analyzing convergence for different communication schemes ${\mathcal I}_T$ can be reduced to figure out how residual errors are accumulated, i.e., to bound $A_T, B_T$ and $C_T$.
In this section, we are going to bound $A_T, B_T$ and $C_T$ when the update scheme is ${\mathcal I}_T^1$.
To that end, we first give a technical lemma, which facilitate the computation.
Lemma~\ref{lem:rho} captures the accumulation rate of residual errors for ${\mathcal I}_T^1$.

\subsection{One technical lemma}
\begin{lem}[Manipulation on $\rho_{s, t-1}$]
	\label{lem:rho}
	When ${\mathcal I}_T = {\mathcal I}_T^1$,	the following properties hold for $\rho_{s, t-1}$:
	\begin{enumerate}
		\item
		$\rho_{s, t-1} = \prod_{l=s}^{t-1} \rho_l$ with $\rho_l = 1$ if $l$ mod $I \in [I_1]$, else $\rho_l = \rho$ where $I = I_1 + I_2$ and $\rho$ is defined in Assumption~\ref{asum:W}. As a direct consequence, $\rho_{s, t-1} = \rho_{s, l-1} \rho_{l, t-1}$ for any $s\le l \le t$.
		\item
		Define
		\begin{equation}
		\label{eq:alpha}
		\alpha_j = \sum_{t=jI+1}^{(j+1)I} \sum_{s=1}^{t-1}\rho_{s, t-1}.
		\end{equation}
		Then for all $j \ge 0$,
		\begin{equation}
		\label{eq:alpha_u}
		\alpha_j \le \frac{1}{2}\left( \frac{1+\rho^{I_2}}{1-\rho^{I_2}} I_1^2 + \frac{1+\rho}{1-\rho} I_1 \right)  + I \frac{\rho}{1-\rho}.
		\end{equation}
		\item
		Define
		\begin{equation}
		\label{eq:beta}
		\beta_j = \sum_{t=jI+1}^{(j+1)I} \sum_{s=1}^{t-1}\rho_{s, t-1}^2.
		\end{equation}
		Then for all $j \ge 0$,
		\begin{equation}
		\label{eq:beta_u}
		\beta_j \le \frac{1}{2}\left( \frac{1+\rho^{2I_2}}{1-\rho^{2I_2}} I_1^2 + \frac{1+\rho^2}{1-\rho^2} I_1 \right)  + I \frac{\rho^2}{1-\rho^2}.
		\end{equation}
		\item
		For any $t \ge 1$, $\sum_{s=1}^{t-1}\rho_{s, t-1} \le K$ where
		\begin{equation}
		\label{eq:K}
		K = \frac{I_1}{1-\rho^{I_2}} + \frac{\rho}{1-\rho}.
		\end{equation}
		As a direct corollary, $\alpha_j \le IK$.
		\item
		Define
		\begin{equation}
		\label{eq:gamma}
		\gamma_j = \sum_{t=jI+1}^{(j+1)I} (\sum_{s=1}^{t-1}\rho_{s, t-1})^2.
		\end{equation}
		Then $\gamma_j \le K \alpha_j$, where $K$ is given in~\eqref{eq:K}.
		\item
		Assume $T = (R+1)I$ for some non-negative integer $R$. Define
		\begin{equation}
		w_s = \sum_{t=s+1}^{T} \rho_{s, t-1}
		\end{equation}
		Then for all $s \in [T], w_s \le K$ where $K$ is given in~\eqref{eq:K}.
	\end{enumerate}
\end{lem}

\begin{proof}
We prove these properties one by one:
\begin{enumerate}
	\item It is a direct corollary of Lemma~\ref{lem:rho_compute}.
	\item We now directly compute $\alpha_j = \sum_{t=jI+1}^{(j+1)I} \sum_{s=1}^{t-1}\rho_{s, t-1}$. Without loss of generality, assume $t = jI + i$ with $j \ge 0, 1 \le i \le I$. (i) When $1 \le i \le I_1 +1$, then
	\begin{align}
	\label{eq:less}
	\sum_{s=1}^{t-1}\rho_{s, t-1}
	&= (i-1) + I_1 \sum_{r=0}^{j-1} \rho^{I_2(j-r)} + \sum_{r=0}^{j-1} \sum_{l=1}^{I_2} \rho^{I_2(j-r)+1-l}  \nonumber  \\
	&=(i-1) + I_1 \frac{\rho^{I_2} - \rho^{I_2(j+1)}}{1-\rho^{I_2}} + \frac{\rho - \rho^{jI_2+1}}{1-\rho}  \nonumber  \\
	& \le (i-1)  + I_1\frac{\rho^{I_2}}{1-\rho^{I_2}} + \frac{\rho}{1-\rho}.
	\end{align}
	(ii) When $I_1 + 1 \le i \le I$, then
	\begin{align}
	\label{eq:large}
	\sum_{s=1}^{t-1}\rho_{s, t-1}
	& = \rho^{i - I_1 -1} \left[  I_1\sum_{r=0}^j \rho^{I_2(j-r)} + \sum_{r=0}^{j-1} \sum_{l=1}^{I_2} \rho^{I_2(j-r)+1-l} \right] + \sum_{l=1}^{i-I_1-1} \rho^{i-I_1-l} \nonumber \\
	& =\rho^{i - I_1 -1}  \left[   I_1 \frac{1 - \rho^{I_2(j+1)}}{1-\rho^{I_2}} + \frac{\rho - \rho^{jI_2+1}}{1-\rho} \right] + \frac{\rho - \rho^{i-I_1}}{1-\rho} \nonumber \\
	&=\rho^{i - I_1 -1} \cdot  I_1 \frac{1 - \rho^{I_2(j+1)}}{1-\rho^{I_2}}  + \frac{\rho - \rho^{jI_2+i-I_1}}{1-\rho}  \nonumber \\
	&\le I_1  \frac{\rho^{i - I_1 -1} }{1-\rho^{I_2}} + \frac{\rho}{1-\rho}.
	\end{align}
	Therefore, by combining (i) and (ii), we obtain
	\begin{align*}
	\alpha_j &= \sum_{t=jI+1}^{(j+1)I} \sum_{s=1}^{t-1}\rho_{s, t-1} \\
	&\le \sum_{i=1}^{I_1} \left((i-1)  + I_1\frac{\rho^{I_2}}{1-\rho^{I_2}} + \frac{\rho}{1-\rho} \right) + \sum_{i=I_1 + 1}^{I_1 + I_2} \left(I_1  \frac{\rho^{i - I_1 -1} }{1-\rho^{I_2}} + \frac{\rho}{1-\rho}\right)\\
	&= \frac{1}{2}\left( \frac{1+\rho^{I_2}}{1-\rho^{I_2}} I_1^2 + \frac{1+\rho}{1-\rho} I_1 \right)  + I \frac{\rho}{1-\rho}.
	\end{align*}
	\item Note that $\beta_j$'s share a similar structure with $\alpha_j$'s. Thus we can apply a similar argument in the proof of~\eqref{eq:alpha} to prove~\eqref{eq:beta}. A quick consideration reveals that~\eqref{eq:beta} can be obtained by replacing $\rho$ in~\eqref{eq:alpha} with $\rho^2$.
	\item Without loss of generality, assume $t = jI + i$ with $j \ge 0$ and $1 \le i \le I$. When $1 \le i \le I_1 +1$, from~\eqref{eq:less}, $\sum_{s=1}^{t-1}\rho_{s, t-1} \le (i-1)  + I_1\frac{\rho^{I_2}}{1-\rho^{I_2}} + \frac{\rho}{1-\rho} \le \frac{I_1}{1-\rho^{I_2}} + \frac{\rho}{1-\rho} = K$. When $I_1 + 1 \le i \le I_1 +I_2$, from~\eqref{eq:large}, $\sum_{s=1}^{t-1}\rho_{s, t-1} \le I_1  \frac{\rho^{i - I_1 -1} }{1-\rho^{I_2}} + \frac{\rho}{1-\rho} \le \frac{I_1}{1-\rho^{I_2}} + \frac{\rho}{1-\rho} = K$.
	\item The result directly follows from this inequality
	\[\left( \sum_{s=1}^{t-1}\rho_{s, t-1}  \right)^2 \le
	\left(  \max_{t \ge 1}\sum_{s=1}^{t-1}\rho_{s, t-1}\right) \cdot
	\left( \sum_{s=1}^{t-1}\rho_{s, t-1}  \right)
	\le K \left( \sum_{s=1}^{t-1}\rho_{s, t-1}  \right)  \]
	where $K$ is defined in~\eqref{eq:K}.
	\item Without loss of generality, assume $s = jI + i$ with $0 \le j \le R, 1 \le i \le I$. (i) We first consider the case where $1 \le i \le I_1 +1$, then
	\begin{align*}
	w_s & \le \sum_{t=s+1}^{T+1} \rho_{s, t-1}\\
	&= (I_1-i + 1) + \left( I_1 + \frac{\rho - \rho^{I_2+1}}{1-\rho} \right) \sum_{l=1}^{R-j} \rho^{I_2 l} + \sum_{l=1}^{I_2} \rho^{l}    \\
	&\le (I_1-i + 1)  + \left( I_1 + \frac{\rho - \rho^{I_2+1}}{1-\rho} \right) \frac{\rho^{I_2}}{1-\rho^{I_2}}+ \frac{\rho - \rho^{I_2+1}}{1-\rho}   \\
	& \le  \frac{I_1}{1-\rho^{I_2}} + \frac{\rho}{1-\rho} = K.
	\end{align*}
	(ii) Then consider the case where $I_1 + 1 \le i \le I$. If $R=j$, then $w_s = \sum_{l=1}^{I-i} \rho^{l} \le \frac{\rho}{1-\rho} \le K$. If $R \ge j + 1$, then
	\begin{align*}
	w_s & \le \sum_{t=s+1}^{T+1} \rho_{s, t-1}\\
	& = \rho^{I-i+1} \left( I_1 + \frac{\rho - \rho^{I_2+1}}{1-\rho} \right) \sum_{l=0}^{R-j-1} \rho^{I_2 l} + \sum_{l=1}^{I-i+1} \rho^{l}  \\
	& \le \frac{\rho^{I-i+1}}{1-\rho^{I_2}}  \left( I_1 + \frac{\rho - \rho^{I_2+1}}{1-\rho} \right)+ \frac{\rho - \rho^{I-i+2}}{1-\rho}  \\
	&= I_1\frac{\rho^{I-i+1}}{1-\rho^{I_2}} + \frac{\rho}{1-\rho} \\
	&\le \frac{I_1}{1-\rho^{I_2}} + \frac{\rho}{1-\rho} = K.
	\end{align*}
\end{enumerate}
\end{proof}

\subsection{Proof of Theorem~\ref{thm:scheme1}}

\begin{proof}
	Without loss of generality, we assume $T$ is a multiplier of $I$, i.e., $T = (R+1)I$ for some positive integer $R$.
	This assumption will only simplify our proof but will not change the conclusion.

	For $A_T$, by using~\eqref{eq:beta_u} in Lemma~\ref{lem:rho}, we have
	\begin{align*}
	A_T &=\frac{1}{T}\sum_{t=1}^{T} \sum_{s=1}^{t-1} \rho^2_{s, t-1}
	       = \frac{1}{(R+1)} \sum_{j=0}^{R}  \frac{1}{I} \sum_{t=jI+1}^{(j+1)I}  \rho^2_{s, t-1}
	       =  \frac{1}{(R+1)} \sum_{j=0}^{R}  \frac{1}{I} \beta_{j} \\
	      &\le \frac{1}{2I}\left( \frac{1+\rho^{2I_2}}{1-\rho^{2I_2}} I_1^2 + \frac{1+\rho^2}{1-\rho^2} I_1 \right)  + \frac{\rho^2}{1-\rho^2}.
	\end{align*}

	For $B_T$, by using the result about $\gamma_j$ in Lemma~\ref{lem:rho}, we have
	\begin{align*}
	 B_T &= \frac{1}{T} \sum_{t=1}^{T} \left(\sum_{s=1}^{t-1} \rho_{s, t-1} \right)^2
	 =\frac{1}{(R+1)} \sum_{j=0}^{R} \frac{1}{I} \sum_{t=jI+1}^{(j+1)I} \left(\sum_{s=1}^{t-1} \rho_{s, t-1} \right)^2   \\
	&=  \frac{1}{(R+1)} \sum_{j=0}^{R}  \frac{1}{I} \gamma_{j}
	\overset{(a)}{\le} K \frac{1}{(R+1)} \sum_{j=0}^{R} \frac{1}{I}  \alpha_j\\
	&\overset{(b)}{\le} K \min\bigg\{ K,  \frac{1}{2I}\left( \frac{1+\rho^{I_2}}{1-\rho^{I_2}} I_1^2 + \frac{1+\rho}{1-\rho} I_1 \right)  + \frac{\rho}{1-\rho} \bigg\}
	\end{align*}
	where (a) follows the fact that $\gamma_{j}  \le K \alpha_j$ and (b) follows the two bounds on $\alpha_j$ provided in Lemma~\ref{lem:rho}.

	For $C_T$, by using the results about $w_s$ and $K$ in Lemma~\ref{lem:rho}, we have
	\begin{align*}
	C_T &= \max_{s \in [T-1]} \sum_{t=s+1}^T  \rho_{s, t-1}  \left( \sum_{l=1}^{t-1}  \rho_{l, t-1} \right)\\
	&\le \max_{t \in T-1} \sum_{t=s+1}^T  \rho_{s, t-1} \left( \max_{l} \sum_{l=1}^{t-1}  \rho_{l, t-1} \right)\\
	&\le K  \max_{t \in T-1} \sum_{t=s+1}^T  \rho_{s, t-1} \le K^2.
	\end{align*}
\end{proof}

\section{Proof of Theorem~\ref{thm:scheme2}}
\label{append:scheme2}
In this section, we will give the convergence result of Theorem~\ref{thm:scheme2} which states that the convergence will be fastened if we use the decaying strategy ${\mathcal I}_T^2$.
Again, by using the framework introduced in Appendix~\ref{append:PD-SGD}, we only needs to give bounds for $A_T, B_T$ and $C_T$.
To that end, we need a modified version of Lemma~\ref{lem:rho} which reveals how the residual errors are accumulated for ${\mathcal I}_T^2$.

Recall that to define ${\mathcal I}_T^2$, we define an ancillary set
\[  {\mathcal I}(I_1, I_2, M) = \{t \in [M(I_1+I_2)]: t \ \text{mod} \ (I_1+I_2) \notin [I_1] \}, \]
and then recursively define ${\mathcal J}_0 = {\mathcal I}(I_1, I_2, M)$ and
\[ {\mathcal J}_j ={\mathcal I}\left( \bigg\lfloor \frac{I_1}{2^j} \bigg\rfloor , I_2, M\right) + \max({\mathcal J}_{j-1}), 1 \le j \le J \]
where $\max({\mathcal J}_{j-1})$ returns the maximum number collected in ${\mathcal J}_{j-1}$ and $J = \lceil \log_2 I_1 \rceil $.
Finally we set
\[  {\mathcal I}_T^2 = \cup_{j=0}^J {\mathcal J}_{j} \cup [\max({\mathcal J}_{J}):T].  \]
In short, we first run $M$ rounds of LD-SGD with parameters $I_1$ and $I_2$, then run another $M$ rounds of LD-SGD with parameters $\lfloor \frac{I_1}{2} \rfloor$ and $I_2$, and keep this process going on until we reach the $J + 1$ th run, where $I_1$ shrinks to zero and we only run D-SGD.

\begin{lem}
\label{lem:rho_strategy}
Recall $M$ is the decay interval, $T$ the total steps and $\rho_{s, t-1} = \| \mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}\|$ where $\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1}$ is defined in~\eqref{eq:Ph} with ${\bf W}_t$ given in~\eqref{eq:W}.
Let $I_1, I_2$ be the initialized communication parameters.
Assume $T \ge \max \max({\mathcal J}_J)$.
Then for LD-SGD with the decaying strategy, we have that
\begin{enumerate}
	\item $\frac{1}{T}\sum_{t=1}^T\sum_{s=1}^{t-1}\rho_{s, t-1} \le \frac{1}{T} \frac{I_1}{1-\rho^{I_2}} \rho^{T + I_2-\max({\mathcal J}_{J}) -1 } + (1-\frac{\max({\mathcal J}_{J})}{T}) \frac{\rho}{1-\rho}$;
	\item $\frac{1}{T}\sum_{t=1}^T\sum_{s=1}^{t-1}\rho_{s, t-1}^2 \le \frac{1}{T} \frac{I_1}{1-\rho^{2I_2}} \rho^{2(T + I_2-\max({\mathcal J}_{J}) -1)} + (1-\frac{\max({\mathcal J}_{J})}{T}) \frac{\rho^2}{1-\rho^2}$;
	\item 	For any $t \ge 1$, $\sum_{s=1}^{t-1}\rho_{s, t-1} \le K$ where $K = \frac{I_1}{1-\rho^{I_2}} + \frac{\rho}{1-\rho}$;
	\item 	For any $T> s \ge 1$, $\sum_{t=s+1}^{T} \rho_{s, t-1} \le K$.
\end{enumerate}

\end{lem}
\begin{proof}

We verify each inequality by directly computation:
\begin{enumerate}
\item
By exchanging the order of sum, we have
\begin{align*}
&\sum_{t=1}^T\sum_{s=1}^{t-1}\rho_{s, t-1}
= \sum_{s=1}^{T-1} \sum_{t=s}^{T-1} \rho_{s, t}
= \sum_{j=0}^{J} \sum_{s \in {\mathcal J}_j}  \sum_{t=s}^{T-1} \rho_{s, t} + \sum_{s = \max {\mathcal I} +1}^{T-1} \sum_{t=s}^{T-1} \rho_{s, t} \\
=&\sum_{j=0}^{J} \rho^{(J-j)MI_2} \sum_{s=0}^{M-1} \left(\bigg\lfloor \frac{I_1}{2^j} \bigg\rfloor \rho^{(M-s)I_2}
+ \rho^{(M-s-1)I_2} \sum_{l=1}^{I_2} \rho^l \right)\rho^{T-\max({\mathcal J}_{J}) -1} +
\sum_{s = \max {\mathcal I} +1}^{T-1} \sum_{t=s}^{T-1} \rho^{t-s+1}  \\
\le& \sum_{j=0}^{J} \rho^{(J-j)MI_2}  \left( \frac{I_1}{2^j} \frac{ \rho^{I_2} -  \rho^{(M+1)I_2}}{1- \rho^{I_2}} + \frac{\rho-\rho^{MI_2+1}}{1-\rho} \right)\rho^{T-\max({\mathcal J}_{J})-1}
+ \sum_{s = \max({\mathcal J}_{J}) +1}^{T-1} \frac{\rho}{1-\rho}\\
\le & \left( I_1 \frac{\rho^{I_2}}{1-\rho^{I_2}} + \frac{\rho}{1-\rho} \right) \rho^{T-\max {\mathcal I} -1}  + (T-\max({\mathcal J}_{J}) -1) \frac{\rho}{1-\rho}\\
\le &  \frac{I_1}{1-\rho^{I_2}} \rho^{T + I_2-\max({\mathcal J}_{J}) -1 } + (T-\max({\mathcal J}_{J})) \frac{\rho}{1-\rho}\\
\le &  \frac{I_1}{1-\rho^{I_2}} \rho^{T -\max({\mathcal J}_{J}) } + (T-\max({\mathcal J}_{J})) \frac{\rho}{1-\rho}.
\end{align*}
\item One can complete the proof by replacing $\rho$ with $\rho^2$ in the last argument.
\item If $t \in {\mathcal J}_j$, let $t_0 = \max({\mathcal J}_{j-1})$ (which is the largest element in ${\mathcal J}_{j-1}$), then we have
\begin{align*}
\sum_{s=1}^{t-1}\rho_{s, t-1}
&\overset{(a)}{=} \sum_{l=0}^{j-1}  \sum_{s \in {\mathcal J}_l}  \rho_{s, t_0} \rho_{t_0+1, t-1}  + \sum_{s=t_0+1}^{t-1} \rho_{s, t-1} \\
&= \rho_{t_0+1, t-1} \sum_{l=0}^{j-1} \rho^{lI_2M} \sum_{s=0}^{M-1} \rho^{sI_2} \left(  \bigg\lfloor \frac{I_1}{2^l} \bigg\rfloor + \frac{\rho - \rho^{I_2+1}}{1-\rho}\right) +  \sum_{s=t_0+1}^{t-1} \rho_{s, t-1}\\
&\overset{(b)}{\le} \rho_{t_0+1, t-1} \left(\frac{ 1- \rho^{kI_2M} }{1-\rho^{I_2}}I_1 + \frac{\rho(1- \rho^{kI_2M})}{1-\rho}\right) + \sum_{s=t_0+1}^{t-1} \rho_{s, t-1}\\
&\overset{(c)}{\le} \frac{I_1}{1-\rho^{I_2}} + \frac{\rho}{1-\rho} = K
\end{align*}
where (a) uses the fact that $\rho_{s, t-1} = \rho_{s, t_0} \rho_{t_0+1, t-1}$;
(b) follows from $\lfloor \frac{I_1}{2^l} \rfloor  \le I_1$;
to obtain (c), one can conduct a similar discussion like what we have done in~Lemma~\ref{lem:rho} by discussing whether $t$ locates in the local update phase or the communication phrase.
The case is more complicated since we should also think about which round $t$ locates.
No matter which case here, (c) always holds.
\item The idea here is very similar to the that for the latest statement.
If $s \ge \max({\mathcal J}_J)$, then $\sum_{t=s+1}^{T} \rho_{s, t-1} \le \sum_{t=1}^{\infty} \rho^t = \frac{\rho}{1-\rho} \le K$.
Otherwise, local updates are involved in.
Similarly, one can imitate what we have done in Lemma~\ref{lem:rho} by discussing which round and which phase $s$ locates in.
Actually, this bound is rather rough.
\end{enumerate}
\end{proof}

\begin{proof}
By Lemma~\ref{lem:rho_strategy}, we have
\begin{align*}
  A_T &= \frac{1}{T}\sum_{t=1}^T\sum_{s=1}^{t-1}\rho_{s, t-1}^2 \le \frac{1}{T} \frac{I_1}{1-\rho^{2I_2}} \rho^{2(T -\max({\mathcal J}_{J}))} + (1-\frac{\max({\mathcal J}_{J})}{T}) \frac{\rho^2}{1-\rho^2}\\
  B_T &=\frac{1}{T}\sum_{t=1}^T\left( \sum_{s=1}^{t-1}\rho_{s, t-1}\right)^2 \le \left( \max_{t \in [T]}  \sum_{s=1}^{t-1}\rho_{s, t-1}  \right) \cdot  \frac{1}{T}\sum_{t=1}^T\left( \sum_{s=1}^{t-1}\rho_{s, t-1}\right)
  \\
  &\le  K \left[\frac{1}{T} \frac{I_1}{1-\rho^{I_2}} \rho^{T -\max({\mathcal J}_{J})} + (1-\frac{\max({\mathcal J}_{J})}{T}) \frac{\rho}{1-\rho}\right]\\
  C_T & \le  \left( \max_{t \in [T]}  \sum_{s=1}^{t-1}\rho_{s, t-1}  \right) \cdot
     \left(   \max_{s \in [T-1]}  \sum_{t=s+1}^{T}\rho_{s, t-1}    \right)
     \le K^2.
\end{align*}
Then by combing Theorem~\ref{thm:PD-SGD}, we finish the proof of Theorem~\ref{thm:scheme2}.

\end{proof}

\section{Convergence of another update rule}
\label{append:another_update}

\subsection{Main result}
For completeness, in this section, we study another update rule in this section:
\begin{equation}
\label{eq:new_update}
{\bf X}_{t+1} = {\bf X}_t{\bf W}_t - \eta {\bf G}({\bf X}_t;\xi_t)
\end{equation}
where ${\bf W}_t$ is given in~\eqref{eq:W}. Since in this update rule, the stochastic gradient descent happens after each node communicates with its neighbors, we call this type of update as \textbf{communication-before}. By contrast, what we have analyzed in the body of this paper is termed as \textbf{communication-after}. A lot of previous efforts study the communication-before update rule, including~\cite{jiang2017collaborative,lian2017can}.
Fortunately, our framework is so powerful that the convergence result for this new update rule can be easily parallel.

\begin{theorem}[LD-SGD with any ${\mathcal I}_T$ and the update rule~\eqref{eq:new_update}]
	\label{thm:PD-SGD-}
	Let Assumption~\ref{asum:smooth},~\ref{asum:within-var},~\ref{asum:inter-var},~\ref{asum:W} hold and the constants $L$, $\kappa$, $\sigma$, and $\rho$ be defined therein.
	Let $\Delta = f(\overline{{ \boldsymbol x}}_0) - \min_{{ \boldsymbol x} } f ({ \boldsymbol x} )$ be the initial error. For any fixed $T$, define
	\begin{gather*}
		\widehat{A}_T =\frac{1}{T}\sum_{t=1}^{T} \sum_{s=1}^{t-1} \rho^2_{s+1, t-1}, \\
		\widehat{B}_T = \frac{1}{T} \sum_{t=1}^{T} \left(\sum_{s=1}^{t-1} \rho_{s+1, t-1} \right)^2, \\
		\widehat{C}_T = \max_{s \in [T-1]} \sum_{t=s+1}^T  \rho_{s+1, t-1}  \left( \sum_{l=1}^{t-1}  \rho_{l+1, t-1} \right).
	\end{gather*}
	If the learning rate $\eta$ is small enough such that
	\begin{equation}
	\eta \: \leq \: \min \bigg\{ \frac{1}{2L}, \; \frac{1}{4\sqrt{2}L\sqrt{\widehat{C}_{T}}} \bigg\} ,
	\end{equation}
	then
	\begin{equation}
	\frac{1}{T} \sum_{t=1}^{T} {\mathbb E} \big\|\nabla f (\overline{{ \boldsymbol x}}_t) \big\|^2
	\: \leq \:
	{\underbrace{\frac{2\Delta}{\eta T} + \frac{\eta L\sigma^2}{n}}_{\text{fully sync SGD}}}
	+
	{\underbrace{\vphantom{ \left(\frac{a^{0.3}}{b}\right) } 4\eta^2L^2(\widehat{A}_T \sigma^2 + \widehat{B}_{T}\kappa^2}_{ \text{residual error}})} .
	\end{equation}
\end{theorem}

\begin{remark}
Comparing the difference of results between Theorem~\ref{thm:PD-SGD} and Theorem~\ref{thm:PD-SGD-}, one can find that only the value of $A_T, B_T$ and $C_T$ have been modified.
In this way, one can parallel the conclusions derived for the update rule~\eqref{eq:pdsgd} to those with the update rule~\eqref{eq:new_update} by simply substituting $A_T, B_T$ and $C_T$ with $\widehat{A}_T, \widehat{B}_T$ and $\widehat{C}_T$.

Note that $\widehat{A}_T, \widehat{B}_T$ and $\widehat{C}_T$ is always no less than $A_T, B_T$ and $C_T$.
This indicators that the communication-after update rule~\eqref{eq:pdsgd} converges faster than the communication-before update rule~\eqref{eq:new_update}.
As an example, we also given a counterpart of Theorem~\ref{thm:scheme1} in the latter section.
\end{remark}

\subsection{Useful lemmas and missing proof}

\begin{lem}[Residual error decomposition]
\label{lem:residual-decom-2}
	Let ${\bf X}_1 = { \boldsymbol x}_1 {\bf 1}_n^\top \in {\mathbb R}^{d\times n}$ be the initialization, then for any $t \ge 2$,
	\begin{equation}
	\label{eq:decomposition-2}
	{\bf X}_t({\bf I}-{\bf Q})= - \eta \sum_{s=1}^{t-1} {\bf G}({\bf X}_s;\xi_s) \left(  \mbox{\boldmath$\Phi$\unboldmath}_{s+1, t-1} - {\bf Q} \right)
	\end{equation}
	where $\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} $ is already given in~\eqref{eq:Ph}.
\end{lem}

\begin{proof}
We still denote the gradient ${\bf G}({\bf X}_t; \xi_t)$ as ${\bf G}_t$. According to the update rule, we have
\begin{align*}
    {\bf X}_{t}({\bf I}_n-{\bf Q})&=({\bf X}_{t-1}{\bf W}_{t-1}-\eta {\bf G}_{t-1})({\bf I}_n-{\bf Q})\\
                 &\overset{(a)}{=} {\bf X}_{t-1}({\bf I}_n-{\bf Q}){\bf W}_{t-1}-\eta{\bf G}_{t-1}({\bf I}_n-Q)\\
                 &\overset{(b)}{=} {\bf X}_{t-l}({\bf I}_n-{\bf Q})\prod_{s=t-l}^{t-1}{\bf W}_{s}-\eta\sum_{s=t-l}^{t-1}{\bf G}_{s}(\mbox{\boldmath$\Phi$\unboldmath}_{s+1,t-1}-{\bf Q})\\
                 &\overset{(c)}{=}{\bf X}_{1}({\bf I}_n-{\bf Q})\mbox{\boldmath$\Phi$\unboldmath}_{1, t-1}-\eta\sum_{s=1}^{t-1}{\bf G}_{s}(\mbox{\boldmath$\Phi$\unboldmath}_{s+1,t-1}-{\bf Q})
\end{align*}
where $(a)$ follows from ${\bf W}_{t-1}{\bf Q}={\bf Q}{\bf W}_{t-1}$; (b) results by iteratively expanding the expression of ${\bf X}_{s}$ from $s=t-1$ to $s=t-l+1$ and plugging in the definition of $\mbox{\boldmath$\Phi$\unboldmath}_{s,t-1}$ in \eqref{eq:Ph}; (c) follows simply by setting $l=t-1$. Finally, the conclusion follows from the assumption ${\bf X}_{1}({\bf I}_n-{\bf Q})={\bf 0}$.
\end{proof}

\begin{lem}[Bound on residual errors]
	\label{lem:residual-bound-2}
	Let $\rho_{s, t-1} = \|\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1} - {\bf Q}\|$ where $\mbox{\boldmath$\Phi$\unboldmath}_{s, t-1}$ is defined in~\eqref{eq:Ph}. Then the residual error can be upper bounded, i.e., $V_t \le 2 \eta^2 U_t$ where
	\begin{equation*}
	U_t = \sigma^2  \sum_{s=1}^{t-1} \rho^2_{s+1, t-1}
	+  \left( \sum_{s=1}^{t-1}  \rho_{s+1, t-1} \right) \left(  \sum_{s=1}^{t-1} \rho_{s+1, t-1} \left( 8L^2 V_s  + 4 \kappa^2 + 4 {\mathbb E} \| \overline{\nabla f}({\bf X}_s)  \|^2 \right) \right).
	\end{equation*}
\end{lem}

\begin{proof}
The proof can be simply parallel by replacing $\rho_{s, t-1}$ with $\rho_{s+1, t-1}$ in Lemma~\ref{lem:residual-bound}.
\end{proof}

The next thing is to bound the average residual error, i.e., $\frac{1}{T}\sum_{t=1}^T V_t$.

\begin{lem}[Bound on average residual error]
	\label{lem:residual-average-2}
	For any fixed $T$, define
	\begin{equation}
		\label{eq:hatABC}
		\widehat{A}_T =\frac{1}{T}\sum_{t=1}^{T} \sum_{s=1}^{t-1} \rho^2_{s+1, t-1}, \quad
		\widehat{B}_T = \frac{1}{T} \sum_{t=1}^{T} \left(\sum_{s=1}^{t-1} \rho_{s+1, t-1} \right)^2, \quad
		\widehat{C}_T = \max_{s \in [T-1]} \sum_{t=s+1}^T  \rho_{s+1, t-1}  \left( \sum_{l=1}^{t-1}  \rho_{l+1, t-1} \right).
		\end{equation}
	Assuming the learning rate is so small that $16\eta^2L^2\widehat{C}_{T} < 1$, then
	\begin{equation}
	\frac{1}{T}\sum_{t=1}^T V_t \le  \frac{2\eta^2}{1-16\eta^2L^2\widehat{C}_T}\left[ \widehat{A}_T \sigma^2 + \widehat{B}_T  \kappa^2 + 4\widehat{C}_T \frac{1}{T}\sum_{t=1}^{T}  {\mathbb E} \| \overline{\nabla f}({\bf X}_t)  \|^2  \right]
	\end{equation}
\end{lem}
\begin{proof}
One can replace Lemma~\ref{lem:residual-bound} with Lemma~\ref{lem:residual-bound-2} in the proof of Lemma~\ref{lem:residual-average} to achieve the conclusion.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:PD-SGD-}]
	To prove Theorem~\ref{thm:PD-SGD-}, one can simply replace Lemma~\ref{lem:residual-average} with Lemma~\ref{lem:residual-average-2} in the proof of Appendix~\ref{append:main_proof}.
\end{proof}

\subsection{Example: Results of LD-SGD with ${\mathcal I}_T^1$ and the other update rule}
In this part, we are going to bound $\widehat{A}_T, \widehat{B}_T$ and $\widehat{C}_T$ when the update scheme is ${\mathcal I}_T^1$.
The result shown below shows the superiority of the original update~\eqref{eq:pdsgd}.

\begin{lem}[Manipulation on $\rho_{s+1,t-1}$]
	\label{lem:coro_rho_another}
	Noting that
	\begin{equation}
	\label{eq:rho_relation}
	\sum_{s=1}^{t-1}\rho_{s+1,t-1}=\sum_{s=2}^{t}\rho_{s,t-1}\le\sum_{s=1}^{t}\rho_{s,t-1}=\sum_{s=1}^{t-1}\rho_{s,t-1}+1,
	\end{equation}
	When ${\mathcal I}_T={\mathcal I}_T^1$, we can immediately deduce the following properties from Lemma~\ref{lem:rho} for $\rho_{s+1,t-1}$.
	\begin{enumerate}
	\item$\tilde{\alpha}_{j}=\sum_{jI+1}^{(j+1)I}\sum_{s=1}^{t-1}\rho_{s+1, t-1}\le\frac{1}{2}\left( \frac{1+\rho^{I_2}}{1-\rho^{I_2}} I_1^2 + \frac{1+\rho}{1-\rho} I_1 \right)  + I \frac{1}{1-\rho}$. \\
	\item $\tilde{\beta}_j = \sum_{t=jI+1}^{(j+1)I} \sum_{s=1}^{t-1}\rho_{s+1, t-1}^2\le\frac{1}{2}\left( \frac{1+\rho^{2I_2}}{1-\rho^{2I_2}} I_1^2 + \frac{1+\rho^2}{1-\rho^2} I_1 \right)  + I \frac{1}{1-\rho^2}$.\\
	\item Let $\tilde{K} = \frac{I_1}{1-\rho^{I_2}} + \frac{1}{1-\rho}=K+1$, then $\sum_{s=1}^{t-1}\rho_{s+1, t-1} \le \tilde{K}$ and $\tilde{\alpha}_{j} \le I \tilde{K}$.  \\
	\item  $\tilde{\gamma}_j = \sum_{t=jI+1}^{(j+1)I} (\sum_{s=1}^{t-1}\rho_{s+1, t-1})^2\le \tilde{K}\tilde{\alpha}_{j}$.\\
	\item If $T = (R+1)I$, we have $\tilde{w}_{s}=\sum_{t=s+1}^{T}\rho_{s+1,t-1}=1+\sum_{t=s+2}^{T}\rho_{s+1, t-1}=1+w_{s+1}\le 1+K=\tilde{K}$.
	\end{enumerate}
\end{lem}

\begin{theorem}[LD-SGD with ${\mathcal I}_T^1$ and the update rule~\eqref{eq:new_update}]
	\label{thm:scheme1-}
	When we set ${\mathcal I}_T = {\mathcal I}_T^1$ for LD-SGD with update rule~\eqref{eq:new_update}, under the same setting, Theorem~\ref{thm:PD-SGD-} holds with
	\begin{gather*}
	\widehat{A}_T \le \frac{1}{2I}\left( \frac{1+\rho^{2I_2}}{1-\rho^{2I_2}} I_1^2 + \frac{1+\rho^2}{1-\rho^2} I_1 \right)  +  \frac{1}{1-\rho^2}, \\
	\max \left\{  \widehat{B}_T, \widehat{C}_T \right\}\le \tilde{K}^2, \tilde{K}= \frac{I_1}{1 - \rho^{I_2}} + \frac{1}{1-\rho}.
	\end{gather*}
	Therefore, LD-SGD converges with ${\mathcal I}_T^1$ and the update rule~\eqref{eq:new_update}.
\end{theorem}

\end{appendix}

redpajama_set_name: RedPajamaArXiv