$\frac{\partial\operatorname{tr}BQ_{uv}}{\partial\bar{x}_{ij}}=-\begin{bmatrix}Q_{0v}BQ_{u1}XJ^{-L}\end{bmatrix}_{ij}-\begin{bmatrix}Q_{1v}BQ_{u0}XJ^{L}\end{bmatrix}_{ij}.$

Let us focus on the second term at the right hand side of Inequality (29).
Observing that
${{\mathbb{E}}}[x_{i_{1}j_{1}}\bar{x}_{i_{2}j_{2}}]=n^{-1}[R_{j_{1}-j_{2}}]_{i_{1},i_{2}}$,
and recalling the expression of the block-Toeplitz matrix ${\mathcal{R}}$
given by Equation (11), we have

$\displaystyle\sum_{i_{1},i_{2}\in[N]}\sum_{j_{1},j_{2}\in[n]}{{\mathbb{E}}}\Bigl{[}\frac{\partial\overline{\operatorname{tr}BQ_{uv}}}{\partial\bar{x}_{i_{1}j_{1}}}{{\mathbb{E}}}[x_{i_{1}j_{1}}\bar{x}_{i_{2}j_{2}}]\frac{\partial\operatorname{tr}BQ_{uv}}{\partial\bar{x}_{i_{2}j_{2}}}\Bigr{]}$
$\displaystyle\leq
2{{\mathbb{E}}}\operatorname{vec}(Q_{0v}BQ_{u1}XJ^{-L})^{*}{\mathcal{R}}\operatorname{vec}(Q_{0v}BQ_{u1}XJ^{-L})+2{{\mathbb{E}}}\operatorname{vec}(Q_{1v}BQ_{u0}XJ^{L})^{*}{\mathcal{R}}\operatorname{vec}(Q_{1v}BQ_{u0}XJ^{L})$
$\displaystyle\leq\frac{2{\boldsymbol{M}}}{n}\left({{\mathbb{E}}}\|Q_{0v}BQ_{u1}XJ^{-L}\|_{\text{HS}}^{2}+{{\mathbb{E}}}\|Q_{1v}BQ_{u0}XJ^{L}\|_{\text{HS}}^{2}\right)$
$\displaystyle\leq\frac{4{\boldsymbol{M}}\|B\|^{2}}{(\Im\eta)^{4}n}{{\mathbb{E}}}\|X\|_{\text{HS}}^{2}$
$\displaystyle\leq\frac{4\boldsymbol{\gamma}_{\sup}{\boldsymbol{M}}^{2}\|B\|^{2}}{(\Im\eta)^{4}}.$

The first term at the right hand side of Inequality (29) is treated similarly,
leading to the bound given in the statement, and the proof is complete. ∎

In order to establish the convergence (4), using Proposition 29 and the Borel-
Cantelli lemma, it will be enough to show that

$\forall\eta\in\mathbb{C}_{+},\quad\frac{1}{2N}\operatorname{tr}D^{(N)}\left({{\mathbb{E}}}Q^{(N)}(z,\eta)-G^{(N)}(z,\eta)\right)\xrightarrow[N\to\infty]{}0.$
(31)

Following the general canvas of [28], we approximate our process
$\boldsymbol{x}^{(N)}$ by a Moving Average process with a finite memory. We
shall construct from this MA process a resolvent that will be more easily
manageable than $Q^{(N)}$.

With reference to Theorem 5, first consider a discrete analogue of the
integral within the expression of ${\mathcal{F}}_{\Sigma,z}$. A
straightforward adaptation of its proof yields the following proposition and
we omit the details.

######  Proposition 30.

Let $\Sigma:{{\mathbb{T}}}\to{\mathcal{H}}_{+}^{N}$ be a continuous function,
and let $z\in\mathbb{C}$. Then, the conclusions of Theorem 5 remain true if
the function ${\mathcal{F}}_{\Sigma,z}$ there is replaced with

$\widecheck{\mathcal{F}}_{\Sigma,z}(M(\eta),\eta)=\\\
\Bigl{(}\frac{1}{n}\sum_{\ell\in[n]}\left({\mathscr{T}}((I_{2}\otimes\Sigma(e^{2\imath\pi\ell/n}))M(\eta))+\begin{bmatrix}&e^{-2\imath\pi\ell
L/n}\\\ e^{-2\imath\pi\ell
L/n}\end{bmatrix}\right)^{-1}\otimes\Sigma(e^{2\imath\pi\ell/n})-\begin{bmatrix}\eta&z\\\
\bar{z}&\eta\end{bmatrix}\otimes I_{N}\Bigr{)}^{-1}.$

Now, given an integer constant $K>0$, let us define the function
${\widehat{S}}^{(N,K)}$ on ${{\mathbb{T}}}$ as

${\widehat{S}}^{(N,K)}(e^{\imath\theta})=\frac{1}{2\pi}\int_{0}^{2\pi}F_{K}(e^{\imath(\theta-\psi)})S^{(N)}(e^{\imath\psi})\
d\psi,$

where $F_{K}$ is the Fejér kernel (see Equation (13)). This function has the
following properties:

  1. 1.

By the non-negativity of the Fejér kernel, ${\widehat{S}}^{(N,K)}$ is a
spectral density.

  2. 2.

By replacing $F_{K}(e^{\imath(\theta-\psi)})$ with the first expression of
this kernel provided by (13), and by developing the integrand above, we obtain
that ${\widehat{S}}^{(N,K)}$ is a Laurent trigonometric polynomial of the form
${\widehat{S}}^{(N,K)}(e^{\imath\theta})=\sum_{\ell=-K}^{K}e^{\imath\ell\theta}\widetilde{R}_{\ell}^{(N,K)}$.

  3. 3.

With Assumptions 1–(i) and 1–(ii), we have

$\sup_{N}\left\|{\widehat{S}}^{(N,K)}-S^{(N)}\right\|^{{\mathbb{T}}}_{\infty}\xrightarrow[K\to\infty]{}0.$
(32)

Relation (32) can be established by splitting the integral that defines
${\widehat{S}}^{(N,K)}(e^{\imath\theta})$ into two pieces as
$\int_{0}^{2\pi}=\int_{\psi:|\theta-\psi|\leq\delta}+\int_{\psi:|\theta-\psi|>\delta}$
for a properly chosen $\delta>0$, and by using the properties of the Fejér
kernel provided after Equation (13).

Consider the implicit equation

${\widehat{G}}^{(N,K)}(z,\eta)=\widecheck{\mathcal{F}}_{{\widehat{S}}^{(N,K)},z}({\widehat{G}}^{(N,K)}(z,\eta),\eta)\
\ \text{(in}\ \ \mathfrak{S}^{2N}).$

From Proposition 30, the solution ${\widehat{G}}^{(N,K)}(z,\cdot)$ exists and
is unique. The following three propositions will be proved in Section 4.3.

######  Proposition 31.

For each $\eta$ such that $\Im\eta\geq C_{\ref{hG-G}}$ with
$C_{\ref{hG-G}}=C_{\ref{hG-G}}(\boldsymbol{\gamma}_{\sup},{\boldsymbol{M}})>0$,

$\limsup_{N}\|{\widehat{G}}^{(N,K)}(z,\eta)-G^{(N)}(z,\eta)\|\xrightarrow[K\to\infty]{}0.$

Let $(\hat{x}^{(N,K)}_{k})_{k\in\mathbb{Z}}$ be a $\mathbb{C}^{N}$–valued
stationary centered Gaussian process with the spectral density
$n^{-1}{\widehat{S}}^{(N,K)}$. Define

${\widehat{X}}^{(N,K)}=\begin{bmatrix}\hat{x}^{(N,K)}_{0}&\cdots&\hat{x}^{(N,K)}_{n-1}\end{bmatrix}\
\ \text{and}\ \
{\widehat{Q}}^{(N,K)}(z,\eta)=({\boldsymbol{H}}({\widehat{X}}^{(N,K)}J^{L}({\widehat{X}}^{(N,K)})^{*}-z)-\eta
I)^{-1}.$

We then have the following proposition.

######  Proposition 32.

Fix $K>0$. Then, for an arbitrary deterministic matrix
$D^{(N)}\in\mathbb{C}^{2N\times 2N}$ with $\|D^{(N)}\|=1$, we have

$\frac{1}{N}\left|\operatorname{tr}D^{(N)}\left({{\mathbb{E}}}{\widehat{Q}}^{(N,K)}(z,\eta)-{\widehat{G}}^{(N,K)}(z,\eta)\right)\right|\leq\frac{CK}{\sqrt{N}},$

where $C>0$ depends only on $\eta,{\boldsymbol{M}}$, and
$\boldsymbol{\gamma}_{\sup}$.

We note here that the bound provided in the statement of this proposition is
not optimal but is good enough for our purpose.

######  Proposition 33.

With $D^{(N)}$ as in the previous proposition,

$\limsup_{N}\frac{1}{N}\left|\operatorname{tr}D^{(N)}\left({{\mathbb{E}}}Q^{(N)}(z,\eta)-{{\mathbb{E}}}{\widehat{Q}}^{(N,K)}(z,\eta)\right)\right|\xrightarrow[K\to\infty]{}0.$

#### Theorem 6: end of the proof.

We write

$\displaystyle\frac{1}{N}\operatorname{tr}D^{(N)}({{\mathbb{E}}}Q^{(N)}-G^{(N)})$
$\displaystyle=\frac{1}{N}\operatorname{tr}D^{(N)}({{\mathbb{E}}}Q^{(N)}-{{\mathbb{E}}}{\widehat{Q}}^{N,K})+\frac{1}{N}\operatorname{tr}D^{(N)}({{\mathbb{E}}}{\widehat{Q}}^{N,K}-{\widehat{G}}^{(N,K)})$
$\displaystyle\phantom{=}+\frac{1}{N}\operatorname{tr}D^{(N)}({\widehat{G}}^{(N,K)}-G^{(N)})$
$\displaystyle\triangleq\chi_{1}(N,K)+\chi_{2}(N,K)+\chi_{3}(N,K).$

Fix an arbitrarily small $\varepsilon>0$. Let $K_{0},N_{0}>0$ be such that, by
Propositions 33 and 31,

$|\chi_{1}(N,K_{0})|,|\chi_{3}(N,K_{0})|\leq\varepsilon\quad\text{for all}\
N\geq N_{0}\ \text{and}\ \Im\eta>C_{\ref{hG-G}}.$

By Proposition 32, $\chi_{2}(N,K_{0})\to_{N\to\infty}0$. Thus,
$(2N)^{-1}\operatorname{tr}D^{(N)}({{\mathbb{E}}}Q^{(N)}-G^{(N)})\to_{N}0$
first for $\Im\eta>C_{\ref{hG-G}}$, and hence for each $\eta\in\mathbb{C}_{+}$
by analyticity. Thus (31) is established. This completes the proof of Theorem
6.

###  4.3 Remaining proofs for Section 4.2

#### Proof of Proposition 31

Let $\bar{S}^{(N,K)}(e^{\imath\theta})={\widehat{S}}^{(N,K)}(e^{2\imath\pi
k/n})$ and $\bar{U}_{L}(e^{\imath\theta})=U_{L}(e^{2\imath\pi k/n})$ for
$\theta\in[2\pi k/n,2\pi(k+1)/n)$ be the respective stepwise continuous
versions of the functions ${\widehat{S}}^{(N,K)}$ and $U_{L}$ with step size
$2\pi/n$. Within this proof, we re-denote the function
${\mathcal{F}}_{\Sigma,z}$ defined in the statement of Theorem 5 as
${\mathcal{F}}_{\Sigma,z,U_{L}}$ to stress the dependence on $U_{L}$. With
this notation, it is obvious that
$\widecheck{\mathcal{F}}_{{\widehat{S}}^{(N,K)},z}={\mathcal{F}}_{\bar{S}^{(N,K)},z,\bar{U}_{L}}$.

In the rest of the proof, we often drop the superscripts (N) and (N,K) and the
subscript L for brevity. Given $M\in\mathfrak{S}^{2N}$, put
$A_{{\boldsymbol{S}},{\boldsymbol{U}}}(M,e^{\imath\theta})\triangleq{\mathscr{T}}((I_{2}\otimes{\boldsymbol{S}}(e^{\imath\theta}))M)+{\boldsymbol{U}}(e^{\imath\theta})$,
where $({\boldsymbol{S}},{\boldsymbol{U}})=(S,U)$ or $(\bar{S},\bar{U})$.
Write
$B_{{\boldsymbol{S}},{\boldsymbol{U}}}(M)=(2\pi)^{-1}\int_{0}^{2\pi}A_{{\boldsymbol{S}},{\boldsymbol{U}}}(M,e^{\imath\theta})^{-1}\otimes{\boldsymbol{S}}(e^{\imath\theta})d\theta$.

We also assume that $K$ is large enough so that

$\sup_{N}\|\bar{S}\|^{{\mathbb{T}}}_{\infty}\leq 2{\boldsymbol{M}}.$

By dropping the unnecessary parameters from the notations, we write

$\displaystyle G-{\widehat{G}}$
$\displaystyle={\mathcal{F}}_{S,U}(G)-{\mathcal{F}}_{\bar{S},\bar{U}}({\widehat{G}})={\mathcal{F}}_{S,U}(G)\left(B_{\bar{S},\bar{U}}({\widehat{G}})-B_{S,U}(G)\right){\mathcal{F}}_{\bar{S},\bar{U}}({\widehat{G}})$
$\displaystyle={\mathcal{F}}_{S,U}(G)\left(\frac{1}{2\pi}\int_{0}^{2\pi}\left(A_{\bar{S},\bar{U}}({\widehat{G}},e^{\imath\theta})^{-1}\otimes\bar{S}(e^{\imath\theta})-A_{S,U}(G,e^{\imath\theta})^{-1}\otimes
S(e^{\imath\theta})\right)d\theta\right){\mathcal{F}}_{\bar{S},\bar{U}}({\widehat{G}})$
$\displaystyle={\mathcal{F}}_{S,U}(G)\left(\frac{1}{2\pi}\int\left(A_{\bar{S},\bar{U}}({\widehat{G}})^{-1}\otimes\bar{S}-A_{S,U}({\widehat{G}})^{-1}\otimes
S\right.\right.$
$\displaystyle\phantom{=}\quad\quad\quad\quad\quad\quad\quad\quad\left.\left.+(A_{S,U}({\widehat{G}})^{-1}-A_{S,U}(G)^{-1})\otimes
S\right)d\theta\right){\mathcal{F}}_{\bar{S},\bar{U}}({\widehat{G}})$
$\displaystyle={\mathcal{F}}_{S,U}(G)\left(\frac{1}{2\pi}\int\left(A_{\bar{S},\bar{U}}({\widehat{G}})^{-1}\otimes(\bar{S}-S)+(A_{\bar{S},\bar{U}}({\widehat{G}})^{-1}-A_{S,U}({\widehat{G}})^{-1})\otimes
S\right.\right.$
$\displaystyle\phantom{=}\quad\quad\quad\quad\quad\quad\quad\quad\left.\left.+(A_{S,U}({\widehat{G}})^{-1}-A_{S,U}(G)^{-1})\otimes
S\right)d\theta\right){\mathcal{F}}_{{\bar{S},\bar{U}}}({\widehat{G}})$
$\displaystyle\triangleq{\mathcal{F}}_{{S,U}}(G)\left(\frac{1}{2\pi}\int(\chi_{1}+\chi_{2}+\chi_{3})d\theta\right){\mathcal{F}}_{{\bar{S},\bar{U}}}({\widehat{G}}).$

