# A Stochastic Gradient Tracking Algorithm for Decentralized Optimization With
Inexact Communication

Suhail M. Shah∗ Raghu Bollapragada University of Texas at Austin.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Decentralized optimization is typically studied under the assumption of noise-
free transmission. However, real-world scenarios often involve the presence of
noise due to factors such as additive white Gaussian noise channels or
probabilistic quantization of transmitted data. These sources of noise have
the potential to degrade the performance of decentralized optimization
algorithms if not effectively addressed. In this paper, we focus on the noisy
communication setting and propose an algorithm that bridges the performance
gap caused by communication noise while also mitigating other challenges like
data heterogeneity. We establish theoretical results of the proposed algorithm
that quantify the effect of communication noise and gradient noise on the
performance of the algorithm. Notably, our algorithm achieves the optimal
convergence rate for minimizing strongly convex, smooth functions in the
context of inexact communication and stochastic gradients. Finally, we
illustrate the superior performance of the proposed algorithm compared to its
state-of-the-art counterparts on machine learning problems using MNIST and
CIFAR-10 datasets.

##  1 Introduction

The seminal works [1, 2] were one of the earliest works to formally study the
problem of decentralized decision making and optimization. These works helped
launch the field of decentralized optimization, where a connected network of
multi agents collectively optimize an objective function by only exchanging
information between neighboring agents in the network. Over the last four
decades, this area has intermittently experienced phases of extensive research
activity with the current iteration being mainly spurred by machine learning
(ML) based optimization on decentralized data among other applications. Adding
a distributed component to an optimization algorithm for ML naturally lends
itself to several advantages over its centralized counterparts such as data
privacy and fault tolerance while improving scalability with problem size.
Formally, the problem of decentralized optimization in its most succinct form
can be stated as:

$\displaystyle\min_{x_{i}\in\mathbb{R}^{d}}\,$
$\displaystyle\textbf{f}(\textbf{x})\stackrel{{\scriptstyle\rm
def}}{{=}}\frac{1}{n}\sum_{i=1}^{n}f_{i}(x_{i})$ s.t. $\displaystyle
x_{i}=x_{j},\,\forall\,i,j\in\\{1,2,\cdots,n\\}$ (1)

where $\textbf{x}:=(x_{1},\cdots,x_{n})\in\mathbb{R}^{nd}$ with $x_{i}$ being
the copy of the optimization variable held by the $i$th node (agent) of a
network and $f_{i}:\mathbb{R}^{d}\to\mathbb{R}$ is the expected value
$f_{i}(.)=\mathbb{E}_{\xi_{i}}\,[F_{i}(.,\xi_{i})]$ of the stochastic function
$F_{i}(.,\xi_{i}):\mathbb{R}^{d}\to\mathbb{R}$ private to node $i$. Problems
of this nature arise in several applications with a prominent example being
machine learning, where the $f_{i}$ is a function of the data held at node
$i$.

A key aspect of decentralized algorithms is the need for communication between
nodes to achieve consensus
($x_{i}=x_{j},\,\forall\,i,j\in[n]:=\\{1,2,\cdots,n\\}$). However, this
communication is typically not noise-free, and any form of inexactness in the
algorithm can potentially degrade its performance if not addressed properly.
Even fundamental algorithms like decentralized gradient descent (DGD) do not
possess convergence guarantees or assured performance in the presence of
inexact communication [3, Theorem III.8] or, Section IV, ibid. Therefore, it
is essential to develop a framework that incorporates inexact communication to
design algorithms that effectively mitigate its adverse effects.

Data heterogeneity poses another challenge in decentralized optimization where
the training data is decentralized over the nodes or generated on client
devices so that each node has only access to $f_{i}(\cdot)$. Fundamental
algorithms such as stochastic decentralized gradient descent (S-DGD), used to
solve (1) are adversely affected by data heterogeneity [4]. To overcome these
limitations, Gradient Tracking (GT) type methods [5, 6] have been developed
which communicate an additional vector that tracks the gradient of the global
objective function. However, any inexactness in the communication can again
severely degrade the overall performance [3, 7]. In fact, with quantization,
GT can empirically show divergent behaviour [3, Section IV].

In this paper we consider the question of whether the inadequacies in
performance resulting from inexact communication in decentralized algorithms
can be properly addressed while retaining the benefits such as achieving
consensus or removing data heterogeneity dependence. Specifically, our focus
is on designing and analyzing algorithms based on the GT strategy in the
setting where the information, which could be the current iterate or the
gradient tracking vector, is corrupted by additive zero-mean noise with finite
variance.

Table 1: Comparison of convergence rates for strongly convex, smooth functions with stochastic gradients/communication noise for related works.  Reference | Grad. Noise | Comm. Noise |  No. of iterations to $\epsilon$-acc.
---|---|---|---
[6, 8, 4] \- Gradient Tracking (GT) | ✗ | ✗ | $\mathcal{O}\Big{(}\frac{L}{\mu\tau}\log\frac{1}{\epsilon}\Big{)}$
[9] \- Stochastic DGD | ✓ | ✗ | $\mathcal{O}\Big{(}\frac{1}{n\mu}\frac{\sigma_{g}^{2}}{\epsilon}+\frac{\sqrt{L}}{\mu\tau}\frac{\sigma_{g}}{\sqrt{\epsilon}}+\frac{\sqrt{L}}{\mu\tau}\frac{\chi^{2}}{\sqrt{\epsilon}}+\frac{L}{\mu\tau}\log\frac{1}{\epsilon}\Big{)}$
[10, 4] - Stochastic GT | ✓ | ✗ | $\mathcal{O}\Big{(}\frac{1}{n\mu}\frac{\sigma_{g}^{2}}{\epsilon}+\frac{\sqrt{L}}{\mu\tau}\frac{\sigma_{g}}{\sqrt{\epsilon}}+\frac{L}{\mu\tau}\log\frac{1}{\epsilon}\Big{)}$
[11] \- QDGD | ✗ | ✓ | $\mathcal{O}\Big{(}\frac{L^{2}}{\mu^{2}\tau}\frac{n\chi^{2}}{\epsilon^{2}}+\frac{L^{2}}{\mu^{2}\tau}\frac{n\sigma_{c}^{2}}{\epsilon^{2}}\Big{)}$
[12] \- S-Near DGDt | ✓ | ✓ | Non convergent.
This work, (IC-GT) | ✓ | ✓ | $\mathcal{O}\Big{(}\frac{1}{n\mu}\frac{\sigma_{g}^{2}}{\epsilon}+\frac{\sqrt{L}}{\mu\tau}\frac{\sigma_{g}}{\sqrt{\epsilon}}+\frac{1}{\mu\tau}\frac{\sigma^{2}_{c}}{\epsilon}+\frac{L}{\mu\tau}\log\frac{1}{\epsilon}\Big{)}$

Notation: $\sigma^{2}_{g}$: Gradient noise Variance, $\sigma^{2}_{c}$:
Communication noise variance, $\chi^{2}$: Data heterogeneity constant
satisfying $n^{-1}\sum_{i=1}^{n}\|\nabla f_{i}(x^{*})-\nabla
f(x^{*})\|^{2}\leq\chi^{2}$ for optimal point $x^{*}$. $L,\mu,\tau,n$:
Smoothness constant, strong convexity parameter, constant depending on network
topology, total number of nodes. For S-Near DGD, $t$ denotes the number of
consensus steps during each iteration and convergence is inexact even with
$t\to\infty$. The convergence is to a neighbourhood of size
$\mathcal{O}\big{(}\tau^{2t}\chi^{2}+\frac{L^{2}}{\mu^{2}}\sigma^{2}_{c}\big{)}$.

###  1.1 Related Work

Several works explored the topic of inexact communication in the context of
decentralized optimization, including [13, 11, 14, 15, 16, 17, 12, 18, 19, 20,
21]. Notably, one of the earliest and significant works in this setting are
[22, 23]. The current work extends them in several ways, including the
utilization of GT to address data heterogeneity and the assumptions about the
underlying functions. These differences allow us to achieve superior
theoretical and empirical convergence properties compared to contemporary
works, as documented in Table 1 and discussed in Section 3.

Another related line of research to our work is that of decentralized
optimization with randomized compressed communication [24, 25, 26, 27]. These
works focus on iterate quantization for smooth and strongly convex
deterministic optimization problems using randomized compression operators.
However, there are significant distinctions between our work and these prior
works, including differences in the underlying assumptions. Specifically, the
algorithms proposed in the aforementioned works assume access to the
compression error vector, which is transmitted to the receiving node for error
compensation over a noiseless channel. Furthermore, the error variance is
assumed to be controllable ([24, Assumption 2]) with the convergence
performance being intricately linked to it([24, Theorem 1]). In our setting,
neither of these assumptions are applicable as they are violated in many
practical scenarios, as discussed in Section 2.

The benefits of using the GT strategy to address data heterogeneity have been
extensively studied in numerous works [6, 8, 4]. In the deterministic setting,
algorithms such as EXTRA [5] achieve linear convergence for strongly convex,
smooth functions. For the stochastic optimization setting (without
communication noise), [10, 4] demonstrate that GT based DGD is agnostic to the
data heterogeneity. Furthermore, variants of GT such as NEXT [28] or the D2
algorithm proposed in [29] have been shown to mitigate the effects of data
heterogeneity. Other works exploring the GT strategy in various contexts
include [8, 30, 6, 31, 32, 33, 34].

###  1.2 Contributions

The main contributions can be summarized as follows:

  * -

We propose and analyze a novel variant of the Gradient Tracking algorithm
called Inexact Communication based Gradient Tracking (IC-GT) to address the
challenges posed by communication noise and data heterogeneity. Unlike
previous approaches, our method not only retains the benefits of GT but also
effectively eliminates the negative impact of inexact communication on
algorithm performance through careful design interventions.

  * -

We show IC-GT can recover (upto logarithmic factors) the optimal convergence
rate requirements of $\mathcal{O}(1/\epsilon)$ iterations required to achieve
$\epsilon$-accuracy for stochastic optimization while removing the data
heterogeneity dependence even in the presence of communication noise. By
extending the theory for exact communication based decentralized optimization
[35, 4], our results improve upon the existing works which consider
communication and gradient noise under similar assumptions and achieve either
a worse convergence rate or inexact convergence (cf. Table 1).

  * -

To validate our theoretical results, we report experimental results that
compare IC-GT with similar methods like DGD [1], DIGGing[6] and EXTRA[5]. Our
experiments demonstrate the superior performance of IC-GT on logistic
regression and image recognition problems on well known datasets.

The paper is organized as follows. We introduce the notation that is used
through out the paper in the rest of this section. In Section 2, we describe
the problem formulation and in Section 3, we present the proposed algorithm
and its implementation. Section 4 provides the convergence analysis while
Section 5 presents the numerical evidence in its support. Future directions of
research and conclusions are listed in Section 6.

Notation:  We use $\mathbb{R}$ to denote the set of real numbers and
$\mathbb{N}$ to denote the set of all strictly positive integers. We use
$\mathbf{x}_{k}\in\mathbb{R}^{nd}$ to denote the stacked version of
$\\{x_{i,k}\\}_{i\in[n]}$, where $x_{i,k}\in\mathbb{R}^{d}$ is a column vector
which denotes the value of the objective variable held by node $i$ at
iteration $k$, i.e. $\mathbf{x}_{k}:=(x_{1,k},\cdots,x_{n,k})$. We define
$\bar{\textbf{{x}}}_{k}:=\frac{1}{n}(1_{n}1_{n}^{T}\otimes
I_{d})\mathbf{x}_{k}=\left(\frac{1}{n}\sum_{i=1}^{n}x_{i,k},\cdots,\frac{1}{n}\sum_{i=1}^{n}x_{i,k}\right)$,
where the column vector $1_{n}:=(1,\cdots,1)\in\mathbb{R}^{n}$ and
$I_{d}\in\mathbb{R}^{d\times d}$ being the identity matrix. The symbol
$\otimes$ is used to denote the Kronecker product between any two matrices
while $\|\cdot\|$ is understood to be the $\ell_{2}$-norm of a vector or a
matrix depending upon the argument. The $\ell_{2}$ inner product between any
two vectors is denoted using $\langle\cdot,\cdot\rangle$. The following
notation is used for the gradients,

$\nabla\textbf{f}(\mathbf{x}_{k}):=\left(\nabla f_{1}(x_{1,k}),\cdots,\nabla
f_{n}(x_{n,k})\right)\text{ and
}\nabla\textbf{f}(\bar{\textbf{x}}_{k}):=\left(\nabla
f_{1}(\bar{x}_{k}),\,\cdots\,,\nabla f_{n}(\bar{x}_{k})\right).$

We also define the matrices,

$\textbf{I}_{n}=I_{n}\otimes I_{d}\quad\text{ and
}\quad\bar{\textbf{I}}_{n}:=\textbf{I}_{n}-\frac{1_{n}1_{n}^{T}\otimes
I_{d}}{n}.$

Finally, for any two real valued functions $f(\cdot)$ and $g(\cdot)$,
$f(x)=\mathcal{O}(g(x))$ denotes the standard Big-O notation which implies
that there exists a finite constant $C>0$ and $x_{0}$ such that $|f(x)|\leq
Cg(x)$ for all $x\geq x_{0}$. We use $\mathcal{\tilde{O}}(\cdot)$ when
ignoring logarithmic factors.

##  2 Preliminaries

In this section, we provide preliminaries regarding the network and
communication model, and also state the assumptions that are used in the
paper.

The network is represented by a (undirected) graph
$\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$, where $\mathcal{V}$ denotes the
set of nodes and $\mathcal{E}$ represents the set of edges. We use the matrix
$Q=[q_{ij}]_{i,j\in[n]}\in\mathbb{R}^{n\times n}$ to denote the mixing matrix
(or consensus matrix) that captures the connectivity of the network. By this,
we mean that the entry $q_{ij}>0$ (assumed to be equal to $q_{ji}$), if there
is an edge between any two nodes $i,\,j\in\mathcal{V}$. We use
$\mathcal{N}(i)$ to denote the set of neighbours of $i$, i.e., the set
$j\in\mathcal{V}$ with $j\neq i$ for which $q_{ij}>0$. We make the following
assumption regarding the matrix $Q$.

######  Assumption 1 (Mixing matrix).

The mixing matrix $Q$ is symmetric and doubly stochastic. Furthermore, the
eigenvalues $\\{\lambda_{i}\\}_{i\in[n]}$ of $Q$ satisfy
$1=\lambda_{1}>\lambda_{2}\geq\cdots\geq\lambda_{n}>-1$.

######  Remark 1.

The symmetric and double stochasticity assumption of $Q$ is standard in
decentralized optimization along with $\lambda_{2}<1$ which implies that the
graph is connected. Therefore, it implies that $(Q\otimes I_{d})\textbf{x
}=\textbf{x }$ if and only if $x_{i}=x_{j}$ for all $i,j\in\mathcal{V}$.
Moreover, it also ensures that the spectral gap
$\delta(Q):=1-\max\\{|\lambda_{2}|,|\lambda_{n}|\\}$ is greater than zero
which in turn ensures that the consensus error decreases linearly after each
averaging step, i.e.,

$\left\|(Q\otimes I_{d})\textbf{x }-\left(\frac{1_{n}1_{n}^{T}}{n}\otimes
I_{d}\right)\textbf{x}\right\|^{2}\leq(1-\delta)^{2}\left\|\textbf{x}-\left(\frac{1_{n}1_{n}^{T}}{n}\otimes
I_{d}\right)\textbf{x}\right\|^{2}$ (2)

for any $\textbf{x}\in\mathbb{R}^{nd}$. For undirected graphs, this assumption
can be guaranteed by using the Metropolis weights([6, Section 3]).

We next describe the communication model considered in this work. We make the
assumption that when any node $i\in[n]$ sends a signal vector
$x_{i,k}\in\mathbb{R}^{d}$ to a neighboring node $j$ at iteration
$k\in\mathbb{N}$, node $j$ receives the vector
$\varphi_{c}(x_{i,k})\in\mathbb{R}^{d}$ instead of the original vector
$x_{i,k}$ , where $\varphi_{c}(\cdot):\mathbb{R}^{d}\to\mathbb{R}^{d}$
represents a random transformation given by

$\varphi_{c}(x_{i,k}):=x_{i,k}+\epsilon_{i,k,c}\,,$

where $\epsilon_{i,k,c}\in\mathbb{R}^{d}$ is a random vector. We emphasize
that we do not assume access to the values of $\epsilon_{i,k,c}$. We make the
following assumption concerning $\epsilon_{i,k,c}$.

######  Assumption 2 (Noisy signal transmission).

The random noisy vector $\epsilon_{i,k,c}$ is assumed to be zero mean
conditioned on $x_{k}$ with bounded variance for all $i\in[n]$ and
$k\in\mathbb{N}$, i.e.,

$\mathbb{E}\,[\epsilon_{i,k,c}|x_{i,k}]=0,\,\,\,\,\,\mathbb{E}\,[\|\epsilon_{i,k,c}\|^{2}]\leq\sigma^{2}_{c},$

for some finite $\sigma_{c}>0$.

We describe two important examples of $\varphi_{c}(\cdot)$ for which
Assumption 2 is satisfied.

Additive White Gaussian Noise channel (AWGN): The most common approach to
modeling an analog based communication channel between two nodes is through an
AWGN channel [36]. In this scenario, when a node transmits a signal
$y_{\text{tr}}\in\mathbb{R}$ to a neighboring node, the received signal at the
receiving node, denoted as $y_{\text{rc}}$, can be represented as

$y_{\text{rc}}=hy_{\text{tr}}+\epsilon_{c},$

where $h\in\mathbb{R}$ captures channel effects like fading [37], and
$\epsilon_{c}$ represents zero-mean Gaussian noise with variance
$\sigma_{c}^{2}$, independent of the transmitted signal $y_{\text{tr}}$.
Assuming that the receiving node possesses a prior estimate of $h$ [38,
Chapter 4], it can construct an estimate of the true signal
$\hat{y}_{\text{rc}}$ as,

$\hat{y}_{\text{rc}}=\frac{1}{h}y_{\text{rc}}=y_{\text{tr}}+\frac{\epsilon_{c}}{h}.$

Hence, in this scenario, we can express $\varphi_{c}(\cdot)$ as,

$\varphi_{c}(y_{\text{tr}})=y_{tr}+\frac{\epsilon_{c}}{h},$

implying Assumption 2 is satisfied since
$\mathbb{E}\,[\varphi_{c}(y_{\text{tr}})]=y_{\text{tr}}$ and
$\mathbb{E}\,[\|\varphi_{c}(y_{\text{tr}})-y_{\text{tr}}\|^{2}]\leq\sigma_{c}^{2}/h^{2}$.

Probabilistic Quantization: Another significant example of operator
$\varphi_{c}$ arises in the context of quantization with unbiased compression
operators. Specifically, consider a scalar $x\in\mathbb{R}$. The quantized
value $\varphi_{c}(x)$ can be determined based on the following rule:

$\varphi_{c}(x)=\begin{cases}\lfloor x\rfloor_{p}\text{ with probability
}(\lceil x\rceil_{p}-x)\Delta_{p}\\\ \lceil x\rceil_{p}\text{ with probability
}(x-\lfloor x\rfloor_{p})\Delta_{p}\end{cases}$ (3)

