This paper studied a decentralized BFL system in multi-server edge computing with a holistic design of both blackoffloading-assisted ML model training and mobile block mining schemes. A model aggregation solution has been developed via P2P-based consensus among ESs to build a global model that is shared with MDs via Blockchain for reliable model learning empowered by block mining. blackWe aimed to minimize the system latency by a novel parameterized A2C algorithm with a careful design of actor and critic. A comprehensive analysis of the convergence properties of our proposed BFL model was given. Numerical simulations verified the superior performance of our proposed consensus-based BFL scheme over state-of-the-art schemes in terms of higher accuracy and lower loss. The proposed parameterized A2C algorithm also exhibited the faster convergence rate and lower system latency, compared with the existing DRL schemes.

Proof of Theorem  REF
Brief Recap of ML Model Training
Let set \(\mathcal {N}_m^{(k)}\)  contain the devices associated with ES \(m\)  during global aggregation \(k\)  and also the ES \(m\)  itself. Also, let \(y\)  denote the index of an arbitrary ES/MD. Each ES \(m\)  at global aggregation \(k\)  acquires its local aggregated gradient, which is then normalized by the total number of data points \(D^{(k)}\)  to form \(\nabla {F}^{\mathsf {A},(k)}_{m}\)  according to (REF ), which can be written in the compact form as
\({\nabla {F}}_{m}^{\mathsf {A},(k)}=\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}_y^{\mathsf {C},k}}.\) 
Then, the ESs engage in consensus process, where the final parameter at each ES \(m\)  can be expressed as
\({\nabla {F}}_m^{\mathsf {L},(k)}= \sum _{m\in \mathcal {M}} {\nabla {F}}_{m}^{\mathsf {A},(k)} + \mathbf {c}^{(k)}_m= \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)} + \mathbf {c}^{(k)}_m,\) 
where \(\mathbf {c}^{(k)}_m\)  denotes the error of consensus, which is caused by finite rounds of P2P communications. The selected ES at aggregation round \(k\) , denoted by \(m_k\) , then adds a boosting coefficient \(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\)  to its local gradient to form the following vector:
\(\overline{\nabla {F}}_{m_k}^{(k)}=\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}{\nabla {F}}_{m_k}^{\mathsf {L},(k)} = \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)} + \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\mathbf {c}^{(k)}_{m_k}.\) 
The aggregator ES \(m_k\)  then updates the global model parameter as follows:
\(\mathbf {w}^{(k+1)}=\mathbf {w}^{(k)}-\eta _{k} \overline{\nabla {F}}_{m_k}^{(k)}.\) 