By Lemma 28, we have that
$\|{\mathscr{T}}((I_{2}\otimes{\boldsymbol{S}}(e^{\imath\theta})){\boldsymbol{G}})\|\leq
2\boldsymbol{\gamma}_{\sup}{\boldsymbol{M}}/\Im\eta$ for any of the
possibilities for ${\boldsymbol{S}}$ and for
${\boldsymbol{G}}=G,{\widehat{G}}$. Thus, for

$2\boldsymbol{\gamma}_{\sup}{\boldsymbol{M}}/\Im\eta\leq 1/2,$

we have $\|A_{{\boldsymbol{S}}}({\boldsymbol{G}},e^{\imath\theta})^{-1}\|\leq
2$. Therefore,

$\|\chi_{1}\|\leq 2\|\bar{S}-S\|^{{\mathbb{T}}}_{\infty}.$

Moreover,

$\displaystyle\chi_{2}$
$\displaystyle=(A_{\bar{S},\bar{U}}({\widehat{G}})^{-1}-A_{S,U}({\widehat{G}})^{-1})\otimes
S$
$\displaystyle=\left(A_{\bar{S},\bar{U}}({\widehat{G}})^{-1}\left({\mathscr{T}}((I_{2}\otimes(\bar{S}-S)){\widehat{G}})+U-\bar{U}\right)A_{S,U}({\widehat{G}})^{-1}\right)\otimes
S$

satisfies

$\|\chi_{2}\|\leq
4{\boldsymbol{M}}\boldsymbol{\gamma}_{\sup}(\Im\eta)^{-1}\|\bar{S}-S\|^{{\mathbb{T}}}_{\infty}+4{\boldsymbol{M}}\|U-\bar{U}\|$

for the same values of $\eta$. By mimicking the calculation that lead to
Inequality (28), we obtain

$\|\chi_{3}\|\leq\frac{4}{(\Im\eta)^{2}}\boldsymbol{\gamma}_{\sup}{\boldsymbol{M}}^{2}\|G-{\widehat{G}}\|.$

Using the inequality
$\|{\mathcal{F}}_{{\boldsymbol{S}}}({\boldsymbol{G}})\|\leq 1/(\Im\eta)$, we
thus arrive at

$\left(1-\frac{4\boldsymbol{\gamma}_{\sup}{\boldsymbol{M}}^{2}}{(\Im\eta)^{4}}\right)\|G^{(N)}-{\widehat{G}}^{(N,K)}\|\\\
\leq\frac{2}{(\Im\eta)^{2}}\left(1+\frac{4\boldsymbol{\gamma}_{\sup}{\boldsymbol{M}}}{\Im\eta}\right)\|\bar{S}^{(N,K)}-S^{(N)}\|^{{\mathbb{T}}}_{\infty}+\frac{4\boldsymbol{M}}{(\Im\eta)^{2}}\|\bar{U}_{L}-U_{L}\|^{{\mathbb{T}}}_{\infty}.$

Thus, if
$\Im\eta>(8\boldsymbol{\gamma}_{\sup}{\boldsymbol{M}}^{2})^{1/4}\vee(4\boldsymbol{\gamma}_{\sup}\boldsymbol{M})$,
then

$\|G^{(N)}-{\widehat{G}}^{(N,K)}\|\leq
C\|\bar{S}^{(N,K)}-S^{(N)}\|^{{\mathbb{T}}}_{\infty}+C^{\prime}\|\bar{U}_{L}-U_{L}\|^{{\mathbb{T}}}_{\infty}$

for some constants $C,C^{\prime}>0$. Now the proof can be completed by using
the convergence (32).

#### Proof of Proposition 32

From now on, $C$ is a positive constant that depends on $\eta$,
${\boldsymbol{M}}$, and $\boldsymbol{\gamma}_{\sup}$ at most, and can change
from line to line. Recalling Properties 1 and 2 of the density
${\widehat{S}}^{(N,K)}$ that were stated in Section 4.2 above, our first step
is to apply the well-known operator version of the Fejér-Riesz theorem (see
[29, Sec. 6.6]) to ${\widehat{S}}^{(N,K)}$. This implies that for each
$(N,K)$, there exists an $N\times N$ matrix trigonometric polynomial

$P^{(N,K)}(e^{\imath\theta})=\sum_{\ell=0}^{K}e^{\imath\ell\theta}B_{\ell}^{(N,K)}$

such that
${\widehat{S}}^{(N,K)}(e^{\imath\theta})=P^{(N,K)}(e^{\imath\theta})P^{(N,K)}(e^{\imath\theta})^{*}$.

Letting $\boldsymbol{\xi}^{(N)}=(\boldsymbol{\xi}^{(N)}_{k})_{k\in\mathbb{Z}}$
be an i.i.d. process with
$\boldsymbol{\xi}^{(N)}_{k}\sim{\mathcal{N}}_{\mathbb{C}}(0,I_{N})$, the
process $(\hat{x}^{(N,K)}_{k})_{k\in\mathbb{Z}}$ that we used to construct the
resolvent ${\widehat{Q}}^{(N,K)}$ can be defined as

$\hat{x}^{(N,K)}_{k}=\frac{1}{\sqrt{n}}\sum_{\ell=0}^{K}B_{\ell}^{(N,K)}\boldsymbol{\xi}^{(N)}_{k-\ell}.$

Define the finite sequence of random vectors
$(\tilde{x}^{(N,K)}_{k})_{k\in[n]}$ as

$\tilde{x}^{(N,K)}_{k}=\frac{1}{\sqrt{n}}\sum_{\ell=0}^{K}B_{\ell}^{(N,K)}\boldsymbol{\xi}^{(N)}_{(k-\ell)\\!\\!\mod
n}$

(thus, $\tilde{x}^{(N,K)}_{k}$ is the analogue of $\hat{x}^{(N,K)}_{k}$
obtained through a circular convolution). Define

${\widetilde{X}}^{(N,K)}=\begin{bmatrix}\tilde{x}^{(N,K)}_{0}&\cdots&\tilde{x}^{(N,K)}_{n-1}\end{bmatrix}\in\mathbb{C}^{N\times
n},$

and

${\widetilde{Q}}^{(N,K)}(z,\eta)=({\boldsymbol{H}}({\widetilde{X}}^{(N,K)}J^{L}({\widetilde{X}}^{(N,K)})^{*}-z)-\eta
I)^{-1}.$

Observing that $\operatorname{rank}({\widehat{X}}-{\widetilde{X}})\leq K$, we
get

$\operatorname{rank}({\boldsymbol{H}}({\widehat{X}}J^{L}{\widehat{X}}^{*}-z)-{\boldsymbol{H}}({\widetilde{X}}J^{L}{\widetilde{X}}^{*}-z))\leq
4K.$

Thus, for each matrix $D\in\mathbb{C}^{2N\times 2N}$, the inequality

$\left|\operatorname{tr}D({\widehat{Q}}(z,\eta)-{\widetilde{Q}}(z,\eta))\right|\leq\frac{4K\|D\|}{\Im\eta}$
(33)

holds (see [34, Lemma 2.6]). We can thus work with ${\widetilde{Q}}$ in place
of ${\widehat{Q}}$ for establishing Proposition 32.

For $k\in[n]$, let

$w_{k}^{(N,K)}=\frac{1}{\sqrt{n}}\sum_{\ell=0}^{n-1}e^{2\imath\pi
k\ell/n}\tilde{x}_{\ell}^{(N,K)}$

be the discrete Fourier transform of the finite sequence
$(\tilde{x}_{0},\ldots,\tilde{x}_{n-1})$, and define the matrix

$W^{(N,K)}=\begin{bmatrix}w_{0}^{(N,K)}&\cdots&w_{n-1}^{(N,K)}\end{bmatrix}={\widetilde{X}}^{(N,K)}{{\mathsf{F}}}\in\mathbb{C}^{N\times
n}$

where ${\mathsf{F}}$ is the Fourier matrix defined in (7). Since the
$\tilde{x}_{\ell}$ are built through a circular convolution, the vectors
$w_{k}$ are independent, and
$w_{k}\sim{\mathcal{N}}_{\mathbb{C}}(0,n^{-1}{\widehat{S}}(e^{2\imath\pi
k/n}))$. Recalling that $J={\mathsf{F}}\Omega{\mathsf{F}}^{*}$ with
$\Omega=\operatorname*{diag}(\omega^{\ell})_{\ell=0}^{n-1}$ and
$\omega=\exp(-2\imath\pi/n)$, we can write

${\widetilde{Q}}(z,\eta)=({\boldsymbol{H}}({\widetilde{X}}J^{L}{\widetilde{X}}^{*}-z)-\eta
I)^{-1}=({\boldsymbol{H}}(W\Omega^{L}W^{*}-z)-\eta I)^{-1}.$

The remainder of the proof will be devoted towards showing that

$\left\|{{\mathbb{E}}}{\widetilde{Q}}^{(N,K)}(z,\eta)-{\widehat{G}}^{(N,K)}(z,\eta)\right\|\leq
CN^{-1/2},$ (34)

taking advantage of the independence of the columns of $W$. This bound, used
in conjunction with the bound (33), immediately leads to the result of
Proposition 32.

The proof of Inequality (34) relies on the NP inequality that we used above,
as well as on the well-known Integration by Parts (IP) formula for Gaussian
functionals [17, 22]. Recalling the definition of the vector
${\boldsymbol{v}}$ and the functional $\varphi$ after Proposition 29 above,
the IP formula reads as

${{\mathbb{E}}}v_{k}\varphi({\boldsymbol{v}})=\sum_{\ell=0}^{n-1}\left[\Sigma\right]_{k\ell}{{\mathbb{E}}}\left[\frac{\partial\varphi({\boldsymbol{v}})}{\partial\bar{v}_{\ell}}\right].$

Write
${\widetilde{Q}}(z,\eta)=\begin{bmatrix}{\widetilde{Q}}_{00}&{\widetilde{Q}}_{01}\\\
{\widetilde{Q}}_{10}&{\widetilde{Q}}_{11}\end{bmatrix}$, and
$W=\begin{bmatrix}w_{ij}\end{bmatrix}_{i\in[N],j\in[n]}$. By reproducing
verbatim the derivation that we made to obtain the Identity (30), we have

$\frac{\partial
a^{*}{\widetilde{Q}}_{uv}b}{\partial\bar{w}_{ij}}=-\begin{bmatrix}a^{*}{\widetilde{Q}}_{u1}W\Omega^{-L}\end{bmatrix}_{j}\begin{bmatrix}{\widetilde{Q}}_{0v}b\end{bmatrix}_{i}-\begin{bmatrix}a^{*}{\widetilde{Q}}_{u0}W\Omega^{L}\end{bmatrix}_{j}\begin{bmatrix}{\widetilde{Q}}_{1v}b\end{bmatrix}_{i}.$

In the subsequent derivations, we write
${\widehat{S}}_{k}={\widehat{S}}(e^{2\imath\pi k/n})$. Let $a,b$ be two
constant vectors in $\mathbb{C}^{N}$. Write
$b=[b_{0},\ldots,b_{N-1}]^{\mathsf{T}}$, and let
$\alpha_{uv}(\ell)={{\mathbb{E}}}\begin{bmatrix}[a^{*}{\widetilde{Q}}_{uv}W]_{\ell}[W^{*}b]_{\ell}\end{bmatrix}$.
By the IP formula, we have

$\displaystyle\alpha_{uv}(\ell)$
$\displaystyle=\sum_{i\in[N]}{{\mathbb{E}}}\begin{bmatrix}[a^{*}{\widetilde{Q}}_{uv}]_{i}w_{i\ell}[W^{*}b]_{\ell}\end{bmatrix}=\frac{1}{n}\sum_{i,m\in[N]}[{\widehat{S}}_{\ell}]_{im}{{\mathbb{E}}}\frac{\partial([a^{*}{\widetilde{Q}}_{uv}]_{i}[W^{*}b]_{\ell})}{\partial\bar{w}_{m\ell}}$
$\displaystyle=\frac{1}{n}\sum_{i,m}[{\widehat{S}}_{\ell}]_{im}{{\mathbb{E}}}\Bigl{[}-[a^{*}{\widetilde{Q}}_{u1}W\Omega^{-L}]_{\ell}[{\widetilde{Q}}_{0v}]_{mi}[W^{*}b]_{\ell}-[a^{*}{\widetilde{Q}}_{u0}W\Omega^{L}]_{\ell}[{\widetilde{Q}}_{1v}]_{mi}[W^{*}b]_{\ell}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\
+[a^{*}{\widetilde{Q}}_{uv}]_{i}b_{m}\Bigr{]}$
$\displaystyle=-{{\mathbb{E}}}\Bigl{[}[a^{*}{\widetilde{Q}}_{u1}W]_{\ell}[W^{*}b]_{\ell}\omega^{-\ell
L}\frac{\operatorname{tr}{\widetilde{Q}}_{0v}{\widehat{S}}_{\ell}}{n}\Bigr{]}-{{\mathbb{E}}}\Bigl{[}[a^{*}{\widetilde{Q}}_{u0}W]_{\ell}[W^{*}b]_{\ell}\omega^{\ell
L}\frac{\operatorname{tr}{\widetilde{Q}}_{1v}{\widehat{S}}_{\ell}}{n}\Bigr{]}$
$\displaystyle\phantom{=}+\frac{{{\mathbb{E}}}[a^{*}{\widetilde{Q}}_{uv}{\widehat{S}}_{\ell}b]}{n}.$

Write
$\widetilde{qs}_{uv}(\ell)={{\mathbb{E}}}\operatorname{tr}{\widetilde{Q}}_{uv}{\widehat{S}}_{\ell}/n$.
We shall isolate the terms $\widetilde{qs}_{0v}(\ell)$ and
$\widetilde{qs}_{1v}(\ell)$ in the last display by resorting to the following
lemma.

######  Lemma 34.

The two inequalities,
$\operatorname{\mathbb{V}ar}\widetilde{qs}_{uv}(\ell)\leq C/n^{2}$, and
$\operatorname{\mathbb{V}ar}[a^{*}{\widetilde{Q}}_{uv}W]_{\ell}[W^{*}b]_{\ell}\leq
C\|a\|^{2}\|b\|^{2}/n$ hold.

###### Proof.

The first bound is obtained by repeating almost word for word the proof of
Proposition 29. To obtain the second bound, we also use the NP inequality
again. We start by writing

$\displaystyle\frac{\partial[a^{*}{\widetilde{Q}}_{uv}W]_{\ell}[W^{*}b]_{\ell}}{\partial\bar{w}_{ij}}$
$\displaystyle=\sum_{k}\frac{\partial[a^{*}{\widetilde{Q}}_{uv}]_{k}w_{k\ell}[W^{*}b]_{\ell}}{\partial\bar{w}_{ij}}$
$\displaystyle=[a^{*}{\widetilde{Q}}_{uv}W]_{\ell}b_{i}\mathbbm{1}_{j=\ell}-[a^{*}{\widetilde{Q}}_{u1}W\Omega^{-L}]_{j}[Q_{0v}W]_{i\ell}[W^{*}b]_{\ell}$
$\displaystyle\phantom{=}-[a^{*}{\widetilde{Q}}_{u0}W\Omega^{L}]_{j}[Q_{1v}W]_{i\ell}[W^{*}b]_{\ell}.$

We focus on the second term at the right hand side of Inequality (29),
treating separately the three terms at the right hand side of the last
display. Starting with the first term, we get

$\frac{1}{n}\sum_{i_{1},i_{2}\in[N]}{{\mathbb{E}}}\overline{[a^{*}{\widetilde{Q}}_{uv}W]_{\ell}b_{i_{1}}}[{\widehat{S}}_{\ell}]_{i_{1},i_{2}}{[a^{*}{\widetilde{Q}}_{uv}W]_{\ell}b_{i_{2}}}\\\
=\frac{1}{n}b^{*}{\widehat{S}}_{\ell}b\,{{\mathbb{E}}}|[a^{*}{\widetilde{Q}}_{uv}W]_{\ell}|^{2}\leq\|a\|^{2}\|b\|^{2}C/n.$