where $\lfloor x\rfloor_{p}$ and $\lceil x\rceil_{p}$ denote the operations of
rounding down and up to the nearest integer multiple of $\frac{1}{\Delta_{p}}$
respectively, and $\Delta_{p}$ is a positive integer. The operator
$\varphi_{c}$ defined in (3) satisfies $\mathbb{E}\,[\varphi_{c}(x)]=x$ and
$\mathbb{E}\,[|\varphi_{c}(x)-x|^{2}]\leq\tfrac{1}{4\Delta_{p}^{2}}$ as shown
in [39] implying Assumption 2 is satisfied.

We also make the following assumptions regarding the objective function.

######  Assumption 3 (Regularity and convexity).

Each local function $f_{i}$ is $L$-smooth and $\mu$-strongly convex.

######  Assumption 4 (Unbiased Gradient Samples).

Each node $i$ has access to conditionally unbiased, finite variance gradient
samples $\nabla F_{i}(x_{i,k},\xi_{k})$ of $\nabla f_{i}(x_{i,k})$ for any
given $x_{i,k}\in\mathbb{R}^{d},$ $k\in\mathbb{N}$. That is,

$\mathbb{E}_{\xi_{i,k}}\,[\nabla F_{i}(x_{i,k},\xi_{i,k})\,|\,x_{i,k}]=\nabla
f_{i}(x_{i,k})\text{ and }\mathbb{E}_{\xi_{i,k}}\,[\|\nabla
F_{i}(x_{i,k},\xi_{i,k})-\nabla f_{i}(x_{i,k})\|^{2}]\leq\sigma^{2}_{g}$

for some finite $\sigma_{g}>0$ with $\xi_{i,k}$ being assumed to be
independent of $\epsilon_{i,k,c}$.

######  Remark 2.

The finite variance assumption in Assumption 4 can be relaxed along two
possible lines with minor modifications to the convergence analysis. One
relaxation would be to allow the noise to grow with the gradient norm (cf.
Assumption 3b, [35]). The other possibility is to replace $\sigma^{2}$ with
$\sigma^{2}_{*}:=\frac{1}{n}\sum_{i=1}^{n}\|\nabla F(x^{*},\xi_{i})-\nabla
f(x^{*})\|^{2}$, the noise at the optimal point $x^{*}$, as in [40].

######  Remark 3.

The convergence analysis can also be extended to a non-convex setting by
modifying the measure of stationary to be the $\ell_{2}$-norm of the gradient.

##  3 The IC-GT method

In this section, we describe the proposed method that accounts for inexact
communication, referred to as Inexact Communication based Gradient Tracking
(IC-GT) designed to solve the problem (1). Algorithm 1 presents the pseudo
code of (IC-GT).

Algorithm 1 INEXACT COMMUNICATION based GRADIENT TRACKING (IC-GT)

1: Input Graph $\mathcal{G}(\mathcal{V},\mathcal{E})$; Matrix
$Q=[q_{ij}]_{i,j\in[n]}\in\mathbb{R}^{n\times n}$ ; Operator
$\varphi_{c}(\cdot)$; Noise attenuation parameter $\gamma>0$; Step size
parameter $\alpha>0$.

2: Initialization $x_{i,0}\in\mathbb{R}^{d},\,\forall i$; $y_{i,0}:=\nabla
F_{i}(x_{i,0},\xi_{i,0}),\,\forall i$.

3: while $k\geq 1$ in parallel: do

4: for all $i\in[n],$ do

5: $v_{i,k}=(1-\gamma)x_{i,k}+\gamma
q_{ii}x_{i,k}+\gamma\sum_{j\in\mathcal{N}(i)}q_{ij}\varphi_{c}(x_{j,k})\ $

6: $x_{i,k+1}=v_{i,k}-\alpha y_{i,k}$

7: $y_{i,k+1}=(1-\gamma)y_{i,k}+\gamma
q_{ii}y_{i,k}+\gamma\sum_{j\in\mathcal{N}(i)}q_{ij}\varphi_{c}(y_{j,k})+\nabla
F_{i}(x_{i,k+1},\xi_{i,k+1})-\nabla F_{i}(x_{i,k},\xi_{i,k})$

8: end for

9: $k\rightarrow k+1$

10: end while

To express IC-GT in matrix form, we introduce the matrices
$Q^{\prime}:=[q^{\prime}_{ij}]_{i,j\in[n]}$ and
$\hat{Q}:=[\hat{q}_{ij}]_{i,j\in[n]}$ defined as follows:

$\textbf{Q}^{\prime}\stackrel{{\scriptstyle\rm
def}}{{=}}\left(I_{n}-Q\right)\otimes
I_{d}\qquad\qquad\hat{\textbf{Q}}\stackrel{{\scriptstyle\rm
def}}{{=}}\left(Q-\text{diag}(Q)\right)\otimes I_{d},$ (4)

where $\text{diag}(Q)$ denotes the diagonal matrix with entries $q_{ij}$ for
$i=j$ and 0 otherwise. Using the communication model,
$\varphi_{c}(x_{j,k})=x_{j,k}+\epsilon_{j,k,c},$ we can express the iteration
for $v_{i,k}$ as follows:

$\displaystyle v_{i,k}$
$\displaystyle=\left(1-\gamma(1-q_{ii})\right)x_{i,k}+\gamma\sum_{j\in\mathcal{N}(i)}q_{ij}\varphi_{c}(x_{j,k})$
$\displaystyle=\left(x_{i,k}-\gamma(1-q_{ii}))x_{i,k}+\gamma\sum_{j\in\mathcal{N}(i)}q_{ij}x_{j,k}\right)+\gamma\sum_{j\in\mathcal{N}(i)}q_{ij}\epsilon_{j,k,c}.$

Performing a similar manipulation for the $y$ update, we can express IC-GT
using (4) as follows:

$\displaystyle\mathbf{v}_{k}$
$\displaystyle=(\textbf{I}_{n}-\gamma\textbf{Q}^{\prime})\mathbf{x}_{k}+\gamma\hat{\textbf{Q}}\bm{\epsilon}_{k,c}$
(5) $\displaystyle\mathbf{x}_{k+1}$
$\displaystyle=\mathbf{v}_{k}-\alpha\mathbf{y}_{k}$ (6)
$\displaystyle\mathbf{y}_{k+1}$
$\displaystyle=(\textbf{I}_{n}-\gamma\textbf{Q}^{\prime})\mathbf{y}_{k}+\nabla\textbf{F}(\mathbf{x}_{k+1},\mathbf{\bm{\xi}}_{k+1})-\nabla\mathbf{F}(\mathbf{x}_{k},\mathbf{\bm{\xi}}_{k})+\gamma\hat{\textbf{Q}}\hat{\bm{\epsilon}}_{k,c}$
(7)

where $\hat{\epsilon}_{i,k,c}:=\varphi_{c}(y_{i,k})-y_{i,k}$,
$\bm{\epsilon}_{k,c}:=\left(\epsilon_{1,k,c},\cdots,\epsilon_{n,k,c}\right)$
and $\nabla\textbf{F}(\mathbf{x}_{k},\mathbf{\bm{\xi}}_{k}):=\big{(}\nabla
F_{1}(x_{1,k},\xi_{1,k}),\cdots,$ $\nabla F_{n}(x_{n,k},\xi_{n,k})\big{)}$.

We next discuss the main modification made to the standard DGD algorithm [1]
utilized in IC-GT to better understand its communicating and computational
capabilities.

(i) Use of $\textbf{I}_{n}-\gamma\textbf{Q}^{\prime}$: In the context of IC-
GT, the weight matrix $\textbf{I}_{n}-\gamma\textbf{Q}^{\prime}$ is employed
instead of the typical Q used in DGD [1]. To illustrate its effectiveness in
mitigating communication noise, let us examine the sequence
$\\{\mathbf{x}_{k}\\}_{k\geq 0}$ generated according to the recursion:

$\displaystyle\mathbf{x}_{k}$
$\displaystyle=(\textbf{I}_{n}-\gamma\textbf{Q}^{\prime})\mathbf{x}_{k-1}+\gamma\hat{\textbf{Q}}\bm{\epsilon}_{k-1,c},$
(8)

where the noise term $\bm{\epsilon}_{k-1,c}$ satisfies Assumption 2. The
recursion in (8) can be interpreted as a distributed averaging algorithm using
the weight matrix $\textbf{I}_{n}-\gamma\textbf{Q}^{\prime}$. Specifically,
when $\gamma=1$ and $\bm{\epsilon}_{k-1,c}=0$, (8) reduces to the standard
distributed averaging algorithm [41]. Next, we consider the expression for the
averaged iterates $\bar{\mathbf{x}}_{k}$ obtained by multiplying (8) by
$\frac{1}{n}\left(1_{n}1_{n}^{T}\otimes I_{d}\right)$:

$\displaystyle\mathbf{\bar{x}}_{k}=\mathbf{\bar{x}}_{k-1}-\gamma\frac{1}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\hat{\textbf{Q}}\bm{\epsilon}_{k-1,c},$ (9)

where we used $\left(1_{n}^{T}\otimes
I_{d}\right)\left(\textbf{I}_{n}-\gamma\textbf{Q}^{\prime}\right)=(1^{T}_{n}\otimes
I_{d})$ from Assumption 1. Subtracting (9) from (8) and defining
$\tilde{\textbf{Q}}:=\left(\textbf{I}_{n}-n^{-1}1_{n}1^{T}_{n}\otimes
I_{d}\right)\hat{\textbf{Q}}$ and recalling
$\bar{\textbf{I}}_{n}:=\textbf{I}_{n}-\frac{1_{n}1_{n}^{T}\otimes I_{d}}{n}$,
we get,

$\displaystyle\mathbf{x}_{k}-\mathbf{\bar{x}}_{k}$
$\displaystyle=(\textbf{I}_{n}-\gamma\textbf{Q}^{\prime})(\mathbf{x}_{k-1}-\mathbf{\bar{x}}_{k-1})+\gamma\tilde{\textbf{Q}}\bm{\epsilon}_{k-1,c}$
$\displaystyle=(\textbf{I}_{n}-\gamma\textbf{Q}^{\prime})(\mathbf{x}_{k-1}-\mathbf{\bar{x}}_{k-1})+\gamma\tilde{\textbf{Q}}\bm{\epsilon}_{k-1,c}-\frac{1_{n}1_{n}^{T}\otimes
I_{d}}{n}(\mathbf{x}_{k-1}-\mathbf{\bar{x}}_{k-1})$
$\displaystyle=(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})(\mathbf{x}_{k-1}-\mathbf{\bar{x}}_{k-1})+\gamma\tilde{\textbf{Q}}\bm{\epsilon}_{k-1,c},$

where the second equality is due to $\frac{1_{n}1_{n}^{T}\otimes
I_{d}}{n}(\mathbf{x}_{k-1}-\mathbf{\bar{x}}_{k-1})=0$. Applying norms and
taking squares yields,

$\displaystyle\|\mathbf{x}_{k}-\mathbf{\bar{x}}_{k}\|^{2}$
$\displaystyle\leq\|\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime}\|^{2}\|\mathbf{x}_{k-1}-\mathbf{\bar{x}}_{k-1}\|^{2}+\gamma^{2}\|\tilde{\textbf{Q}}\bm{\epsilon}_{k-1,c}\|^{2}+2\gamma\left\langle(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})(\mathbf{x}_{k-1}-\bar{\textbf{x}}_{k-1}),\tilde{\textbf{Q}}\bm{\epsilon}_{k-1,c}\right\rangle.$

Using the conditional zero mean and finite variance assumption for
$\bm{\epsilon}_{k-1,c}$ (Assumption 2), we get,

$\displaystyle\mathbb{E}[\|\mathbf{x}_{k}-\mathbf{\bar{x}}_{k}\|^{2}]$
$\displaystyle\leq\left(1-\gamma(1-\lambda_{2})\right)^{2}\mathbb{E}[\|\mathbf{x}_{k-1}-\mathbf{\bar{x}}_{k-1}\|^{2}]+2n\gamma^{2}\sigma_{c}^{2},$

where we used $\|\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime}\|\leq
1-\gamma(1-\lambda_{2})$ (cf. (Proof.)) and $\|\tilde{\textbf{Q}}\|^{2}\leq
2$. Applying the above inequality repeatedly through iteration $k=0$ yields,

$\displaystyle\mathbb{E}[\|\mathbf{x}_{k}-\mathbf{\bar{x}}_{k}\|^{2}]$
$\displaystyle\leq\left(1-\gamma(1-\lambda_{2})\right)^{2k}\|\mathbf{x}_{0}-\mathbf{\bar{x}}_{0}\|^{2}+\frac{2n\gamma\sigma_{c}^{2}}{1-\lambda_{2}}.$
(10)

(10) unveils a fundamental trade-off between two crucial aspects: the rate of
decay of the consensus error and the mitigation of the influence exerted by
the communication noise variance. As the parameter $\gamma$ decreases, a
smaller final consensus error can be achieved. However, this improvement comes
at the expense of a slower convergence rate in reducing the consensus error.
In view of this trade-off, the parameter $\gamma$ is referred to as the ‘noise
attenuation’ parameter.

(ii) Use of Gradient Tracking: Another crucial feature of IC-GT is its ability
to track gradients while accommodating inexact communication through gradient
tracking. The inclusion of gradient tracking offers the advantage of making
the algorithm agnostic to data heterogeneity. To elaborate, the number of
iterations required to achieve $\epsilon$-accuracy using stochastic DGD
depends on $\mathcal{O}\left(\frac{\sqrt{L}\chi^{2}}{\sqrt{\epsilon}}\right)$
[35], where $\chi$ is a constant satisfies the inequality

$\frac{1}{n}\sum_{i=1}^{n}\|\nabla f_{i}(x^{*})-\nabla
f(x^{*})\|^{2}\leq\chi^{2},$

with $x^{*}$ denoting the optimal solution of (1). In contrast, IC-GT
eliminates the dependence on $\chi$ entirely and, moreover, recovers the
linear convergence rate in scenarios where the variances of both the gradient
and communication noise are zero.

##  4 Convergence Analysis

In this section, we establish theoretical convergence guarantees for the
proposed IC-GT algorithm. We build up to our main result through a series of
technical lemmas which we state next.

### Preliminaries

For the sake of brevity, we assume
$\bm{\epsilon}_{k,c}=\hat{\bm{\epsilon}}_{k,c}$ in (5)-(7) for all
$k\in\mathbb{N}$ without loss of generality. We begin by expressing the
algorithm in terms of the difference between the variables and their
corresponding averages, which we refer to as the consensus error. To denote
this, we adopt the notation $\Delta\textbf{z }:=\textbf{z}-\bar{\textbf{z}}$
for any variable $\textbf{z}\in\mathbb{R}^{nd}$, where $\bar{\textbf{z}}$
denotes the average, i.e.
$\bar{\textbf{z}}:=\Big{(}\frac{1_{n}1_{n}^{T}}{n}\otimes I_{d}\Big{)}z$. We
first establish a recursive relation for the consensus error.

######  Lemma 1.

_[ Recursive relation for consensus errors]_ Suppose
$\bm{\epsilon}_{k,c}=\hat{\bm{\epsilon}}_{k,c}$ in (5)-(7) for all
$k\in\mathbb{N}$. Then, the iterates generated by IC-GT satisfy the following
recursive relation:

$\Psi_{k}=\textbf{J}_{\gamma}\Psi_{k-1}+\alpha\textbf{E}_{k-1},$ (11)

where

$\Psi_{k}\stackrel{{\scriptstyle\rm
def}}{{=}}\begin{bmatrix}\Delta\mathbf{v}_{k}\\\ \Delta\mathbf{x}_{k}\\\
\alpha\Delta\mathbf{y}_{k}\end{bmatrix},\qquad\,\,\,\textbf{J}_{\gamma}\stackrel{{\scriptstyle\rm
def}}{{=}}\begin{bmatrix}\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime}&0&-(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})\\\
0&\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime}&-\bar{\textbf{I}}_{n}\\\
0&0&\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime}\end{bmatrix},$ (12)

and

$\textbf{E}_{k-1}\stackrel{{\scriptstyle\rm
def}}{{=}}\frac{\gamma}{\alpha}\begin{bmatrix}\tilde{\textbf{Q}}\bm{\epsilon}_{k,c}\\\
\tilde{\textbf{Q}}\bm{\epsilon}_{k-1,c}\\\
\alpha\tilde{\textbf{Q}}\bm{\epsilon}_{k-1,c}\end{bmatrix}+\begin{bmatrix}0\\\
0\\\
\bar{\textbf{I}}_{n}\left(\nabla\textbf{F}(\mathbf{x}_{k},\bm{\xi}_{k})-\nabla\textbf{F}(\mathbf{x}_{k-1},\bm{\xi}_{k-1})\right)\end{bmatrix}$

with $\bar{\textbf{I}}_{n}:=\left(I_{n}-\frac{1_{n}1_{n}^{T}}{n}\right)\otimes
I_{d}$, $\textbf{Q}^{\prime}\stackrel{{\scriptstyle\rm
def}}{{=}}(I_{n}-Q)\otimes I_{d}$, $\hat{\textbf{Q}}\stackrel{{\scriptstyle\rm
def}}{{=}}(Q-\text{diag}(Q))\otimes I_{d}$ and
$\tilde{\textbf{Q}}\stackrel{{\scriptstyle\rm
def}}{{=}}\bar{\textbf{I}}_{n}\hat{\textbf{Q}}$.

The proof of this lemma is provided in Appendix I. One of the challenges in
analyzing IC-GT is that the matrix $\textbf{J}_{\gamma}$ defined in (12) is
not necessarily a contractive matrix. In other words, the condition
$\|\textbf{J}_{\gamma}\|<1$ is not guaranteed to hold. However, the following
result demonstrates that despite this restriction, there exists a positive
integer $\tau$ such that $\|\textbf{J}_{\gamma}\|^{\tau}<1$.

######  Lemma 2.

_[ Strict contractive property for $\textbf{J}_{\gamma}$]_ Suppose Assumption
1 holds. For any given $\delta\in(0,1)$, $\gamma\in(0,1/4)$ and $\lambda_{2}$
associated with the matrix $Q$, suppose $\tau\in\mathbb{N}$ satisfies

$\tau\geq\left\lceil\frac{2}{\gamma(1-\lambda_{2})}\max\left\\{4\ln\left(\frac{2}{\gamma(1-\lambda_{2})}\right)\,,\,\left(\gamma(1-\lambda_{2})-\ln\frac{\sqrt{\delta}}{4}\right)\right\\}\right\rceil,$
(13)

where $\lceil\cdot\rceil$ denotes the ceiling function. Then,
$\|\textbf{J}^{\tau}_{\gamma}\|^{2}\leq\delta<1$, where
$\textbf{J}^{\tau}_{\gamma}:=\underbrace{\textbf{J}_{\gamma}\times\cdots\times\textbf{J}_{\gamma}}_{\tau\text{
times }}$.

The proof of this lemma is provided in Appendix II. The next result
establishes a descent relation for the consensus error
$\mathbb{E}\,[\|\Psi_{t+\tau}\|^{2}]$ in terms of
$\mathbb{E}[\|\Psi_{t}\|^{2}]$.