Convergence Analysis
Using the \(\beta \) -smoothness of the global loss function (Assumption REF ), we have:
\(F^{({k})}(\mathbf {w}^{(k+1)}) \le F^{({k})}(\mathbf {w}^{(k)}) + \nabla {F^{({k})}(\mathbf {w}^{(k)})}^\top \left( \mathbf {w}^{(k+1)} - \mathbf {w}^{(k)}\right)+ \frac{\beta }{2} \left\Vert \mathbf {w}^{(k+1)} - \mathbf {w}^{(k)}\right\Vert ^2.\) 
Using the updating rule of \(\mathbf {w}^{(k+1)}\)  and taking the conditional expectation (with respect to data sampling conducted via mini-batch SGD at the last aggregation instance), we have
\(\begin{aligned}&\mathbb {E}_k \left[F^{(k)}(\mathbf {w}^{(k+1)})\right] \le F^{(k)}(\mathbf {w}^{(k)}) -\\& \nabla {F^{(k)}(\mathbf {w}^{(k)})}^\top \mathbb {E}_k\left[ \eta _{k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)} + \eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\mathbf {c}^{(k)}_{m_k} \right]\\&+ \frac{\beta }{2} \mathbb {E}_k\left[\left\Vert \eta _{k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)} + \eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \mathbf {c}^{(k)}_{m_k}\right\Vert ^2\right].\end{aligned}\) 
Since \({\nabla {F}}_y^{\mathsf {C},(k)} =-\left( \mathbf {w}_y^{(k),e^{(k)}_y}-\mathbf {w}^{(k)}\right) \Big / {\eta _{k}}\) , we have
\({\nabla {F}}_y^{\mathsf {C},(k)} = {\frac{1}{{{B}}^{(k)}_y}} \sum _{e=1}^{e^{(k)}_y} \sum _{d\in \mathcal {B}^{(k),e}_{y}} \hspace{-2.84526pt} {\nabla f(\mathbf {w}^{(k),e-1}_{y},d)},\) 
where \(\mathcal {B}_y^{(k),e}\)  denotes the set of data points selected to form the mini-batch at the \(e\) -th local SGD iteration at ES/MD \(y\) . Since the mini-batch size is fixed during local SGD iterations at each global aggregation round, we defined \(B_y^{(k)}=|\mathcal {B}^{(k),e}_{y}|,~\forall e\) . Noting that SGD is unbiased it can be easily shown that
\(\mathbb {E}_k\left[{\nabla {F}}_y^{\mathsf {C},(k)}\right] = \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}.\) 
Replacing the above result in (REF ), we get
\(\begin{aligned}\mathbb {E}_k \left[F^{(k)}(\mathbf {w}^{(k+1)})\right] \le & F^{(k)}(\mathbf {w}^{(k)}) - \nabla {F^{(k)}(\mathbf {w}^{(k)})}^\top \mathbb {E}_k\Big [ \eta _{k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\\&+\eta _k \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\mathbf {c}_{m_k}^{(k)}\Big ]\\&+ \frac{\beta }{2} \mathbb {E}_k\left[\left\Vert \eta _{k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)}+\eta _k \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right].\end{aligned}\) 
Using the linearity of expectation and inner product, we can simplify the above expression as follows:
\(\begin{aligned}\mathbb {E}_k \left[F^{(k)}(\mathbf {w}^{(k+1)})\right] \le & F^{(k)}(\mathbf {w}^{(k)}) - \nabla {F^{(k)}(\mathbf {w}^{(k)})}^\top \mathbb {E}_k\left[ \eta _{k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right] \\&+\eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\nabla {F^{(k)}(\mathbf {w}^{(k)})}^\top \mathbb {E}_k\left[- \mathbf {c}_{m_k}^{(k)}\right]\\&+ \frac{\beta }{2} \mathbb {E}_k\left[\left\Vert \eta _{k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)}+\eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right].\end{aligned}\) 
Using Cauchy-Schwartz and Young’s inequalities, we have
\(\mathbf {a}^\top \mathbf {b} \le \frac{\alpha }{2} \Vert \mathbf {a} \Vert ^2 + \frac{1}{2\alpha } \Vert \mathbf {b} \Vert ^2,~\alpha \in \mathbb {R}^{++}\) 
for two real valued vectors \(\mathbf {a}\)  and \(\mathbf {b}\) , implying \(\mathbf {a}^\top \mathbf {b} \le \Vert \mathbf {a} \Vert ^2 + \frac{1}{4} \Vert \mathbf {b} \Vert ^2\) . Using this inequality in (REF ) yields
\(\begin{aligned}\mathbb {E}_k \left[F^{(k)}(\mathbf {w}^{(k+1)})\right] \le & F^{(k)}(\mathbf {w}^{(k)}) - \nabla {F^{(k)}(\mathbf {w}^{(k)})}^\top \mathbb {E}_k\left[ \eta _{k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right] \\&+\frac{\eta _k }{4} \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 + \eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]\\&+ \frac{\beta }{2} \mathbb {E}_k\left[\left\Vert \eta _{k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{{D}}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)}+\eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right].\end{aligned}\) 
Further, for any two real valued vectors \(\mathbf {a}\)  and \(\mathbf {b}\) , we have: \(2\mathbf {a}^\top \mathbf {b}=\Vert \mathbf {a}\Vert ^2+\Vert \mathbf {b}\Vert ^2-\Vert \mathbf {a}-\mathbf {b}\Vert ^2\) . Using this equality in (REF ) results in the following bound:
\(\begin{aligned}&\mathbb {E}_k \left[F^{(k)}(\mathbf {w}^{(k+1)})\right] \le F^{(k)}(\mathbf {w}^{(k)}) - \frac{\eta _{k}}{2}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} } \mathbb {E}_k{4}[\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 +\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2 \hspace{-39.83385pt}\\&- \left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}-\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2{4}]+\frac{\eta _k}{4} \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 \\&+ \eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]+\\& \frac{\beta \eta ^2_{k}}{2} \mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)}+ \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right].\hspace{-11.38109pt}\end{aligned}\) 
Applying the Cauchy-Schwarz inequality (i.e., \(\Vert \mathbf {a}+\mathbf {b}\Vert ^2 \le 2\Vert \mathbf {a}\Vert ^2 +2\Vert \mathbf {b} \Vert ^2\) ) on the last term of the above bound yields
\(\begin{aligned}&\mathbb {E}_k \left[F^{(k)}(\mathbf {w}^{(k+1)})\right] \le F^{(k)}(\mathbf {w}^{(k)}) - \frac{\eta _{k}}{2}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} } \mathbb {E}_k{4}[\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 +\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2\hspace{-22.76219pt}\\&- \left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}-\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2{4}]+\frac{\eta _k}{4}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 \\&+ \eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]\hspace{-11.38109pt}\\&+ {\beta \eta ^2_{k}} \underbrace{\mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)}\right\Vert ^2\right]}_{(a)}+{\beta \eta ^2_{k}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\right)^2} \mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right].\end{aligned}\) 
Focusing on term \((a)\)  in (REF ), using (REF ), we upper bound it as follows:
\(\begin{aligned}&\mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)}\right\Vert ^2\right]\\&=\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2\mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} \sum _{d\in \mathcal {B}^{(k),e}_{y}} \hspace{-2.84526pt} \frac{\nabla f(\mathbf {w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_y}\right\Vert ^2\right]\\&=\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2\mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} \left(\sum _{d\in \mathcal {B}^{(k),e}_{y}} \hspace{-2.84526pt} \frac{\nabla f(\mathbf {w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_y}-\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})+\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})\right)\right\Vert ^2\right]\\&=\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2\mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} \left(\sum _{d\in \mathcal {B}^{(k),e}_{y}} \hspace{-2.84526pt} \frac{\nabla f(\mathbf {w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_y}-\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})+\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})\right)\right\Vert ^2\right]\\&\le 2\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2\underbrace{\mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} \left(\sum _{d\in \mathcal {B}^{(k),e}_{y}} \hspace{-2.84526pt} \frac{\nabla f(\mathbf {w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_y}-\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})\right)\right\Vert ^2\right]}_{(a)}\\&+2\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2\mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y}\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})\right\Vert ^2\right].\end{aligned}\) 
where the last inequality is obtained via Cauchy-Schwarz inequality. Note that \(\sum _{d\in \mathcal {B}^{(k),e}_{y}} \hspace{-2.84526pt} \frac{\nabla f(\mathbf {w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_y}-\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})\)  in the above expression corresponds to the noise of SGD at local iteration \(i\)  at device \(y\) , which is zero mean and iid across the devices and the iterations. Using these facts in term \((a)\)  in (REF ) implies
\(\begin{aligned}&\mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)}\right\Vert ^2\right]\\&=\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}\right)^2\underbrace{\mathbb {E}_k\left[\left\Vert \sum _{e=1}^{e^{(k)}_y} \left(\sum _{d\in \mathcal {B}^{(k),e}_{y}} \hspace{-2.84526pt} \frac{\nabla f(\mathbf {w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_y}-\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})\right)\right\Vert ^2\right]}_{(a)}\\&+\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y}\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})\right\Vert ^2\right].\end{aligned}\) 
Using Lemma REF  (Appendix ) and the fact that SGD noise is zero mean, expanding term \((a)\)  in (REF ) yields
\(\begin{aligned}&\mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}{\nabla {F}}_y^{\mathsf {C},(k)}\right\Vert ^2\right]\\&\le \left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}\right)^2\sum _{e=1}^{e^{(k)}_y}2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y\\&+\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y}\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})\right\Vert ^2\right].\end{aligned}\) 
Replacing the above result back in (REF ), we get
\(\begin{aligned}&\mathbb {E}_k \left[F^{(k)}(\mathbf {w}^{(k+1)})\right] \le F^{(k)}(\mathbf {w}^{(k)}) - \frac{\eta _{k}}{2}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} } \mathbb {E}_k{4}[\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 +\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2\\&- \left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}-\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2{4}]+\frac{\eta _k}{4}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 \\&+ \eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]+ {\beta \eta ^2_{k}}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}\right)^2\sum _{e=1}^{e^{(k)}_y}2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y\\&+{\beta \eta ^2_{k}}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \mathbb {E}_k\left[\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y}\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})\right\Vert ^2\right]\\&+{\beta \eta ^2_{k}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\right)^2} \mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right].\end{aligned}\) 
With rearranging the terms in the above bound, we get
\(\begin{aligned}&\mathbb {E}_k \left[F^{(k)}(\mathbf {w}^{(k+1)})\right] \le F^{(k)}(\mathbf {w}^{(k)}) -\left(\frac{\eta _k}{4}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\right)\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 \\&+\eta _k\left(\underbrace{\beta \eta _k\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\right)^2-\frac{1}{2}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}}_{(a)}\right) \left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2\\&+\left(\frac{\eta _k}{2}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\right) \left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}-\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2\\&+{\eta _k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \left(1+\beta {\eta _k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\right) \mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]\\&+{\beta \eta ^2_{k}}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y}\right)^2\sum _{e=1}^{e^{(k)}_y}2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y.\end{aligned}\) 
Assuming \(\eta _k \le \frac{{D}^{(k)}}{2\beta \sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}\)  makes term \((a)\)  in the above expression negative and also implies \(1+\beta {\eta _k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \le \frac{3}{2}\) . Replacing these results in the above bound gives us
\(\begin{aligned}&\mathbb {E}_k \left[F^{(k)}(\mathbf {w}^{(k+1)})\right] \le F^{(k)}(\mathbf {w}^{(k)}) -\left(\frac{\eta _k}{4}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\right)\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 \\&+\left(\frac{\eta _k}{2}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\right) \underbrace{\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}-\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2}_{(a)}\\&+\frac{3}{2}{\eta _k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]+2{\beta \eta ^2_{k}}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} \sqrt{e^{(k)}_y}}\right)^2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y. \hspace{-14.22636pt}\end{aligned}\) 
We next aim to bound term \((a)\)  in (REF ) as follows:
\(\begin{aligned}&\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}-\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2\\&=\left\Vert \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} } \nabla {F^{(k)}_y(\mathbf {w}^{(k)})}-\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2\\&{\le } \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} }\mathbb {E}_k\left[\left\Vert \nabla {F^{(k)}_y(\mathbf {w}^{(k)})}-\frac{1}{e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2\right]\\&{\le } \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)} e_y^{(k)}}\sum _{e=1}^{e^{(k)}_y} \mathbb {E}_k\left[\left\Vert \nabla {F^{(k)}_y(\mathbf {w}^{(k)})}-{\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2\right]\le \beta ^2\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)} e_y^{(k)}}\sum _{e=1}^{e^{(k)}_y} \mathbb {E}_k\left[\left\Vert \mathbf {w}^{(k)}-\mathbf {w}^{(k),e-1}_{y}\right\Vert ^2\right],\hspace{-28.45274pt}\end{aligned}\) 
where we used Jensens's inequality and \(\beta \) -smoothness of the loss functions.
We then bound the last term in the above bound as follows:
\(&\mathbb {E}_k\left[\left\Vert \mathbf {w}^{(k)}-\mathbf {w}^{(k),e-1}_{y}\right\Vert ^2\right]{=}\eta _k^2 \mathbb {E}_k\left[\left\Vert \sum _{e^{\prime }=1}^{e-1} \sum _{d\in \mathcal {B}^{(k),e^{\prime }}_{y}} \hspace{-2.84526pt} {\frac{\nabla f(\mathbf {w}^{(k),e^{\prime }-1}_{y},d)}{{B}^{(k)}_{y}}}\right\Vert ^2 \right]\nonumber \\&= \eta _k^2 \mathbb {E}_k{4}[\Bigg \Vert \sum _{e^{\prime }=1}^{e-1} \Big (\sum _{d\in \mathcal {B}^{(k),e^{\prime }}_{y}} \hspace{-2.84526pt} {\frac{\nabla f(\mathbf {w}^{(k),e^{\prime }-1}_{y},d)}{{B}^{(k)}_{y}}}-\nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y})+\nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y})\Big )\Bigg \Vert ^2 {4}]\nonumber \\& {\le }2 \eta _k^2 \mathbb {E}_k\left[\Bigg \Vert \sum _{e^{\prime }=1}^{e-1} \sum _{d\in \mathcal {B}^{(k),e^{\prime }}_{y}} \hspace{-2.84526pt} {\frac{\nabla f(\mathbf {w}^{(k),e^{\prime }-1}_{y},d)}{{B}^{(k)}_{y}}}-\nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y})\Bigg \Vert ^2\right]+2 \eta _k^2 \mathbb {E}_k\left[\Bigg \Vert \sum _{e^{\prime }=1}^{e-1} \nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y}) \Bigg \Vert ^2\right]\nonumber \\& \nonumber {=} {2 \eta _k^2 \sum _{e^{\prime }=1}^{e-1}\mathbb {E}_k\left[\Bigg \Vert \sum _{d\in \mathcal {B}^{(k),e^{\prime }}_{y}} \hspace{-2.84526pt} {\frac{\nabla f(\mathbf {w}^{(k),e^{\prime }-1}_{y},d)}{{B}^{(k)}_{y}}}-\nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y})\Bigg \Vert ^2\right]}+{2 \eta _k^2 \mathbb {E}_k\left[\Bigg \Vert \sum _{e^{\prime }=1}^{e-1}\nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y})\Bigg \Vert ^2\right]}\\& \le 4 (e-1)\eta _k^2 \left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y +\underbrace{2 \eta _k^2 \mathbb {E}_k\left[\Bigg \Vert \sum _{e^{\prime }=1}^{e-1}\nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y})\Bigg \Vert ^2\right]}_{(a)},\) 