Turning to the second of these terms, we have

$\displaystyle\frac{1}{n}\sum_{i_{1},i_{2}\in[N]}\sum_{j\in[n]}{{\mathbb{E}}}|[W^{*}b]_{\ell}|^{2}\,|[a^{*}{\widetilde{Q}}_{u1}W\Omega^{-L}]_{j}|^{2}\overline{[Q_{0v}W]_{i_{1}\ell}}[{\widehat{S}}_{j}]_{i_{1},i_{2}}[Q_{0v}W]_{i_{2}\ell}$
$\displaystyle\leq\frac{{\boldsymbol{M}}}{n}{{\mathbb{E}}}|[W^{*}b]_{\ell}|^{2}\,\|a^{*}{\widetilde{Q}}_{u1}W\|^{2}\|[Q_{0v}W]_{\cdot,\ell}\|^{2}$
$\displaystyle\leq\|a\|^{2}\|b\|^{2}C/n^{2},$

where the last inequality can be obtained by applying, _e.g._ , Lemma 17 along
with standard inequalities. The third term can be handled similarly. ∎

Thanks to these bounds and to Cauchy-Schwarz inequality, we obtain the
identity

$\alpha_{uv}(\ell)=-\alpha_{u0}(\ell)\omega^{\ell
L}\widetilde{qs}_{1v}(\ell)-\alpha_{u1}(\ell)\omega^{-\ell
L}\widetilde{qs}_{0v}(\ell)+n^{-1}{{\mathbb{E}}}[a^{*}{\widetilde{Q}}_{uv}{\widehat{S}}_{\ell}b]+\varepsilon,$

with $\|\varepsilon\|\leq C\|a\|\|b\|n^{-3/2}$. This leads to the system of
equations

$\begin{bmatrix}1+\omega^{\ell L}\widetilde{qs}_{10}(\ell)&\omega^{-\ell
L}\widetilde{qs}_{00}(\ell)\\\ \omega^{\ell
L}\widetilde{qs}_{11}(\ell)&1+\omega^{-\ell
L}\widetilde{qs}_{01}(\ell)\end{bmatrix}\begin{bmatrix}\alpha_{u0}(\ell)\\\
\alpha_{u1}(\ell)\end{bmatrix}=\frac{1}{n}\begin{bmatrix}{{\mathbb{E}}}[a^{*}{\widetilde{Q}}_{u0}{\widehat{S}}_{\ell}b]\\\
{{\mathbb{E}}}[a^{*}{\widetilde{Q}}_{u1}{\widehat{S}}_{\ell}b]\end{bmatrix}+\boldsymbol{\varepsilon},$

with $\|\boldsymbol{\varepsilon}\|\leq C\|a\|\|b\|n^{-3/2}$. The matrix at the
left hand side of this expression, that we denote as $T_{\ell}$, is written as

$T_{\ell}=I_{2}+{\mathscr{T}}\left((I_{2}\otimes{\widehat{S}}_{\ell})\left({\widetilde{Q}}^{\mathsf{T}}\begin{bmatrix}&\omega^{-\ell
L}\\\ \omega^{\ell L}\end{bmatrix}\right)\right).$

Assume that $K$ is large enough so that $\|{\widehat{S}}_{\ell}\|\leq
2{\boldsymbol{M}}$ for all $\ell\in[n]$, and take $\Im\eta\geq
4\boldsymbol{\gamma}_{\sup}{\boldsymbol{M}}$. Then by Lemma 28 we get that
$\|T_{\ell}-I_{2}\|\leq 1/2$. Thus, the determinant

$d(\ell)=(1+\omega^{\ell L}\widetilde{qs}_{10}(\ell))(1+\omega^{-\ell
L}\widetilde{qs}_{01}(\ell))-\widetilde{qs}_{00}(\ell)\widetilde{qs}_{11}(\ell)$

of $T_{\ell}$ is such that $|d(\ell)|$ is bounded away from zero uniformly in
$N$ and $\ell$. Solving our system, and reusing henceforth the notations
$\varepsilon$ and $\boldsymbol{\varepsilon}$ at will, we get that

$\begin{bmatrix}\alpha_{u0}(\ell)\\\
\alpha_{u1}(\ell)\end{bmatrix}=\frac{1}{n}\frac{1}{d(\ell)}\begin{bmatrix}(1+\omega^{-\ell
L}\widetilde{qs}_{01}(\ell))&-\omega^{-\ell L}\widetilde{qs}_{00}(\ell)\\\
-\omega^{\ell L}\widetilde{qs}_{11}(\ell)&(1+\omega^{\ell
L}\widetilde{qs}_{10}(\ell))\end{bmatrix}\begin{bmatrix}{{\mathbb{E}}}[a^{*}{\widetilde{Q}}_{u0}{\widehat{S}}_{\ell}b]\\\
{{\mathbb{E}}}[a^{*}{\widetilde{Q}}_{u1}{\widehat{S}}_{\ell}b]\end{bmatrix}+\boldsymbol{\varepsilon},$
(35)

with $\|\boldsymbol{\varepsilon}\|\leq C\|a\|\|b\|n^{-3/2}$.

Now, keeping in mind the identity
${\widetilde{Q}}\Bigl{(}{\boldsymbol{H}}(W\Omega^{L}W^{*})-\begin{bmatrix}\eta&z\\\
\bar{z}&\eta\end{bmatrix}\otimes I_{N}\Bigr{)}=I$, our purpose is to find an
approximant of the matrix

${\widetilde{Q}}{\boldsymbol{H}}(W\Omega^{L}W^{*})=\begin{bmatrix}{\widetilde{Q}}_{01}W\Omega^{-L}W^{*}&{\widetilde{Q}}_{00}W\Omega^{L}W^{*}\\\
{\widetilde{Q}}_{11}W\Omega^{-L}W^{*}&{\widetilde{Q}}_{10}W\Omega^{L}W^{*}\end{bmatrix}.$

To that end, we write

${{\mathbb{E}}}[a^{*}{\widetilde{Q}}_{u0}W\Omega^{L}W^{*}b]=\sum_{\ell\in[n]}\omega^{\ell
L}\alpha_{u0}(\ell),\quad\text{and}\quad{{\mathbb{E}}}[a^{*}{\widetilde{Q}}_{u1}W\Omega^{-L}W^{*}b]=\sum_{\ell\in[n]}\omega^{-\ell
L}\alpha_{u1}(\ell),$

and we use Equation (35) to obtain

$\displaystyle\begin{bmatrix}{{\mathbb{E}}}a^{*}{\widetilde{Q}}_{u1}W\Omega^{-L}W^{*}b&{{\mathbb{E}}}a^{*}{\widetilde{Q}}_{u0}W\Omega^{L}W^{*}b\end{bmatrix}$
$\displaystyle=a^{*}{{\mathbb{E}}}\begin{bmatrix}{\widetilde{Q}}_{u0}&{\widetilde{Q}}_{u1}\end{bmatrix}\times\frac{1}{n}\sum_{\ell\in[n]}\frac{1}{d(\ell)}\begin{bmatrix}-\widetilde{qs}_{11}(\ell)&\omega^{\ell
L}+\widetilde{qs}_{01}(\ell)\\\ \omega^{-\ell
L}+\widetilde{qs}_{10}(\ell)&-\widetilde{qs}_{00}(\ell)\end{bmatrix}\otimes({\widehat{S}}_{\ell}b)+\boldsymbol{\varepsilon}$
(36)

with $\|\boldsymbol{\varepsilon}\|\leq C\|a\|\|b\|n^{-1/2}$ (note that we lost
a factor of $n^{-1}$ because of the summation $\sum_{\ell\in[n]}$). Let
$U_{L,\ell}\triangleq U_{L}(e^{2\imath\pi\ell/n})=\begin{bmatrix}&\omega^{\ell
L}\\\ \omega^{-\ell L}\end{bmatrix}$, and define the matrix

$\displaystyle C(z,\eta)$
$\displaystyle\triangleq\frac{1}{n}\sum_{\ell\in[n]}\frac{1}{d(\ell)}\begin{bmatrix}-\widetilde{qs}_{11}(\ell)&\omega^{\ell
L}+\widetilde{qs}_{01}(\ell)\\\ \omega^{-\ell
L}+\widetilde{qs}_{10}(\ell)&-\widetilde{qs}_{00}(\ell)\end{bmatrix}\otimes{\widehat{S}}_{\ell}$
$\displaystyle=\frac{1}{n}\sum_{\ell\in[n]}\left(\begin{bmatrix}\widetilde{qs}_{00}(\ell)&\widetilde{qs}_{01}(\ell)\\\
\widetilde{qs}_{10}(\ell)&\widetilde{qs}_{11}(\ell)\end{bmatrix}+U_{L,\ell}\right)^{-1}\otimes{\widehat{S}}_{\ell}$
$\displaystyle=\frac{1}{n}\sum_{\ell\in[n]}\left({\mathscr{T}}((I_{2}\otimes{\widehat{S}}_{\ell}){{\mathbb{E}}}{\widetilde{Q}})+U_{L,\ell}\right)^{-1}\otimes{\widehat{S}}_{\ell}.$

Then, Equation (36) can be rewritten as

$\displaystyle{{\mathbb{E}}}a^{*}{\widetilde{Q}}_{u1}W\Omega^{-L}W^{*}b$
$\displaystyle=a^{*}{{\mathbb{E}}}\begin{bmatrix}{\widetilde{Q}}_{u0}&{\widetilde{Q}}_{u1}\end{bmatrix}C\begin{bmatrix}b\\\
0\end{bmatrix}+\varepsilon,$
$\displaystyle{{\mathbb{E}}}a^{*}{\widetilde{Q}}_{u0}W\Omega^{L}W^{*}b$
$\displaystyle=a^{*}{{\mathbb{E}}}\begin{bmatrix}{\widetilde{Q}}_{u0}&{\widetilde{Q}}_{u1}\end{bmatrix}C\begin{bmatrix}0\\\
b\end{bmatrix}+\varepsilon^{\prime},$

with $|\varepsilon|,|\varepsilon^{\prime}|\leq C\|a\|\|b\|n^{-1/2}$. Let
$\boldsymbol{a}$ and $\boldsymbol{b}$ be two constant vectors in
$\mathbb{C}^{2N}$. Recalling the expression of
${\widetilde{Q}}{\boldsymbol{H}}(W\Omega^{L}W^{*})$ above, the last display
can be written compactly as

$\left|\boldsymbol{a}\left({{\mathbb{E}}}{\widetilde{Q}}{\boldsymbol{H}}(W\Omega^{L}W^{*})-{{\mathbb{E}}}{\widetilde{Q}}C\right)\boldsymbol{b}\right|\leq
C\|\boldsymbol{a}\|\|\boldsymbol{b}\|n^{-1/2},$

equivalently,

$\left\|{{\mathbb{E}}}{\widetilde{Q}}{\boldsymbol{H}}(W\Omega^{L}W^{*})-{{\mathbb{E}}}{\widetilde{Q}}C\right\|\leq
Cn^{-1/2}.$

Since ${{\mathbb{E}}}{\widetilde{Q}}\in\mathfrak{S}^{2N}$, it is easy to
prove, mostly by mimicking the first part of the proof of Theorem 5, that the
matrix function

$R(z,\eta)=\Bigl{(}C(z,\eta)-\begin{bmatrix}\eta&z\\\
\bar{z}&\eta\end{bmatrix}\otimes I_{N}\Bigr{)}^{-1}$

is well defined for $\eta\in\mathbb{C}\setminus{{\mathbb{R}}}$, and
$R(z,\cdot)\in\mathfrak{S}^{2N}$. In particular, $\|R(z,\eta)\|\leq 1/\Im\eta$
for $\eta\in\mathbb{C}_{+}$. We therefore have