######  Lemma 3.

_[ Descent relation for consensus error, $\mathbb{E}[\|\Psi_{t}\|^{2}]\,$]_
Suppose Assumptions 1-4 hold and
$\bm{\epsilon}_{k,c}=\hat{\bm{\epsilon}}_{k,c}$ in (5)-(7) for all
$k\in\mathbb{N}$. If $\gamma$ and $\alpha$ satisfy (19), then, for a given
$0<\rho^{\prime}\leq 1/4$, there exists a $\tau\in\mathbb{N}$ such that the
following relations are satisfied for $t\geq\tau$:

$\displaystyle\mathbb{E}[\|\Psi_{t}\|^{2}]$
$\displaystyle\leq\rho^{\prime}\mathbb{E}[\|\Psi_{t-\tau}\|^{2}]+576\alpha^{2}\tau
L^{2}\sum_{i=t-\tau}^{t-1}\mathbb{E}[\|\Psi_{i}\|^{2}]+1344\alpha^{2}\tau\sum_{i=t-\tau}^{t-1}\mathbb{E}\left[\left\|\nabla\textbf{f}(\bar{\textbf{x}}_{i})-\nabla\textbf{f}(\textbf{x}^{*})\right\|^{2}\right]$
$\displaystyle\qquad+64\gamma^{2}\big{(}2+\alpha^{2}(\tau^{2}+1/2)+\alpha^{2}t\big{)}n\sigma_{c}^{2}\tau+196n(\tau+1)\alpha^{2}\sigma^{2}_{g}$
(14)

and for any $\ell<\tau$:

$\displaystyle\mathbb{E}[\|\Psi_{\ell}\|^{2}]$ $\displaystyle\leq
2(1+\tau^{2})\|\Psi_{0}\|^{2}+576\alpha^{2}\tau
L^{2}\sum_{i=0}^{\ell-1}\mathbb{E}[\|\Psi_{i}\|^{2}]+1344\alpha^{2}\tau\sum_{i=0}^{\ell-1}\mathbb{E}\left[\left\|\nabla\textbf{f}(\bar{\textbf{x}}_{i})-\nabla\textbf{f}(\textbf{x}^{*})\right\|^{2}\right]$
$\displaystyle\qquad+64\gamma^{2}\big{(}2+\alpha^{2}(\tau^{2}+1/2)+\alpha^{2}\ell\big{)}n\sigma_{c}^{2}\tau+196n(\tau+1)\alpha^{2}\sigma^{2}_{g}.$
(15)

The proof of this lemma is provided in Appendix III. We next prove an
auxiliary result that will be useful for bounding the consensus error.

######  Lemma 4.

Suppose the non-negative scalar sequences $\\{a_{t}\\}_{t\geq 0}$ and
$\\{e_{t}\\}_{t\geq 0}$ satisfy the following recursive relation for a fixed
$\tau\in\mathbb{N}$:

$\displaystyle a_{t}$
$\displaystyle\leq\begin{cases}\rho^{\prime}a_{t-\tau}+\frac{b}{\tau}\sum_{i=t-\tau}^{t-1}a_{i}+c\sum_{i=t-\tau}^{t-1}e_{i}+r&\textit{if
}t\geq\tau\vspace{1em}\\\
\rho^{\prime\prime}a_{0}+\frac{b}{\tau}\sum_{i=0}^{t-1}a_{i}+c\sum_{i=0}^{t-1}e_{i}+r&\textit{if
}t<\tau\end{cases}$ (16)

where $b,\,c,\,r,\,\rho^{\prime\prime}$ are non-negative constants satisfying
$b\leq\rho^{\prime}/4$ and $\rho^{\prime}\in\left(0,1/4\right]$. Then, for any
$t\in\mathbb{N}$,

$\displaystyle a_{t}$ $\displaystyle\leq
20\rho^{\prime\prime}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t}a_{0}+60c\sum_{i=0}^{t-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-i}e_{i}+\frac{26r}{\rho},$
(17)

where $\rho:=1-2\rho^{\prime}$.

The proof of this lemma is provided in Appendix IV. We are ready to state and
prove the main convergence result.

### Main Result

For convenience, we define $\Delta x^{*}_{k}$ as

$\displaystyle\Delta x^{*}_{k}\stackrel{{\scriptstyle\rm
def}}{{=}}\mathbb{E}\left[\|\bar{x}_{k}-x^{*}\|^{2}\right],\qquad\forall
k\in\mathbb{N}.$ (18)

where $x^{*}$ is the optimal solution of (1).

######  Theorem 5.

_[ Convergence rate of IC-GT]_ Suppose Assumptions 1-4 hold and
$\bm{\epsilon}_{k,c}=\hat{\bm{\epsilon}}_{k,c}$ in (5)-(7) for all
$k\in\mathbb{N}$. If

$\alpha\leq\min\left\\{1,\frac{1}{161280\tau L}\right\\}\quad\mbox{and}\quad
0<\gamma<1/4,$ (19)

where

$\tau=\left\lceil\tfrac{2}{\gamma(1-\lambda_{2})}\max\left\\{4\ln\left(\tfrac{2}{\gamma(1-\lambda_{2})}\right)\,,\,\gamma(1-\lambda_{2})+\ln
16\right\\}\right\rceil.$ (20)

Then, for any $T\in\mathbb{N}$, we have,

$\displaystyle\Delta x^{*}_{T}$
$\displaystyle\leq(1-\alpha\mu/4)^{T}\left(\Delta
x^{*}_{0}+\frac{800(1+\tau^{2})L}{n(1-\alpha\mu/4)\mu}\|\Psi_{0}\|^{2}\right)+\left(\frac{4\alpha}{\mu}+\frac{101920\,L(\tau+1)n\alpha^{2}}{\mu}\right)\frac{\sigma_{g}^{2}}{n}$
$\displaystyle+\left(\frac{4(1+2\mu^{-1}T\alpha)}{\mu}\frac{\gamma^{2}}{\alpha}+\frac{33280(2+\alpha^{2}(\tau^{2}+\frac{1}{2})+\alpha^{2}T)L}{\mu}n\tau\gamma^{2}\right)\frac{\sigma^{2}_{c}}{n}.$
(21)

We make the following remarks regrading Theorem 5.

######  Remark 4.

(Dependence of $\tau$ on network) The parameter $\tau$ depends on the network
connectivity $(\lambda_{2})$ and the noise attenuation parameter $\gamma$ (cf.
20) which highlights the role played by $\gamma$ in shaping the consensus
properties of IC-GT (cf. Lemma 3). From (20), we note that a smaller value of
$\gamma$ increases $\tau$ but reduces the impact of the communication noise
variance $\sigma^{2}_{c}$ in (5) which is reminiscent of the trade-off
discussed in Section 3.

######  Remark 5.

(Iteration complexity of IC-GT) (19) and (20) suggest that the choices of the
step size $\alpha$ and the noise attenuation parameter $\gamma$ are inherently
connected. Using (20) in (19), we have the following relation:

$\frac{\alpha}{\gamma}=\tilde{\mathcal{O}}\left(\frac{1-\lambda_{2}}{L}\right)$
(22)

To calculate the number of iterations $T$ required to reach
$\epsilon$-accuracy, we note that the contribution of the gradient noise terms
in (5) is given by

$\mathcal{O}\big{(}(\alpha+n\alpha^{2})\sigma_{g}^{2}/n\big{)}=\mathcal{O}\big{(}\alpha\sigma_{g}^{2}/n\big{)}\qquad\text{if
}\alpha\leq 1/n$ (23)

while the contribution of the communication noise terms in (5) is given by:

$\displaystyle\mathcal{O}\Bigg{(}\left(\frac{(1+T\alpha)\gamma^{2}}{\alpha}+(\alpha^{2}\tau^{2}+\alpha^{2}T)n\tau\gamma^{2}\right)\frac{\sigma_{c}^{2}}{n}\Bigg{)}$
$\displaystyle=\mathcal{\tilde{O}}\Bigg{(}\left(\frac{(1+T\alpha)\gamma^{2}}{\alpha}+\frac{n\alpha^{2}}{\gamma}+n\alpha^{2}\gamma
T\right)\frac{\sigma_{c}^{2}}{n}\Bigg{)},$ (24)

where we used $\tau=\mathcal{\tilde{O}}(1/\gamma)$ and ignored the dependency
on other problem parameters. If we set $\gamma=\tilde{\mathcal{O}}(\alpha)$
such that (22) is satisfied, the above bound further simplifies to

$\mathcal{\tilde{O}}\Bigg{(}\left(\frac{(1+T\alpha)\gamma^{2}}{\alpha}+\frac{n\alpha^{2}}{\gamma}+n\alpha^{2}\gamma
T\right)\frac{\sigma_{c}^{2}}{n}\Bigg{)}=\mathcal{\tilde{O}}\left(\left((1+T\alpha)\alpha+n\alpha+n\alpha^{3}T\right)\frac{\sigma_{c}^{2}}{n}\right)$

For any given $\epsilon>0$, we can set $\alpha=\epsilon$ implying that
$T=\mathcal{\tilde{O}}(\epsilon^{-1})$ iterations are required to achieve the
specified $\epsilon$-accuracy.

######  Remark 6.

($\mathbf{\sigma_{c}^{2}=0,\,\sigma_{g}^{2}=0}$ and
$\mathbf{\sigma_{c}^{2}=0,\,\sigma_{g}^{2}>0}$): In the absence of
communication or gradient approximation errors
($\sigma_{c}^{2}=0,\,\sigma_{g}^{2}=0$), we can achieve the deterministic
linear convergence rate of the gradient tracking algorithm [6]. Referring to
equation (5), we obtain the following inequality:

$\Delta x^{*}_{T}\leq(1-\alpha\mu/4)^{T}\left(\Delta
x^{*}_{0}+\frac{800(1+\tau^{2})L}{n(1-\alpha\mu/4)\mu}\|\Psi_{0}\|^{2}\right)$

The case $\sigma_{c}^{2}=0,\,\sigma_{g}^{2}>0$ considers stochastic
decentralized optimization with no communication noise. For this scenario,
with a constant $\alpha>0$, we have linear convergence to a neighbourhood of
size $\mathcal{O}\big{(}(\alpha^{2}n+\alpha)\sigma_{g}^{2}/n\big{)}$ [10]. A
point to be remarked here is that IC-GT not only removes the data
heterogeneity terms which arise in the convergence bound for DGD (cf. Table 1)
but also makes sure that the variance scales linearly with the number of nodes
provided $\alpha\leq 1/n$ (cf. (23)).

######  Remark 7.

(Consensus Error): We can establish convergence error bounds for the expected
consensus error $\mathbb{E}[\|\Psi_{k}\|^{2}]$ by combining the results of
Lemma 3 and Theorem 5. However, for brevity, we omit the explicit presentation
of these results as they are of the same order as the results for $\Delta
x^{*}_{T}$.

#### Proof of Theorem 5

Using (5) and recalling that $\mathbf{\bar{x}}:=\frac{(1_{n}1_{n}^{T})\otimes
I_{d}}{n}\mathbf{x}$, the recursion for $\mathbf{\bar{x}}_{k}$ can be
expressed as

$\displaystyle\mathbf{\bar{x}}_{k+1}$
$\displaystyle=\bar{\textbf{v}}_{k}-\alpha\bar{\textbf{y}}_{k}$
$\displaystyle=\mathbf{\bar{x}}_{k}+\gamma\bar{\bm{\epsilon}}_{k,c}-\alpha\bar{\textbf{y}}_{k},$
(25)

where $\bar{\bm{\epsilon}}_{k,c}:=\frac{1}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\hat{\textbf{Q}}\bm{\epsilon}_{k,c}$ and the last equality is due
to
$\bar{\textbf{v}}_{k}=\bar{\mathbf{x}}_{k}+\gamma\bar{\bm{\epsilon}}_{k,c}$.
Similarly, the recursion for
$\bar{\mathbf{y}}_{k}:=\frac{1}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}y_{k}$ can be given as,

$\bar{\mathbf{y}}_{k}=\bar{\mathbf{y}}_{k-1}+\frac{1}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\big{(}\nabla\textbf{F}(\mathbf{x}_{k},\bm{\xi}_{k})-\nabla\textbf{F}(\mathbf{x}_{k-1},\bm{\xi}_{k-1})\big{)}+\gamma\bar{\bm{\epsilon}}_{k-1,c}.$

Taking telescopic sum from $0$ to $k$ leads to the following recursion:

$\bar{\mathbf{y}}_{k}=\frac{1}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\nabla\textbf{F}(\mathbf{x}_{k},\bm{\xi}_{k})+\gamma\sum_{j=1}^{k}\bar{\bm{\epsilon}}_{j-1,c}$
(26)

since $\bar{\mathbf{y}}_{0}=\frac{1}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\nabla\textbf{F}(\mathbf{x}_{0},\bm{\xi}_{0})$. Plugging (26) in
(4), we get,

$\displaystyle\mathbf{\bar{x}}_{k+1}$
$\displaystyle=\mathbf{\bar{x}}_{k}+\gamma\bar{\bm{\epsilon}}_{k,c}-\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\nabla\textbf{F}(\mathbf{x}_{k},\bm{\xi}_{k})-\gamma\alpha\sum_{j=0}^{k-1}\bar{\bm{\epsilon}}_{j,c}$
$\displaystyle=\bar{\textbf{x}}_{k}-\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\nabla\textbf{f}(\mathbf{x}_{k})+\gamma\left(\bar{\bm{\epsilon}}_{k,c}-\alpha\sum_{j=0}^{k-1}\bar{\bm{\epsilon}}_{j,c}\right)+\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\Big{(}\nabla\textbf{f}(\mathbf{x}_{k})-\nabla\textbf{
F}(\mathbf{x}_{k},\bm{\xi}_{k})\Big{)}$
$\displaystyle=\bar{\textbf{x}}_{k}-\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\nabla\textbf{f}(\mathbf{x}_{k})+\underbrace{\alpha\bm{\epsilon}_{k,g}+\gamma\bar{\bm{\epsilon}}_{k,c}}_{\delta_{k}}-\alpha\gamma\sum_{j=0}^{k-1}\bar{\bm{\epsilon}}_{j,c}$
(27)

where $\bm{\epsilon}_{k,g}$ is defined to be
$\bm{\epsilon}_{k,g}:=\frac{1}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\Big{(}\nabla\textbf{f}(\mathbf{x}_{k})-\nabla\textbf{F}(\mathbf{x}_{k},\bm{\xi}_{k})\Big{)}$
with $\mathbb{E}\,[\bm{\epsilon}_{k,g}|\mathbf{x}_{k}]=0$ and
$\mathbb{E}[\|\bm{\epsilon}_{k,g}\|^{2}]\leq\sigma_{g}^{2}$ from Assumption 4.
Now, let $\mathcal{F}_{k}\stackrel{{\scriptstyle\rm
def}}{{=}}\sigma(\mathbf{x}_{0},\bm{\xi}_{0},\bm{\epsilon}_{0,c},\cdots,\bm{\xi}_{k-1},\bm{\epsilon}_{k-1,c})$
be the sigma algebra generated by the random variables up to iteration $k$.
Then, for any constant $\beta>0$, we have,

$\displaystyle\mathbb{E}[\|\bar{\mathbf{x}}_{k+1}-\mathbf{x}^{*}\|^{2}|\mathcal{F}_{k}]$
$\displaystyle~{}~{}~{}~{}~{}\leq(1+\beta)\mathbb{E}[\|\bar{\mathbf{x}}_{k}-\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\nabla\textbf{f}(\mathbf{x}_{k})-\mathbf{x}^{*}+\delta_{k}\|^{2}|\mathcal{F}_{k}]+(1+\beta^{-1})\alpha^{2}\gamma^{2}\mathbb{E}\left[\left\|\sum_{j=0}^{k-1}\bar{\bm{\epsilon}}_{j,c}\right\|^{2}\Big{|}\mathcal{F}_{k}\right]$
$\displaystyle~{}~{}~{}~{}~{}=(1+\beta)\|\bar{\mathbf{x}}_{k}-\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\nabla\textbf{f}(\mathbf{x}_{k})-\mathbf{x}^{*}\|^{2}$
$\displaystyle~{}~{}~{}~{}~{}\qquad+(1+\beta)\mathbb{E}[\|\delta_{k}\|^{2}|\mathcal{F}_{k}]+(1+\beta^{-1})\alpha^{2}\gamma^{2}\mathbb{E}\left[\left\|\sum_{j=0}^{k-1}\bar{\bm{\epsilon}}_{j,c}\right\|^{2}\Big{|}\mathcal{F}_{k}\right],$
(28)

where the equality is due to $\mathbb{E}[\delta_{k}|\mathcal{F}_{k}]=0$ from
Assumption 3. From Assumptions 2 and 4, we have,

$\mathbb{E}[\|\delta_{k}\|^{2}]=\mathbb{E}[\left\|\alpha\bm{\epsilon}_{k,g}+\gamma\bar{\bm{\epsilon}}_{k,c}\right\|^{2}]\leq\alpha^{2}\sigma_{g}^{2}+\gamma^{2}\sigma^{2}_{c},$
(29)

where we have used
$\mathbb{E}[\langle\bm{\epsilon}_{k,g},\bar{\bm{\epsilon}}_{k,c}\rangle]=0$.
Furthermore, we have,

$\displaystyle\mathbb{E}\left[\left\|\sum_{j=0}^{k-1}\bar{\bm{\epsilon}}_{j,c}\right\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{j=0}^{k-1}\left\|\bar{\bm{\epsilon}}_{j,c}\right\|^{2}\right]+\sum_{1\leq
p,p^{\prime}\leq
k-1}\mathbb{E}\left[\langle\bar{\bm{\epsilon}}_{p,c},\bar{\bm{\epsilon}}_{p^{\prime},c}\rangle\right]\leq\sum_{j=0}^{k-1}\sigma_{c}^{2}=k\sigma_{c}^{2},$
(30)

where we use
$\mathbb{E}[\langle\bar{\bm{\epsilon}}_{p,c},\bar{\bm{\epsilon}}_{p^{\prime},c}\rangle]=\mathbb{E}[\mathbb{E}\left[\langle\bar{\bm{\epsilon}}_{p,c},\bar{\bm{\epsilon}}_{p^{\prime},c}\rangle|\mathcal{F}_{p^{\prime}}\right]]=0$
for $p<p^{\prime}$. Taking full expectations in (4), it then follows that,

$\mathbb{E}[\|\bar{\mathbf{x}}_{k+1}-\mathbf{x}^{*}\|^{2}]\leq(1+\beta)\mathbb{E}\left[\left\|\bar{\mathbf{x}}_{k}-\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\nabla\textbf{f}(\mathbf{x}_{k})-\mathbf{x}^{*}\right\|^{2}\right]\\\
+\big{(}(1+\beta)(\gamma^{2}\sigma_{c}^{2}+\alpha^{2}\sigma_{g}^{2})+k(1+\beta^{-1})\alpha^{2}\gamma^{2}\sigma^{2}_{c}\big{)}.$