where we used Cauchy–Schwarz inequality, the fact that noise of SGD is zero mean, and Lemma REF . We then bound term \((a)\)  in (REF ) as follows:
\(&2 \eta _k^2 \mathbb {E}_k\left[\Bigg \Vert \sum _{e^{\prime }=1}^{e-1}\nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y})\Bigg \Vert ^2\right] \le 2 \eta _k^2 (e-1)\sum _{e^{\prime }=1}^{e-1}\mathbb {E}_k\left[\Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y}) - \nabla F^{(k)}_y(\mathbf {w}^{(k)})+ \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2 \right]\nonumber \\&{\le } 4 \eta _k^2 (e-1)\sum _{e^{\prime }=1}^{e-1}\mathbb {E}_k\left[\Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y}) - \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2\right] + 4 \eta _k^2 (e-1)\sum _{e^{\prime }=1}^{e-1} \Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2\nonumber \\&\le 4 \eta _k^2 (e-1)\sum _{e^{\prime }=1}^{e-1}\mathbb {E}_k\left[\Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k),e^{\prime }-1}_{y}) - \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2\right] + 4 \eta _k^2 (e-1)\sum _{e^{\prime }=1}^{e-1} \Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2\nonumber \\&\le 4\eta _k^2\beta ^2 (e-1) \sum _{e^{\prime }=1}^{e-1}\mathbb {E}_k\left[\Bigg \Vert \mathbf {w}^{(k),e^{\prime }-1}_{y} - \mathbf {w}^{(k)}\Bigg \Vert ^2\right]+ 4 \eta _k^2 (e-1)\sum _{e^{\prime }=1}^{e-1} \Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2 ,\) 

where we used Cauchy-Schwarz inequality repeatedly and applied the \(\beta \) -smoothness of the loss function. Replacing the above expression in (REF ) yields
\(\mathbb {E}_k\left[ \left\Vert \mathbf {w}^{(k)}-\mathbf {w}^{(k),e-1}_{y}\right\Vert ^2\right] \le & 4 (e-1)\eta _k^2 \left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y\nonumber \\& + 4\eta _k^2\beta ^2 (e-1) \sum _{e^{\prime }=1}^{e-1}\mathbb {E}_k\left[\Bigg \Vert \mathbf {w}^{(k),e^{\prime }-1}_{y} - \mathbf {w}^{(k)}\Bigg \Vert ^2\right]+ 4 \eta _k^2 (e-1)\sum _{e^{\prime }=1}^{e-1} \Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2,\) 

which implies:
\(&\sum _{e=1}^{e_y^{(k)}} \mathbb {E}_k\left[\left\Vert \mathbf {w}^{(k)}-\mathbf {w}^{(k),e-1}_{y}\right\Vert ^2\right] \le 4 \eta _k^2\sum _{e=1}^{e_y^{(k)}} (e-1) \left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2 \nonumber \\& + 4\eta _k^2\beta ^2 \sum _{e=1}^{e_y^{(k)}}(e-1) \sum _{e^{\prime }=1}^{e-1}\mathbb {E}_k\left[\Bigg \Vert \mathbf {w}^{(k),e^{\prime }-1}_{y} - \mathbf {w}^{(k)}\Bigg \Vert ^2\right]+ 4 \eta _k^2 \sum _{e=1}^{e_y^{(k)}}(e-1)\sum _{e^{\prime }=1}^{e-1} \Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2\nonumber \\&\le 4 \eta _k^2 \left(e_y^{(k)}\right)\left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2 \nonumber \\& + 4\eta _k^2\beta ^2 \left(e_y^{(k)}\right)\left(e_y^{(k)}-1\right) \sum _{e=1}^{e_y^{(k)}}\mathbb {E}_k\left[\Bigg \Vert \mathbf {w}^{(k),e-1}_{y} - \mathbf {w}^{(k)}\Bigg \Vert ^2\right]+ 4 \eta _k^2 \left(e_y^{(k)}\right)\left(e_y^{(k)}-1\right) \sum _{e=1}^{e_y^{(k)}} \Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2,\) 

Assuming \(\eta _k \le \left(2\beta \sqrt{e_y^{(k)}(e_y^{(k)}-1)}\right)^{-1},\forall n\) , we get
\(\nonumber \sum _{e=1}^{e_y^{(k)}} \mathbb {E}_k\left[\left\Vert \mathbf {w}^{(k)}-\mathbf {w}^{(k),e-1}_{y}\right\Vert ^2\right] \le &\frac{4 \eta _k^2 \left(e_y^{(k)}\right)\left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}{1- 4\eta _k^2\beta ^2 e_y^{(k)}\left(e_y^{(k)}-1\right)}\\& + \frac{4 \eta _k^2 \left(e_y^{(k)}\right)^2\left(e_y^{(k)}-1\right)}{1- 4\eta _k^2\beta ^2 e_y^{(k)}\left(e_y^{(k)}-1\right)} \Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2.\) 