$\displaystyle\|{{\mathbb{E}}}{\widetilde{Q}}-R\|$
$\displaystyle=\|{{\mathbb{E}}}{\widetilde{Q}}(R^{-1}-{\widetilde{Q}}^{-1})R\|=\|({{\mathbb{E}}}{\widetilde{Q}}C-{{\mathbb{E}}}{\widetilde{Q}}{\boldsymbol{H}}(W\Omega^{L}W^{*}))R\|$
$\displaystyle\leq\|({{\mathbb{E}}}{\widetilde{Q}}C-{{\mathbb{E}}}{\widetilde{Q}}{\boldsymbol{H}}(W\Omega^{L}W^{*})\|\,\|R\|$
$\displaystyle\leq Cn^{-1/2}.$

To complete the proof of Proposition 32, it remains to control the norm
$\|R-{\widehat{G}}\|$. Remembering that ${\widehat{G}}$ is defined through the
implicit equation in Proposition 31, we use the contraction property of
$\widecheck{\mathcal{F}}_{{\widehat{S}},z}(\cdot,\eta)$ to gain this control.
By mimicking the derivation that led to Inequality (28), we obtain that if $K$
is large enough so that $\|{\widehat{S}}\|^{{\mathbb{T}}}_{\infty}\leq
2{\boldsymbol{M}}$, and if $\Im\eta$ is large enough, then

$\|\widecheck{\mathcal{F}}_{{\widehat{S}},z}(M,\eta)-\widecheck{\mathcal{F}}_{{\widehat{S}},z}(M^{\prime},\eta)\|\leq\frac{1}{2}\|M-M^{\prime}\|.$

Notice that
$R=\widecheck{\mathcal{F}}_{{\widehat{S}},z}({{\mathbb{E}}}{\widetilde{Q}},\eta)$.
Therefore, if $\Im\eta$ is large enough, we have

$\|R-{\widehat{G}}\|=\|\widecheck{\mathcal{F}}_{{\widehat{S}},z}({{\mathbb{E}}}{\widetilde{Q}},\eta)-\widecheck{\mathcal{F}}_{{\widehat{S}},z}(R,\eta)+\widecheck{\mathcal{F}}_{{\widehat{S}},z}(R,\eta)-\widecheck{\mathcal{F}}_{{\widehat{S}},z}({\widehat{G}},\eta)\|\leq\frac{1}{2}\|{{\mathbb{E}}}{\widetilde{Q}}-R\|+\frac{1}{2}\|R-{\widehat{G}}\|,$

leading to

$\|R-{\widehat{G}}\|\leq\|{{\mathbb{E}}}{\widetilde{Q}}-R\|\leq Cn^{-1/2}.$

Finally
$\|{{\mathbb{E}}}{\widetilde{Q}}-{\widehat{G}}\|\leq\|{{\mathbb{E}}}{\widetilde{Q}}-R\|+\|R-{\widehat{G}}\|\leq
Cn^{-1/2}$. The proof of Proposition 32 can now be completed by combining this
bound with the inequality (33).

#### Proof of Proposition 33

We can assume that the processes $(x^{(N)}_{k})_{k}$ and
$({\hat{x}}^{(N,K)}_{k})_{k}$ that constitute the columns of the matrices
$X^{(N)}$ and ${\widehat{X}}^{(N,K)}$ respectively, are generated by applying
the filters with Fourier transforms $n^{-1/2}S^{(N)}(e^{\imath\theta})^{1/2}$
and $n^{-1/2}{\widehat{S}}^{(N,K)}(e^{\imath\theta})^{1/2}$ respectively to
the same i.i.d. process
$\boldsymbol{\xi}^{(N)}=(\boldsymbol{\xi}^{(N)}_{k})_{k\in\mathbb{Z}}$ with
$\boldsymbol{\xi}^{(N)}_{k}\sim{\mathcal{N}}_{\mathbb{C}}(0,I_{N})$. This
being the case, we have

${{\mathbb{E}}}\|x^{(N)}_{k}-\hat{x}^{(N,K)}_{k}\|^{2}=\frac{1}{n}\frac{1}{2\pi}\int_{0}^{2\pi}\|S^{(N)}(e^{\imath\theta})^{1/2}-{\widehat{S}}^{(N,K)}(e^{\imath\theta})^{1/2}\|_{\text{HS}}^{2}d\theta.$

Hence, by (32), we get that

$\sup_{N}{{\mathbb{E}}}\|x^{(N)}_{k}-\hat{x}^{(N,K)}_{k}\|^{2}\xrightarrow[K\to\infty]{}0.$

For any two square matrices $M_{1}$ and $M_{2}$ of same order, by Cauchy-
Schwarz inequality,
$|\operatorname{tr}M_{1}M_{2}|\leq\|M_{1}\|_{\text{HS}}\|M_{2}\|_{\text{HS}}$.
Thus, by the resolvent identity,

$\displaystyle\frac{1}{N^{2}}\left|\operatorname{tr}D({{\mathbb{E}}}Q(z,\eta)-{{\mathbb{E}}}{\widehat{Q}}(z,\eta))\right|^{2}$
$\displaystyle\leq\frac{1}{N^{2}}{{\mathbb{E}}}\left|\operatorname{tr}DQ(z,\eta)({\boldsymbol{H}}({\widehat{X}}J^{L}{\widehat{X}}^{*})-{\boldsymbol{H}}(XJ^{L}X^{*})){\widehat{Q}}(z,\eta)\right|^{2}$
$\displaystyle\leq\frac{1}{(\Im\eta)^{4}}\frac{1}{N}{{\mathbb{E}}}\|{\boldsymbol{H}}({\widehat{X}}J^{L}{\widehat{X}}^{*})-{\boldsymbol{H}}(XJ^{L}X^{*})\|_{\text{HS}}^{2}.$

Writing
${{\mathbb{E}}}\|XJ^{L}X^{*}-{\widehat{X}}J^{L}{\widehat{X}}^{*}\|_{\text{HS}}^{2}={{\mathbb{E}}}\|(X-{\widehat{X}})J^{L}X^{*}+{\widehat{X}}J^{L}(X-{\widehat{X}})^{*}\|_{\text{HS}}^{2}$,
it is enough to bound
${{\mathbb{E}}}\|(X-{\widehat{X}})J^{L}X^{*}\|_{\text{HS}}^{2}$. Given a
constant $\kappa>0$, we have

$\displaystyle\frac{1}{n}{{\mathbb{E}}}\|(X-{\widehat{X}})J^{L}X^{*}\|_{\text{HS}}^{2}$
$\displaystyle\leq\frac{1}{n}{{\mathbb{E}}}\|(X-{\widehat{X}})\|_{\text{HS}}^{2}\|X\|^{2}$
$\displaystyle\leq\frac{\kappa^{2}}{n}{{\mathbb{E}}}\|(X-{\widehat{X}})\|_{\text{HS}}^{2}+\frac{1}{n}{{\mathbb{E}}}\|(X-{\widehat{X}})\|_{\text{HS}}^{2}\|X\|^{2}\mathbbm{1}_{\|X\|>\kappa}$
$\displaystyle\leq\kappa^{2}{{\mathbb{E}}}\|x_{k}-\hat{x}_{k}\|^{2}+\frac{1}{n}({{\mathbb{E}}}(\|X-{\widehat{X}}\|_{\text{HS}}^{4})^{1/2}({{\mathbb{E}}}\|X\|^{4}\mathbbm{1}_{\|X\|>\kappa})^{1/2}.$

With the help of Lemma 17, the second term in the last expression can be made
as small as desired, independently of $N$, when $N$ is large enough, by
choosing $\kappa$ large enough. The first term converges to zero as
$K\to\infty$ as shown above.

###  4.4 Corollary 9: sketch of the proof

We have here $G(z,\eta)={\mathcal{F}}_{I_{N},z}(G(z,\eta),\eta)$ for
$\eta\in\mathbb{C}_{+}$. We also know from the proof of Theorem 5 that if we
start with $P_{0}(z,\eta)=-\eta^{-1}I_{2N}$, then the iterates
$P_{k+1}(z,\eta)={\mathcal{F}}_{I,z}(P_{k}(z,\eta),\eta)$ converge to
$G(z,\eta)$ uniformly on the compacts of $\mathbb{C}_{+}$ in the parameter
$\eta$. Writing ${\mathscr{T}}(P_{k})=\begin{bmatrix}p_{00,k}&p_{01,k}\\\
p_{10,k}&p_{11,k}\end{bmatrix}$ where the argument $(z,\eta)$ is omitted, by
developing the expression of ${\mathcal{F}}_{I_{N},z}(P_{k},\eta)$, we get
that

$P_{k+1}=\begin{bmatrix}\frac{1}{2\pi}\int\frac{p_{11,k}}{\Delta_{k}(e^{\imath\theta})}d\theta-\eta&-\frac{1}{2\pi}\int\frac{(p_{01,k}+e^{-\imath\theta})}{\Delta_{k}(e^{\imath\theta})}d\theta-z\\\
-\frac{1}{2\pi}\int\frac{(p_{10,k}+e^{\imath\theta})}{\Delta_{k}(e^{\imath\theta})}d\theta-\bar{z}&\frac{1}{2\pi}\int\frac{p_{00,k}}{\Delta_{k}(e^{\imath\theta})}d\theta-\eta\end{bmatrix}^{-1}\otimes
I_{N},$

where
$\Delta_{k}(e^{\imath\theta})=p_{00,k}p_{11,k}-(p_{01,k}+e^{-\imath\theta})(p_{10,k}+e^{\imath\theta})$.
Setting from now on $\eta=\imath t$ with $t>0$, it is obvious that
$p_{00,0}=p_{11,0}=\imath h_{0}$ for $h_{0}=1/t>0$, and
$p_{01,0}=\bar{p}_{10,0}$ ($=0$ here). Assuming that $p_{00,k}=p_{11,k}=\imath
h_{k}$ for some $h_{k}>0$ and $p_{01,k}=\bar{p}_{10,k}$, it is not difficult
to show by developing the last display that the same properties hold for
$P_{k+1}$. Passing to the limit, we obtain that $g_{00}(z,\imath
t)=g_{11}(z,\imath t)=\imath h$ for some $h>0$, and $g_{01}(z,\imath
t)=\bar{g}_{10}(z,\imath t)$, where we wrote
${\mathscr{T}}(G)=\begin{bmatrix}g_{00}&g_{01}\\\ g_{10}&g_{11}\end{bmatrix}$.
With this at hand, the equation $G(z,\imath t)={\mathcal{F}}_{I,z}(G(z,\imath
t),\imath t)$ becomes

$\displaystyle G$
$\displaystyle=\Bigl{(}\frac{1}{2\pi}\int_{0}^{2\pi}\frac{1}{{\widetilde{\Delta}}(e^{\imath\theta})}\begin{bmatrix}-\imath
h&g_{01}+e^{-\imath\theta}\\\ \bar{g}_{01}+e^{\imath\theta}&-\imath
h\end{bmatrix}d\theta-\begin{bmatrix}\imath t&z\\\ \bar{z}&\imath
t\end{bmatrix}\Bigr{)}^{-1}\otimes I_{N}$
$\displaystyle=\frac{n}{N}\begin{bmatrix}\imath h&g_{01}\\\
\bar{g}_{01}&\imath h\end{bmatrix}\otimes I_{N}$

where
${\widetilde{\Delta}}(e^{\imath\theta})=h^{2}+|g_{01}+e^{-\imath\theta}|^{2}$.
After some calculation, this equation can be equivalently restated in the form
of the following system of two equations:

$\displaystyle\frac{N}{n}$
$\displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}\frac{h^{2}+|g_{01}|^{2}+g_{01}e^{\imath\theta}}{{\widetilde{\Delta}}(e^{\imath\theta})}d\theta+th-\bar{z}g_{01},$
$\displaystyle 0$
$\displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}\frac{he^{-\imath\theta}}{{\widetilde{\Delta}}(e^{\imath\theta})}d\theta-
zh-tg_{01}.$

This coincides with the system of equations (33a) and (33b) of [7].

##  Appendix A Proof of Lemma 16

  1. 1.

Using Markov’s inequality, an obvious integration with respect to the
exponential distribution, and using the inequality $-\log(1-x)\leq 2x$ for
$x\in[0,1/2]$, we have

$\displaystyle{{\mathbb{P}}}\left[\|\Sigma^{1/2}\xi\|\geq\sqrt{2Nt}\right]$
$\displaystyle={{\mathbb{P}}}\left[\sum_{\ell=0}^{N-1}s_{\ell}(\Sigma)|\xi_{\ell}|^{2}\geq
2Nt\right]={{\mathbb{P}}}\left[\exp{\frac{\sum_{\ell=0}^{N-1}s_{\ell}(\Sigma)|\xi_{\ell}|^{2}}{2\|\Sigma\|}}\geq\exp\frac{Nt}{\|\Sigma\|}\right]$
$\displaystyle\leq
e^{-Nt/\|\Sigma\|}{{\mathbb{E}}}\left[\exp{\frac{\sum_{\ell=0}^{N-1}s_{\ell}(\Sigma)|\xi_{\ell}|^{2}}{2\|\Sigma\|}}\right]=e^{-\frac{Nt}{\|\Sigma\|}}\prod_{\ell=0}^{N-1}\left(1-s_{\ell}(\Sigma)/(2\|\Sigma\|)\right)^{-1}$
$\displaystyle\leq\exp\Bigl{(}-\frac{Nt}{\|\Sigma\|}+\sum_{\ell=0}^{N-1}\frac{s_{\ell}(\Sigma)}{\|\Sigma\|}\Bigr{)}$
$\displaystyle\leq e^{-(t/\|\Sigma\|-1)N}.$

  2. 2.

We have
$\|\Sigma^{1/2}\xi\|^{2}\stackrel{{\scriptstyle{\mathcal{L}}}}{{=}}\sum_{\ell=0}^{N-1}s_{\ell}(\Sigma)|\xi_{\ell}|^{2}\geq\alpha\sum_{\ell=0}^{m-1}|\xi_{\ell}|^{2}$.
Thus, by a calculation similar to above,

${{\mathbb{P}}}[\|\Sigma^{1/2}\xi\|\leq\sqrt{\alpha
m/2}]\leq{{\mathbb{P}}}[\sum_{\ell=0}^{m-1}|\xi_{\ell}|^{2}\leq
m/2]\leq\exp(-c_{\ref{gauss},\ref{normgauss}}m).$

  3. 3.

We obviously have that

$(\xi+a)^{*}M(\xi+a)=(\xi+a)^{*}\Re M(\xi+a)+\imath\,(\xi+a)^{*}\Im M(\xi+a),$

and both $(\xi+a)^{*}\Re M(\xi+a)$ and $(\xi+a)^{*}\Im M(\xi+a)$ are real.
Furthermore,

$\|M\|_{\text{HS}}^{2}=\|\Re M\|_{\text{HS}}^{2}+\|\Im M\|_{\text{HS}}^{2}.$

Let us assume that $\|\Re M\|_{\text{HS}}\geq\|M\|_{\text{HS}}/\sqrt{2}$,
otherwise, we replace $\Re M$ with $\Im M$. From these facts, we deduce that

${\mathcal{L}}((\xi+a)^{*}M(\xi+a)/\|M\|_{\text{HS}},t)\leq{\mathcal{L}}((\xi+a)^{*}\Re
M(\xi+a)/\|\Re M\|_{\text{HS}},\sqrt{2}t).$

By a spectral factorization of the Hermitian matrix $\Re M$,

$(\xi+a)^{*}\Re M(\xi+a)/\|\Re
M\|_{\text{HS}}\stackrel{{\scriptstyle{\mathcal{L}}}}{{=}}\sum_{\ell\in[N]}\beta_{\ell}|\xi_{\ell}+u_{\ell}|^{2},$

where the $u_{\ell}$ are deterministic complex numbers, and the $\beta_{\ell}$
are deterministic reals that satisfy $\sum\beta_{\ell}^{2}=1$, since they are
the eigenvalues of $\|\Re M\|_{\text{HS}}^{-1}\Re M$. The random variable
$|\xi_{\ell}+u_{\ell}|^{2}$ is non-central chi-squared with two degrees of
freedom and has the density

$f_{\ell}(x)=\exp(-(x+|u_{\ell}|^{2}))\boldsymbol{I}_{0}(2|u_{\ell}|\sqrt{x})$

on ${{\mathbb{R}}}_{+}$, where $\boldsymbol{I}_{0}$ is the modified Bessel
function. Since these densities are bounded by one [1], we can get the result
from [33, Th. 1.2].

  4. 4.

By the restriction property of Lévy’s anti-concentration function,

${\mathcal{L}}(\Sigma^{1/2}\xi,\sqrt{m}t)\leq\sup_{(d_{0},\ldots,d_{m-1})\in\mathbb{C}^{m}}{{\mathbb{P}}}\left[\sum_{\ell=0}^{m-1}\left|s_{\ell}(\Sigma)^{1/2}\xi_{\ell}-d_{\ell}\right|^{2}\leq
mt^{2}\right].$

We furthermore use the following well-known tensorization result (see [31,
Lemma 2.2]): Suppose $\\{w_{0},\ldots,w_{m-1}\\}$ is a collection of
independent non-negative random variables such that there is a constant $c>0$
such that for each $t\geq 0$,

${{\mathbb{P}}}[w_{\ell}\leq t]\leq ct.$

Then there exists a constant $c^{\prime}>0$ so that

${{\mathbb{P}}}[\sum_{\ell=0}^{m-1}w_{\ell}^{2}\leq
mt^{2}]\leq(c^{\prime}t)^{m}.$

In the present case, for each $\ell\in[m]$ and each $d_{\ell}\in\mathbb{C}$,
$w_{\ell}^{2}=[|s_{\ell}(\Sigma)^{1/2}\xi_{\ell}-d_{\ell}|]^{2}$ is a non-
central chi-squared random variable with two degrees of freedom and has a
density bounded by a constant that depends only on $\alpha$, as can be checked
from the previous item. Thus, the tensorization argument applies and the
result follows.

  5. 5.

By a singular value decomposition of $M$, we obtain that

${{\mathbb{P}}}[\|M\xi\|^{2}\geq
t\|M\|_{\text{HS}}^{2}]={{\mathbb{P}}}[\sum_{\ell=0}^{N-1}\sigma_{\ell}^{2}|\xi_{\ell}|^{2}\geq
t]$

where $\sum\sigma_{\ell}^{2}=1$. Writing

${{\mathbb{P}}}[\sum_{\ell}\sigma_{\ell}^{2}|\xi_{\ell}|^{2}\geq
t]={{\mathbb{P}}}[\exp(\sum_{\ell}\sigma_{\ell}^{2}|\xi_{\ell}|^{2}/2)\geq\exp(t/2)]$

and following the arguments given for Item 1, we easily get the result.

Proof of Lemma 16 is now complete.