where we used (29) to get the inequality. We note that since
$\|\bar{\mathbf{x}}_{k+1}-\mathbf{x}^{*}\|^{2}=\big{\|}\frac{(11^{T})\otimes
I_{d}}{n}(\textbf{x}_{k+1}-\textbf{x}^{*})\big{\|}^{2}=n\|\bar{x}_{k+1}-x^{*}\|^{2}$,
the above inequality leads to,

$\mathbb{E}\left[\|\bar{x}_{k+1}-x^{*}\|^{2}\right]\leq(1+\beta)\mathbb{E}\left[\left\|\bar{x}_{k}-\frac{\alpha}{n}\sum_{i=1}^{n}\nabla
f_{i}(x_{i,k})-x^{*}\right\|^{2}\right]\\\
+n^{-1}\big{(}(1+\beta)(\gamma^{2}\sigma_{c}^{2}+\alpha^{2}\sigma_{g}^{2})+k(1+\beta^{-1})\alpha^{2}\gamma^{2}\sigma^{2}_{c}\big{)}.$
(31)

Considering the first term on the right hand side of (31), we have,

$\displaystyle\Big{\|}\bar{x}_{k}-\frac{\alpha}{n}\sum_{i=1}^{n}\nabla
f_{i}(x_{i,k})-x^{*}\Big{\|}^{2}$
$\displaystyle=\|\bar{x}_{k}-x^{*}\|^{2}-\frac{2\alpha}{n}\left\langle\sum_{i=1}^{n}\nabla
f_{i}(x_{i,k}),\bar{x}_{k}-x^{*}\right\rangle+\alpha^{2}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(x_{i,k})\Big{\|}^{2}.$ (32)

The second term on the right hand side of (32) can be bounded as

$\displaystyle\langle\sum_{i=1}^{n}\nabla
f_{i}(x_{i,k}),\bar{x}_{k}-x^{*}\rangle$
$\displaystyle=\langle\sum_{i=1}^{n}\nabla
f_{i}(x_{i,k}),\bar{x}_{k}-x_{i,k}\rangle+\langle\sum_{i=1}^{n}\nabla
f_{i}(x_{i,k}),x_{i,k}-x^{*}\rangle$
$\displaystyle\geq\sum_{i=1}^{n}\Big{[}f_{i}(\bar{x}_{k})-f_{i}(x_{i,k})-\frac{L}{2}\|\bar{x}_{k}-x_{i,k}\|^{2}+f_{i}(x_{i,k})-f_{i}(x^{*})+\frac{\mu}{2}\|x_{i,k}-x^{*}\|^{2}\Big{]}$
$\displaystyle\geq\sum_{i=1}^{n}\Big{[}f_{i}(\bar{x}_{k})-f_{i}(x^{*})-\frac{L+\mu}{2}\|\bar{x}_{k}-x_{i,k}\|^{2}+\frac{\mu}{4}\|\bar{x}_{k}-x^{*}\|^{2}\Big{]},$
(33)

where the second inequality is due to Assumption 3 and the last inequality is
due to the inequality $\|\bar{x}_{k}-x^{*}\|^{2}\leq
2\|\bar{x}_{k}-x_{i,k}\|^{2}+2\|x_{i,k}-x^{*}\|^{2}$. The last term on the
right hand side of (32) can be bounded as

$\displaystyle\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(x_{i,k})\Big{\|}^{2}$
$\displaystyle=\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(x_{i,k})-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(\bar{x}_{k})+\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(\bar{x}_{k})-\frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(x^{*})\Big{\|}^{2}$
$\displaystyle\leq\frac{2L^{2}}{n}\sum_{i=1}^{n}\|\bar{x}_{k}-x_{i,k}\|^{2}+\frac{4L}{n}\sum_{i=1}^{n}(f_{i}(\bar{x}_{k})-f_{i}(x^{*})),$
(34)

where in the second summation, we used the fact that $\|\nabla
f_{i}(\bar{x}_{k})-\nabla f_{i}(x^{*})\|^{2}\leq
2L(f_{i}(\bar{x}_{k})-f_{i}(x^{*}))$ by Assumption 3 [42, Theorem 2.1.5].
Using (4) and (4) in (32) along with $\alpha<1/4L$, we have,

$\displaystyle\left\|\bar{x}_{k+1}-x^{*}\right\|^{2}$
$\displaystyle\leq(1-\alpha\mu/2)\|\bar{x}_{k}-x^{*}\|^{2}-\frac{\alpha}{n}\big{(}\sum_{i=1}^{n}f_{i}(\bar{x}_{k})-f_{i}(x^{*})\big{)}+\frac{(3L/2+\mu)\alpha}{n}\sum_{i=1}^{n}\|\bar{x}_{k}-x_{i,k}\|^{2}$
$\displaystyle\leq(1-\alpha\mu/2)\|\bar{x}_{k}-x^{*}\|^{2}-\alpha\left(\textbf{f}(\bar{\textbf{x}}_{k})-\textbf{f}(\textbf{x}^{*})\right)+{\color[rgb]{0,0,0}\frac{5\alpha
L}{2n}}\|\Psi_{k}\|^{2},$ (35)

where the last inequality is due to
$\|\Delta\textbf{x}_{k}\|^{2}\leq\|\Psi_{k}\|^{2}$. Using (4) in (31), we get,

$\displaystyle\mathbb{E}[\|\bar{x}_{k+1}-x^{*}\|^{2}]$
$\displaystyle\leq(1+\beta)\Bigg{\\{}(1-\alpha\mu/2)\mathbb{E}[\|\bar{x}_{k}-x^{*}\|^{2}]-\alpha\left(\mathbb{E}[\textbf{f}(\bar{\textbf{x}}_{k})]-\textbf{f}(\textbf{x}^{*})\right)$
$\displaystyle\qquad+{\color[rgb]{0,0,0}\frac{5\alpha
L}{2n}}\mathbb{E}[\|\Psi_{k}\|^{2}]\Bigg{\\}}+\frac{1}{n}\big{(}(1+\beta)(\gamma^{2}\sigma_{c}^{2}+\alpha^{2}\sigma_{g}^{2})+k(1+\beta^{-1})\alpha^{2}\gamma^{2}\sigma^{2}_{c}\big{)}.$

Set $\beta\stackrel{{\scriptstyle\rm
def}}{{=}}\frac{\alpha\mu}{4(1-\frac{\alpha\mu}{2})}$. We note that
$(1+\beta^{-1})\leq 4/\alpha\mu$ and
$(1+\beta)=\frac{(1-\alpha\mu/4)}{(1-\alpha\mu/2)}$ with $1\leq(1+\beta)\leq
2$. Then, we have,

$\displaystyle\mathbb{E}\left[\|\bar{x}_{k+1}-x^{*}\|^{2}\right]$
$\displaystyle\leq\Big{\\{}(1-\alpha\mu/4)\mathbb{E}\left[\|\bar{x}_{k}-x^{*}\|^{2}\right]-\alpha\left(\mathbb{E}[\textbf{f}(\bar{\textbf{x}}_{k})]-\textbf{f}(\textbf{x}^{*})\right)$
$\displaystyle\qquad+\frac{5\alpha
L}{n}\mathbb{E}[\|\Psi_{k}\|^{2}]\Big{\\}}+\frac{1}{n}\big{(}(2+4\mu^{-1}k\alpha)\gamma^{2}\sigma^{2}_{c}+2\alpha^{2}\sigma_{g}^{2}\big{)}.$
(36)

Multiplying both sides of 4 by $w_{k+1}\stackrel{{\scriptstyle\rm
def}}{{=}}(1-\alpha\mu/4)^{-(k+1)}$, we have,

$\displaystyle w_{k+1}\Delta x^{*}_{k+1}$
$\displaystyle\leq(1-\alpha\mu/4)w_{k+1}\Delta x^{*}_{k}+\frac{5\alpha
L}{n}w_{k+1}\mathbb{E}[\|\Psi_{k}\|^{2}]$ $\displaystyle\qquad-\alpha
w_{k+1}(\mathbb{E}[\textbf{f}(\mathbf{\bar{x}}_{k})]-\textbf{f}(\mathbf{x}^{*}))+\frac{w_{k+1}}{n}\big{(}\gamma^{2}(2+4k\mu^{-1}\alpha)\sigma^{2}_{c}+2\alpha^{2}\sigma_{g}^{2}\big{)}.$

Rearranging the terms, we get,

$\displaystyle 0$ $\displaystyle\leq w_{k}\Delta x^{*}_{k}-w_{k+1}\Delta
x^{*}_{k+1}+\frac{5\alpha L}{n}w_{k+1}\mathbb{E}[\|\Psi_{k}\|^{2}]$
$\displaystyle\qquad-\alpha
w_{k+1}(\mathbb{E}\,[\textbf{f}(\mathbf{\bar{x}}_{k})]-\textbf{f}(\mathbf{x}^{*}))+\frac{w_{k+1}}{n}\big{(}\gamma^{2}(2+4k\mu^{-1}\alpha)\sigma^{2}_{c}+2\alpha^{2}\sigma_{g}^{2}\big{)}.$

Summing the above inequality from $k=0$ to $T-1$, we get,

$\displaystyle w_{T}\Delta x^{*}_{T}$ $\displaystyle\leq w_{0}\Delta
x^{*}_{0}+\frac{1}{n}\big{(}\gamma^{2}(2+4T\mu^{-1}\alpha)\sigma^{2}_{c}+2\alpha^{2}\sigma_{g}^{2}\big{)}\sum_{k=0}^{T-1}w_{k+1}+\frac{5\alpha
L}{n}\sum_{k=0}^{T-1}w_{k+1}\mathbb{E}[\|\Psi_{k}\|^{2}]$
$\displaystyle\qquad-\alpha\sum_{k=0}^{T-1}w_{k+1}(\mathbb{E}[f(\mathbf{\bar{x}}_{k})]-f(\mathbf{x}^{*})).$
(37)

We note that we can write the relations (3)-(3) in Lemma 3 in the form of (16)
with

$\displaystyle b:=576\alpha^{2}L^{2}\tau^{2}\qquad c:=1344\alpha^{2}\tau$
$\displaystyle
r:=64\gamma^{2}\big{(}2+\alpha^{2}(\tau^{2}+1/2)+\alpha^{2}T\big{)}n\sigma_{c}^{2}\tau+196n(\tau+1)\alpha^{2}\sigma^{2}_{g}$
(38) $\displaystyle
e_{k}:=\mathbb{E}\left[\|\nabla\textbf{f}(\bar{\mathbf{x}}_{k})-\nabla\textbf{f}(\mathbf{x}^{*})\|^{2}\right]$

and we have taken $\rho^{\prime}=1/4$ which fixes $\tau$ in (20) according to
the bound (13) (cf. (81)). Note that since
$\alpha<\frac{\sqrt{\rho^{\prime}}}{2\sqrt{576}L\tau}$,
$b\leq\frac{\rho^{\prime}}{4}=\frac{1}{16}$. Then, with
$a_{t}\stackrel{{\scriptstyle\rm def}}{{=}}\mathbb{E}[\|\Psi_{t}\|^{2}]$ in
Lemma 4, we get,

$\displaystyle\mathbb{E}[\|\Psi_{t}\|^{2}]$ $\displaystyle\leq
40(1+\tau^{2})\left(1-\frac{3\rho}{4\tau}\right)^{t}\|\Psi_{0}\|^{2}+60c\sum_{j=0}^{t-1}\left(1-\frac{3\rho}{4\tau}\right)^{t-j}\mathbb{E}\left[\|\nabla\textbf{f(}\bar{\mathbf{x}}_{j})-\nabla\textbf{f}(\textbf{x}^{*})\|^{2}\right]+52r$
(39)

with $\rho^{\prime\prime}=2(1+\tau^{2})\|\Psi_{0}\|^{2}$ and
$\rho=1-2\rho^{\prime}=1/2$. We next bound the summation
$\sum_{k=0}^{T-1}w_{k+1}\mathbb{E}\|\Psi_{k}\|^{2}$ in (4). To do this, we
multiply both sides of (39) by $w_{k+1}$ and sum from $t=0$ to $T-1$:

$\displaystyle\sum_{k=0}^{T-1}(1-\alpha\mu/4)^{-(k+1)}\mathbb{E}\|\Psi_{k}\|^{2}$
$\displaystyle\leq
40(1+\tau^{2})\|\Psi_{0}\|^{2}\sum_{k=0}^{T-1}(1-\alpha\mu/4)^{-(k+1)}\left(1-\frac{3\rho}{4\tau}\right)^{k}$
$\displaystyle\qquad+60c\sum_{k=0}^{T-1}(1-\alpha\mu/4)^{-(k+1)}\sum_{j=0}^{k-1}\left(1-\frac{3\rho}{4\tau}\right)^{t-j}e_{j}+52rW_{T-1},$
(40)

where $W_{T-1}=\sum_{k=0}^{T-1}w_{k+1}$. From (19), we have,

$\alpha\mu/2\leq 3\rho/4\tau\implies\alpha\mu/2(1-\alpha\mu/8)\leq
3\rho/4\tau\implies 1-3\rho/4\tau\leq(1-\alpha\mu/4)^{2}.$ (41)

We use (41) to bound the two summations on the right hand side of (4) as
follows:

$\sum_{k=0}^{T-1}(1-\alpha\mu/4)^{-(k+1)}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{k}\leq\sum_{k=0}^{T-1}(1-\alpha\mu/4)^{k-1}\leq\frac{4w_{1}}{\alpha\mu},$
(42)

and

$\displaystyle\sum_{k=0}^{T-1}(1-\alpha\mu/4)^{-(k+1)}$
$\displaystyle\sum_{j=0}^{k-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{k-j}e_{j}=\sum_{k=0}^{T-1}\sum_{j=0}^{k-1}(1-\alpha\mu/4)^{-(k+1)+j+1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{k-j}w_{j+1}e_{j}$
$\displaystyle~{}~{}~{}~{}~{}=\sum_{k=0}^{T-1}\sum_{j=0}^{k-1}\Bigg{(}\frac{1-3\rho/4\tau}{1-\alpha\mu/4}\Bigg{)}^{k-j}w_{j+1}e_{j}\leq\sum_{k=0}^{T-1}\sum_{j=0}^{k-1}(1-\alpha\mu/4)^{k-j}w_{j+1}e_{j}$
$\displaystyle~{}~{}~{}~{}~{}\leq\sum_{k=0}^{T-1}(1-\alpha\mu/4)^{k}\sum_{k=0}^{T-1}w_{k+1}e_{k}\leq\frac{4}{\mu\alpha}\sum_{k=0}^{T-1}w_{k+1}e_{k},$
(43)

where the first equality is due to (41) and the second inequality is obtained
using the relation
$\sum_{k=0}^{T-1}\sum_{j=0}^{k-1}a_{k-j}b_{j}\leq\sum_{k=0}^{T-1}a_{k}\sum_{k=0}^{T-1}b_{k}$
for any two non-negative scalar sequences $a_{k},\,b_{k},\,k\geq 0$. Plugging
the previous two bounds in (4), we get,

$\displaystyle\sum_{k=0}^{T-1}w_{k+1}\mathbb{E}[\|\Psi_{k}\|^{2}]$
$\displaystyle\leq\frac{160w_{1}(1+\tau^{2})\|\Psi_{0}\|^{2}}{\alpha\mu}+\frac{240ncL}{\mu\alpha}\sum_{k=0}^{T-1}w_{k+1}\left(\mathbb{E}[\textbf{f}(\bar{\mathbf{x}}_{k})]-\textbf{f}(\textbf{x}^{*})\right)+52rW_{T-1},$

where we have additionally used the fact that
$\|e_{k}\|^{2}=\mathbb{E}\left[\|\nabla\textbf{f}(\mathbf{\bar{x}}_{k}))-\nabla\textbf{f}(\textbf{x}^{*})\|^{2}\right]\leq
2nL(\mathbb{E}[\textbf{f}(\mathbf{\bar{x}}_{k}))]-\mathbf{f}(\textbf{x}^{*}))$
from Assumption 3 [42, Theorem 2.1.5]. Finally, using the above bound in (4),
we get,

$\displaystyle w_{T}\Delta x^{*}_{T}$ $\displaystyle\leq w_{0}\Delta
x^{*}_{0}+\frac{1}{n}\big{(}\gamma^{2}(2+4T\mu^{-1}\alpha)\sigma^{2}_{c}+2\alpha^{2}\sigma_{g}^{2}\big{)}W_{T-1}$
$\displaystyle\quad+\frac{5\alpha
L}{n}\Bigg{(}\frac{160w_{1}(1+\tau^{2})\|\Psi_{0}\|^{2}}{\mu\alpha}+\frac{240ncL}{\mu\alpha}\sum_{k=0}^{T-1}w_{k+1}\left(\mathbb{E}[\textbf{f}(\mathbf{\bar{x}}_{k}))]-\mathbf{f}(\textbf{x}^{*})\right)+52rW_{T-1}\Bigg{)}$
$\displaystyle\quad-\alpha\sum_{k=0}^{T-1}w_{k+1}(\mathbb{E}[\,\textbf{f}(\mathbf{\bar{x}}_{k})]-\mathbf{f}(\textbf{x}^{*})).$

Rearranging the terms in the above inequality and recalling that
$c=1344\alpha^{2}\tau$, we get,

$\displaystyle\Delta x^{*}_{T}$
$\displaystyle\leq\frac{1}{w_{T}}\Bigg{\\{}\Delta
x^{*}_{0}+\frac{800w_{1}(1+\tau^{2})L}{n\mu}\|\Psi_{0}\|^{2}\Bigg{\\}}+\frac{2}{\mu\alpha}\Bigg{\\{}\frac{\gamma^{2}(2+4T\mu^{-1}\alpha)\sigma^{2}_{c}}{n}+\frac{2\alpha^{2}\sigma_{g}^{2}}{n}\Bigg{\\}}$
$\displaystyle\quad+\frac{520Lr}{n\mu}+\alpha\underbrace{\Bigg{\\{}\frac{1612800\tau
L^{2}}{\mu}\alpha-1\Bigg{\\}}}_{\leq
0}\sum_{k=0}^{T-1}\frac{w_{k+1}}{w_{T}}\underbrace{(\mathbb{E}[\mathbf{f}(\mathbf{\bar{x}}_{k})]-f(\mathbf{x}^{*}))}_{\geq
0},$

where we used $W_{T-1}/w_{T}\leq 2/\mu\alpha$. The last term on the right had
side is less than zero due to the condition on $\alpha$ (see (19)). Plugging
the value of $r$ from (38) in the above inequality completes the proof.∎

##  5 Numerical Experiments

In this section, we present an empirical evaluation of the performance of IC-
GT through two sets of numerical experiments. The first set focuses on
logistic regression on the MNIST dataset, while the second set explores the
effect of different noise variances in a deep learning setting. All
experiments were implemented using PyTorch, with a dedicated CPU core
functioning as a node.

### Logistic regression

We first consider $\ell_{2}$ regularized logistic regression problems of the
form,

$\min_{x\in\mathbb{R}^{d}}\,\left\\{L(x;y,z):=-\frac{1}{m}\sum_{i=1}^{m}\Big{\\{}z^{i}\log\varphi(x^{T}y^{i})+(1-z^{i})\log(1-\varphi(x^{T}y^{i}))\Big{\\}}+\frac{\lambda}{2}\|x\|^{2}\right\\},$
(44)