Replacing the above expression in (REF ), we get:
\(\begin{aligned}&\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}-\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{{D}^{(k)} e^{(k)}_y} \sum _{e=1}^{e^{(k)}_y} {\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y})}\right\Vert ^2\le \beta ^2\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)} e_y^{(k)}}\sum _{e=1}^{e^{(k)}_y} \mathbb {E}_k\left[\left\Vert \mathbf {w}^{(k)}-\mathbf {w}^{(k),e-1}_{y}\right\Vert ^2\right]\\&\le \beta ^2\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)} e_y^{(k)}}{4}[ \frac{4 \eta _k^2 \left(e_y^{(k)}\right)\left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}{1- 4\eta _k^2\beta ^2 e_y^{(k)}\left(e_y^{(k)}-1\right)}\\& + \frac{4 \eta _k^2 \left(e_y^{(k)}\right)^2\left(e_y^{(k)}-1\right)}{1- 4\eta _k^2\beta ^2 e_y^{(k)}\left(e_y^{(k)}-1\right)} \Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2{4}]\\&=\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}e_y^{(k)}} \frac{4 \beta ^2 \eta _k^2 e_y^{(k)}\left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}{1- 4\eta _k^2\beta ^2 e_y^{(k)}\left(e_y^{(k)}-1\right)}\\&+ \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}}\frac{4 \beta ^2\eta _k^2 e_y^{(k)}\left(e_y^{(k)}-1\right)}{1- 4\eta _k^2\beta ^2 e_y^{(k)}\left(e_y^{(k)}-1\right)} \Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2\\&\le \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}e_y^{(k)}} \frac{4 \beta ^2 \eta _k^2 e_y^{(k)}\left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}{1- 4\eta _k^2\beta ^2 e_y^{(k)}\left(e_y^{(k)}-1\right)}\\&+\frac{4 \beta ^2\eta _k^2 e^{(k)}_{\mathsf {max}}\left(e^{(k)}_{\mathsf {max}}-1\right)}{1- 4\eta _k^2\beta ^2 e^{(k)}_{\mathsf {max}}\left(e^{(k)}_{\mathsf {max}}-1\right)} \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}} \Bigg \Vert \nabla F^{(k)}_y(\mathbf {w}^{(k)})\Bigg \Vert ^2\\&\le \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}} \frac{4 \beta ^2 \eta _k^2 \left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}{1- 4\eta _k^2\beta ^2 e_y^{(k)}\left(e_y^{(k)}-1\right)}\\&+\frac{4 \beta ^2\eta _k^2 e^{(k)}_{\mathsf {max}}\left(e^{(k)}_{\mathsf {max}}-1\right)}{1- 4\eta _k^2\beta ^2 e^{(k)}_{\mathsf {max}}\left(e^{(k)}_{\mathsf {max}}-1\right)} \left( \zeta _1 \left\Vert \nabla F^{(k)}(\mathbf {w}^{(k)})\right\Vert ^2 + \zeta _2 \right),\end{aligned}\) 
where we used
\(e^{(k)}_{\mathsf {max}}=\max _{n\in \mathcal {N}}\lbrace e^{(k)}_y\rbrace \) , and the bounded dissimilarity of local gradients (Assumption REF ).
Replacing the above expression in (REF ) gives us
\(\begin{aligned}&\mathbb {E}_k \left[F^{(k)}(\mathbf {w}^{(k+1)})\right] \le F^{(k)}(\mathbf {w}^{(k)}) -\left(\frac{\eta _k}{4}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\right)\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 \\&+\left(\frac{\eta _k}{2}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}}\right) {4}[ \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}} \frac{4 \beta ^2 \eta _k^2 \left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}{1- 4\eta _k^2\beta ^2 e_y^{(k)}\left(e_y^{(k)}-1\right)}\\&+\frac{4 \beta ^2\eta _k^2 e^{(k)}_{\mathsf {max}}\left(e^{(k)}_{\mathsf {max}}-1\right)}{1- 4\eta _k^2\beta ^2 e^{(k)}_{\mathsf {max}}\left(e^{(k)}_{\mathsf {max}}-1\right)} \left( \zeta _1 \left\Vert \nabla F^{(k)}(\mathbf {w}^{(k)})\right\Vert ^2 + \zeta _2 \right){4}]\\&+\frac{3}{2}{\eta _k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]+2{\beta \eta ^2_{k}}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} \sqrt{e^{(k)}_y}}\right)^2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y, \hspace{-14.22636pt}\end{aligned}\) 
which implies
\(\hspace{-39.83385pt}\mathbb {E}_k &\left[F^{(k)} (\mathbf {w}^{(k+1)})\right] \le F^{(k)}(\mathbf {w}^{(k)}) + \frac{\eta _{k}}{2}\sum _{n\in \mathcal {N}}\frac{{D}^{(k)}_{y}e^{(k)}_{y}}{{D}^{(k)} } \left(\frac{4 \eta _k^2\beta ^2 \left(e_{\mathsf {max}}^{(k)}\right)\left(e_{\mathsf {max}}^{(k)}-1\right)}{1- 4\eta _k^2\beta ^2 e_{\mathsf {max}}^{(k)}\left(e_{\mathsf {max}}^{(k)}-1\right)}\zeta _1-\frac{1}{2} \right)\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 \nonumber \\&\hspace{-22.76219pt}\nonumber + \frac{\eta _{k}}{2}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} } {4}(\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}} \frac{4 \beta ^2 \eta _k^2 \left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}{1- 4\eta _k^2\beta ^2 e_{\mathsf {max}}^{(k)}\left(e_{\mathsf {max}}^{(k)}-1\right)}+ \frac{4\zeta _2 \eta _k^2\beta ^2 \left(e_{\mathsf {max}}^{(k)}\right)\left(e_{\mathsf {max}}^{(k)}-1\right)}{1- 4\eta _k^2\beta ^2 e_{\mathsf {max}}^{(k)}\left(e_{\mathsf {max}}^{(k)}-1\right)}{4})\nonumber \\&\hspace{-22.76219pt}+\frac{3}{2}{\eta _k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]+2{\beta \eta ^2_{k}}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} \sqrt{e^{(k)}_y}}\right)^2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y.\hspace{-39.83385pt}\) 
Assuming \(\frac{4 \eta _k^2\beta ^2 \left(e_{\mathsf {max}}^{(k)}\right)\left(e_{\mathsf {max}}^{(k)}-1\right)}{1- 4\eta _k^2\beta ^2 e_{\mathsf {max}}^{(k)}\left(e_{\mathsf {max}}^{(k)}-1\right)}\zeta _1 \le \frac{1}{4} \) , implying \(\frac{1}{1- 4\eta _k^2\beta ^2 e_{\mathsf {max}}^{(k)}\left(e_{\mathsf {max}}^{(k)}-1\right)} \le \frac{1+4\zeta _1}{\zeta _1}\le 5\) , which can be obtained under the step size choice of \(\eta _k \le \frac{1}{2\beta } \sqrt{ \frac{1}{(4\zeta _1+1)\left( e_{\mathsf {max}}^{(k)}\left(e_{\mathsf {max}}^{(k)}-1\right)\right)}}\) , we get
\(\mathbb {E}_k &\left[F^{(k)} (\mathbf {w}^{(k+1)})\right] \le F^{(k)}(\mathbf {w}^{(k)}) -\frac{1}{8}{\eta _{k}}\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2\sum _{n\in \mathcal {N}}\frac{{D}^{(k)}_{y}e^{(k)}_{y}}{{D}^{(k)} }\nonumber \\&\nonumber + \frac{\eta _{k}}{2}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} } {4}(\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}} {20 \beta ^2 \eta _k^2 \left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}+ {20\zeta _2 \eta _k^2\beta ^2 \left(e_{\mathsf {max}}^{(k)}\right)\left(e_{\mathsf {max}}^{(k)}-1\right)}{4})\nonumber \\&+\frac{3}{2}{\eta _k}\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{{D}}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)}} \mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]\nonumber \\&+2{\beta \eta ^2_{k}}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right)^2 \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} \sqrt{e^{(k)}_y}}\right)^2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y.\hspace{-39.83385pt}\) 