## References

  * [1] M. Abramowitz and I. A. Stegun.  Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, volume 55 of National Bureau of Standards Applied Mathematics Series.  United States Department of Commerce, 1964.
  * [2] M. Bhattacharjee and A. Bose.  Large sample behaviour of high dimensional autocovariance matrices.  Ann. Statist., 44(2):598–628, 2016.
  * [3] M. Bhattacharjee and A. Bose.  Joint convergence of sample autocovariance matrices when $p/n\to 0$ with application.  Ann. Statist., 47(6):3470–3503, 2019.  To appear.
  * [4] V. Bolotnikov.  On a general moment problem on the half axis.  Linear Algebra Appl., 255:57–112, 1997.
  * [5] Ch. Bordenave and D. Chafaï.  Around the circular law.  Probab. Surv., 9:1–89, 2012.
  * [6] A. Bose and M. Bhattacharjee.  Large Covariance and Autocovariance Matrices. Chapman & Hall/CRC, Boca Raton, London, New York, 2018.
  * [7] A. Bose and W. Hachem.  Smallest singular value and limit eigenvalue distribution of a class of non-hermitian random matrices with statistical application.  J. Multi. Anal., 178:Paper number 104623. To appear, 2020.
  * [8] A. Böttcher and S. M. Grudsky.  Spectral Properties of Banded Toeplitz Matrices.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005.
  * [9] D. R. Brillinger.  Time series: data analysis and theory.  SIAM, 2001.
  * [10] S. Chatterjee and A. Bose.  A new method for bounding rates of convergence of empirical spectral distributions.  J. Theoret. Probab., 17(4):1003–1019, 2004.
  * [11] N. Cook, W. Hachem, J. Najim, and D. Renfrew.  Non-Hermitian random matrices with a variance profile (I): deterministic equivalents and limiting ESDs.  Electron. J. Probab., 23:Paper No. 110, 1–61, 2018.
  * [12] D. Damanik, A. Pushnitski, and B. Simon.  The analytic theory of matrix orthogonal polynomials.  Surv. Approx. Theory, 4:1–85, 2008.
  * [13] J. Feinberg and A. Zee.  Non-Hermitian random matrix theory: method of Hermitian reduction.  Nuclear Phys. B, 504(3):579–608, 1997.
  * [14] J. S. Geronimo and T. P. Hill.  Necessary and sufficient condition that the limit of Stieltjes transforms is a Stieltjes transform.  J. Approx. Theory, 121(1):54–60, 2003.
  * [15] F. Gesztesy and E. Tsekanovskii.  On matrix-valued Herglotz functions.  Math. Nachr., 218:61–138, 2000.
  * [16] V. L. Girko.  The circular law.  Teor. Veroyatnost. i Primenen., 29(4):669–679, 1984.  English translation: Theory Probab. Appl. 29(4), 694-706, 1984.
  * [17] J. Glimm and A. Jaffe.  Quantum Physics. A functional integral point of view.  Springer-Verlag, New York, second edition, 1987.
  * [18] F. Götze and A. Tikhomirov.  The circular law for random matrices.  Ann. Probab., 38(4):1444–1491, 2010.
  * [19] W. Hachem, Ph. Loubaton, and J. Najim.  Deterministic equivalents for certain functionals of large random matrices.  Ann. Appl. Probab., 17(3):875–930, 2007.
  * [20] R. A. Horn and C. R. Johnson.  Matrix Analysis.  Cambridge University Press, Cambridge, 1990.  Corrected reprint of the 1985 original.
  * [21] T. Kailath, A. Vieira, and M. Morf.  Inverses of Toeplitz operators, innovations, and orthogonal polynomials.  SIAM Rev., 20(1):106–119, 1978.
  * [22] A. M. Khorunzhy and L. A. Pastur.  Limits of infinite interaction radius, dimensionality and the number of components for random operators with off-diagonal randomness.  Comm. Math. Phys., 153(3):605–646, 1993.
  * [23] A. E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann.  Smallest singular value of random matrices and geometry of random polytopes.  Adv. Math., 195(2):491–523, 2005.
  * [24] P. G. Nevai.  Orthogonal polynomials.  Mem. Amer. Math. Soc., 18(213):v+185, 1979.
  * [25] H. H. Nguyen.  On the least singular value of random symmetric matrices.  Electron. J. Probab., 17:1–19, 2012.
  * [26] L. A. Pastur.  A simple approach to the global regime of Gaussian ensembles of random matrices.  Ukraïn. Mat. Zh., 57(6):790–817, 2005.
  * [27] L. A. Pastur and M. Shcherbina.  Eigenvalue Distribution of Large Random Matrices, volume 171 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2011.
  * [28] C. Peligrad and M. Peligrad.  The limiting spectral distribution in terms of spectral density.  Random Matrices Theory Appl., 5(1):1650003, 1–19, 2016.  Erratum: 5(1):1792001-1 (2016).
  * [29] M. Rosenblum and J. Rovnyak.  Hardy Classes and Operator Theory.  Oxford Mathematical Monographs. Oxford University Press, New York and Clarendon Press, Oxford, 1985.
  * [30] Y. A. Rozanov.  Stationary Random Processes.  Holden-Day, Inc., San Francisco, Calif.-London-Amsterdam, 1967.  Translated from the Russian by A. Feinstein.
  * [31] M. Rudelson and R. Vershynin.  The Littlewood-Offord problem and invertibility of random matrices.  Adv. Math., 218(2):600–633, 2008.
  * [32] M. Rudelson and R. Vershynin.  Smallest singular value of a random rectangular matrix.  Comm. Pure Appl. Math., 62(12):1707–1739, 2009.
  * [33] M. Rudelson and R. Vershynin.  Small ball probabilities for linear images of high-dimensional distributions.  Int. Math. Res. Not. IMRN, (19):9594–9617, 2015.
  * [34] J. W. Silverstein and Z. D. Bai.  On the empirical distribution of eigenvalues of a class of large-dimensional random matrices.  J. Multivariate Anal., 54(2):175–192, 1995.
  * [35] B. Simon.  Szegő’s Theorem and its Descendants: Spectral theory for $L^{2}$ perturbations of orthogonal polynomials.  M. B. Porter Lectures. Princeton University Press, Princeton, NJ, 2011\.
  * [36] H. Stahl and V. Totik.  General Orthogonal Polynomials, volume 43 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 1992.
  * [37] T. Tao.  Topics in Random Matrix Theory, volume 132 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2012.
  * [38] T. Tao and V. Vu.  Random matrices: universality of ESDs and the circular law.  Ann. Probab., 38(5):2023–2065, 2010.  With an appendix by Manjunath Krishnapur.
  * [39] L. N. Trefethen and M. Embree.  Spectra and Pseudospectra: The behavior of nonnormal matrices and operators.  Princeton University Press, Princeton, NJ, 2005.
  * [40] R. Vershynin.  Invertibility of symmetric random matrices.  Random Structures & Algorithms, 44(2):135–182, 2014.
  * [41] R. Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
  * [42] J. Yao and W. Yuan.  On eigenvalue distributions of large auto-covariance matrices.  arXiv preprint arXiv:2011.09165, 2020.


# Unbounded Gradients in Federated Leaning with Buffered Asynchronous
Aggregation

Mohammad Taha Toghani and César A. Uribe The authors are with the Department
of Electrical and Computer Engineering, Rice University, 6100 Main St,
Houston, TX 77005, USA, {mttoghani<EMAIL_ADDRESS>This work was partially
funded by ARPA-H Strategic Initiative Seed Fund #916012. Part of this material
is based upon work supported by the National Science Foundation under Grants
#2211815 and No. #2213568.

###### Abstract

Synchronous updates may compromise the efficiency of cross-device federated
learning once the number of active clients increases. The FedBuff algorithm
(Nguyen et al. [1]) alleviates this problem by allowing asynchronous updates
(staleness), which enhances the scalability of training while preserving
privacy via secure aggregation. We revisit the FedBuff algorithm for
asynchronous federated learning and extend the existing analysis by removing
the boundedness assumptions from the gradient norm. This paper presents a
theoretical analysis of the convergence rate of this algorithm when
heterogeneity in data, batch size, and delay are considered.

##  I Introduction

Federated learning (FL) is an approach in machine learning theory and practice
that allows training models on distributed data sources [2, 3]. The
distributed structure of FL has numerous benefits over traditional centralized
methods, including parallel computing, efficient storage, and improvements in
data privacy. However, this framework also presents communication efficiency,
data heterogeneity, and scalability challenges. Several works have been
proposed to improve the performance of FL [4, 5, 6]. Existing works usually
address a subset of these challenges while imposing additional constraints or
limitations in other aspects. For example, the work in [7] shows a trade-off
between privacy, communication efficiency, and accuracy gains for the
distributed discrete Gaussian mechanism for FL with secure aggregation.

One of the most important advantages of FL is scalability. Training models on
centralized data stored on a single server can be problematic when dealing
with large amounts of data. Servers may be unable to handle the load, or
clients might refuse to share their data with a third party. In FL, the data
is distributed across many devices, potentially improving data privacy and
computation scalability. However, this also presents some challenges. First,
keeping the update mechanism synchronized across all devices may be very
difficult when the number of clients is large [8]. Second, even if feasible,
imposing synchronization results in huge (unnecessary) delays in the learning
procedure [6]. Finally, each client often might have different data
distributions, which can impact the convergence of algorithms [9, 10].

In synchronous FL, e.g., FedAvg [3, 2], the server first sends a copy of the
current model to each client. The clients then train the model locally on
their private data and send the model updates back to the server. The server
then aggregates the client updates to produce a new shared model. The process
is repeated for many rounds until the shared model converges to the desired
accuracy. However, the existence of delays, message losses, and stragglers
hinders the performance of distributed learning. Several works have been
proposed to improve the scalability of federated/distributed learning via
enabling asynchronous communications [11, 12, 8, 13, 6, 14, 15]. In the
majority of these results, each client immediately communicates the parameters
to the server after applying a series of local updates. The server updates the
global parameter once it receives any client update. This has the benefit of
reducing the training time and better scalability in practice and theory [16,
6, 12, 15] since the server can start aggregating the client updates as soon
as they are available.

The setup, known as “vanilla” asynchronous FL, has several challenges that
must be addressed. First, due to the nature of asynchronous updates, the
clients are supposed to deal with staleness, where the client updates are not
up-to-date with the current model on the server [1]. Moreover, the
asynchronous setup may imply potential risks for privacy due to the lack of
secure aggregation, i.e., the immediate communication of every single client
to the server [17, 18]. In [1], the authors proposed an algorithm called
federated learning with buffered asynchronous aggregation (FedBuff), which
modifies pure asynchronous FL by enabling secure aggregation while clients
perform asynchronous updates. This novel method is considered a variant of
asynchronous FL while serving as an intermediate approach between synchronous
and asynchronous FL.

TABLE I: Comparison of the characteristics considered in our analysis with
relevant works for federated learning for smooth & non-convex objective
functions. Parameter $\tau$ denotes the maximum delay.

Algorithm | Reference | Asynchronous | Buffered | Unbounded | Convergence
---|---|---|---|---|---
Update | Aggregation | Gradient |  Rate
| McMahan et al. [2] | ✗ | ✓ | - | -
FedAvg | Yu et al. [19] | ✗ | ✓ | ✗ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)$
| Wang et al. [10] | ✗ | ✓ | ✓ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)$
FedAsync | Xie et al. [8] | ✓ | ✗ | ✗ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)$
FedBuff | Nguyen et al. [1] | ✓ | ✓ | ✗ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)$
This Work | ✓ | ✓ | ✓ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)$

FedBuff [1] is shown to converge for the class of smooth and non-convex
objective functions under the boundedness of the gradient norm. By removing
this assumption, we provide a new analysis for FedBuff and improve the
existing theory by extending it to a broader class of functions. We derive our
bounds based on stochastic and heterogeneous variance and the maximum delay
between downloads and uploads across all the clients. Table I summarizes the
properties and rate of our analysis for FedBuff algorithm alongside and
provides a comparison with existing analyses for FedAsync [8] and FedAvg [3,
2]. The rates reflect the complexity of the number of updates performed by the
central server. The speed of asynchronous algorithms is faster since the
constraint for synchronized updates is removed in asynchronous variations. To
our knowledge, this is the first analysis for (a variant of) asynchronous
federated learning with no boundedness assumption on the gradient norm.

Following is an outline of the remainder of this paper. The problem setup and
FedBuff algorithm are presented in Section II. Moreover, our convergence
result and its corresponding assumptions are provided in Section II. We state
detailed proof of our result in section III. Finally, we conclude remarks and
prospects for future research in Section IV.

##  II Problem Setup, Algorithm, & Main Result

In this section, we first state the problem setup, and after explaining the
FedBuff algorithm [1], we present our main result along with the underlying
assumptions.

$\diamond$ Problem Setup: We consider a set of $n$ clients and one server,
where each client $i\in[n]$ owns a private function
$f_{i}:\mathbb{R}^{d}\to\mathbb{R}$ and the goal is to jointly minimize the
average local cost functions via finding a $d$-dimensional parameter
$w\in\mathbb{R}^{d}$ that

$\displaystyle\begin{split}\min_{w\in\mathbb{R}^{d}}f(w)&\coloneqq\frac{1}{n}\sum\limits_{i=1}^{n}f_{i}(w),\\\
\text{with}\quad f_{i}(w)&\coloneqq\mathbb{E}_{\xi_{i}\sim
p_{i}}[\ell_{i}(w,\xi_{i})],\end{split}$ (1)

where $\ell_{i}:\mathbb{R}^{d}\times\mathcal{S}_{i}\to\mathbb{R}$ is a cost
function that determines the prediction error of $w$ over a single data point
$\xi_{i}\in\mathcal{S}_{i}$ on user $i$, and $p_{i}$ represents user $i$’s
data distribution over $\mathcal{S}_{i}$, for $i\in[n]$. In the above
definition, $f_{i}(\cdot)$ is the local cost function of client $i$, and
$f(\cdot)$ denotes the global (average) cost function which the clients try to
collaboratively minimize. Now, let $\mathcal{D}_{i}$ be a data batch sampled
from $p_{i}$. Similar to (1), we denote the stochastic cost function
$\tilde{f}_{i}(w,\mathcal{D}_{i})$ as follows:

$\displaystyle\tilde{f}_{i}(w,\mathcal{D}_{i})$
$\displaystyle\coloneqq\frac{1}{|\mathcal{D}_{i}|}\sum\limits_{\xi_{i}\in\mathcal{D}_{i}}\ell_{i}(w,\xi_{i}).$
(2)

Minimization of (1) by having access to an oracle of samples and its variants
are extensively studied for many different frameworks [4]. Now, we are ready
to explain the FedBuff.

$\diamond$ FedBuff Algorithm: Let $w^{0}$ be the initialization parameter at
the server. The ultimate goal is to minimize the cost function in (1), using
an algorithm via access to the stochastic gradients. All clients can
communicate with the server, and each client $i\in[n]$ communicates when its
connection to the server is stable. First, let us explain the FedBuff
algorithm from the client and server perspectives.

  1. 1.

Client Algorithm: Each client $i$ requests to read the server’s parameter
$w\in\mathbb{R}^{d}$ once the connection is stable and the server is ready to
send the parameter.111We drop the timestep from the parameters in the client
algorithm, for clarity of exposition. We use the time notation in our analysis
in Section III. There is often some delay in this step which we call the
download delay. This may be originated from factors such as unstable
connection, bandwidth limit, or communication failure. For example, maybe the
server seeks to reduce the simultaneously active users by setting client $i$
on hold. The download delay can model all these factors. Once the parameter is
received (downloaded) from the server, client $i$ performs $Q$ steps of local
stochastic gradient descent starting from the downloaded model $w$ for its
cost function $f_{i}(\cdot)$. In words, agent $i$ runs a $Q$-step algorithm
(loop of size $Q$), where at each local round $q\in\\{0,1,\dots Q{-}1\\}$,
client $i$ samples a data batch $\mathcal{D}_{i,q}$ with respect to
distribution $p_{i}$ and performs one step of gradient descent with local
stepsize $\eta>0$. Finally, agent $i$ returns the updates (the difference
between the initial and final parameters) to the server. We refer to the time
required to broadcast parameters to the server as the upload delay, which
could have similar factors as the download delay. Agent repeats all this
procedure until the server sends a termination message. Algorithm 1 summarizes
the pseudo-code of operations at client $i\in[n]$, where Steps 4-8 show the
local updates performed at the agent. Moreover, $\Delta_{i}$ in Step 9 denotes
the difference communicated to the server.