where $x\in\mathbb{R}^{d}$ denote the learnable model parameters,
$\\{y^{i},z^{i}\\}_{i=1}^{m}$ denote the set of $m$ data points,
$\varphi(\cdot)$ denotes the sigmoid function, and $\lambda>0$ is the
regularization parameter. We use the MNIST dataset which consists of 60,000,
28$\times$28 pixel grayscale images of handwritten single digits between 0 and
9. The data is partitioned in a disjoint manner amongst the nodes by assigning
each node $10^{3}$ data samples independently.

(a)

(b)

(c)

(d)

Figure 1: (a)-(b) Optimality Error, Average consensus error vs. communication
rounds for MNIST dataset with star topology $(n=10)$. (c) Final Optimal error
$\|x_{T}-x^{*}\|^{2},\,T=5\times 10^{3}$ for $n\in\\{5,10,15,20,25\\}$ for
different topologies. (d) Final Optimal error $\|x_{T}-x^{*}\|^{2}$ for
$\sigma_{c}\in\\{10^{-3},10^{-2},10^{-1},1\\}$

To simulate the inexact communication setting, we incorporate zero-mean
Gaussian noise with a variance of $\sigma_{c}^{2}$ into the transmitted model
estimates independently. We adopt a star topology with $n=10$ for the
communication structure. In evaluating the performance, we employ the
$\ell_{2}$ distance between the averaged variable $\bar{x}_{k}$ and the
optimal point $x^{*}$. The optimal point $x^{*}$ is computed using the L-BFGS
algorithm from the SciPy library in Python. We also include the average
consensus error as a performance metric, which is computed as
$\frac{1}{|\mathcal{E}|}\sum_{(i,j)\in\mathcal{E}}\|x_{i}-x_{j}\|^{2}$, where
$\mathcal{E}$ represents the edge set. We compare our proposed algorithm (IC-
GT) with several baselines, including the NEAR-SGD algorithm from [12], the
EXTRA algorithm proposed in [5], and the gradient tracking method [4].
Additionally, we include the performance of the DGD algorithm for comparison
purposes.

In our experiments, we set the batch size to $32$ and tune the step size
$\alpha$ using a grid-search over the range $\alpha\in[10^{-4},1]$ to obtain
the best performance for all the algorithms. The total number of communication
rounds is set to $T=5\times 10^{3}$. For IC-GT, we set the attenuation noise
parameter $\gamma$ to $\gamma=\alpha\times\log T$. The performance results are
reported in Figure 1(a)-(b). From the plots, it is evident that IC-GT
outperforms all the other algorithms in terms of both the optimality error and
the consensus error.

To assess the scalability of IC-GT and examine the impact of graph
connectivity on its convergence accuracy, we conducted experiments with
varying network sizes, specifically $n\in\\{5,10,15,20,25\\}$. We kept the
noise variance fixed at $\sigma_{c}^{2}=0.01$ for the following graph
topologies: (i) Fully connected (f.c.), (ii) Erdős-Rényi graph with an edge
probability of 0.5 (rand), (iii) Ring topology, and (iv) Star topology. From
Figure 1(c), we observe that as the graph connectivity deteriorates, the final
performance of IC-GT also deteriorates. In the case of a fully connected
graph, there is an improvement in performance with an increasing number of
nodes due to a decrease in gradient variance resulting from an increased
effective mini-batch size. Finally, we also investigate the effect of varying
$\sigma_{c}^{2}$ on the performance of IC-GT, as depicted in Figure 1(d).

### Neural network based experiments

In this subsection, we investigate a deep learning scenario that involves
random compressed communication using probabilistic quantization (see (3)). We
assume a star-based topology with $n=10$ for both the MNIST and CIFAR
datasets. For the MNIST dataset, we utilize a learning model with a total of
$8.4$K parameters. This model comprises two convolution layers, the first with
$250$ parameters and the second with $5$K parameters, followed by a fully
connected layer with $3.2$K parameters. For the CIFAR-10 dataset, we adopt the
standard LENET architecture, which consists of three convolution layers and
two fully connected layers. This architecture has a total of $0.54$M
parameters. The configuration of the max-pooling and batch normalization
layers follows the standard settings used in LENET models.

We compare IC-GT with two other strategies commonly employed to address noise
in an inexact communication setting. The first strategy involves utilizing a
decreasing noise variance policy, where the variance decreases as the number
of communication rounds progresses. In this approach, we employ GT with
quantization and adjust the quantization levels to become finer as the rounds
increase. Specifically, in the case of (3), we uniformly increase the
parameter $\Delta_{p}$ from $\Delta_{p}=1$ to $\Delta_{p}=5\times 10^{3}$ as
the rounds progress. This results in higher levels of noise variance in the
initial rounds and lower levels in the final rounds. The second strategy
maintains a uniform quantization level of $\Delta_{p}=10^{2}$ throughout all
communication rounds, leading to a fixed noise variance. We employ the same
quantization level of $\Delta_{p}=10^{2}$ for IC-GT.

The results of the comparison have been plotted in Figure 2(a)-(b). In both
plots, the baseline represents the highest achievable accuracy that can be
obtained in a centralized setting using the models employed. From the plots,
we observe that for both the CIFAR-10 and MNIST datasets, the performance of
IC-GT is the closest to the baseline. The performance difference between IC-GT
and the baseline appears to be more pronounced in the case of CIFAR-10
compared to MNIST.

(a)

(b)

Figure 2: (a) Test Accuracy vs. communication rounds for CIFAR-10 dataset with
star topology ($n=10$). (b) Test Accuracy vs. communication rounds for MNIST
dataset with star topology ($n=10$).

##  6 Final Remarks

In this paper, we proposed a gradient tracking based algorithm for
decentralized optimization in an inexact communication scenario. We
established theoretical convergence guarantees and analyzed the impact of
communication and gradient noise on performance. Our algorithm effectively
mitigates the impact of communication noise and data heterogeneity, and
achieves optimal iteration complexity for strongly convex, stochastic smooth
functions. Experimental results on logistic regression and neural networks
demonstrated the superiority of the proposed algorithm over existing methods.
As future work, the algorithm can be extended to other settings, such as
directed graphs and asynchronous updates, and incorporate variance reduction
techniques to enhance convergence rate.

## Appendix I: Proof of Lemma 1

###### Proof.

From (5), we have,

$\displaystyle\mathbf{v}_{k}$
$\displaystyle=(\textbf{I}_{n}-\gamma\textbf{Q}^{\prime})\mathbf{x}_{k}+\gamma\hat{\textbf{Q}}\epsilon_{k,c}.$
(45)

Multiplying both sides of (45) by $\frac{1}{n}1_{n}1_{n}^{T}\otimes I_{d}$, we
get,

$\displaystyle\bar{\textbf{v}}_{k}$
$\displaystyle=\bar{\textbf{x}}_{k}+\frac{\gamma}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\hat{\textbf{Q}}\epsilon_{k,c}$
$\displaystyle=(\textbf{I}_{n}-\gamma\textbf{Q}^{\prime})\bar{\textbf{x}}_{k}+\frac{\gamma}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\hat{\textbf{Q}}\epsilon_{k,c}.$ (46)

where we used $\frac{1}{n}1_{n}^{T}\textbf{Q}^{\prime}=0$ to get the first
inequality and
$(\textbf{I}_{n}-\gamma\textbf{Q}^{\prime})\bar{\textbf{x}}_{k}=\bar{\textbf{x}}_{k}$
to get the last inequality. Subtracting (Proof.) from (45) and adding
$-\frac{1}{n}1_{n}1_{n}^{T}\Delta\mathbf{x}_{k}$, we get,

$\Delta\mathbf{v}_{k}=(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})\Delta\mathbf{x}_{k}+\gamma\tilde{\textbf{Q}}\epsilon_{k,c}.$
(47)

From (6), the expression for $\Delta\mathbf{x}_{k}$ can be written as,

$\Delta\mathbf{x}_{k}=\Delta\mathbf{v}_{k-1}-\alpha\Delta\mathbf{y}_{k-1}.$
(48)

Substituting for $\Delta\mathbf{x}_{k}$ in (47) using (48) yields the
following recursive relation for $\Delta\mathbf{v}_{k}$ in terms of
$\Delta\mathbf{v}_{k-1}$ and $\Delta\mathbf{y}_{k-1}$:

$\displaystyle\Delta\mathbf{v}_{k}=(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})\Delta\mathbf{v}_{k-1}-\alpha(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})\Delta\mathbf{y}_{k-1}+\gamma\tilde{\mathbf{Q}}\epsilon_{k,c}$

Next, the recursive relation for $\Delta\mathbf{x}_{k}$ in terms of
$\Delta\mathbf{x}_{k-1}$ and $\Delta\mathbf{y}_{k-1}$ is obtained by
substituting for $\Delta\mathbf{v}_{k-1}$ in (48) using (47). That is,

$\displaystyle\Delta\mathbf{x}_{k}=(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})\Delta\mathbf{x}_{k-1}+\gamma\tilde{\textbf{Q}}\epsilon_{k-1,c}-\alpha\Delta\mathbf{y}_{k-1}.$

The recursive expression for $\Delta\mathbf{y}_{k}$ can be obtained similarly
using the expression for $\bar{\mathbf{y}}_{k}$ and subtracting it from (7),
concluding the proof. ∎

### Appendix II: Proof of Lemma 2

###### Proof.

Using mathematical induction, we can show that $\textbf{J}^{\tau}_{\gamma}$
for any $\tau\in\mathbb{N}$ is given as,

$\textbf{J}^{\tau}_{\gamma}=\begin{bmatrix}(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau}&0&-\tau(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau}\\\
0&(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau}&-\tau(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\left(\tau-1\right)}\\\
0&0&(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau}\ \end{bmatrix}.$
(49)

Taking norms in (49) and using triangular inequality, we get,

$\|\textbf{J}_{\gamma}^{\tau}\|\leq\|(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau}\|+\tau\|(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{(\tau-1)}\|+\tau\|(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau}\|.$
(50)

We will next bound the terms on the right hand side of (50). Note that the
smallest eigenvalue of the matrix
$(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau}$ is zero and the
remaining eigenvalues are of the form $(1-\gamma(1-\lambda_{i}))^{\tau}$ for
$i=2,\dots,n$, where $\lambda_{i}$ are the eigenvalues of $Q$ defined in
Assumption 1. Therefore,

$\displaystyle\|(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau}\|$
$\displaystyle=\max_{i=2,\dots,n}(1-\gamma(1-\lambda_{i}))^{\tau}$
$\displaystyle=(1-\gamma(1-\lambda_{2}))^{\tau}.$ (51)

From (13), it follows that $\tau\geq
2\left(1-\frac{\ln\sqrt{\delta}/4}{\gamma(1-\lambda_{2})}\right)>-\frac{\ln\sqrt{\delta}/2}{\gamma(1-\lambda_{2})}$.
Substituting this inequality in (Proof.), we get,

$\displaystyle\big{(}1-\gamma(1-\lambda_{2})\big{)}^{\tau}$
$\displaystyle\leq\exp\big{(}-\tau\gamma(1-\lambda_{2})\big{)}\leq\frac{\sqrt{\delta}}{2}.$
(52)

We next bound the second term in (50). For convenience, we define
$\textbf{Q}_{1}\stackrel{{\scriptstyle\rm
def}}{{=}}\tau(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau-1}$. The
smallest eigenvalue of $\textbf{Q}_{1}$ is zero and the remaining eigenvalues
are of the form $\tau(1-\gamma(1-\lambda_{i}))^{\tau-1},$ for $i=2,\dots,n$.
Therefore,

$\displaystyle\|\textbf{Q}_{1}\|$
$\displaystyle\leq\tau(1-\gamma(1-\lambda_{2}))^{\tau-1}\leq\tau\exp(-(\tau-1)\gamma(1-\lambda_{2})).$
(53)

Taking logarithm on both sides of (53) yields,

$\displaystyle\ln\|\textbf{Q}_{1}\|$
$\displaystyle\leq\ln\tau-(\tau-1)\gamma(1-\lambda_{2}).$ (54)

Now, consider $\frac{\ln\tau}{\tau}$ as a function of $\tau$ and observe that
it is monotonically decreasing for any $\tau>\exp(1)$ since its first
derivative $\frac{1-\ln\tau}{\tau^{2}}<0$. From (13), we have $\tau\geq 16\ln
4>\exp(1)$ since $\gamma<1/4$ and $\lambda_{2}\in(-1,1)$. For convenience, we
define
$\epsilon_{\gamma,\lambda_{2}}=\frac{\gamma(1-\lambda_{2})}{2}\in[0,1/4)$.
Therefore, from(13), it follows that,

$\displaystyle\frac{\ln\tau}{\tau}\leq\epsilon_{\gamma,\lambda_{2}}\frac{\ln\frac{4}{\epsilon_{\gamma,\lambda_{2}}}+\ln\ln\frac{1}{\epsilon_{\gamma,\lambda_{2}}}}{4\ln
1/\epsilon_{\gamma,\lambda_{2}}}\leq\epsilon_{\gamma,\lambda_{2}}=\frac{\gamma(1-\lambda_{2})}{2}.$
(55)

Using (55) and $\tau\geq
2\left(1-\frac{\ln\sqrt{\delta}/4}{\gamma(1-\lambda_{2})}\right)$ in (54), we
get,

$\displaystyle\ln\|\textbf{Q}_{1}\|$
$\displaystyle\leq\ln\tau-(\tau-1)\gamma(1-\lambda_{2})$
$\displaystyle\leq\frac{\tau\gamma(1-\lambda_{2})}{2}-(\tau-1)\gamma(1-\lambda_{2})$
$\displaystyle=\gamma(1-\lambda_{2})\left(1-\frac{\tau}{2}\right)$
$\displaystyle\leq\ln\sqrt{\delta}/4.$

Therefore,

$\displaystyle\|\textbf{Q}_{1}\|\leq\sqrt{\delta}/4.$ (56)

Finally, we bound the third term in (50) as,

$\displaystyle\tau\|(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau}\|\leq\|\textbf{Q}_{1}\|\leq\sqrt{\delta}/4.$
(57)

Combining, (50), (52),(56) and (57), we get,

$\|\textbf{J}^{\tau}_{\gamma}\|^{2}\leq\left(\frac{\sqrt{\delta}}{2}+\frac{\sqrt{\delta}}{4}+\frac{\sqrt{\delta}}{4}\right)^{2}=\delta.$

.

∎

## Appendix III: Proof of Lemma 3

###### Proof.

We begin by iterating the relation (11) with $k=t+\tau$:

$\displaystyle\Psi_{t+\tau}$
$\displaystyle=\textbf{J}_{\gamma}\Psi_{t+\tau-1}+\alpha\textbf{E}_{t+\tau-1}$
$\displaystyle=\textbf{J}^{\tau}_{\gamma}\Psi_{t}+\alpha\sum_{i=0}^{\tau-1}\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}_{t+i}$
(58)

We next consider $\textbf{E}_{k}$ whose definition is recalled here:

$\textbf{E}_{k-1}=\underbrace{\frac{\gamma}{\alpha}\begin{bmatrix}\tilde{\textbf{Q}}\bm{\epsilon}_{k,c}\\\
\tilde{\textbf{Q}}\bm{\epsilon_{k-1,c}}\\\
\alpha\tilde{\textbf{Q}}\bm{\epsilon_{k-1,c}}\end{bmatrix}}_{\textbf{E}^{c}_{k-1}}+\underbrace{\begin{bmatrix}0\\\
0\\\
\bar{\textbf{I}}_{n}(\nabla\textbf{F}(\mathbf{x}_{k},\bm{\xi}_{k})-\nabla\textbf{F}(\mathbf{x}_{k-1},\bm{\xi}_{k-1}))\end{bmatrix}}_{\textbf{E}_{k-1}^{g}},\quad\forall
k\in\mathbb{N}.$

We note that

$\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}_{t+i}\right\|^{2}\right]\leq
2\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}^{c}_{t+i}\right\|^{2}\right]+2\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}^{g}_{t+i}\right\|^{2}\right]$
(59)

We first bound the first term on the right hand side of (59). Using the
expression for the matrix product $\textbf{J}_{\gamma}^{\tau-i-1}$ for any
$0\leq i\leq\tau-1$ (cf. (49)), we have,

$\textbf{J}^{\tau-i-1}_{\gamma}\textbf{
E}^{c}_{t+i}=\frac{\gamma}{\alpha}\begin{bmatrix}(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau-i-1}\tilde{\textbf{Q}}\bm{\epsilon}_{t+i+1,c}-\alpha(\tau-i-1)(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau-i-1}\tilde{\textbf{Q}}\bm{\epsilon}_{t+i,c}\\\
(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau-i-1}\tilde{\textbf{Q}}-\alpha(\tau-i-1)(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau-i-2}\tilde{\textbf{Q}}\big{)}\bm{\epsilon}_{t+i,c}\\\
\alpha(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau-i-1}\tilde{\textbf{Q}}\bm{\epsilon}_{t+i,c}\end{bmatrix}.$
(60)

Note that, using $\|Q\|,\,\|\text{diag}(Q)\|\leq 1$, we have,

$\|(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\tau-i-1}\|^{2}\leq
1,\qquad\|\hat{\textbf{Q}}\|=\|(Q^{\prime}-\text{diag}(Q^{\prime}))\otimes
I_{d}\|\leq
2,\quad\mbox{and}\quad\|\tilde{\textbf{Q}}\|\leq\left\|\textbf{I}_{n}-\frac{11^{T}}{n}\right\|\|\hat{\textbf{Q}}\|\leq
2.$ (61)

Taking norms in (60) and using the bounds (61), we get,

$\displaystyle\mathbb{E}\left[\|\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}^{c}_{t+i}\|^{2}\right]$
$\displaystyle\leq\frac{4\gamma^{2}}{\alpha^{2}}(2(1+\alpha^{2}(\tau-i-1)^{2})+\alpha^{2})\max\\{\mathbb{E}\left[\|\bm{\epsilon}_{t+i+1,c}\|^{2}\right],\mathbb{E}\left[\|\bm{\epsilon}_{t+i,c}\|^{2}\right]\\}$
$\displaystyle\leq\frac{4\gamma^{2}}{\alpha^{2}}(2+2\alpha^{2}\tau^{2}+\alpha^{2})\max\\{\mathbb{E}\left[\|\bm{\epsilon}_{t+i+1,c}\|^{2}\right],\mathbb{E}\left[\|\bm{\epsilon}_{t+i,c}\|^{2}\right]\\}$
$\displaystyle\leq\frac{8\gamma^{2}}{\alpha^{2}}(1+\alpha^{2}\left(\tau^{2}+1/2\right)n\sigma_{c}^{2},$
(62)

where the last inequality is due to Assumption 2. Hence,

$\displaystyle\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\textbf{J}^{\tau-i-1}_{\gamma}\textbf{
E}^{c}_{t+i}\right\|^{2}\right]$
$\displaystyle=\sum_{i=0}^{\tau-1}\mathbb{E}\left[\left\|\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}^{c}_{t+i}\right\|^{2}\right]\leq\frac{8\gamma^{2}}{\alpha^{2}}\big{(}1+\alpha^{2}(\tau^{2}+1/2)\big{)}n\sigma_{c}^{2}\tau,$
(63)