Rearranging the terms of the above bound gives the following bound on the norm of gradient:
\(&\left\Vert \nabla {F^{(k)}(\mathbf {w}^{(k)})}\right\Vert ^2 \le \frac{F^{(k)}(\mathbf {w}^{(k)}) - \mathbb {E}_k \left[F^{(k)} (\mathbf {w}^{(k+1)})\right]}{\eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}/(8D^{(k)})}\nonumber \\&\hspace{-17.07164pt}+\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}} {80 \beta ^2 \eta _k^2 \left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}+ {80\zeta _2 \eta _k^2\beta ^2 \left(e_{\mathsf {max}}^{(k)}\right)\left(e_{\mathsf {max}}^{(k)}-1\right)}\nonumber \\&\hspace{-22.76219pt}+24\mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]+16{\beta \eta _{k}}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right) \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} \sqrt{e^{(k)}_y}}\right)^2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y.\) 
Note that \(F^{(k)}(\mathbf {w}^{(k)})\)  in the first term on the right hand side of the above bound is in fact the loss under which the global aggregation started from, i.e., \(F^{(k)}(\mathbf {w}^{(k)} |, {\mathcal {D}}^{(k)})\)  and \(F^{(k)}(\mathbf {w}^{(k+1)})\)  is the loss under which the global aggregation concludes, i.e., \(F^{(k)}(\mathbf {w}^{(k+1)} | {\mathcal {D}}^{(k)})\) . We next find the connection between
\(F^{(k)}(\mathbf {w}^{(k)} | {\mathcal {D}}^{(k)})\)  and the actual loss under which iteration \(k-1\)  has been concluded, i.e., \(F^{(k-1)}(\mathbf {w}^{(k)} | {\mathcal {D}}^{(k-1)})\) . Using the definition of model/concept drift in Definition REF , since the global loss is defined as the loss per data point we have:
\(F^{(k)}(\mathbf {w}^{(k)} | {\mathcal {D}}^{(k)})&= \sum _{m\in \mathcal {M}}\sum _{y \in \mathcal {N}^{(k)}_m} \Bigg [\frac{{D}_y^{(k)}}{{D}^{(k)}}F_{y}^{(k)}(\mathbf {w}^{(k)}|{\mathcal {D}}_y^{(k)})-\frac{{D}_y^{(k-1)}}{{D}^{(k-1)}}F^{(k-1)}_{y}(\mathbf {w}^{(k)}|{{D}}_y^{(k-1)})+\frac{{D}_y^{(k-1)}}{{D}^{(k-1)}}F^{(k-1)}_{y}(\mathbf {w}^{(k)}|{{D}}_y^{(k-1)})\Bigg ]\nonumber \\&\le \sum _{m\in \mathcal {M}}\sum _{y \in \mathcal {N}^{(k)}_m} \Delta _y^{(k)} + \sum _{m\in \mathcal {M}}\sum _{y \in \mathcal {N}^{(k)}_m}\frac{{D}_y^{(k-1)}}{{D}^{(k-1)}}F^{(k-1)}_{y}(\mathbf {w}^{(k)}|{{D}}_y^{(k-1)})\nonumber \\&=\sum _{m\in \mathcal {M}}\sum _{y \in \mathcal {N}^{(k)}_m} \Delta _y^{(k)}+ F^{(k-1)}(\mathbf {w}^{(k)}|{\mathcal {D}}^{(k-1)})= \Delta ^{(k)} + F^{(k-1)}(\mathbf {w}^{(k)}),~k\ge 1.\) 
Taking total expectation from both hand sides of (REF ) and taking the summation over global aggregation index implies
\(&\hspace{-45.5244pt}\frac{1}{K} \sum _{k=0}^{K-1} \mathbb {E} \left[\Vert \nabla F^{(k)}(\mathbf {w}^{({k})}) \Vert ^2\right] \le \frac{1}{K}\frac{F^{(0)}(\mathbf {w}^{(0)}) - F^{(0)}(\mathbf {w}^{(1)})}{\eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}/(8D^{(k)})}+ \frac{1}{K}\sum _{k=1}^{K-1}\frac{F^{(k-1)}(\mathbf {w}^{(k)}) - F^{(k)}(\mathbf {w}^{(k+1)})}{\eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}/(8D^{(k)})}\nonumber \\&+\frac{1}{K}\sum _{k=1}^{K-1}\frac{ \Delta ^{(k)}}{\eta _k\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}/(8D^{(k)})}\nonumber \\&\hspace{-17.07164pt}+\frac{1}{K}\sum _{k=0}^{K-1}\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}} {80 \beta ^2 \eta _k^2 \left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}+\frac{1}{K}\sum _{k=0}^{K-1} {80\zeta _2 \eta _k^2\beta ^2 \left(e_{\mathsf {max}}^{(k)}\right)\left(e_{\mathsf {max}}^{(k)}-1\right)}\nonumber \\&\hspace{-22.76219pt}+\frac{1}{K}\sum _{k=0}^{K-1} 24\mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]+\frac{1}{K}\sum _{k=0}^{K-1}16{\beta \eta _{k}}\left(\sum _{m\in \mathcal {M}}\sum _{y^{\prime }\in \mathcal {N}^{(k)}_m}\frac{{D}^{(k)}_{y^{\prime }}e^{(k)}_{y^{\prime }}}{{D}^{(k)} }\right) \sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} \sqrt{e^{(k)}_y}}\right)^2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y.\hspace{-17.07164pt}\) 