Algorithm 1 FedBuff (Client $i$)

1: input: number of local steps $Q$, local stepsize $\eta$.

2: repeat

3: read $w$ from the server {download phase}

4: $w_{i,0}\leftarrow w$

5: for $q=0$ to $Q{-}1$ do

6: sample a data batch $\mathcal{D}_{i,q}$

7: $w_{i,q+1}\leftarrow
w_{i,q}-\eta\nabla\tilde{f}_{i}(w_{i,q},\mathcal{D}_{i,q})$

8: end for

9: $\Delta_{i}\leftarrow w_{i,0}-w_{i,Q}$

10: client $i$ broadcasts $\Delta_{i}$ to the server{upload phase}

11: until not interrupted by the server

  2. 2.

Server Algorithm: The server considers an initialization for parameter
$w^{0}\in\mathbb{R}^{d}$. Then, starting from timestep $t=0$, the server
repeats an iterative procedure in addition to sending its parameters to the
clients upon their request. Algorithm 2 describes the server operations in
FedBuff. In a nutshell, the algorithm consists of two parts, (i) secure
aggregation of client updates in a buffer with size $K\geq 1$, and (ii) update
the parameters using the aggregated updates. In other words, let $k,t$
respectively denote the indices associated with buffer and server
updates.222As explained in [1], the buffer and secure aggregation may be
performed on a secure channel which prevents the server from observing
individual local updates received from the clients. The server starting from
$t=0$, receives updates broadcast by the agents asynchronously depending on
their upload & download delays as well as the time required for $Q$ local
updates. A secure buffered aggregates these updates, up to $K$ separate
updates received by the clients in $\overline{\Delta}^{0}$, initially set to
zero. By indexing $k$, we keep track of uploaded updates on the server. When
the buffer saturates of $K$ different updates, the server uses the aggregator
parameter $\overline{\Delta}^{0}$ and updates its parameter $w^{0}$ according
to line 9 of Algorithm 2. Then, the server increases its update counter $t$
and removes all updates from the buffer, i.e., $k=0$. In this algorithm, we
denote the agent which sends the $k$-th update at round $t$ by index
$i_{t,k}\in[n]$. Basically, server repeats Steps 5-14 until some convergence
criteria be satisfied. After the convergence, the server sends a termination
message to all the clients.

As we described above, the crucial novelty of this algorithm is on the server
side, where the server operations, with the help of a secure buffered
aggregation, control the staleness and prevent unnecessary access to
individual updates. Note that for $K=1$, the presented algorithm reduces to
vanilla asynchronous federated learning with no buffer aggregation. Figure 1
illustrates the update schedule for FedBuff and provides a comparison with the
asynchronous updates in FedAvg [2]. As shown on the left of Figure 1, the
vertical lines with light blue color are associated with uploaded updates.
Note that the buffer size is $K=2$ in this example. These vertical lines are
of two types, (i) solid or (ii) hatched. The solid lines reflect the time the
buffer is full, so the server performs an update. Contrary to FedBuff, under
the synchronous updates (as shown in the right figure), the server should halt
the training procedure until all clients selected within one round receive the
updates.

Algorithm 2 FedBuff (Server)

1: input: model $w^{0}$, server stepsize $\beta$, buffer size $K$

2: $t\leftarrow 0$, $k\leftarrow 0$

3: $\overline{\Delta}^{0}\leftarrow 0$

4: repeat

5: if the server receives an update $\Delta_{i_{t,k}}$ from some client
$i_{t,k}{\in}[n]$ then

6: $\overline{\Delta}^{t}\leftarrow\overline{\Delta}^{t}+\Delta_{i_{t,k}}$

7: $k\leftarrow k+1$

8: if $k=K$ then

9: $w^{t+1}\leftarrow w^{t}-\beta\overline{\Delta}^{t}$

10: $k\leftarrow 0$

11: $t\leftarrow t+1$

12: $\overline{\Delta}^{t}\leftarrow 0$

13: end if

14: end if

15: until not converged

Figure 1: Communication and update schedule for synchronous and buffered
asynchronous aggregation: The demonstrated setup in this example contains
$n=5$ agents, with $Q=3$ local updates, buffer size $K=2$ for FedBuff [1], and
sampling rate $0.6$ for FedAvg [2].

Next, we present our assumptions on staleness, bounded stochasticity, and
population diversity (heterogeneity).

$\diamond$ Assumptions & Main Result: Here, we present our main result
alongside a few standard assumptions. First, to be coherent with the proof in
[1], let us denote $\tau_{i}^{t}$ to be the timestep of the last downloaded
parameter on client $i\in[n]$ up to the $t$-th update at the server. We are
ready to introduce the assumptions in our analysis for FedBuff, i.e.,
Algorithms 1 & 2.

######  Assumption 1 (Bounded Staleness).

For all clients, $i\in[n]$ and server steps $t\geq 0$, the staleness or
effective delay between the download and upload steps is bounded by some
constant $\tau$, i.e.,

$\displaystyle\sup_{t\geq 0}\max_{i\in[n]}\left\lvert
t-\tau_{i}^{t}\right\rvert\leq\tau,$ (3)

and the server receives updates uniformly, i.e.,
$i_{t,k}\sim\mathrm{Uniform}([n])$.

Note that $\tau_{i}^{t}$ is the timestep of the last parameter downloaded via
agent $i$ up to timestep $t$ at the server. Therefore, if agent $i$
contributes in the $(t{+}1)$-th update, i.e., $i_{t,k}=i$, for some
$k\in\\{0,1,\dots,K{-}1\\}$, the difference between the download and upload
rounds is bounded. This is a standard assumption in the analysis of
asynchronous algorithms with heterogeneous data on the clients.333It is worth
mentioning that Mishchenko et al. [15] relaxed this assumption (to unbounded
delay) for the analysis of homogeneous smooth & strongly convex functions.

######  Assumption 2 (Smoothness).

For all clients $i\in[n]$, function $f_{i}:\mathbb{R}^{d}\to\mathbb{R}$ is
bounded below, differentiable, and $L$-smooth, i.e., for all
$w,u\in\mathbb{R}^{d}$,

$\displaystyle\left\lVert\nabla f_{i}(w)-\nabla f_{i}(u)\right\rVert\leq
L\lVert w-u\rVert$ (4) $\displaystyle
f_{i}^{\star}\coloneqq\min_{w\in\mathbb{R}^{d}}f_{i}(w)>-\infty.$ (5)

This assumption guarantees the necessary conditions for analyzing smooth &
non-convex functions. Note that boundedness from below can be relaxed only to
the global cost function $f$, i.e., it is sufficient to only assume that
$f^{\star}\coloneqq\min_{w\in\mathbb{R}^{d}}f(w)>-\infty$ in our analysis
instead of (5) for all $i\in[n]$. Now, we introduce the assumptions on bounded
stochasticity and heterogeneity.

######  Assumption 3 (Bounded Variance).

For all clients $i\in[n]$, the variance of a stochastic gradient
$\nabla\ell_{i}(w,\xi_{i})$ on a single data point $\xi_{i}\in\mathcal{S}_{i}$
is bounded, i.e., for all $w\in\mathbb{R}^{d}$

$\displaystyle\mathbb{E}_{\xi_{i}\sim
p_{i}}\left\lVert\nabla\ell_{i}(w,\xi_{i})-\nabla
f_{i}(w)\right\rVert^{2}\leq\sigma^{2}.$ (6)

This assumption is conventional in the analysis of stochastic optimization
algorithms and has been used in many relevant works [20, 1, 6, 9, 10, 21, 14].
Note that as we defined the stochastic loss in (2) and used the stochastic
gradients in Step 7, we also need to show the stochastic variance for the
gradients of the sampled batches. For simplicity, let us assume that all batch
sizes are of size at least $b$, therefore according to (6), we have:

$\displaystyle\mathbb{E}_{p_{i}}\left\lVert\nabla\tilde{f}_{i}(w,\mathcal{D}_{i})-\nabla
f_{i}(w)\right\rVert^{2}\leq\frac{\sigma^{2}}{|\mathcal{D}_{i}|}\leq\hat{\sigma}^{2}\coloneqq\frac{\sigma^{2}}{b}.$
(7)

######  Assumption 4 (Bounded Population Diversity).

For all $w\in\mathbb{R}^{d}$, the gradients of local functions $f_{i}(w)$ and
the global function $f(w)$ satisfy the following property:

$\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\lVert\nabla f_{i}(w)-\nabla
f(w)\rVert^{2}\leq\gamma^{2}.$ (8)

In our analysis, we work with heterogeneous cost functions. Therefore, it is a
reasonable and conventional assumption to assume that the boundedness of the
population diversity [1, 22, 5]. The inequality in 9 measures the variance of
local full gradients from the average full gradient, which resembles to the
expressions in (6) & (7). The authors of [5] discusses the connection of this
bound to the similarity of local data distributions $p_{i}$, for all
$i\in[n]$.

Now, we present our result under the stated assumptions.

######  Theorem 1.

Let Assumptions 1-4 hold, $\beta=\frac{1}{K}$, and
$\eta=\frac{1}{Q\sqrt{LT}}$. Then, the following property holds for the joint
iterates of Algorithms 1 and 2: for any timestep $T\geq
160L(Q{+}7)(\tau{+}1)^{3}$ at the server

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\,\mathbb{E}\left\lVert\nabla
f\left(w^{t}\right)\right\rVert^{2}$
$\displaystyle\leq\frac{8\sqrt{L}\left(f(w^{0}){-}f^{\star}\right)}{\sqrt{T}}$
$\displaystyle+\frac{16\sqrt{L}\left(\frac{\sigma^{2}}{b}+\gamma^{2}\right)}{\sqrt{T}}$
$\displaystyle+\frac{320L(Q{+}1)(\tau^{2}{+}1)\left(\frac{\sigma^{2}}{b}+n\gamma^{2}\right)}{T}.$

We present the proof for Theorem 1 in Section III.

The above theorem states the convergence of the FedBuff algorithm to a first-
order stationary point. This result states a convergence rate of
$\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)$,
where the term affected by the maximum delay (second term) decays faster,
hence the same convergence complexity as the synchronized counterpart. Note
that this rate states the number of updates occurring on the server (iteration
complexity), which in the case of asynchronous updates, practically converges
much faster ($3.3\times$ according to [1]) than synchronized updates.

######  Remark 1.

The choice of $\beta$ in Theorem 1 is an arbitrary option that implies the
rate in the theorem statement. The convergence proof holds for any choices of
$\beta$, such that $\beta K=\mathcal{O}\left(1\right)$.

######  Remark 2.

In our analysis for Theorem 1, we considered bounded population diversity in
Assumption 4. One can see that by relaxing this assumption to a stronger
variant

$\displaystyle\max_{i\in[n]}\sup_{w\in\mathbb{R}^{d}}\lVert\nabla
f_{i}(w)-\nabla f(w)\rVert^{2}\leq\gamma^{2},$ (9)

i.e., uniformly bounded heterogeneity444This stronger assumption is considered
in the analysis of works such as [22][Assumption 3] and [23][6.1.1 Assumptions
and Preliminaries, (vii)]), $n\gamma^{2}$ can be replaced with $\gamma^{2}$ in
the third term of the rate.

Next, we will provide detailed proof for Theorem 1.

##  III Convergence Result

This section provides a detailed explanation of the proof of the convergence
result in Section II.

###### Proof of Theorem 1.

Before proceeding with the proof, let us state some inequalities. For any set
of $m$ vectors $\\{w_{i}\\}_{i{=}1}^{m}$ such that $w_{i}\in\mathbb{R}^{d}$,
and a constant $\alpha>0$, the following properties hold: for all $i,j\in[m]$:

$\displaystyle\lVert w_{i}+w_{j}\rVert^{2}$
$\displaystyle\leq(1{+}\alpha)\lVert w_{i}\rVert^{2}+(1{+}\alpha^{-1})\lVert
w_{j}\rVert^{2},$ (10a) $\displaystyle 2\langle w_{i},w_{j}\rangle$
$\displaystyle\leq\alpha\lVert w_{i}\rVert^{2}+\alpha^{-1}\lVert
w_{j}\rVert^{2},$ (10b)
$\displaystyle\left\lVert\sum\limits_{i=1}^{m}w_{i}\right\rVert^{2}$
$\displaystyle\leq m\left(\sum\limits_{i=1}^{m}\lVert w_{i}\rVert^{2}\right).$
(10c)

For simplicity, let us denote
$\tilde{\nabla}f_{i}\left(w\right)=\nabla\tilde{f}_{i}\left(w,\mathcal{D}_{i}\right)$.
Therefore, at round $t$, the server updates its parameter by receiving
$\overline{\Delta}^{t}$, as follows:

$\displaystyle w^{t{+}1}$
$\displaystyle=w^{t}-\beta\overline{\Delta}^{t}=w^{t}-\beta\sum_{k=0}^{K{-}1}\Delta_{i_{t,k}}$
$\displaystyle=w^{t}-\eta\beta\sum_{k=0}^{K{-}1}\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i_{t,k}}\left(w_{i_{t,k},q}^{\tau_{i_{t,k}}^{t}}\right).$
(11)

Due to Assumption 2, we can infer that $f$ is $L$-smooth, thus

$\displaystyle f(w^{t{+}1}$
$\displaystyle)\overset{\eqref{eq:smoothness}}{\leq}f(w^{t})+\frac{L\eta^{2}\beta^{2}}{2}\underbrace{\left\lVert\sum_{k=0}^{K{-}1}\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i_{t,k}}\left(w_{i_{t,k},q}^{\tau_{i_{t,k}}^{t}}\right)\right\rVert^{2}}_{=:S_{1}}$
$\displaystyle+\eta\beta\underbrace{\left\langle\nabla
f(w^{t}),\sum_{k=0}^{K{-}1}\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i_{t,k}}\left(w_{i_{t,k},q}^{\tau_{i_{t,k}}^{t}}\right)\right\rangle}_{=:S_{2}}$
(12)

We first provide a lower bound on term $S_{2}$ in (III). Let us denote
$\tilde{g}_{i}^{t}=\sum_{q{=}0}^{Q{-}1}\tilde{\nabla}f_{i}(w_{i,q}^{\tau_{i}^{t}})$,
$\tilde{g}^{t}=\frac{1}{n}\sum_{i{=}1}^{n}\tilde{g}_{i}^{t}$,
$g_{i}^{t}=\sum_{q{=}0}^{Q{-}1}\nabla f_{i}(w_{i,q}^{\tau_{i}^{t}})$, and
$g^{t}=\frac{1}{n}\sum_{i{=}1}^{n}g_{i}^{t}$. Therefore,

$\displaystyle\mathbb{E}\left[S_{2}\right]=\mathbb{E}\left[\mathbb{E}_{i_{t,k}}\left\langle\nabla
f(w^{t}),\sum_{k=0}^{K{-}1}\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i_{t,k}}\left(w_{i_{t,k},q}^{\tau_{i_{t,k}}^{t}}\right)\right\rangle\right]$
$\displaystyle=\mathbb{E}\left\langle\nabla
f(w^{t}),\frac{1}{n}\sum\limits_{i=1}^{n}\sum_{k=0}^{K{-}1}\mathbb{E}_{p_{i}}\left[\tilde{g}_{i}^{t}\right]\right\rangle$
(13) $\displaystyle=KQ\,\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}+K\left[\mathbb{E}\left\langle\nabla
f(w^{t}),g^{t}-Q\nabla f(w^{t})\right\rangle\right]$
$\displaystyle{\geq}\frac{K(2Q{-}1)}{2}\,\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}-\frac{K}{2}\mathbb{E}\left\lVert g^{t}-Q\nabla
f(w^{t})\right\rVert^{2}.$