where the equality is due to Assumption 2 and the fact that the cross terms of
the form $\langle\bm{\epsilon}_{i,c},\bm{\epsilon}_{j,c}\rangle$ are all zero.
That is, if we denote $\mathcal{F}_{k}\stackrel{{\scriptstyle\rm
def}}{{=}}\sigma(\mathbf{x}_{0},\bm{\xi}_{0},\bm{\epsilon}_{0,c},\cdots,\bm{\xi}_{k-1},\bm{\epsilon}_{k-1,c})$
to be the sigma algebra generated by the random variables up to iteration $k$,
we have for any $i,j$ with $i<j$,
$\mathbb{E}[\langle\bm{\epsilon}_{i,c},\bm{\epsilon}_{j,c}\rangle]=\mathbb{E}[\mathbb{E}\left[\langle\bm{\epsilon}_{i,c},\bm{\epsilon}_{j,c}\rangle|\mathcal{F}_{j}\right]]=0$.

Next we consider $\textbf{E}^{g}_{k}$ to bound the second summation in (59).
Let $\textbf{g}_{k}\stackrel{{\scriptstyle\rm
def}}{{=}}\nabla\textbf{F}(\mathbf{x}_{k},\bm{\xi}_{k})-\nabla\textbf{f}(\mathbf{x}_{k})$
and
$\textbf{d}_{k}=\nabla\textbf{f}(\textbf{x}_{k})-\nabla\textbf{f}(\textbf{x}^{*})$.
We note from Assumption 4, $\textbf{g}_{k}$ is a zero mean vector given
$\mathbf{x}_{k}$ with variance $n\sigma_{g}^{2}$. Using
$\bar{\mathbf{Q}}\stackrel{{\scriptstyle\rm
def}}{{=}}(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})$ and the expression
for the matrix product $\textbf{J}_{\gamma}^{\tau-i-1}$ (cf. 49), we have,

$\displaystyle\mathbb{E}$
$\displaystyle\left[\left\|\sum_{i=0}^{\tau-1}\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}^{g}_{t+i}\right\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}(\nabla\textbf{F}(\mathbf{x}_{t+i+1},\bm{\xi}_{t+i+1})-\nabla\textbf{F}(\mathbf{x}_{t+i},\bm{\xi}_{t+i}))\right\|^{2}\right]$
$\displaystyle~{}~{}~{}~{}~{}+\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-2}\bar{\textbf{I}}_{n}(\nabla\textbf{F}(\mathbf{x}_{t+i+1},\bm{\xi}_{t+i+1})-\nabla\textbf{F}(\mathbf{x}_{t+i},\bm{\xi}_{t+i}))\right\|^{2}\right]$
$\displaystyle~{}~{}~{}~{}~{}+\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}\left(\nabla\textbf{F}(\mathbf{x}_{t+i+1},\bm{\xi}_{t+i+1})-\nabla\textbf{F}(\mathbf{x}_{t+i},\bm{\xi}_{t+i}))\right)\right\|^{2}\right]$
$\displaystyle\leq
2\Bigg{\\{}\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}(\textbf{g}_{t+i+1}-\textbf{g}_{t+i})\right\|^{2}\right]+\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}(\textbf{d}_{t+i+1}-\textbf{d}_{t+i})\right\|^{2}\right]$
$\displaystyle~{}~{}~{}~{}~{}+\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-2}\bar{\textbf{I}}_{n}(\textbf{g}_{t+i+1}-\textbf{g}_{t+i})\right\|^{2}\right]+\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-2}\bar{\textbf{I}}_{n}(\textbf{d}_{t+i+1}-\textbf{d}_{t+i})\right\|^{2}\right]$
$\displaystyle~{}~{}~{}~{}~{}+\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}(\textbf{g}_{t+i+1}-\textbf{g}_{t+i})\right\|^{2}\right]+\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}(\textbf{d}_{t+i+1}-\textbf{d}_{t+i})\right\|^{2}\right]\Bigg{\\}},$
(64)

where the inequality is obtained by adding and subtracting the terms
$\nabla\textbf{f}(\mathbf{x}_{t+i+1}),\,\nabla\textbf{f}(\mathbf{x}_{t+i})$,
and $\nabla\textbf{f}(\mathbf{x}^{*})$ in each of the three terms in the first
equality. We bound the first term on the right hand side of (Proof.) and
follow a similar approach to bound the rest of the terms. However, before
proceeding, we state the following fact whose proof is provided at the end of
this appendix:

$\left\|(i+1)\bar{\textbf{Q}}^{i+1}\bar{\textbf{I}}_{n}-i\bar{\textbf{Q}}^{i}\bar{\textbf{I}}_{n}\right\|^{2}\leq
4,\quad\forall i\in\mathbb{N}.$ (65)

The first term on the right hand side of (Proof.) is bounded as,

$\displaystyle\mathbb{E}$
$\displaystyle\left[\left\|\sum_{i=0}^{\tau-1}(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}(\textbf{g}_{t+i+1}-\textbf{g}_{t+i})\right\|^{2}\right]$
$\displaystyle~{}~{}~{}~{}=\mathbb{E}\Bigg{[}\Bigg{\|}\sum_{i=1}^{\tau-1}\big{(}(\tau-i)\bar{\mathbf{Q}}^{\tau-i}\bar{\textbf{I}}_{n}-(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-1}\big{)}\textbf{g}_{t+i}-(\tau-1)\bar{\mathbf{Q}}^{\tau-1}\bar{\textbf{I}}_{n}\textbf{g}_{t}\Bigg{\|}^{2}\Bigg{]}$
$\displaystyle~{}~{}~{}~{}~{}\leq\sum_{i=1}^{\tau-1}\left\|(\tau-i)\bar{\mathbf{Q}}^{\tau-1}\bar{\textbf{I}}_{n}-(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}\right\|^{2}\mathbb{E}[\|\textbf{g}_{t+i}\|^{2}]+\left\|(\tau-1)\bar{\mathbf{Q}}^{\tau-1}\bar{\textbf{I}}_{n}\right\|^{2}\mathbb{E}[\|\textbf{g}_{t}\|^{2}]$
$\displaystyle~{}~{}~{}~{}~{}\leq
4\sum_{i=1}^{\tau-1}\mathbb{E}[\|\textbf{g}_{t+i}\|^{2}]+n\sigma_{g}^{2}\leq
4\tau n\sigma_{g}^{2}$ (66)

where the first inequality is due to Assumption 4 and the fact that the cross
terms of the form
$\mathbb{E}[\langle\textbf{g}_{p},\textbf{g}_{p^{\prime}}\rangle]=0$, for any
$p<p^{\prime}$, and the second the inequality is due to Assumption 4, (65),
and the fact that
$\tau\|\textbf{I}_{n}-\gamma\textbf{Q}^{\prime}\|^{\tau-1}\|\bar{\textbf{I}}_{n}\|\leq
1$(cf. (56)). Following a similar approach, we can bound the rest of the terms
involving $\textbf{g}_{k}$ as:

$\displaystyle\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-2}\bar{\textbf{I}}_{n}(\textbf{g}_{t+i+1}-\textbf{g}_{t+i})\right\|^{2}\right]$
$\displaystyle\leq 4\tau n\sigma_{g}^{2}$
$\displaystyle\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}(\textbf{g}_{t+i+1}-\textbf{g}_{t+i})\right\|^{2}\right]$
$\displaystyle\leq 4(\tau+1)n\sigma_{g}^{2}.$ (67)

Similarly, considering the second term in (Proof.), we have,

$\displaystyle\mathbb{E}$
$\displaystyle\left[\left\|\sum_{i=0}^{\tau-1}(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}(\textbf{d}_{t+i+1}-\textbf{d}_{t+i})\right\|^{2}\right]$
$\displaystyle~{}~{}~{}~{}~{}\leq\tau\left((\tau-1)\|\bar{\mathbf{Q}}^{\tau-1}\bar{\textbf{I}}_{n}\|^{2}\mathbb{E}[\left\|\textbf{d}_{t}\|^{2}\right]+\sum_{i=1}^{\tau-1}\left\|(\tau-i)\bar{\mathbf{Q}}^{\tau-1}\bar{\textbf{I}}_{n}-(\tau-i-1)\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}\right\|^{2}\mathbb{E}[\|\textbf{d}_{t+i}\|^{2}]\right)$
$\displaystyle~{}~{}~{}~{}~{}\leq
4\tau\sum_{i=0}^{\tau-1}\mathbb{E}[\left\|\textbf{d}_{t+i}\right\|^{2}],$ (68)

where the first inequality is due to the fact that
$\left\|\sum_{i=0}^{\tau-1}a_{i}\right\|^{2}\leq\tau\sum_{i=0}^{\tau-1}\|a_{i}\|^{2}$
for any $a\in\mathbb{R}^{d}$. The same bound also holds for the fourth term in
(Proof.) while for the last term, we have,

$\displaystyle\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}(\textbf{d}_{t+i+1}-\textbf{d}_{t+i})\right\|^{2}\right]$
$\displaystyle\leq
4\tau\sum_{i=0}^{\tau}\mathbb{E}[\left\|\textbf{d}_{t+i}\right\|^{2}].$ (69)

We next bound the summation
$\sum_{i=0}^{\tau}\mathbb{E}[\left\|\textbf{d}_{t+i}\right\|^{2}$. For all
$i<\tau$:

$\displaystyle\|\textbf{d}_{t+i}\|^{2}$
$\displaystyle=\|\nabla\textbf{f}(\mathbf{x}_{t+i})-\nabla\textbf{f}(\bar{\mathbf{x}}_{t+i})+\nabla\textbf{f}(\bar{\mathbf{x}}_{t+i})-\nabla\textbf{f}(\textbf{x}^{*})\|^{2}$
$\displaystyle\leq
2L^{2}\|\Psi_{t+i}\|^{2}+2\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+i})-\nabla\textbf{f}(\textbf{x}^{*})\|^{2},$
(70)

where the second inequality is due to Assumption 3. Now, for $i=\tau$, we
have,

$\displaystyle\|\textbf{d}_{t+\tau}\|^{2}$ $\displaystyle\leq
2L^{2}\|\Psi_{t+\tau}\|^{2}+2\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+\tau})-\nabla\textbf{f}(\textbf{x}^{*})\|^{2}$
$\displaystyle\leq
2L^{2}\|\Psi_{t+\tau}\|^{2}+4\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+\tau})-\nabla\textbf{f}(\bar{\textbf{x}}_{t+\tau-1})\|^{2}+4\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+\tau-1})-\nabla\textbf{f}(\textbf{x}^{*})\|^{2}$
$\displaystyle\leq
2L^{2}\|\Psi_{t+\tau}\|^{2}+4L^{2}\|\bar{\textbf{x}}_{t+\tau}-\bar{\textbf{x}}_{t+\tau-1}\|^{2}+4\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+\tau-1})-\nabla\textbf{f}(\textbf{x}^{*})\|^{2}.$
(71)

The expression for $\bar{\textbf{x}}_{t+\tau}$ can be written as (cf. (4)),

$\displaystyle\mathbf{\bar{x}}_{t+\tau}$
$\displaystyle=\bar{\textbf{x}}_{t+\tau-1}-\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\nabla\textbf{f}(\mathbf{x}_{t+\tau-1})+\alpha\bm{\epsilon}_{t+\tau-1,g}+\gamma\bar{\bm{\epsilon}}_{t+\tau-1,c}-\alpha\gamma\sum_{j=0}^{t+\tau-2}\bar{\bm{\epsilon}}_{j,c},$

where $\bm{\epsilon}_{k,g}\stackrel{{\scriptstyle\rm
def}}{{=}}\frac{1}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\Big{(}\nabla\textbf{f}(\mathbf{x}_{k})-\nabla\textbf{F}(\mathbf{x}_{k},\bm{\xi}_{k})\Big{)}$
and $\bar{\bm{\epsilon}}_{k,c}\stackrel{{\scriptstyle\rm
def}}{{=}}\frac{1}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\hat{\textbf{Q}}\bm{\epsilon}_{k,c}$ for any $k\in\mathbb{N}$.
Taking square norms and expectations, we get,

$\displaystyle\mathbb{E}$
$\displaystyle[\|\bar{\textbf{x}}_{t+\tau}-\bar{\textbf{x}}_{t+\tau-1}\|^{2}|\mathcal{F}_{t+\tau-1}]$
$\displaystyle~{}~{}~{}~{}~{}~{}\leq
2\mathbb{E}\left[\left\|\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\left(\nabla\textbf{f}(\mathbf{x}_{t+\tau-1})-\nabla\textbf{f}(\mathbf{x}^{*})\right)+\alpha\bm{\epsilon}_{t+\tau-1,g}+\gamma\bar{\bm{\epsilon}}_{t+\tau-1,c}\right\|^{2}\Big{|}\mathcal{F}_{t+\tau-1}\right]$
$\displaystyle\qquad\qquad+2\alpha^{2}\gamma^{2}\mathbb{E}\left[\left\|\sum_{j=0}^{t+\tau-2}\bar{\bm{\epsilon}}_{j,c}\right\|^{2}\Big{|}\mathcal{F}_{t+\tau-1}\right],$
(72)

where we used the fact that $\frac{1}{n}\left(1_{n}1_{n}^{T}\otimes
I_{d}\right)\nabla\textbf{f}(\textbf{x}^{*})=0$. From Assumptions 2 and 4, we
have for all $k\in\mathbb{N}$,

$\mathbb{E}[\alpha\bm{\epsilon}_{k,g}+\gamma\bar{\bm{\epsilon}}_{k,c}|\mathcal{F}_{k}]=0,\qquad\qquad\mathbb{E}[\left\|\alpha\bm{\epsilon}_{k,g}+\gamma\bar{\bm{\epsilon}}_{k,c}\right\|^{2}]\leq\alpha^{2}\sigma_{g}^{2}+\gamma^{2}\sigma^{2}_{c},$
(73)

and

$\displaystyle\mathbb{E}\left[\left\|\sum_{j=0}^{k-1}\bar{\bm{\epsilon}}_{j,c}\right\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{j=0}^{k-1}\left\|\bar{\bm{\epsilon}}_{j,c}\right\|^{2}\right]+\sum_{1\leq
p,p^{\prime}\leq
k-1}\mathbb{E}\left[\langle\bar{\bm{\epsilon}}_{p,c},\bar{\bm{\epsilon}}_{p^{\prime},c}\rangle\right]\leq\sum_{j=0}^{k-1}\sigma_{c}^{2}=k\sigma_{c}^{2},$
(74)

where the last inequality is due to the fact that
$\mathbb{E}[\langle\bar{\bm{\epsilon}}_{p,c},\bar{\bm{\epsilon}}_{p^{\prime},c}\rangle]=\mathbb{E}[\mathbb{E}\left[\langle\bar{\bm{\epsilon}}_{p,c},\bar{\bm{\epsilon}}_{p^{\prime},c}\rangle|\mathcal{F}_{p^{\prime}}\right]]=0$
for any $p<p^{\prime}$. Combining (Proof.), (73) and (74), we have,

$\displaystyle\mathbb{E}$
$\displaystyle[\|\bar{\textbf{x}}_{t+\tau}-\bar{\textbf{x}}_{t+\tau-1}\|^{2}]$
$\displaystyle~{}~{}~{}~{}~{}\leq
2\mathbb{E}\left[\left\|\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\left(\nabla\textbf{f}(\mathbf{x}_{t+\tau-1})-\nabla\textbf{f}(\mathbf{x}^{*})\right)\right\|^{2}\right]+2\alpha^{2}\sigma_{g}^{2}+2\left(1+\alpha^{2}(t+\tau)\right)\gamma^{2}\sigma^{2}_{c}$
$\displaystyle~{}~{}~{}~{}~{}\leq
2\mathbb{E}\left[\left\|\frac{\alpha}{n}\big{(}1_{n}1_{n}^{T}\otimes
I_{d}\big{)}\left(\nabla\textbf{f}(\mathbf{x}_{t+\tau-1})-\nabla\textbf{f}(\bar{\textbf{x}}_{t+\tau-1})+\nabla\textbf{f}(\bar{\textbf{x}}_{t+\tau-1})-\nabla\textbf{f}(\mathbf{x}^{*})\right)\right\|^{2}\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+2\alpha^{2}\sigma_{g}^{2}+2\left(1+\alpha^{2}(t+\tau)\right)\gamma^{2}\sigma^{2}_{c}$
$\displaystyle~{}~{}~{}~{}~{}\leq
4\alpha^{2}L^{2}\mathbb{E}\left[\|\Psi_{t+\tau-1}\|^{2}\right]+4\alpha^{2}\mathbb{E}\left[\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+\tau-1})-\nabla\textbf{f}(\textbf{x}^{*})\|^{2}\right]+2\alpha^{2}\sigma_{g}^{2}+2\left(1+\alpha^{2}(t+\tau)\right)\gamma^{2}\sigma^{2}_{c}.$
(75)

Taking expectations in (Proof.) and using (Proof.), we get,

$\displaystyle\mathbb{E}[\|\textbf{d}_{t+\tau}\|^{2}]$ $\displaystyle\leq
2L^{2}\mathbb{E}[\|\Psi_{t+\tau}\|^{2}]+4\mathbb{E}[\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+\tau-1})-\nabla\textbf{f}(\textbf{x}^{*})\|^{2}]+16L^{4}\alpha^{2}\mathbb{E}[\left\|\Psi_{t+\tau-1}\right\|]^{2}$
$\displaystyle\qquad+16\alpha^{2}L^{2}\mathbb{E}[\left\|\nabla\textbf{f}(\bar{\mathbf{x}}_{t+\tau-1})-\nabla\textbf{f}(\mathbf{x}^{*})\right\|^{2}]+8L^{2}\left(\alpha^{2}\sigma^{2}_{g}+\gamma^{2}(1+\alpha^{2}(t+\tau))\sigma_{c}^{2}\right)$
$\displaystyle\leq
2L^{2}\mathbb{E}[\|\Psi_{t+\tau}\|^{2}]+5\mathbb{E}[\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+\tau-1})-\nabla\textbf{f}(\textbf{x}^{*})\|^{2}]+L^{2}\mathbb{E}[\left\|\Psi_{t+\tau-1}\right\|^{2}]$
$\displaystyle\qquad+8L^{2}\left(\alpha^{2}\sigma^{2}_{g}+\gamma^{2}(1+\alpha^{2}(t+\tau))\sigma_{c}^{2}\right),$
(76)

where the last inequality is due to $\alpha^{2}<1/16L^{2}$. Using (Proof.) and
(Proof.) in (69), we have,

$\displaystyle\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\bar{\mathbf{Q}}^{\tau-i-1}\bar{\textbf{I}}_{n}(\textbf{d}_{t+i+1}-\textbf{d}_{t+i})\right\|^{2}\right]$
$\displaystyle\leq 12\tau
L^{2}\sum_{i=0}^{\tau-1}\mathbb{E}[\|\Psi_{t+i}\|^{2}]+28\tau\sum_{i=0}^{\tau-1}\mathbb{E}[\left\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+i})-\nabla\textbf{f}(\textbf{x}^{*})\right\|^{2}]$
$\displaystyle\qquad+8\tau L^{2}\mathbb{E}[\|\Psi_{t+\tau}\|^{2}]+32\tau
L^{2}\left(\alpha^{2}\sigma^{2}_{g}+\gamma^{2}(1+\alpha^{2}(t+\tau))\sigma_{c}^{2}\right)$
(77)