Assuming the choice of step size \(\eta _k =\frac{\alpha }{{\sqrt{K e^{(k)}_{\mathsf {avg}}}}}\) , where \(e^{(k)}_{\mathsf {avg}}\)  denotes the average number of local iterations across the participating devices, we get:
\(&\hspace{-45.5244pt}\frac{1}{K} \sum _{k=0}^{K-1} \mathbb {E} \left[\Vert \nabla F^{(k)}(\mathbf {w}^{({k})}) \Vert ^2\right] \le \frac{8 \sqrt{{e}^{\mathsf {max}}_{\mathsf {avg}}}}{\alpha \hat{e}^{\mathsf {min}}_{\mathsf {avg}}\sqrt{K}}\left({F^{(0)}(\mathbf {w}^{(0)}) - F^{{(k)}^\star }}\right)+\frac{8 \sqrt{{e}^{\mathsf {max}}_{\mathsf {avg}}}}{\alpha \hat{e}^{\mathsf {min}}_{\mathsf {avg}}\sqrt{K}}\sum _{k=1}^{K-1}{ \Delta ^{(k)}}\nonumber \\&\hspace{-17.07164pt}+\frac{80 \beta ^2 \alpha ^2}{K^2{e}^{\mathsf {min}}_{\mathsf {avg}}}\sum _{k=0}^{K-1}\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}} { \left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}+\frac{80 \beta ^2 \alpha ^2}{K^2{e}^{\mathsf {min}}_{\mathsf {avg}}}\sum _{k=0}^{K-1} {\zeta _2 \left(e_{\mathsf {max}}^{(k)}\right)\left(e_{\mathsf {max}}^{(k)}-1\right)}\nonumber \\&\hspace{-22.76219pt}+\frac{1}{K}\sum _{k=0}^{K-1} 24\underbrace{\mathbb {E}_k\left[\left\Vert \mathbf {c}_{m_k}^{(k)}\right\Vert ^2\right]}_{(a)}+\frac{16 \beta \alpha \hat{e}^{\mathsf {max}}_{\mathsf {avg}}}{K\sqrt{K}\sqrt{{e}^{\mathsf {min}}_{\mathsf {avg}}}}\sum _{k=0}^{K-1}\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} \sqrt{e^{(k)}_y}}\right)^2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y.\hspace{-17.07164pt}\) 
We next aim to bound term \((a)\)  in (REF ). Let \(\widetilde{\nabla F}_m^{(k)}\)  denote the initial local aggregated gradient at ES \(m\) , containing its own gradient and the gradient of its associated users, and \(\widehat{\nabla F}_m^{(k)}\)  denote the gradient at ES \(m\)  after the consensus through P2P communications concludes.
As explained in (REF ), we have
\({\nabla {F}}_m^{\mathsf {L},(k)}= \sum _{m\in \mathcal {M}} {\nabla {F}}_m^{\mathsf {A},(k)} + \mathbf {e}^{(k)}_m.\) 
On the other hand, the evolution of the local gradient during the consensus process can be described as
\({\nabla {F}}^{\mathsf {L},(k)}= \left(\mathbf {\Lambda }^{(k)}\right)^{\varphi ^{(k)}} {\nabla {F}}^{\mathsf {A},(k)},\) 
where \({\nabla {F}}^{\mathsf {L},(k)}\in \mathbb {R}^{d \times d}\)  denotes a matrix,\(d\)  denotes the size/length of the gradient vector. with its row \(m\)  containing the final vector of gradient at ES \(m\)  (i.e., \( {\nabla {F}}_m^{\mathsf {L},(k)}\) ), and \( \nabla {F}^{\mathsf {A},(k)} \in \mathbb {R}^{d \times d}\)  denotes a matrix, with its row \(m\)  containing the initial gradient vector at ES \(m\)  (i.e., \({\nabla {F}}_m^{\mathsf {A},(k)}\) ). In (REF ), \(\mathbf {\Lambda }^{(k)}=[\lambda ^{(k)}_{i,j}]_{i,j\in \mathcal {M}}\)  is the consensus matrix across the ES network and \(\varphi ^{(k)}\)  denotes the rounds of P2P communications at the aggregation round \(k\) .
Let matrix \({{\nabla {F}}^{\mathsf {P},(k)}}\)  denote
the matrix of true/perfect average of the gradient vectors across the ESs, which is given by
\({{\nabla {F}}^{\mathsf {P},(k)}}= \frac{\textbf {1}_{M} \textbf {1}_{M}^\top {\nabla {F}}_m^{\mathsf {A},(k)}}{M}.\) 
Also, let \({{\nabla {F}}^{\mathsf {P},(k)}}_m\)  denote the \(m\) -th row of \({{\nabla {F}}^{\mathsf {P},(k)}}\) .
Since the consensus error is zero mean [1]} across the ESs, we have \( \mathbf {1}^\top \left({\nabla {F}}^{\mathsf {L},(k)} -{\nabla {F}}^{\mathsf {A},(k)}\right)=\mathbf {0}\)  implying that \((\mathbf {1} \mathbf {1}^\top )\left({\nabla {F}}^{\mathsf {L},(k)} -{\nabla {F}}^{\mathsf {A},(k)}\right)=\mathbf {0}\) . Thus, we get
\(\begin{aligned}{\nabla {F}}^{\mathsf {L},(k)} -{{\nabla {F}}^{\mathsf {P},(k)}}&=\left(\mathbf {I}-\frac{\mathbf {1} \mathbf {1}^\top }{M}\right)\left({\nabla {F}}^{\mathsf {L},(k)} -{{\nabla {F}}^{\mathsf {P},(k)}}\right)=\left(\mathbf {I}-\frac{\mathbf {1} \mathbf {1}^\top }{M}\right)\left( \left(\mathbf {\Lambda }^{(k)}\right)^{\varphi ^{(k)}}{\nabla {F}}^{\mathsf {A},(k)}-{{\nabla {F}}^{\mathsf {P},(k)}}\right)\\&=\left(\mathbf {I}-\frac{\mathbf {1} \mathbf {1}^\top }{M}\right)\left(\left(\mathbf {\Lambda }^{(k)}\right)^{\varphi ^{(k)}} {\nabla {F}}^{\mathsf {A},(k)}-\left(\mathbf {\Lambda }^{(k)}\right)^{\varphi ^{(k)}}{{\nabla {F}}^{\mathsf {P},(k)}}\right)\\&=\left(\left(\mathbf {\Lambda }^{(k)}\right)^{\varphi ^{(k)}}-\frac{\mathbf {1} \mathbf {1}^\top }{M}\right)\left({\nabla {F}}^{\mathsf {A},(k)}-{{\nabla {F}}^{\mathsf {P},(k)}}\right),\end{aligned}\) 
where the above derivations are obtained based on the following properties: (i) \(\left(\mathbf {\Lambda }^{(k)}\right)^{\varphi ^{(k)}} {{\nabla {F}}^{\mathsf {P},(k)}}={{\nabla {F}}^{\mathsf {P},(k)}}\) , and (ii) \(\frac{\mathbf {1} \mathbf {1}^\top }{M} \left(\mathbf {\Lambda }^{(k)}\right)^{\varphi ^{(k)}}=\frac{\mathbf {1} \mathbf {1}^\top }{M}\) .
We finally get
\(\begin{aligned}\big \Vert \mathbf {c}^{(k)}_m\big \Vert ^2 &\le \textrm {trace}\left(\left({\nabla {F}}^{\mathsf {A},(k)}-{{\nabla {F}}^{\mathsf {P},(k)}}\right)^\top \left(\left(\mathbf {\Lambda }^{(k)}\right)^{\varphi ^{(k)}}-\frac{\mathbf {1} \mathbf {1}^\top }{M}\right)^2\left({\nabla {F}}^{\mathsf {A},(k)}-{{\nabla {F}}^{\mathsf {P},(k)}}\right)\right)\\&=\textrm {trace}\left(\left({\nabla {F}}^{\mathsf {A},(k)}-{{\nabla {F}}^{\mathsf {P},(k)}}\right)^\top \left(\left(\mathbf {\Lambda }^{(k)}\right)^{\varphi ^{(k)}}\left[\mathbf {I}-\frac{\mathbf {1} \mathbf {1}^\top }{M}\right]\right)^2\left({\nabla {F}}^{\mathsf {A},(k)}-{{\nabla {F}}^{\mathsf {P},(k)}}\right)\right)\\&=\textrm {trace}\left(\left({\nabla {F}}^{\mathsf {A},(k)}-{{\nabla {F}}^{\mathsf {P},(k)}}\right)^\top \left(\left(\mathbf {\Lambda }^{(k)}\right)^{\varphi ^{(k)}}\left[\mathbf {I}-\frac{\mathbf {1} \mathbf {1}^\top }{M}\right]^{\varphi ^{(k)}}\right)^2\left({\nabla {F}}^{\mathsf {A},(k)}-{{\nabla {F}}^{\mathsf {P},(k)}}\right)\right)\\&\le (\lambda ^{(k)})^{2\varphi ^{(k)}} \sum _{m^{\prime }\in \mathcal {M}} \Vert {\nabla {F}}^{\mathsf {A},(k)}_{m^{\prime }} -\nabla {F}^{\mathsf {P},(k)}_{m^{\prime }} \big \Vert ^2\\&\le \frac{1}{M} (\lambda ^{(k)})^{2\varphi ^{(k)}} \sum _{m^{\prime },m^{\prime \prime }\in \mathcal {M}} \Vert {\nabla {F}}^{\mathsf {A},(k)}_{m^{\prime }} -\nabla {F}^{\mathsf {A},(k)}_{m^{\prime \prime }} \big \Vert ^2\\&\le {M} (\lambda ^{(k)})^{2\varphi ^{(k)}} \max _{m^{\prime },m^{\prime \prime }\in \mathcal {M}} \Vert {\nabla {F}}^{\mathsf {A},(k)}_{m^{\prime }} -\nabla {F}^{\mathsf {A},(k)}_{m^{\prime \prime }} \big \Vert ^2\le {M} (\lambda ^{(k)})^{2\varphi ^{(k)}} \left(\Xi ^{(k)}\right)^2.\end{aligned}\) 
Replacing the above result back in (REF ), we get the final result
\(&\hspace{-45.5244pt}\frac{1}{K} \sum _{k=0}^{K-1} \mathbb {E} \left[\Vert \nabla F^{(k)}(\mathbf {w}^{({k})}) \Vert ^2\right] \le \frac{8 \sqrt{{e}^{\mathsf {max}}_{\mathsf {avg}}}}{\alpha \hat{e}^{\mathsf {min}}_{\mathsf {avg}}\sqrt{K}}\left({F^{(0)}(\mathbf {w}^{(0)}) - F^{{(k)}^\star }}\right)+\frac{8 \sqrt{{e}^{\mathsf {max}}_{\mathsf {avg}}}}{\alpha \hat{e}^{\mathsf {min}}_{\mathsf {avg}}\sqrt{K}}\sum _{k=1}^{K-1}{ \Delta ^{(k)}}\nonumber \\&\hspace{-17.07164pt}+\frac{80 \beta ^2 \alpha ^2}{K^2{e}^{\mathsf {min}}_{\mathsf {avg}}}\sum _{k=0}^{K-1}\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\frac{{D}^{(k)}_y}{D^{(k)}} { \left(e_y^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2}+\frac{80 \beta ^2 \alpha ^2}{K^2{e}^{\mathsf {min}}_{\mathsf {avg}}}\sum _{k=0}^{K-1} {\zeta _2 \left(e_{\mathsf {max}}^{(k)}\right)\left(e_{\mathsf {max}}^{(k)}-1\right)}\nonumber \\&\hspace{-22.76219pt}+\frac{1}{K}\sum _{k=0}^{K-1} 24{M} (\lambda ^{(k)})^{2\varphi ^{(k)}} \left(\Xi ^{(k)}\right)^2+\frac{16 \beta \alpha \hat{e}^{\mathsf {max}}_{\mathsf {avg}}}{K\sqrt{K}\sqrt{{e}^{\mathsf {min}}_{\mathsf {avg}}}}\sum _{k=0}^{K-1}\sum _{m\in \mathcal {M}}\sum _{y\in \mathcal {N}_m^{(k)}}\left(\frac{{D}^{(k)}_y}{{D}^{(k)} \sqrt{e^{(k)}_y}}\right)^2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y.\hspace{-17.07164pt}\) 

Proof of Corollary  REF
Assuming \(\Delta ^{(k)}\le \frac{\Upsilon }{K}\)  and considering
the assumption \(\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y}\Theta _y^2\le \vartheta \)  simplifies the bound in (REF ) as follows:
\(&\hspace{-45.5244pt}\frac{1}{K} \sum _{k=0}^{K-1} \mathbb {E} \left[\Vert \nabla F^{(k)}(\mathbf {w}^{({k})}) \Vert ^2\right] \le \frac{8 \sqrt{{e}^{\mathsf {max}}_{\mathsf {avg}}}}{\alpha \hat{e}^{\mathsf {min}}_{\mathsf {avg}}\sqrt{K}}\left({F^{(0)}(\mathbf {w}^{(0)}) - F^{{(k)}^\star }}\right)+\frac{8\Upsilon \sqrt{{e}^{\mathsf {max}}_{\mathsf {avg}}}}{\alpha \hat{e}^{\mathsf {min}}_{\mathsf {avg}}\sqrt{K}}\nonumber \\&\hspace{-17.07164pt}+\frac{80 \beta ^2 \alpha ^2}{K^2{e}^{\mathsf {min}}_{\mathsf {avg}}}K \left(e_{\mathsf {max}}-1\right)\vartheta +\frac{80 \beta ^2 \alpha ^2}{K^2{e}^{\mathsf {min}}_{\mathsf {avg}}}K {\zeta _2 \left(e_{\mathsf {max}}\right)\left(e_{\mathsf {max}}-1\right)}\nonumber \\&\hspace{-22.76219pt}+\frac{1}{K}\sum _{k=0}^{K-1} 24{M} (\lambda ^{(k)})^{2\varphi ^{(k)}} \left(\Xi ^{(k)}\right)^2+\frac{16 \beta \alpha \hat{e}^{\mathsf {max}}_{\mathsf {avg}}}{K\sqrt{K}\sqrt{{e}^{\mathsf {min}}_{\mathsf {avg}}}}K\vartheta .\hspace{-17.07164pt}\) 