Moreover, the following holds for $S_{1}$ in (III):

$\displaystyle\mathbb{E}\left[S_{1}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}_{i_{t,k}}\left\lVert\sum_{k=0}^{K{-}1}\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i_{t,k}}\left(w_{i_{t,k},q}^{\tau_{i_{t,k}}^{t}}\right)\right\rVert^{2}\right]$
$\displaystyle=\frac{1}{n}\mathbb{E}\left[\sum\limits_{i=1}^{n}\left\lVert\sum_{k=0}^{K{-}1}\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)\right\rVert^{2}\right]$
(14)
$\displaystyle=\frac{K^{2}}{n}\,\sum\limits_{i=1}^{n}\mathbb{E}\left\lVert\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)\right\rVert^{2}=\frac{K^{2}}{n}\,\sum\limits_{i=1}^{n}\mathbb{E}\left\lVert\tilde{g}_{i}^{t}\right\rVert^{2}.$

Now, according to (III), (III), and (III), we have:

$\displaystyle\mathbb{E}f\left(w^{t{+}1}\right)\leq\mathbb{E}f(w^{t})-\frac{\eta\beta
K(2Q{-}1)}{2}\mathbb{E}\left\lVert\nabla f(w^{t})\right\rVert^{2}$ (15)
$\displaystyle+\frac{\eta\beta K}{2}\mathbb{E}\underbrace{\left\lVert
g^{t}-Q\nabla
f(w^{t})\right\rVert^{2}}_{=:S_{3}}+\frac{L\eta^{2}\beta^{2}K^{2}}{2n}\mathbb{E}\underbrace{\left[\sum\limits_{i=1}^{n}\left\lVert\tilde{g}_{i}^{t}\right\rVert^{2}\right]}_{=:S_{4}},$

where we bound $S_{3},S_{4}$ as follows:

$\displaystyle S_{3}$
$\displaystyle=\left\lVert\frac{1}{n}\sum\limits_{i=1}^{n}\left(g_{i}^{t}-Q\nabla
f_{i}(w^{t})\right)\right\rVert^{2}$
$\displaystyle{\leq}\frac{1}{n}\sum\limits_{i=1}^{n}\left\lVert
g_{i}^{t}-Q\nabla f_{i}(w^{t})\right\rVert^{2}$
$\displaystyle=\frac{1}{n}\sum\limits_{i=1}^{n}\left\lVert\sum\limits_{q{=}0}^{Q{-}1}\left[\nabla
f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)-\nabla
f_{i}(w^{t})\right]\right\rVert^{2}$
$\displaystyle{\leq}\frac{Q}{n}\sum\limits_{i=1}^{n}\sum\limits_{q=0}^{Q{-}1}\left\lVert\nabla
f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)-\nabla f_{i}(w^{t})\right\rVert^{2},$
(16)

and

$\displaystyle S_{4}$
$\displaystyle=\sum\limits_{i=1}^{n}\Big{\lVert}\sum\limits_{q{=}0}^{Q{-}1}\tilde{\nabla}f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)\Big{\rVert}^{2}$
$\displaystyle{\leq}Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\Big{\lVert}\tilde{\nabla}f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)\Big{\rVert}^{2}$
$\displaystyle=Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\Big{\lVert}\tilde{\nabla}f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)-\nabla
f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)$ $\displaystyle+\nabla
f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)-\nabla f_{i}\left(w^{t}\right)$
$\displaystyle+\nabla f_{i}\left(w^{t}\right)-\nabla
f\left(w^{t}\right)+\nabla f\left(w^{t}\right)\Big{\rVert}^{2}$
$\displaystyle{\leq}4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\Bigg{[}\Big{\lVert}\tilde{\nabla}f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)-\nabla
f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)\Big{\rVert}^{2}$
$\displaystyle+\Big{\lVert}\nabla
f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)-\nabla
f_{i}\left(w^{t}\right)\Big{\rVert}^{2}$ $\displaystyle+\Big{\lVert}\nabla
f_{i}\left(w^{t}\right)-\nabla
f\left(w^{t}\right)\Big{\rVert}^{2}+\Big{\lVert}\nabla
f\left(w^{t}\right)\Big{\rVert}^{2}\Bigg{]},$ (17)

therefore, by taking expectations, we can show that:

$\displaystyle\mathbb{E}[S_{4}]$
$\displaystyle{\leq}4nQ^{2}\left[\hat{\sigma}^{2}+\gamma^{2}+\mathbb{E}\Big{\lVert}\nabla
f\left(w^{t}\right)\Big{\rVert}^{2}\right]$
$\displaystyle+4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\left\lVert\nabla
f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)-\nabla f_{i}(w^{t})\right\rVert^{2}.$
(18)

Therefore, due to (15)-(III), we have

$\displaystyle\mathbb{E}$ $\displaystyle
f\left(w^{t{+}1}\right)\leq\mathbb{E}f(w^{t})$
$\displaystyle-\left[\frac{\eta\beta
K(2Q{-}1)}{2}-2\eta^{2}L\beta^{2}K^{2}Q^{2}\right]\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}$ $\displaystyle+\frac{\eta\beta
KQ}{2n}\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\left\lVert\nabla
f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)-\nabla f_{i}(w^{t})\right\rVert^{2}$
$\displaystyle+\frac{2\eta^{2}\beta^{2}K^{2}QL}{n}\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\left\lVert\nabla
f_{i}\left(w_{i,q}^{\tau_{i}^{t}}\right)-\nabla f_{i}(w^{t})\right\rVert^{2}$
$\displaystyle+2\eta^{2}L\beta^{2}K^{2}Q^{2}\hat{\sigma}^{2}+2\eta^{2}L\beta^{2}K^{2}Q^{2}\gamma^{2}$
$\displaystyle{\leq}\mathbb{E}f(w^{t})$ $\displaystyle-\left[\frac{\eta\beta
K(2Q{-}1)}{2}-2\eta^{2}L\beta^{2}K^{2}Q^{2}\right]\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}$ $\displaystyle+\frac{\eta\beta
KQL^{2}\left(1{+}4\eta\beta
KL\right)}{2n}\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\underbrace{\left\lVert
w_{i,q}^{\tau_{i}^{t}}-w^{t}\right\rVert^{2}}_{=:S_{5}}$
$\displaystyle+2\eta^{2}L\beta^{2}K^{2}Q^{2}\hat{\sigma}^{2}+2\eta^{2}L\beta^{2}K^{2}Q^{2}\gamma^{2}.$
(19)

Hence, it is sufficient to bound $S_{5}$ in (III) as follows:

$\displaystyle S_{5}$ $\displaystyle=\left\lVert
w^{t}-w_{i,q}^{\tau_{i}^{t}}\right\rVert^{2}=\left\lVert\sum\limits_{s{=}\tau_{i}^{t}}^{t{-}1}\left(w^{s{+}1}-w^{s}\right)+w^{\tau_{i}^{t}}-w_{i,q}^{\tau_{i}^{t}}\right\rVert^{2}$
$\displaystyle{\leq}\left(1{+}\frac{1}{\beta^{2}K^{2}}\right)\left\lVert\sum\limits_{s{=}\tau_{i}^{t}}^{t{-}1}\left(w^{s{+}1}-w^{s}\right)\right\rVert^{2}$
$\displaystyle+\quad\left(1{+}\beta^{2}K^{2}\right)\left\lVert
w^{\tau_{i}^{t}}-w_{i,q}^{\tau_{i}^{t}}\right\rVert^{2}$
$\displaystyle{\leq}\tau\left(1{+}\frac{1}{\beta^{2}K^{2}}\right)\left[\sum\limits_{s{=}t{-}\tau}^{t{-}1}\underbrace{\left\lVert
w^{s{+}1}-w^{s}\right\rVert^{2}}_{=:S_{7}}\right]$
$\displaystyle+\qquad\left(1{+}\beta^{2}K^{2}\right)\underbrace{\left\lVert
w^{\tau_{i}^{t}}-w_{i,q}^{\tau_{i}^{t}}\right\rVert^{2}}_{=:S_{6}}.$ (20)

Now, we show a bound on the evolution of local updates at an arbitrary round
$s\geq 0$, i.e., the distance between $w_{i,q}^{s}$ and $w^{s}$, which we will
use to provide a bound on $S_{7}$.

$\displaystyle\mathbb{E}\left\lVert
w_{i,q}^{s}-w^{s}\right\rVert^{2}=\mathbb{E}\left\lVert
w_{i,q{-}1}^{s}-\eta\tilde{\nabla}f_{i}\left(w_{i,q{-}1}^{s}\right)-w^{s}\right\rVert^{2}$
$\displaystyle=\mathbb{E}\Big{\lVert}w_{i,q{-}1}^{s}-w^{s}-\eta\nabla
f\left(w^{s}\right)$
$\displaystyle\quad-\eta\tilde{\nabla}f_{i}\left(w_{i,q{-}1}^{s}\right)+\eta\nabla
f_{i}\left(w_{i,q{-}1}^{s}\right)$ $\displaystyle\quad-\eta\nabla
f_{i}\left(w_{i,q{-}1}^{s}\right)+\eta\nabla f_{i}\left(w^{s}\right)$
$\displaystyle\quad-\eta\nabla f_{i}\left(w^{s}\right)+\eta\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}$
$\displaystyle{\leq}\left(1{+}\frac{1}{2Q}\right)\mathbb{E}\Big{\lVert}w_{i,q{-}1}^{s}-w^{s}\Big{\rVert}^{2}$
$\displaystyle+\hskip
10.00002pt4(1{+}2Q)\eta^{2}\mathbb{E}\Bigg{[}\Big{\lVert}\tilde{\nabla}f_{i}\left(w_{i,q{-}1}^{s}\right)-\nabla
f_{i}\left(w_{i,q{-}1}^{s}\right)\Big{\rVert}^{2}$ $\displaystyle\hskip
71.00017pt+\Big{\lVert}\nabla f_{i}\left(w_{i,q{-}1}^{s}\right)-\nabla
f_{i}\left(w^{s}\right)\Big{\rVert}^{2}$ $\displaystyle\hskip
71.00017pt+\Big{\lVert}\nabla f_{i}\left(w^{s}\right)-\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}$ $\displaystyle\hskip
71.00017pt+\Big{\lVert}\nabla f\left(w^{s}\right)\Big{\rVert}^{2}\Bigg{]}$
(21)
$\displaystyle{\leq}\left(1{+}\frac{1}{2Q}\right)\mathbb{E}\Big{\lVert}w_{i,q{-}1}^{s}-w^{s}\Big{\rVert}^{2}$
$\displaystyle+\hskip
10.00002pt4(1{+}2Q)\eta^{2}\Bigg{[}\hat{\sigma}^{2}+L^{2}\,\mathbb{E}\Big{\lVert}w_{i,q{-}1}^{s}-w^{s}\Big{\rVert}^{2}$
$\displaystyle\hskip 71.00017pt+\mathbb{E}\Big{\lVert}\nabla
f_{i}\left(w^{s}\right)-\nabla f\left(w^{s}\right)\Big{\rVert}^{2}$
$\displaystyle\hskip 71.00017pt+\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}\Bigg{]}.$ (22)

Note that we can select stepsize $\eta\leq\frac{1}{4L(Q{+}1)}$ such that

$\displaystyle\eta^{2}\leq\frac{1}{8L^{2}Q(2Q{+}1)}\Rightarrow
4(1+2Q)\eta^{2}L^{2}\leq\frac{1}{2Q},$ (23)

therefore, due to (III)-(22) and (23), we have:

$\displaystyle\underbrace{\mathbb{E}\left\lVert
w_{i,q}^{s}-w^{s}\right\rVert^{2}}_{:=P_{i,q}^{s}}\leq\left(1{+}\frac{1}{Q}\right)\underbrace{\mathbb{E}\Big{\lVert}w_{i,q{-}1}^{s}-w^{s}\Big{\rVert}^{2}}_{:=P_{i,q{-}1}^{s}}$
$\displaystyle+4(1{+}2Q)\eta^{2}\Bigg{[}\hat{\sigma}^{2}+\mathbb{E}\Big{\lVert}\nabla
f_{i}\left(w^{s}\right)-\nabla f\left(w^{s}\right)\Big{\rVert}^{2}$
$\displaystyle\underbrace{\qquad\qquad\qquad\qquad\qquad\qquad+\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}\Bigg{]}}_{:=R_{i}^{s}}\Rightarrow$ (24)
$\displaystyle P_{i,q}^{s}$
$\displaystyle\leq\left(1{+}\frac{1}{Q}\right)P_{i,q{-}1}^{s}+R_{i}^{s}$
$\displaystyle=R_{i}^{s}\sum\limits_{k=0}^{q{-}1}\left(1{+}\frac{1}{Q}\right)^{k}\leq
R_{i}^{s}\sum\limits_{k=0}^{Q{-}1}\left(1{+}\frac{1}{Q}\right)^{k}$
$\displaystyle=R_{i}^{s}\frac{\left(1{+}\frac{1}{Q}\right)^{Q}-1}{\left(1{+}\frac{1}{Q}\right)-1}=R_{i}^{s}Q\left[\left(1{+}\frac{1}{Q}\right)^{Q}-1\right]$
$\displaystyle\leq R_{i}^{s}Q(e-1)\leq 2R_{i}^{s}Q,$ (25)

for all $q\in[Q]$. Note that according to Algorithm 2, we have:

$\displaystyle w^{s{+}1}$
$\displaystyle=w^{s}-\beta\sum\limits_{k=0}^{K{-}1}\left[w^{\tau_{i_{s}}^{s}}-w_{i_{s},Q}^{\tau_{i_{s}}^{s}}\right]\Rightarrow$
(26) $\displaystyle\mathbb{E}\left\lVert
w^{s{+}1}-w^{s}\right\rVert^{2}\leq\beta^{2}\,\mathbb{E}\left\lVert\sum\limits_{k=0}^{K{-}1}\left[w^{\tau_{i_{s}}^{s}}-w_{i_{s},Q}^{\tau_{i_{s}}^{s}}\right]\right\rVert^{2}$
$\displaystyle{\leq}\beta^{2}K^{2}\left[\mathbb{E}\left[\mathbb{E}_{i_{s}}\left\lVert
w^{\tau_{i_{s}}^{s}}-w_{i_{s},Q}^{\tau_{i_{s}}^{s}}\right\rVert^{2}\right]\right]$
$\displaystyle=\frac{\beta^{2}K^{2}}{n}\sum\limits_{j{=}1}^{n}\mathbb{E}\left\lVert
w^{\tau_{j}^{s}}-w_{j,Q}^{\tau_{j}^{s}}\right\rVert^{2}$
$\displaystyle{\leq}8Q(1{+}2Q)\eta^{2}\beta^{2}K^{2}\hat{\sigma}^{2}$
$\displaystyle+\frac{8Q(1{+}2Q)\eta^{2}\beta^{2}K^{2}}{n}\sum_{j=1}^{n}\mathbb{E}\Big{\lVert}\nabla
f_{j}\left(w^{\tau_{j}^{s}}\right){-}\nabla
f\left(w^{\tau_{j}^{s}}\right)\Big{\rVert}^{2}$
$\displaystyle+\frac{8Q(1{+}2Q)\eta^{2}\beta^{2}K^{2}}{n}\sum_{j=1}^{n}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\tau_{j}^{s}}\right)\Big{\rVert}^{2}.$ (27)

Let $\phi=8\eta^{2}Q^{2}(1{+}2Q)(1{+}\beta^{2}K^{2})$, then according to
(III)-(LABEL:eq:s7-end), we have