The rest of the terms involving $d_{k}$ in (Proof.) can be bounded in the same
manner. Using (Proof.), (Proof.) and (Proof.) in (Proof.), we get,

$\displaystyle\sum_{i=0}^{\tau-1}\mathbb{E}\left[\|\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}^{g}_{t+i}\|^{2}\right]$
$\displaystyle\leq 24n(\tau+1)\sigma^{2}_{g}+72\tau
L^{2}\sum_{i=0}^{\tau-1}\mathbb{E}[\|\Psi_{t+i}\|^{2}]+168\tau\sum_{i=0}^{\tau-1}\mathbb{E}[\left\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+i})-\nabla\textbf{f}(\textbf{x}^{*})\right\|^{2}]$
$\displaystyle\qquad+48\tau L^{2}\mathbb{E}[\|\Psi_{t+\tau}\|^{2}]+192\tau
L^{2}\left(\alpha^{2}\sigma^{2}_{g}+\gamma^{2}(1+\alpha^{2}(t+\tau))\sigma_{c}^{2}\right).$
(78)

Using (63) and (Proof.) to bound the right hand side in (59), we have,

$\displaystyle\mathbb{E}\left[\Big{\|}\sum_{i=0}^{\tau-1}\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}_{t+i}\Big{\|}^{2}\right]$
$\displaystyle~{}~{}~{}~{}~{}\leq\frac{16\gamma^{2}}{\alpha^{2}}\big{(}1+\alpha^{2}(\tau^{2}+1/2)\big{)}n\sigma_{c}^{2}\tau+48n(\tau+1)\sigma^{2}_{g}+144\tau
L^{2}\sum_{i=0}^{\tau-1}\mathbb{E}[\|\Psi_{t+i}\|^{2}]$
$\displaystyle~{}~{}~{}~{}~{}\qquad+336\tau\sum_{i=0}^{\tau-1}\mathbb{E}\left[\left\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+i})-\nabla\textbf{f}(\textbf{x}^{*})\right\|^{2}\right]+96\tau
L^{2}\mathbb{E}[\|\Psi_{t+\tau}\|^{2}]+384\tau
L^{2}\left(\alpha^{2}\sigma^{2}_{g}+\gamma^{2}(1+\alpha^{2}(t+\tau))\sigma_{c}^{2}\right)$
$\displaystyle~{}~{}~{}~{}~{}\leq 144\tau
L^{2}\sum_{i=0}^{\tau-1}\mathbb{E}[\|\Psi_{t+i}\|^{2}]+336\tau\sum_{i=0}^{\tau-1}\mathbb{E}\left[\left\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+i})-\nabla\textbf{f}(\textbf{x}^{*})\right\|^{2}\right]+\frac{1}{4\alpha^{2}}\mathbb{E}[\|\Psi_{t+\tau}\|^{2}]$
$\displaystyle~{}~{}~{}~{}~{}\qquad+\frac{16\gamma^{2}}{\alpha^{2}}\big{(}2+\alpha^{2}(\tau^{2}+1/2)+\alpha^{2}(t+\tau)\big{)}n\sigma_{c}^{2}\tau+49n(\tau+1)\sigma^{2}_{g}$
(79)

where we used $\alpha^{2}<1/384\tau L^{2}$. Next, taking square norms and
expectations in (58), we get,

$\displaystyle\mathbb{E}\left[\|\Psi_{t+\tau}\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|\textbf{J}^{\tau}_{\gamma}\Psi_{t}+\alpha\sum_{i=0}^{\tau-1}\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}_{t+i}\right\|^{2}\right]$
$\displaystyle\leq
2\mathbb{E}\left[\left\|\textbf{J}^{\tau}_{\gamma}\Psi_{t}\right\|^{2}\right]+2\alpha^{2}\mathbb{E}\left[\left\|\sum_{i=0}^{\tau-1}\textbf{J}^{\tau-i-1}_{\gamma}\textbf{E}_{t+i}\right\|^{2}\right].$
(80)

From Lemma 2, it follows that there there exists a $\tau$ such that
$\|\textbf{J}^{\tau}_{\gamma}\|^{2}\leq\frac{1}{4}\rho^{\prime}$ for a given
$\rho^{\prime}\in(0,1/4]$. Therefore,

$4\|\textbf{J}^{\tau}_{\gamma}\Psi_{t}\|^{2}\leq
4\|\textbf{J}^{\tau}_{\gamma}\|^{2}\|\Psi_{t}\|^{2}\leq\rho^{\prime}\|\Psi_{t}\|^{2}.$
(81)

To conclude, we substitute (Proof.) and (81) in (Proof.) to get the required
inequality,

$\displaystyle\mathbb{E}\left[\|\Psi_{t+\tau}\|^{2}\right]$ $\displaystyle\leq
2\mathbb{E}\left[\left\|\textbf{J}^{\tau}_{\gamma}\Psi_{t}\right\|^{2}\right]+288\alpha^{2}\tau
L^{2}\sum_{i=0}^{\tau-1}\mathbb{E}\left[\|\Psi_{t+i}\|^{2}\right]+672\alpha^{2}\tau\sum_{i=0}^{\tau-1}\mathbb{E}\left[\left\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+i})-\nabla\textbf{f}(\textbf{x}^{*})\right\|^{2}\right]+\frac{1}{2}\mathbb{E}[\|\Psi_{t+\tau}\|^{2}]$
$\displaystyle\qquad+32\gamma^{2}\big{(}2+\alpha^{2}(\tau^{2}+1/2)+\alpha^{2}(t+\tau)\big{)}n\sigma_{c}^{2}\tau+98n(\tau+1)\alpha^{2}\sigma^{2}_{g}$
$\displaystyle\mathbb{E}\left[\|\Psi_{t+\tau}\|^{2}\right]$
$\displaystyle\leq\rho^{\prime}\mathbb{E}\|\Psi_{t}\|^{2}+576\alpha^{2}\tau
L^{2}\sum_{i=0}^{\tau-1}\mathbb{E}[\|\Psi_{t+i}\|^{2}]+1344\alpha^{2}\tau\sum_{i=0}^{\tau-1}\mathbb{E}\left[\left\|\nabla\textbf{f}(\bar{\textbf{x}}_{t+i})-\nabla\textbf{f}(\textbf{x}^{*})\right\|^{2}\right]$
$\displaystyle\qquad+64\gamma^{2}\big{(}2+\alpha^{2}(\tau^{2}+1/2)+\alpha^{2}(t+\tau)\big{)}n\sigma_{c}^{2}\tau+196n(\tau+1)\alpha^{2}\sigma^{2}_{g},$

which proves the bound (3). The bound (3) for $\ell<\tau$ is proved exactly
along the same lines with the only modification being that the first term is
scaled by $\|\textbf{J}^{\ell}_{\gamma}\|^{2},\,\ell<\tau$ instead of
$\|\textbf{J}^{\tau}_{\gamma}\|^{2}$. The former can be bounded by using the
expression for $\textbf{J}_{\gamma}^{\ell}$ (cf. 49) as follows:

$\displaystyle\|\textbf{J}_{\gamma}^{\ell}\Psi_{0}\|^{2}$
$\displaystyle\leq\big{\|}(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\ell}-\ell(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\ell}\big{\|}^{2}\|\Delta\textbf{v}_{0}\|^{2}+\big{\|}(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\ell}-\ell(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime})^{\ell-1}\big{\|}^{2}\|\Delta\textbf{x}_{0}\|^{2}$
$\displaystyle\qquad+\alpha^{2}\left\|\left(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime}\right)^{\ell}\right\|^{2}\|\Delta\textbf{y}_{0}\|^{2}$
$\displaystyle\leq
2(1+\ell^{2})(\|\Delta\textbf{v}_{0}\|^{2}+\|\Delta\textbf{x}_{0}\|^{2}+\alpha^{2}\|\Delta\textbf{y}_{0}\|^{2})$
$\displaystyle\leq 2(1+\tau^{2})\|\Psi_{0}\|^{2}$

where the second inequality is due to
$\left\|\left(\bar{\textbf{I}}_{n}-\gamma\textbf{Q}^{\prime}\right)^{\ell}\right\|^{2}\leq
1$ and the last inequality is due to $\ell<\tau$. ∎

To conclude, we provide the proof of (65).

Claim:
$\|(i+1)\bar{\mathbf{Q}}^{i+1}\bar{\textbf{I}}_{n}-i\bar{\mathbf{Q}}^{i}\bar{\textbf{I}}_{n}\|^{2}\leq
4$.

###### Proof.

We have

$\displaystyle\|(i+1)\bar{\mathbf{Q}}^{i+1}\bar{\textbf{I}}_{n}-i\bar{\textbf{Q}}^{i}\bar{\textbf{I}}_{n}\|^{2}$
$\displaystyle\leq\|(i+1)\bar{\mathbf{Q}}^{i+1}-i\bar{\textbf{Q}}^{i}\|^{2}\|\bar{\textbf{I}}_{n}\|^{2}$
$\displaystyle\leq\max_{j\in[n]}|(i+1)(1-\gamma(1-\lambda_{j})^{i+1}-i(1-\gamma(1-\lambda_{j})^{i}|^{2}$
$\displaystyle=\big{|}(1+i)(1-\gamma(1-\bar{\lambda}))^{i+1}-i(1-\gamma(1-\bar{\lambda}))^{i}\big{|}^{2}\,\,(\text{for
some }\bar{\lambda})$
$\displaystyle=\big{|}(1-\gamma(1-\bar{\lambda}))^{i+1}+i(1-\gamma(1-\bar{\lambda}))^{i}(1-\gamma(1-\bar{\lambda})-1)\big{|}^{2}$
$\displaystyle=|(1-\gamma(1-\bar{\lambda}))^{i+1}-i\gamma(1-\bar{\lambda})(1-\gamma(1-\bar{\lambda}))^{i}|^{2}$
$\displaystyle\leq
2|(1-\gamma(1-\bar{\lambda}))|^{2i+2}+2\gamma^{2}(1-\bar{\lambda})^{2}\big{(}\underbrace{i(1-\gamma(1-\bar{\lambda}))^{i}}_{\leq\frac{1}{\gamma(1-\bar{\lambda})}}\big{)}^{2}$
$\displaystyle\leq 4$

where the second inequality is due to $\|\bar{\textbf{I}}_{n}\|\leq 1$ and the
last inequality is due to $\gamma(1-\bar{\lambda})\in[0,1]$. ∎

## Appendix IV: Proof of Lemma 4

###### Proof.

We begin by defining the following quantities, for any $t\geq\tau$,

$A_{t}\stackrel{{\scriptstyle\rm
def}}{{=}}\frac{1}{\tau}\sum_{i=t-\tau}^{t-1}a_{i}\quad\text{and}\quad
E_{t}\stackrel{{\scriptstyle\rm def}}{{=}}\sum_{i=t-\tau}^{t-1}e_{i}.$ (82)

For future reference, we note that for the index $t=k+j$ with $j<\tau\leq t$,
(16) can be expressed in terms of $A_{k+j}$ and $E_{k+j}$

$a_{k+j}\leq\rho^{\prime}a_{k+j-\tau}+bA_{k+j}+cE_{k+j}+r$ (83)

Step (i): We first prove a recursive relation for $A_{k+\tau}$ in terms of
$A_{k}$ for $k\geq\tau$ and $E_{k+i}$ for $0\leq i\leq\tau-1$. We begin by
considering $A_{k+j}$ for any $j<\tau$,

$\displaystyle A_{k+j}$
$\displaystyle=\frac{1}{\tau}\left((a_{k+j-\tau}+\cdots
a_{k-1})+(a_{k}+\cdots+a_{k+j-1})\right)$
$\displaystyle=\frac{1}{\tau}\left(\sum_{i=j}^{\tau-1}a_{k+i-\tau}+\sum_{i=0}^{j-1}a_{k+i}\right).$

By (83) (with $j=i$), substituting for $a_{k+i}$ in the second summation
above,

$\displaystyle A_{k+j}$
$\displaystyle\leq\frac{1}{\tau}\left(\sum_{i=j}^{\tau-1}a_{k+i-\tau}+\sum_{i=0}^{j-1}\rho^{\prime}a_{k+i-\tau}\right)+\frac{b}{\tau}\sum_{i=0}^{j-1}A_{k+i}+\frac{c}{\tau}\sum_{i=0}^{j-1}E_{k+i}+r$
$\displaystyle\leq\frac{1}{\tau}\left(a_{k-1}+\cdots+a_{k+j-\tau}+a_{k+j-\tau-1}+a_{k-\tau}\right)+\frac{b}{\tau}\sum_{i=0}^{j-1}A_{k+i}+\frac{c}{\tau}\sum_{i=0}^{j-1}E_{k+i}+r$
$\displaystyle=A_{k}+\frac{b}{\tau}\sum_{i=0}^{j-1}A_{k+i}+\frac{c}{\tau}\sum_{i=0}^{j-1}E_{k+i}+r,$

where the second inequality holds since $\rho^{\prime}<1$. Thus, if follows
for $j<\tau$,

$A_{k+j}\leq
A_{k}+\frac{b}{\tau}\sum_{i=0}^{j-1}A_{k+i}+\frac{c}{\tau}\sum_{i=0}^{j-1}E_{k+i}+r.$
(84)

By the definition of $A_{k+\tau}$ (82) and (83),

$\displaystyle A_{k+\tau}=\frac{1}{\tau}\sum_{j=0}^{\tau-1}a_{k+j}$
$\displaystyle\leq\frac{1}{\tau}\sum_{j=0}^{\tau-1}\left(\rho^{\prime}a_{k+j-\tau}+bA_{k+j}+cE_{k+j}+r\right)$
(85)
$\displaystyle=\rho^{\prime}A_{k}+\frac{b}{\tau}\sum_{j=0}^{\tau-1}A_{k+j}+\frac{c}{\tau}\sum_{j=0}^{\tau-1}E_{k+j}+r$
$\displaystyle=\rho^{\prime}A_{k}+\frac{b}{\tau}A_{k+\tau-1}+\frac{b}{\tau}\sum_{j=0}^{\tau-2}A_{k+j}+\frac{c}{\tau}\sum_{j=0}^{\tau-2}E_{k+j}+\frac{c}{\tau}E_{k+\tau-1}+r,$

Next, by (84) with $j=\tau-1$ and $b<\rho^{\prime}/4$, it follows that

$\displaystyle A_{k+\tau}$
$\displaystyle\leq\rho^{\prime}A_{k}+\frac{b}{\tau}A_{k+\tau-1}+\frac{b}{\tau}\sum_{j=0}^{\tau-2}A_{k+j}+\frac{c}{\tau}\sum_{j=0}^{\tau-2}E_{k+j}+\frac{c}{\tau}E_{k+\tau-1}+r$
$\displaystyle\leq\rho^{\prime}A_{k}+\frac{b}{\tau}\left(A_{k}+\frac{b}{\tau}\sum_{j=0}^{\tau-2}A_{k+j}+\frac{c}{\tau}\sum_{j=0}^{\tau-2}E_{k+j}+r\right)$
$\displaystyle\qquad\qquad+\frac{b}{\tau}\sum_{j=0}^{\tau-2}A_{k+j}+\frac{c}{\tau}\sum_{j=0}^{\tau-2}E_{k+j}+\frac{c}{\tau}E_{k+\tau-1}+r$
$\displaystyle\leq\rho^{\prime}\left(1+\frac{1}{4\tau}\right)A_{k}+\left(1+\frac{b}{\tau}\right)\left(\frac{b}{\tau}\sum_{j=0}^{\tau-2}A_{k+j}+\frac{c}{\tau}\sum_{j=0}^{\tau-2}E_{k+j}+r\right)+\frac{c}{\tau}E_{k+\tau-1}.$

Recursive application of the above, over $j$ for $1\leq j\leq\tau-1$ yields
the following inequality

$\displaystyle A_{k+\tau}$
$\displaystyle\leq\rho^{\prime}\Bigg{(}1+\frac{1}{4\tau}\Bigg{)}^{\tau-1}A_{k}+\frac{c}{\tau}\sum_{j=0}^{\tau-1}\Big{(}1+\frac{b}{\tau}\Big{)}^{\tau-j-1}E_{k+j}+\Big{(}1+\frac{b}{\tau}\Big{)}^{\tau-1}r$
(86)
$\displaystyle\leq(1-\rho)A_{k}+\frac{2c}{\tau}\sum_{j=0}^{\tau-1}E_{k+j}+2r,$

where $b\leq 1/4$,
$\left(1+\frac{b}{\tau}\right)^{p}\leq\left(1+\frac{1}{4\tau}\right)^{p}\leq\exp(1/4)\leq
2$ for any $p\leq\tau$ and $2\rho^{\prime}=1-\rho$. Next, recall (83) with
$j=\tau$:

$\displaystyle a_{k+\tau}$
$\displaystyle\leq\rho^{\prime}a_{k}+bA_{k+\tau}+c\sum_{j=0}^{\tau-1}e_{k+j}+r$
(87)
$\displaystyle\stackrel{{\scriptstyle(\ref{majineq})}}{{\leq}}\rho^{\prime}a_{k}+b(1-\rho)A_{k}+\frac{2bc}{\tau}\sum_{j=0}^{\tau-1}E_{k+j}+c\sum_{j=0}^{\tau-1}e_{k+j}+(2b+1)r$
$\displaystyle\leq\frac{1}{2}(1-\rho)a_{k}+\frac{\rho}{4}(1-\rho)A_{k}+c\sum_{j=0}^{\tau-1}\Big{(}\frac{1}{\tau}E_{k+j}+e_{k+j}\Big{)}+2r,$

where we have used the fact that $\rho^{\prime}=(1-\rho)/2$,
$b\leq\rho^{\prime}/4<\rho/4$ for $\rho^{\prime}\in(0,1/4]$ to get the last
inequality. Adding, (86) and (87),

$\displaystyle A_{k+\tau}+a_{k+\tau}$
$\displaystyle\leq(1-\rho)\left(1+\frac{\rho}{4}\right)(A_{k}+a_{k})+\frac{3c}{\tau}\sum_{j=0}^{\tau-1}E_{k+j}+c\sum_{j=0}^{\tau-1}e_{k+j}+4r$
(88)
$\displaystyle\leq\left(1-\frac{3\rho}{4}\right)(A_{k}+a_{k})+c\sum_{j=0}^{\tau-1}\left(\frac{3}{\tau}E_{k+j}+e_{k+j}\right)+4r.$

Step (ii): In this step, we establish a descent relation for $A_{t}+a_{t}$.
With $k=(m-1)\tau$ for any integer $m\geq 2$, (88) can be expressed as

$\displaystyle A_{m\tau}+a_{m\tau}$
$\displaystyle\leq\left(1-\frac{3\rho}{4}\right)\left(A_{(m-1)\tau}+a_{(m-1)\tau}\right)+c\sum_{i=0}^{\tau-1}\left(\frac{3}{\tau}E_{(m-1)\tau+i}+e_{(m-1)\tau+i}\right)+4r$
(89)
$\displaystyle\leq\left(1-\frac{3\rho}{4}\right)^{m-1}\left(A_{\tau}+a_{\tau}\right)+c\sum_{j=1}^{m-1}\left(1-\frac{3\rho}{4}\right)^{(m-j-1)}\sum_{i=0}^{\tau-1}\left(\frac{3}{\tau}E_{j\tau+i}+e_{j\tau+i}\right)$
$\displaystyle+4r\sum_{j=0}^{m-1}\left(1-\frac{3\rho}{4}\right)^{j}$

Let $t=m\tau$ and $m\geq 2$. To bound the summation in (89), we note that

$\displaystyle\left(1-\frac{3\rho}{4}\right)^{m-j-1}$
$\displaystyle=\left(1-\frac{3\rho}{4}\right)^{-1}\left(1-\frac{3\rho}{4}\right)^{\frac{t-j\tau}{\tau}}\leq
c^{\prime}\left(1-\frac{3\rho}{4\tau}\right)^{t-j\tau}$

where $c^{\prime}:=\left(1-\frac{3\rho}{4}\right)^{-1}$, $t=m\tau$ and
$(1-x)^{a}\leq 1-ax$ for $a,x\in[0,1]$. Thus, it follows that

$\displaystyle\sum_{j=1}^{m-1}\left(1-\frac{3\rho}{4}\right)^{(m-j-1)}\sum_{i=0}^{\tau-1}\left(\frac{3}{\tau}E_{j\tau+i}+e_{j\tau+i}\right)$
$\displaystyle\leq
c^{\prime}\sum_{j=1}^{m-1}\left(1-\frac{3\rho}{4\tau}\right)^{t-j\tau}\sum_{i=0}^{\tau-1}\left(\frac{3}{\tau}E_{j\tau+i}+e_{j\tau+i}\right)$
(90) $\displaystyle\leq
c^{\prime}\sum_{j=1}^{m-1}\sum_{i=0}^{\tau-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-{j\tau-i}}\left(\frac{3}{\tau}E_{j\tau+i}+e_{j\tau+i}\right)$
$\displaystyle\leq
c^{\prime}\sum_{p=\tau}^{t-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-p}\left(\frac{3}{\tau}E_{p}+e_{p}\right),$

where $\left(1-3\rho/4\tau\right)^{-i}\geq 1$ since $\rho<1$ and the index
$p:=j\tau+i$. To bound the term involving $E_{p}$ in the summation in (90), it
follows by (82)

$\displaystyle\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-p}E_{p}\leq\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-p}\sum_{i=p-\tau}^{p-1}e_{i}$
$\displaystyle\leq\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{-\tau}\sum_{i=p-\tau}^{p-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-i}e_{i}$
$\displaystyle\leq\Big{(}1+\frac{3\rho}{4\tau}\Big{)}^{\tau}\sum_{i=p-\tau}^{p-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-i}e_{i}$
$\displaystyle\leq
3\sum_{i=p-\tau}^{p-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-i}e_{i},$