Assuming \({\varphi ^{(k)}} \ge \frac{1}{2} \left[\log _{\lambda ^{(k)}}\left( \frac{\xi }{\sqrt{K}\left(\Xi ^{(k)}\right)^2{M}^{(k)}}\right)\right]^+\)  implies that (note that \(\lambda ^{(k)}<1\) )
\(&\nonumber {2\varphi ^{(k)}} \ge \log _{\lambda ^{(k)}}\left( \frac{\xi }{\sqrt{K}\left(\Xi ^{(k)}\right)^2{M}^{(k)}}\right)\\&\Rightarrow (\lambda ^{(k)})^{2\varphi ^{(k)}} \le \frac{\xi }{\sqrt{K}\left(\Xi ^{(k)}\right)^2{M}^{(k)}}\\&\Rightarrow \nonumber {M}^{(k)} (\lambda ^{(k)})^{2\varphi ^{(k)}} \left(\Xi ^{(k)}\right)^2 \le \xi /\sqrt{K}.\) 

Replacing this result back in (REF ) yields
\(&\hspace{-45.5244pt}\frac{1}{K} \sum _{k=0}^{K-1} \mathbb {E} \left[\Vert \nabla F^{(k)}(\mathbf {w}^{({k})}) \Vert ^2\right] \le \frac{8 \sqrt{{e}^{\mathsf {max}}_{\mathsf {avg}}}}{\alpha \hat{e}^{\mathsf {min}}_{\mathsf {avg}}\sqrt{K}}\left({F^{(0)}(\mathbf {w}^{(0)}) - F^{{(k)}^\star }}\right)+\frac{8\Upsilon \sqrt{{e}^{\mathsf {max}}_{\mathsf {avg}}}}{\alpha \hat{e}^{\mathsf {min}}_{\mathsf {avg}}\sqrt{K}}\nonumber \\& \nonumber \hspace{-17.07164pt}+\frac{80 \beta ^2 \alpha ^2}{K{e}^{\mathsf {min}}_{\mathsf {avg}}}\left(e_{\mathsf {max}}-1\right)\vartheta +\frac{80 \beta ^2 \alpha ^2}{K{e}^{\mathsf {min}}_{\mathsf {avg}}} {\zeta _2 \left(e_{\mathsf {max}}\right)\left(e_{\mathsf {max}}-1\right)}+ 24\frac{\xi }{\sqrt{K}}+\frac{16 \beta \alpha \hat{e}^{\mathsf {max}}_{\mathsf {avg}}}{\sqrt{K}\sqrt{{e}^{\mathsf {min}}_{\mathsf {avg}}}}\vartheta ,\) 