$\displaystyle\frac{1}{n\phi}\sum_{i=1}^{n}\sum_{q=0}^{Q{-}1}\mathbb{E}[S_{5}]$
$\displaystyle\leq\tau\left[\sum\limits_{s{=}t{-}\tau}^{t{-}1}\left\lVert
w^{s{+}1}-w^{s}\right\rVert^{2}\right]+\frac{1}{n}\sum_{i=1}^{n}\left\lVert
w^{\tau_{i}^{t}}-w_{i,q}^{\tau_{i}^{t}}\right\rVert^{2}$
$\displaystyle\leq\tau^{2}\hat{\sigma}^{2}+\frac{\tau}{n}\sum_{s=t{-}\tau}^{t{-}1}\sum_{j=1}^{n}\mathbb{E}\Big{\lVert}\nabla
f_{j}\left(w^{\tau_{j}^{s}}\right)-\nabla
f\left(w^{\tau_{j}^{s}}\right)\Big{\rVert}^{2}$
$\displaystyle+\frac{\tau}{n}\sum_{s=t{-}\tau}^{t{-}1}\sum_{j=1}^{n}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\tau_{j}^{s}}\right)\Big{\rVert}^{2}+\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\tau_{i}^{t}}\right)\Big{\rVert}^{2}$
$\displaystyle+\hat{\sigma}^{2}+\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\Big{\lVert}\nabla
f_{i}\left(w^{\tau_{i}^{t}}\right)-\nabla
f\left(w^{\tau_{i}^{t}}\right)\Big{\rVert}^{2}.$ (28)

Note that according to (3), we know that:
$\tau_{i}^{t}\in\\{t{-}\tau\,\dots,t\\}$, therefore:

$\displaystyle\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\tau_{i}^{t}}\right)\Big{\rVert}^{2}\leq\sum_{s=t{-}\tau}^{t}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2},$ (29)

and similarly, for any $s\in\\{t{-}\tau\,\dots,t\\}$ and $j\in[n]$,

$\displaystyle\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\tau_{j}^{s}}\right)\Big{\rVert}^{2}\leq\sum_{u=s{-}\tau}^{s}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{u}\right)\Big{\rVert}^{2}.$ (30)

Moreover, we have:

$\displaystyle\Big{\lVert}\nabla f_{j}\left(w^{\tau_{j}^{s}}\right)$
$\displaystyle-\nabla f\left(w^{\tau_{j}^{s}}\right)\Big{\rVert}^{2}$
$\displaystyle\leq\sum_{i=1}^{n}\Big{\lVert}\nabla
f_{i}\left(w^{\tau_{j}^{s}}\right)-\nabla
f\left(w^{\tau_{j}^{s}}\right)\Big{\rVert}^{2}.$ (31)

Therefore, due to (III)-(III), we have:

$\displaystyle\frac{1}{n\phi}\sum_{i=1}^{n}\sum_{q=0}^{Q{-}1}\mathbb{E}[S_{5}]$
$\displaystyle{\leq}\tau^{2}\hat{\sigma}^{2}+\tau^{2}n\gamma^{2}$
$\displaystyle+\tau\sum_{s=t{-}\tau}^{t{-}1}\sum_{u=s{-}\tau}^{s}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{u}\right)\Big{\rVert}^{2}$
$\displaystyle+\hat{\sigma}^{2}+n\gamma^{2}+\sum_{s=t{-}\tau}^{t}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}$
$\displaystyle=(1{+}\tau^{2})\left[\hat{\sigma}^{2}+n\gamma^{2}\right]$
$\displaystyle+\tau\sum_{s=t{-}\tau}^{t{-}1}\sum_{u=s{-}\tau}^{s}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{u}\right)\Big{\rVert}^{2}$
$\displaystyle+\sum_{s=t{-}\tau}^{t}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}.$ (32)

By combining (III) and (III), we have the following inequality:

$\displaystyle\mathbb{E}f\left(w^{t{+}1}\right)\leq\mathbb{E}f(w^{t})+2\eta^{2}L\beta^{2}K^{2}Q^{2}\left[\hat{\sigma}^{2}+\gamma^{2}\right]$
$\displaystyle-\frac{\eta\beta K}{2}\Big{[}(2Q{-}1)-4\eta L\beta KQ^{2}$
$\displaystyle\qquad\qquad-QL^{2}(1{+}\tau^{2})\left(1{+}4\eta\beta
KL\right)\phi\Big{]}\mathbb{E}\left\lVert\nabla f(w^{t})\right\rVert^{2}$
$\displaystyle+\frac{\eta\beta KQL^{2}\left(1{+}4\eta\beta KL\right)\phi}{2}$
$\displaystyle\quad\qquad\sum_{s=t{-}\tau}^{t{-}1}\left[\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}+\tau\sum_{u=s{-}\tau}^{s}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{u}\right)\Big{\rVert}^{2}\right]$ $\displaystyle+\frac{\eta\beta
KQL^{2}(1{+}\tau^{2})\left(1{+}4\eta\beta
KL\right)\phi}{2}\left[\hat{\sigma}^{2}+n\gamma^{2}\right]$
$\displaystyle\leq\mathbb{E}f(w^{t})+2\eta^{2}L\beta^{2}K^{2}Q^{2}\left[\hat{\sigma}^{2}+\gamma^{2}\right]$
$\displaystyle-\frac{\eta\beta KQ}{2}\Big{[}1-4\eta L\beta KQ$
$\displaystyle\qquad\qquad-QL^{2}(1{+}\tau^{2})\left(1{+}4\eta\beta
KL\right)\phi\Big{]}\mathbb{E}\left\lVert\nabla f(w^{t})\right\rVert^{2}$
$\displaystyle+\frac{\eta\beta KQL^{2}\left(1{+}4\eta\beta KL\right)\phi}{2}$
$\displaystyle\quad\qquad\sum_{s=t{-}\tau}^{t{-}1}\left[\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}+\tau\sum_{u=s{-}\tau}^{s}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{u}\right)\Big{\rVert}^{2}\right]$ $\displaystyle+\frac{\eta\beta
KQL^{2}(1{+}\tau^{2})\left(1{+}4\eta\beta
KL\right)\phi}{2}\left[\hat{\sigma}^{2}+n\gamma^{2}\right].$ (33)

Now, we can obtain the following inequality by rearranging the terms in (III):

$\displaystyle\big{[}1-4\eta L\beta KQ-
QL^{2}(1{+}\tau^{2})\left(1{+}4\eta\beta
KL\right)\phi\big{]}\mathbb{E}\left\lVert\nabla f(w^{t})\right\rVert^{2}$
$\displaystyle-L^{2}\left(1{+}4\eta\beta
KL\right)\phi\sum_{s=t{-}\tau}^{t{-}1}\Big{[}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad+\tau\sum_{u=s{-}\tau}^{s}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{u}\right)\Big{\rVert}^{2}\Big{]}$
$\displaystyle\leq\frac{2\left[\mathbb{E}f(w^{t})-\mathbb{E}f\left(w^{t{+}1}\right)\right]}{\eta\beta
KQ}+4\eta\beta KQL\left[\hat{\sigma}^{2}+\gamma^{2}\right]$
$\displaystyle+2L^{2}(1{+}\tau^{2})\left(1{+}4\eta\beta
KL\right)\phi\left[\hat{\sigma}^{2}+n\gamma^{2}\right],$ (34)

whereby mixing the terms in (III), we obtain:

$\displaystyle\big{[}1-4\eta L\beta KQ-L^{2}(\tau^{2}{+}1)\left(1{+}4\eta\beta
KL\right)\phi\big{]}\mathbb{E}\left\lVert\nabla f(w^{t})\right\rVert^{2}$
$\displaystyle\quad-L^{2}\left(1{+}4\eta\beta
KL\right)(\tau{+}1)\phi\sum_{s=t{-}\tau}^{t{-}1}\sum_{u=s{-}\tau}^{s}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{u}\right)\Big{\rVert}^{2}$
$\displaystyle\leq\frac{2\left[\mathbb{E}f(w^{t})-\mathbb{E}f\left(w^{t{+}1}\right)\right]}{\eta\beta
KQ}+4\eta\beta KQL\left[\hat{\sigma}^{2}+\gamma^{2}\right]$
$\displaystyle+2L^{2}(1{+}\tau^{2})\left(1{+}4\eta\beta
KL\right)\phi\left[\hat{\sigma}^{2}+n\gamma^{2}\right].$ (35)

Finally, we add (III), for $t=0,1,\dots T{-}1$, and divide by $T$ to show
that:

$\displaystyle\Bigg{[}1-4\eta L\beta
KQ-L^{2}(\tau^{2}{+}1)\left(1{+}4\eta\beta KL\right)\phi$
$\displaystyle\qquad\qquad-L^{2}\left(1{+}4\eta\beta
KL\right)\tau(\tau{+}1)^{2}\phi\Bigg{]}\frac{\sum\limits_{t=0}^{T{-}1}\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}}{T}$
$\displaystyle\leq\frac{2\left[f(w^{0})-\mathbb{E}f\left(w^{T}\right)\right]}{\eta\beta
KQ}+4\eta\beta KQL\left[\hat{\sigma}^{2}+\gamma^{2}\right]$
$\displaystyle+2L^{2}(1{+}\tau^{2})\left(1{+}4\eta\beta
KL\right)\phi\left[\hat{\sigma}^{2}+n\gamma^{2}\right].$ (36)

Let us fix $\beta=\frac{1}{K}$ and $\eta=\frac{1}{Q\sqrt{LT}}$. Thus, we know
that the following inequality holds

$\displaystyle\max\Big{\\{}4\eta\beta KLQ,\,L^{2}(\tau^{2}{+}1)(1{+}4\eta\beta
KL)\phi,$ $\displaystyle\qquad\quad L^{2}\tau(\tau{+}1)^{2}(1{+}4\eta\beta
KL)\phi\Big{\\}}$ $\displaystyle\leq\frac{1}{4},$ (37)

for $T\geq 160L(Q{+}7)(\tau{+}1)^{3}$. Note that under this choices for $\eta$
and $\beta$, we also have $\eta\leq\frac{1}{4L(Q{+}1)}$, which we used in
(23). Therefore, we can conclude the result in Theorem 1 as follows:

$\displaystyle\frac{1}{T}\sum\limits_{t=0}^{T{-}1}\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}$
$\displaystyle\leq\frac{8\sqrt{L}\left(f(w^{0})-\mathbb{E}f\left(w^{T}\right)\right)}{\sqrt{T}}$
$\displaystyle+\frac{16\sqrt{L}\left(\hat{\sigma}^{2}+\gamma^{2}\right)}{\sqrt{T}}$
(38)
$\displaystyle+\frac{320L(Q{+}1)(\tau^{2}{+}1)\left(\hat{\sigma}^{2}+n\gamma^{2}\right)}{T}.$

∎

##  IV Conclusion

This paper studied the convergence properties of asynchronous federated
learning via secure buffered aggregation. By removing the boundedness
assumption on the gradient norms, we presented a novel analysis of the
convergence of the FedBuff algorithm, where we showed a sublinear convergence
rate of $\mathcal{O}(\epsilon^{2})+\mathcal{O}({\tau^{2}}\epsilon)$ to an
$\epsilon$-first-order stationary solution. We also discussed the dependence
of this rate on the batch size, stochasticity variance, data heterogeneity,
and maximum delays. We leave the privacy analysis of Fed-Buff with gradient
clipping and noise addition to future studies. Also, the communication
complexity of this method and the extensions to decentralized setups remain
for future work.

## References

  * [1] John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba,  “Federated learning with buffered asynchronous aggregation,”  in International Conference on Artificial Intelligence and Statistics. PMLR, 2022, pp. 3581–3607.
  * [2] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas,  “Communication-efficient learning of deep networks from decentralized data,”  in Artificial intelligence and statistics. PMLR, 2017, pp. 1273–1282.
  * [3] Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon,  “Federated learning: Strategies for improving communication efficiency,”  arXiv preprint arXiv:1610.05492, 2016.
  * [4] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.,  “Advances and open problems in federated learning,”  arXiv preprint arXiv:1912.04977, 2019.
  * [5] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar,  “Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach,”  Advances in Neural Information Processing Systems, vol. 33, 2020\.
  * [6] Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G Rabbat,  “Advances in asynchronous parallel and distributed optimization,”  Proceedings of the IEEE, vol. 108, no. 11, pp. 2013–2031, 2020\.
  * [7] Peter Kairouz, Ziyu Liu, and Thomas Steinke,  “The distributed discrete gaussian mechanism for federated learning with secure aggregation,”  in International Conference on Machine Learning. PMLR, 2021, pp. 5201–5212.
  * [8] Cong Xie, Sanmi Koyejo, and Indranil Gupta,  “Asynchronous federated optimization,”  arXiv preprint arXiv:1903.03934, 2019.
  * [9] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik,  “Tighter theory for local sgd on identical and heterogeneous data,”  in International Conference on Artificial Intelligence and Statistics. PMLR, 2020, pp. 4519–4529.
  * [10] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor,  “Tackling the objective inconsistency problem in heterogeneous federated optimization,”  Advances in neural information processing systems, vol. 33, pp. 7611–7623, 2020.
  * [11] Yanan Li, Shusen Yang, Xuebin Ren, and Cong Zhao,  “Asynchronous federated learning with differential privacy for edge intelligence,”  arXiv preprint arXiv:1912.07902, 2019.
  * [12] Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson,  “An asynchronous mini-batch algorithm for regularized stochastic optimization,”  IEEE Transactions on Automatic Control, vol. 61, no. 12, pp. 3740–3754, 2016.
  * [13] Kenta Niwa, Guoqiang Zhang, W Bastiaan Kleijn, Noboru Harada, Hiroshi Sawada, and Akinori Fujino,  “Asynchronous decentralized optimization with implicit stochastic variance reduction,”  in International Conference on Machine Learning. PMLR, 2021, pp. 8195–8204.
  * [14] Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi,  “Sharper convergence guarantees for asynchronous sgd for distributed and federated learning,”  arXiv preprint arXiv:2206.08307, 2022.
  * [15] Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth,  “Asynchronous sgd beats minibatch sgd under arbitrary delays,”  arXiv preprint arXiv:2206.07638, 2022.
  * [16] Feng Niu, Benjamin Recht, Christopher Ré, and Stephen J Wright,  “Hogwild!: A lock-free approach to parallelizing stochastic gradient descent,”  arXiv preprint arXiv:1106.5730, 2011.
  * [17] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth,  “Practical secure aggregation for federated learning on user-held data,”  arXiv preprint arXiv:1611.04482, 2016.
  * [18] Wei-Ning Chen, Christopher A Choquette-Choo, and Peter Kairouz,  “Communication efficient federated learning with secure aggregation and differential privacy,”  in NeurIPS 2021 Workshop Privacy in Machine Learning, 2021.
  * [19] Hao Yu, Sen Yang, and Shenghuo Zhu,  “Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning,”  in Proceedings of the AAAI Conference on Artificial Intelligence, 2019, vol. 33, pp. 5693–5700.
  * [20] Sebastian Urban Stich,  “Local sgd converges fast and communicates little,”  in ICLR 2019-International Conference on Learning Representations, 2019, number CONF.
  * [21] Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi,  “Decentralized deep learning with arbitrary communication compression,”  arXiv preprint arXiv:1907.09356, 2019.
  * [22] Canh T Dinh, Nguyen H Tran, and Tuan Dung Nguyen,  “Personalized federated learning with moreau envelopes,”  arXiv preprint arXiv:2006.08848, 2020.
  * [23] Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al.,  “A field guide to federated optimization,”  arXiv preprint arXiv:2107.06917, 2021.