where the second inequality follows due to $(1-x)^{-1}<1+x$ for $x\in(0,1)$
and the last inequality follows due to
$\left(1+3\rho/4\tau\right)^{\tau}\leq\exp(3\rho/4)\leq 3$ for $\rho<1$.
Summing the above for $p=\tau$ to $t-1$

$\displaystyle\sum_{p=\tau}^{t-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-p}E_{p}$
$\displaystyle\leq
3\sum_{p=\tau}^{t-1}\sum_{i=p-\tau}^{p-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-i}e_{i}$
$\displaystyle=3\left(\sum_{i=t-\tau-1}^{t-2}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-i}e_{i}+\sum_{i=t-\tau-2}^{t-3}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-i}e_{i}+\cdots+\sum_{i=0}^{\tau-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-i}e_{i}\right)$
$\displaystyle\leq
3\tau\sum_{p=0}^{t-2}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-p}e_{p}.$ (91)

Substituting (Proof.) into (90),

$\displaystyle\sum_{j=1}^{m-1}\left(1-\frac{3\rho}{4}\right)^{(m-j-1)}\sum_{i=0}^{\tau-1}\left(\frac{3}{\tau}E_{j\tau+i}+e_{j\tau+i}\right)$
$\displaystyle\leq
10c^{\prime}\sum_{p=0}^{t-1}\left(1-\frac{3\rho}{4\tau}\right)^{t-p}e_{p}$
(92) $\displaystyle\leq
40\sum_{p=0}^{t-1}\left(1-\frac{3\rho}{4\tau}\right)^{t-p}e_{p},$

where for $\rho<1$ and $c^{\prime}:=\left(1-3\rho/4\right)^{-1}$ it follows
that $c^{\prime}\leq 4$. Substituting (92) into (89), if $t=m\tau$ and $m\geq
2$,

$\displaystyle a_{t}\leq A_{t}+a_{t}$
$\displaystyle\leq\Big{(}1-\frac{3\rho}{4}\Big{)}^{m-1}(A_{\tau}+a_{\tau})+40c\sum_{j=0}^{t-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-j}e_{j}+4r\sum_{j=0}^{m-1}\left(1-\frac{3\rho}{4}\right)^{j}$
(93)
$\displaystyle\leq\Big{(}1-\frac{3\rho}{4}\Big{)}^{\frac{t}{\tau}-1}(A_{\tau}+a_{\tau})+40c\sum_{j=0}^{t-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-j}e_{j}+\frac{16r}{3\rho},$
$\displaystyle\leq\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-\tau}(A_{\tau}+a_{\tau})+40c\sum_{j=0}^{t-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-j}e_{j}+\frac{16r}{3\rho},$

where we have used $(1-x)^{\frac{1}{\tau}}<1-\frac{x}{\tau}$ for $x\in[0,1]$
and $\tau\in\mathbb{N}$ to get the last inequality. For the case where
$t=m\tau+\ell$, $m\geq 2$ and $\ell<\tau$, the above bound is

$\displaystyle a_{t}$
$\displaystyle\leq\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-\tau-\ell}(A_{\tau+\ell}+a_{\tau+\ell})+40c\sum_{j=\ell}^{t-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-j}e_{j}+\frac{16r}{3\rho}$
(94) $\displaystyle\leq
5\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t}(A_{\tau+\ell}+a_{\tau+\ell})+40c\sum_{j=\ell}^{t-1}\Big{(}1-\frac{3\rho}{4\tau}\Big{)}^{t-j}e_{j}+\frac{16r}{3\rho},$

where the last inequality holds due to
$\left(1-\frac{3\rho}{4\tau}\right)^{-\ell-\tau}<\exp\left(3\rho/2\right)<5$
for $\ell<\tau$.

Step (iii): In this step, we use (16) to bound the term
$A_{\tau+\ell}+a_{\tau+\ell}$ in (94) where $\ell<\tau$. The argument is
similar to the one employed in Step (i) with appropriate modifications. By
(16), for $t=j$ and $j<\tau$,

$a_{j}\leq\rho^{\prime\prime}a_{0}+\frac{b}{\tau}\sum_{i=0}^{j-1}a_{i}+c\sum_{i=0}^{j-1}e_{i}+r.$
(95)

Note, by (16) and $\rho^{\prime}<1$, (95) holds for $\tau\leq j<2\tau$ with a
larger $r$,

$\displaystyle a_{j}$
$\displaystyle\leq\rho^{\prime}a_{j-\tau}+\frac{b}{\tau}\sum_{i=j-\tau}^{j-1}a_{i}+c\sum_{i=j-\tau}^{j-1}e_{i}+r$
(96)
$\displaystyle\leq\rho^{\prime}\left(\rho^{\prime\prime}a_{0}+\frac{b}{\tau}\sum_{i=0}^{j-\tau-1}a_{i}+c\sum_{i=0}^{j-\tau-1}e_{i}+r\right)+\frac{b}{\tau}\sum_{i=j-\tau}^{j-1}a_{i}+c\sum_{i=j-\tau}^{j-1}e_{i}+r$
$\displaystyle\leq\rho^{\prime\prime}a_{0}+\frac{b}{\tau}\sum_{i=0}^{j-1}a_{i}+c\sum_{i=0}^{j-1}e_{j}+2r.$

Recursive application of (96), over $j$ for $1\leq j<2\tau$ yields

$\displaystyle a_{j}$
$\displaystyle\leq\left(1+\frac{b}{\tau}\right)^{j-1}\rho^{\prime\prime}a_{0}+c\sum_{i=0}^{j-1}\left(1+\frac{b}{\tau}\right)^{j-i-1}e_{i}+2\left(1+\frac{b}{\tau}\right)^{j-1}r$
$\displaystyle\leq 2\rho^{\prime\prime}a_{0}+2c\sum_{i=0}^{j-1}e_{i}+4r,\qquad
j<2\tau$ (97)

where the inequality holds due to the fact that
$\left(1+b/\tau\right)^{p}\leq\exp(pb/\tau)\leq\exp(2b)<2$ for $p<2\tau$.
Next, by (Proof.) we bound $A_{\tau+\ell}$ for $\tau+\ell<2\tau$

$\displaystyle A_{\tau+\ell}=\frac{1}{\tau}\sum_{j=\ell}^{\tau+\ell-1}a_{j}$
$\displaystyle\leq\frac{1}{\tau}\sum_{j=\ell}^{\tau+\ell-1}\left(2\rho^{\prime\prime}a_{0}+2c\sum_{i=0}^{j-1}e_{i}+4r\right)$
(98)
$\displaystyle\leq\left(2\rho^{\prime\prime}a_{0}+2c\sum_{i=0}^{\tau+\ell-1}e_{i}+4r\right)\left(\frac{1}{\tau}\sum_{j=\ell}^{\tau+\ell-1}1\right)$
$\displaystyle=2\rho^{\prime\prime}a_{0}+2c\sum_{i=0}^{\tau+\ell-1}e_{i}+4r.$

Finally, adding (Proof.) with $j=\tau+\ell$ and (98) gives

$\displaystyle A_{\tau+\ell}+a_{\tau+\ell}$ $\displaystyle\leq
4\rho^{\prime\prime}a_{0}+4c\sum_{i=0}^{\tau+\ell-1}e_{i}+4r.$ (99)

Substituting for $A_{\tau+\ell}+a_{\tau+\ell}$ in (94) using the above
inequality completes the proof for any $t\geq 2\tau$. For $t<2\tau$, we have
from (Proof.) with $j=t$ and the fact that
$\left(1-\frac{3\rho}{4\tau}\right)^{-t}\leq 2$ for any $t<2\tau$,

$\displaystyle a_{t}$ $\displaystyle\leq
2\rho^{\prime\prime}a_{0}+2c\sum_{i=0}^{t-1}e_{i}+4r$ $\displaystyle\leq
4\rho^{\prime\prime}\left(1-\frac{3\rho}{4\tau}\right)^{t}a_{0}+4c\sum_{i=0}^{t-1}\left(1-\frac{3\rho}{4\tau}\right)^{t-i}e_{i}+8\left(1-\frac{3\rho}{4\tau}\right)^{t}r,$

implying that (17) also holds for any $t<2\tau$. ∎

## References

  * [1] J. Tsitsiklis, D. Bertsekas, and M. Athans, “Distributed asynchronous deterministic and stochastic gradient optimization algorithms,” _IEEE transactions on automatic control_ , vol. 31, no. 9, pp. 803–812, 1986.
  * [2] J. N. Tsitsiklis, “Problems in decentralized decision making and computation.” Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, Tech. Rep., 1984.
  * [3] C. Iakovidou and E. Wei, “S-near-dgd: A flexible distributed stochastic gradient method for inexact communication,” _IEEE Transactions on Automatic Control_ , 2022.
  * [4] A. Koloskova, T. Lin, and S. U. Stich, “An improved analysis of gradient tracking for decentralized machine learning,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 11 422–11 435, 2021.
  * [5] W. Shi, Q. Ling, G. Wu, and W. Yin, “Extra: An exact first-order algorithm for decentralized consensus optimization,” _SIAM Journal on Optimization_ , vol. 25, no. 2, pp. 944–966, 2015.
  * [6] A. Nedic, A. Olshevsky, and W. Shi, “Achieving geometric convergence for distributed optimization over time-varying graphs,” _SIAM Journal on Optimization_ , vol. 27, no. 4, pp. 2597–2633, 2017.
  * [7] K. Yuan, W. Xu, and Q. Ling, “Can primal methods outperform primal-dual methods in decentralized dynamic optimization?” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 4466–4480, 2020.
  * [8] G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” _IEEE Transactions on Control of Network Systems_ , vol. 5, no. 3, pp. 1245–1260, 2017.
  * [9] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, “A unified theory of decentralized sgd with changing topology and local updates,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 5381–5393.
  * [10] S. Pu and A. Nedić, “Distributed stochastic gradient tracking methods,” _Mathematical Programming_ , vol. 187, no. 1, pp. 409–457, 2021.
  * [11] A. Reisizadeh, A. Mokhtari, H. Hassani, and R. Pedarsani, “An exact quantized decentralized gradient descent algorithm,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 19, pp. 4934–4947, 2019.
  * [12] C. Iakovidou and E. Wei, “S-near-dgd: A flexible distributed stochastic gradient method for inexact communication,” _IEEE Transactions on Automatic Control_ , 2022.
  * [13] T. T. Doan, S. T. Maguluri, and J. Romberg, “Convergence rates of distributed gradient methods under random quantization: A stochastic approximation approach,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 10, pp. 4469–4484, 2020.
  * [14] R. L. Cavalcante and S. Stanczak, “A distributed subgradient method for dynamic convex optimization problems under noisy information exchange,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 7, no. 2, pp. 243–256, 2013.
  * [15] K. Srivastava and A. Nedic, “Distributed asynchronous constrained stochastic optimization,” _IEEE journal of selected topics in signal processing_ , vol. 5, no. 4, pp. 772–790, 2011.
  * [16] C.-S. Lee, N. Michelusi, and G. Scutari, “Finite rate quantized distributed optimization with geometric convergence,” in _2018 52nd Asilomar Conference on Signals, Systems, and Computers_. IEEE, 2018, pp. 1876–1880.
  * [17] T. T. Doan, S. T. Maguluri, and J. Romberg, “Fast convergence rates of distributed subgradient methods with adaptive quantization,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 5, pp. 2191–2205, 2020.
  * [18] I. D. Schizas, A. Ribeiro, and G. B. Giannakis, “Consensus in ad hoc wsns with noisy links—part i: Distributed estimation of deterministic signals,” _IEEE Transactions on Signal Processing_ , vol. 56, no. 1, pp. 350–364, 2007\.
  * [19] S. M. Shah and V. S. Borkar, “Distributed stochastic approximation with local projections,” _SIAM Journal on Optimization_ , vol. 28, no. 4, pp. 3375–3401, 2018.
  * [20] V. S. Borkar and S. M. Shah, “Distributed algorithms: Tsitsiklis and beyond,” in _2018 Information Theory and Applications Workshop (ITA)_. IEEE, 2018, pp. 1–9.
  * [21] S. M. Shah, L. Su, and V. K. Lau, “Robust federated learning over noisy fading channels,” _IEEE Internet of Things Journal_ , vol. 10, no. 9, pp. 7993–8013, 2022.
  * [22] K. Srivastava, A. Nedić, and D. M. Stipanović, “Distributed constrained optimization over noisy networks,” in _49th IEEE Conference on Decision and Control (CDC)_. IEEE, 2010, pp. 1945–1950.
  * [23] ——, “Distributed constrained optimization over noisy networks,” in _49th IEEE Conference on Decision and Control (CDC)_. IEEE, 2010, pp. 1945–1950.
  * [24] X. Liu, Y. Li, R. Wang, J. Tang, and M. Yan, “Linear convergent decentralized optimization with compression,” _arXiv preprint arXiv:2007.00232_ , 2020\.
  * [25] Y. Liao, Z. Li, K. Huang, and S. Pu, “A compressed gradient tracking method for decentralized optimization with linear convergence,” _IEEE Transactions on Automatic Control_ , vol. 67, no. 10, pp. 5622–5629, 2022.
  * [26] D. Kovalev, A. Koloskova, M. Jaggi, P. Richtarik, and S. Stich, “cs1,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2021, pp. 4087–4095.
  * [27] Z. Li, W. Shi, and M. Yan, “A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 17, pp. 4494–4506, 2019.
  * [28] P. Di Lorenzo and G. Scutari, “Next: In-network nonconvex optimization,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 2, no. 2, pp. 120–136, 2016.
  * [29] H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu, “D2 : Decentralized training over decentralized data,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 4848–4856.
  * [30] A. Nedić, A. Olshevsky, W. Shi, and C. A. Uribe, “Geometrically convergent distributed optimization with uncoordinated step-sizes,” in _2017 American Control Conference (ACC)_. IEEE, 2017, pp. 3950–3955.
  * [31] R. Xin, A. K. Sahu, U. A. Khan, and S. Kar, “Distributed stochastic optimization with gradient tracking over strongly-connected networks,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_. IEEE, 2019, pp. 8353–8358.
  * [32] S. Lu, X. Zhang, H. Sun, and M. Hong, “Gnsd: A gradient-tracking based nonconvex stochastic algorithm for decentralized optimization,” in _2019 IEEE Data Science Workshop (DSW)_. IEEE, 2019, pp. 315–321.
  * [33] B. Li, S. Cen, Y. Chen, and Y. Chi, “Communication-efficient distributed optimization in networks with gradient tracking and variance reduction,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2020, pp. 1662–1672.
  * [34] J. Zhang and K. You, “Decentralized stochastic gradient tracking for non-convex empirical risk minimization,” _arXiv preprint arXiv:1909.02712_ , 2019.
  * [35] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, “A unified theory of decentralized sgd with changing topology and local updates,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 5381–5393.
  * [36] D. R. Pauluzzi and N. C. Beaulieu, “A comparison of snr estimation techniques for the awgn channel,” _IEEE Transactions on communications_ , vol. 48, no. 10, pp. 1681–1691, 2000.
  * [37] S. Stein, “Fading channel issues in system engineering,” _IEEE Journal on selected areas in communications_ , vol. 5, no. 2, pp. 68–89, 1987.
  * [38] T. S. Rappaport, _Wireless communications: Principles and practice_. Pearson Education India, 2010.
  * [39] D. Yuan, S. Xu, H. Zhao, and L. Rong, “Distributed dual averaging method for multi-agent optimization with quantized communication,” _Systems & Control Letters_, vol. 61, no. 11, pp. 1053–1061, 2012.
  * [40] L. M. Nguyen, P. H. Nguyen, P. Richtárik, K. Scheinberg, M. Takác, and M. van Dijk, “New convergence aspects of stochastic gradient algorithms,” _JMLR_ , vol. 20, pp. 1–49, 2019.
  * [41] L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” _Systems & Control Letters_, vol. 53, no. 1, pp. 65–78, 2004.
  * [42] Y. Nesterov, “Introductory lectures on convex programming volume i: Basic course,” _Lecture notes_ , vol. 3, no. 4, p. 5, 1998.