and thus
\(&\frac{1}{K} \sum _{k=0}^{K-1} \mathbb {E} \left[\Vert \nabla F^{(k)}(\mathbf {w}^{({k})}) \Vert ^2\right] =\mathcal {O}\left(\frac{ \sqrt{{e}^{\mathsf {max}}_{\mathsf {avg}}}}{\alpha \hat{e}^{\mathsf {min}}_{\mathsf {avg}}\sqrt{K}}\right)+\mathcal {O}\left(\frac{\Upsilon \sqrt{{e}^{\mathsf {max}}_{\mathsf {avg}}}}{\alpha \hat{e}^{\mathsf {min}}_{\mathsf {avg}}\sqrt{K}} \right)+ \mathcal {O}\left(\frac{ \beta ^2 \alpha ^2}{K{e}^{\mathsf {min}}_{\mathsf {avg}}}\left(e_{\mathsf {max}}-1\right)\vartheta \right) \nonumber \\&+ \mathcal {O}\left(\frac{\beta ^2 \alpha ^2}{K{e}^{\mathsf {min}}_{\mathsf {avg}}} {\zeta _2 \left(e_{\mathsf {max}}\right)\left(e_{\mathsf {max}}-1\right)}\right)+ \mathcal {O}\left(\frac{\xi }{\sqrt{K}}\right)+\mathcal {O}\left(\frac{\beta \alpha \hat{e}^{\mathsf {max}}_{\mathsf {avg}}}{\sqrt{K}\sqrt{{e}^{\mathsf {min}}_{\mathsf {avg}}}}\vartheta \right)\nonumber \\&= \mathcal {O}\left(1/\sqrt{K}\right), \hspace{-17.07164pt}\) 

which concludes the proof.

Characterization of the Gradient of the Critic's Loss
Inspired by [2]}, our proof for the Lipschitz continuity property of the MSPBE loss function's gradient is presented as below. blackFirst, the loss function in (REF ) can be re-written as
\(E_\theta (\omega ) = \frac{1}{2} || V_\omega -\Lambda (B_\theta V_\omega )||^2 = \frac{1}{2} || \Lambda (V_\omega - B_\theta V_\omega ) ||^2, (since~V_\omega =\Lambda V_\omega ),\) 
which is upper-bounded by its expectation value given by the loss across the entire system state vector \(H\) :
\(E_\theta (\omega ) \le \frac{1}{2} || \Lambda (V_\omega - B_\theta V_\omega ) ||^2_H,\) 
where \(H\)  is the diagonal matrix whose elements are within the stationary system state distribution \(d^{\pi _\theta (s)}\) , \(\forall s \in \mathcal {S}\)  as defined in section REF . Under this stationary condition, (REF ) can be further analyzed as:
\(&\hspace{-42.67912pt} E_\theta (\omega ) = \frac{1}{2} \left[ \Lambda (V_\omega - B_\theta V_\omega ) \right]^\top H \left[ \Lambda (V_\omega - B_\theta V_\omega ) \right]\\&= \frac{1}{2} (V_\omega - B_\theta V_\omega )^\top \Lambda ^\top \raisebox {0pt}{\scalebox {1}{H}}\Lambda (V_\omega - B_\theta V_\omega ) \\&= \frac{1}{2} || \bar{\Lambda }\sqrt{\raisebox {0pt}{\scalebox {1}{H}}} (V_\omega - B_\theta V_\omega ) ||_2^2,\hspace{-17.07164pt}\) 

where \(\bar{\Lambda } = \sqrt{\raisebox {0pt}{\scalebox {1}{H}}} ^\top (\raisebox {0pt}{\scalebox {1}{H}}^\top )^{-1} \sqrt{\raisebox {0pt}{\scalebox {1}{H}}} \)  is an orthogonal projector of a column element of \(\sqrt{\raisebox {0pt}{\scalebox {1}{H}}} ^\top \) . Then, the Hessian product of the loss function is given by
\({H}(\omega )= (I - \gamma \raisebox {0pt}{\scalebox {1}{P}})^\top \sqrt{\raisebox {0pt}{\scalebox {1}{H}}} \bar{\Lambda } \sqrt{\raisebox {0pt}{\scalebox {1}{H}}} (I - \gamma \raisebox {0pt}{\scalebox {1}{P}})^\top ,\) 
where \(I \in {R}^{|\mathcal {S}| \times |\mathcal {S}|}\)  is the identity matrix, and \(\raisebox {0pt}{\scalebox {1}{P}}\)  is the transition probability as defined in Section REF . Since \( E_\theta (\omega )\)  is convex, its gradient is \(\ell \) -Lipschitz if
\(\omega ^\top {H}(\omega ) \omega \le l||\omega ||^2_2\) 
holds. Indeed, we have

H() = (I - \(P\))\(H\)  \(H\) (I - \(P\))
=
||\(H\)(I - \(P\))||22
=
||\(H\)||22 - 2\(H\)\(P\)+
2 || \(H\) \(P\)||22
||\(H\)||22 - 2\(H\)\(P\)+
2 ||\(H\) \(P\)||22
=
||\(H\) (I - \(P\))||22.

Using the Cauchy-Schwartz inequality, we have

H() ( ||\(H\) ||2 +||\(H\) \(P\)||2 )2 ( ||\(H\) ||22 + ||\(H\) ||2 )2 =
(1+)2||\(H\) ||22.

Here, we have

||\(H\) ||22 = ||||2\(P\)= i |S| di ((i))2
i |S| di ||i||22 ||i||22 (i||i||22 ) ||i||22.

Thus, we get
\(\omega ^\top {H}(\omega ) \omega \le (1+\gamma )^2\left(\underset{i}{\max }||^i||^2_2 \right) ||\theta ^i||^2_2,\) 
which leads to REF , and completes our proof.

Mini-Batch SGD Noise Characterization
Lemma 2 
During each aggregation round \(t\) , for each MD/ES \(i \in \mathcal {N} \cup \mathcal {M}\) , the variance of stochastic gradient during mini-batch gradient descent iteration \(k\) , i.e., \(\widetilde{\nabla } F_i^{(t)}(\mathbf {x})\)  is upper-bounded by
\(\mathbb {E}\left[ \left\Vert \sum _{d\in \mathcal {B}^{(k),e}_{y}} \hspace{-2.84526pt} \frac{\nabla f(\mathbf {w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_y}-\nabla F^{(k)}_y(\mathbf {w}^{(k),e-1}_{y}) \right\Vert ^2 \right] & \le 2\left(1-\frac{{B}^{(k)}_y}{{D}^{(k)}_y}\right) \frac{({\sigma }_{y}^{(k)})^2}{{B}^{(k)}_y} \Theta ^2_y,~\forall e,\) 

where \(\sigma _y^{(k)}\)  denotes the sampled variance of data at the respective node.

The proof can be easily carried out using the result on the variance of of simple random sampling in [3]} and our definition of the data variability in Definition REF , and thus omitted for brevity.
 