††thanks<EMAIL_ADDRESS>
# A Family of Bipartite Separability Criteria Based on Bloch Representation of
Density Matrices

Xue-Na Zhu1 Jing Wang2 Gui Bao1 Ming Li2 Shu-Qian Shen2 Shao-Ming Fei3,4
1School of Mathematics and Statistics Science, Ludong University, Yantai
264025, China
2College of the Science, China University of Petroleum, Qingdao 266580, China
3School of Mathematical Sciences, Capital Normal University, Beijing 100048,
China
4Max-Planck-Institute for Mathematics in the Sciences, 04103 Leipzig, Germany

###### Abstract

Abstract We study the separability of bipartite quantum systems in arbitrary
dimensions based on the Bloch representation of density matrices. We present
two separability criteria for quantum states in terms of the matrices
$T_{\alpha\beta}(\rho)$ and $W_{ab,\alpha\beta}(\rho)$ constructed from the
correlation tensors in the Bloch representation. These separability criteria
can be simplified and detect more entanglement than the previous separability
criteria. Detailed examples are given to illustrate the advantages of results.

##  I Introduction

Quantum entanglement F ; K ; H ; J ; C  lies at the heart of quantum
information processing and quantum computation ma . The quantification of
quantum entanglement has drawn much attention in the last decade. A prior
question in the study of quantum entanglement is to determine whether a given
quantum state is entangled or not. Denote $H_{M}$ and $H_{N}$ the vector
spaces with dimensions $M$ and $N$, respectively. A bipartite $M\otimes N$
state $\rho\in H_{M}\otimes H_{N}$ is said to be separable if it can be
written as a convex sum of tensor products of the states of subsystems,

$\rho=\sum_{i}p_{i}\rho^{i}_{M}\otimes\rho^{i}_{N},$ (1)

where $p_{i}\geq 0$ and $\sum_{i}p_{i}=1$. Otherwise $\rho$ is said to be
entangled.

As a consequence, much efforts have been devoted to the so-called separability
problem. The most well-known one is the positive partial transpose (PPT)
criterion ph1 ; ph2 , which is both necessary and sufficient for low-
dimensional systems $2\otimes 2$ and $2\otimes 3$. For high-dimensional
states, the PPT criterion is only a necessary one. A variety of separability
criteria have been proposed so far, such realignment criteria r1 ; r2 ,
covariance matrix criterion (CMC) 151  and so on 1 ; 2 ; 3 ; S . In
particular, much subsequent works VJ ; shen ; Liming ; 2020  have been devoted
to finding necessary conditions for separability based on Bloch representation
of density matrices.

In terms of the Bloch representation any quantum state $\rho\in H_{M}\otimes
H_{N}$ can be written as,

$\rho=\frac{1}{MN}\big{(}I_{M}\otimes
I_{N}+\sum_{k=1}^{M^{2}-1}r_{k}\lambda^{M}_{k}\otimes
I_{N}+\sum_{l=1}^{N^{2}-1}s_{l}I_{M}\otimes\lambda^{N}_{l}+\sum_{k=1}^{M^{2}-1}\sum_{l=1}^{N^{2}-1}t_{kl}\lambda^{M}_{k}\otimes\lambda^{N}_{l}\big{)},$
(2)

where $I_{i}$ $(i=M,N)$ denote the $i\times i$ identity matrix,
$\lambda^{M}_{i}$, $i=1,2,...,M^{2}-1$, are the generators of $SU(M)$ given by
$\\{\omega_{l},u_{jk},v_{jk}\\}$ with
$\omega_{l}=\sqrt{\frac{2}{(l+1)(l+2)}}\left(\sum_{i=0}^{l}|i\rangle\langle
i|-(l+1)|l+1\rangle\langle l+1|\right)$, $u_{jk}=|j\rangle\langle
k|+|k\rangle\langle j|$, $v_{jk}=-i(|j\rangle\langle k|-|k\rangle\langle j|)$,
$0\leq l\leq M-2$ and $0\leq j<k\leq M-1$,
$r_{i}=\frac{M}{2}Tr(\rho\lambda^{M}_{i}\otimes I_{N})$,
$s_{i}=\frac{N}{2}Tr(\rho I_{N}\otimes\lambda^{N}_{i})$ and
$t_{ij}=\frac{MN}{4}Tr(\rho\lambda^{M}_{i}\otimes\lambda^{N}_{j}).$

Denote $r=(r_{1},...,r_{M^{2}-1})^{t}$ and $s=(s_{1},...,s_{N^{2}-1})^{t}$,
where $t$ stands for transpose. Let $T(\rho)$ be the matrix with entries
$t_{kl}$. If the bipartite state $\rho\in H_{M}\otimes H_{N}$ with Bloch
representation (2) is separable, it has been shown that VJ

$||T(\rho)||_{KF}\leq\sqrt{\frac{MN(M-1)(N-1)}{4}},$ (3)

where the Ky Fan matrix norm is defined as the sum of the singular value of
the matrix, $||A||_{KF}=Tr\sqrt{A^{\dagger}A}.$ In Liming  the authors
presented a stronger separability criteria,

$||T^{{}^{\prime}}(\rho)||_{KF}\leq\frac{\sqrt{(M^{2}-M+2)(N^{2}-N+2)}}{2MN}$
(4)

for separable states, where $T^{{}^{\prime}}(\rho)=\begin{pmatrix}1&s^{t}\\\
r&T(\rho)\end{pmatrix}.$ In shen , the authors constructed the following
matrix,

$S^{m}_{ab}(\rho)=\begin{pmatrix}abE_{m\times m}&aw^{t}_{m}(s)\\\
bw_{m}(r)&T(\rho)\end{pmatrix},$

where $a$ and $b$ are nonnegative real numbers, $E_{mm}$ is the $m\times m$
matrix with all entries being $1$, $m$ is a given natural number, $w_{m}(x)$
denotes $m$ columns of the column vector $x$, i.e., $w_{m}(x)=(x...x).$ The
Theorem 1 of shen  showed that if the state $\rho\in H_{M}\otimes H_{N}$ is
separable, then $\rho$ satisfies

$||S^{m}_{ab}(\rho)||_{KF}\leq\frac{1}{2}\sqrt{(2ma^{2}+M^{2}-M)(2mb^{2}+N^{2}-N)},$
(5)

which is even stronger than the previous criteria.

##  II Separability Conditions from the Bloch Representation based on
$T_{\alpha\beta}(\rho)$

Denote $\alpha=(a_{1},...,a_{n})^{t}$ and $\beta=(b_{1},...,b_{m})^{t}$, where
$a_{i}$ $(i=1,...,n)$ and $b_{j}$ $(j=1,...,m)$ are given real numbers, $m$
and $n$ are positive integers. We define the following matrix,

$T_{\alpha\beta}(\rho)=\begin{pmatrix}\alpha\beta^{t}&\alpha s^{t}\\\
r\beta^{t}&T(\rho)\end{pmatrix}.$ (6)

Using $T_{\alpha\beta}(\rho)$, we have the following separability criterion
for bipartite states.

###### Theorem 1

If the state $\rho\in H_{M}\otimes H_{N}$ is separable, then

$||T_{\alpha\beta}(\rho)||_{KF}\leq\sqrt{||\alpha||^{2}_{2}+\frac{M(M-1)}{2}}\sqrt{||\beta||^{2}_{2}+\frac{N(N-1)}{2}},$
(7)

where $||\cdot||_{2}$ is the Euclidean norm on $R^{N^{2}-1}$.

[Proof] A bipartite quantum state with Bloch representation (2) is separable
if and only if there exist vectors $\mu_{i}\in R^{M^{2}-1}$ and $\nu_{i}\in
R^{N^{2}-1}$ with $||\mu_{i}||_{2}=\sqrt{\frac{M(M-1)}{2}}$ and
$||\nu_{i}||_{2}=\sqrt{\frac{N(N-1)}{2}}$, and $0<p_{i}\leq 1$ with
$\sum_{i}p_{i}=1$ such that

$T(\rho)=\sum_{i}p_{i}\mu_{i}\nu^{t}_{i},r=\sum_{i}p_{i}\mu_{i},s=\sum_{i}p_{i}\nu_{i}.$

The matrix $T_{\alpha\beta}(\rho)$ can then be written as,

$\displaystyle T_{\alpha\beta}(\rho)$ $\displaystyle=$
$\displaystyle\begin{pmatrix}\alpha\beta^{t}&\alpha s^{t}\\\
r\beta^{t}&T(\rho)\end{pmatrix}$ $\displaystyle=$
$\displaystyle\sum_{i}p_{i}\begin{pmatrix}\alpha\beta^{t}&\alpha\nu^{t}_{i}\\\
\mu_{i}\beta^{t}&\mu_{i}\nu^{t}_{i}\end{pmatrix}$ $\displaystyle=$
$\displaystyle\sum_{i}p_{i}\begin{pmatrix}\alpha\\\
\mu_{i}\end{pmatrix}\begin{pmatrix}\beta^{t},\nu^{t}_{i}\end{pmatrix}.$

Therefore,

$\displaystyle||T_{\alpha\beta}(\rho)||_{KF}$ $\displaystyle\leq$
$\displaystyle\sum_{i}p_{i}\left|\left|\begin{pmatrix}\alpha\\\
\mu_{i}\end{pmatrix}\right|\right|_{2}\cdot\left|\left|\begin{pmatrix}\beta^{t},\nu^{t}_{i}\end{pmatrix}\right|\right|_{2}$
$\displaystyle=$
$\displaystyle\sqrt{||\alpha||^{2}_{2}+\frac{M(M-1)}{2}}\sqrt{||\beta||^{2}_{2}+\frac{N(N-1)}{2}}.$

$\Box$

It can be seen that if we chose $a_{i}=a$ and $b_{j}=b$ for $i,j=1,...,n$ and
$m=n$, Theorem 1 reduces to the separability criterion (5) given in shen .

Define

$R(\beta)=\begin{pmatrix}p\beta\beta^{t}&\beta c^{t}\\\
c\beta^{t}&\textrm{W}\end{pmatrix},$

where $p$ is a nonzero real number, $\beta$ ($c$) is a nonzero $n$
($m$)-dimensional real vector, W is an $m\times m$ Hermitian matrix. We denote
$\lambda_{i}(R(\beta))$ $(i=1,...,m+n)$ the singular values of $R(\beta)$ with
$\lambda_{i}(R(\beta))\leq\lambda_{j}(R(\beta))$ $(i\leq j)$.

###### Lemma 1

For $\beta_{1}\not=\beta_{2}$ but $||\beta_{1}||_{2}=||\beta_{2}||_{2}$, we
have $\lambda_{i}(R(\beta_{1}))=\lambda_{i}(R(\beta_{2}))$ $(i=1,...,m+n).$

[Proof] With respect to any nonzero real vector
$\beta=(b_{1},b_{2},...,b_{n})^{t}$, there exists a unitary matrix U such that
$\textrm{U}\beta=(0,0,...,0,||\beta||_{2})^{t}$. Then we have

$\begin{pmatrix}U&0\\\ 0&I\end{pmatrix}R\begin{pmatrix}U^{\dagger}&0\\\
0&I\end{pmatrix}=\begin{pmatrix}0&0&0\\\
0&p||\beta||^{2}_{2}&||\beta||_{2}c^{t}\\\ 0&||\beta||_{2}c&\textrm{W}\\\
\end{pmatrix}.$

Denote

$D(\beta)=\begin{pmatrix}p||\beta||^{2}_{2}&||\beta||_{2}c^{t}\\\
||\beta||_{2}c&\textrm{W}\\\ \end{pmatrix}.$

Since the singular values of an Hermitian matrix do not change under the
unitary transformations, we have
$\lambda_{i}(R(\beta))=\lambda_{i}\left(\begin{pmatrix}0&0\\\ 0&D(\beta)\\\
\end{pmatrix}\right),$ $(i=1,...,m+n).$ Because of
$D(\beta_{1})=D(\beta_{2})$, we complete the proof. $\Box$

Since the Ky Fan matrix norm
$||T_{\alpha\beta}(\rho)||_{KF}=Tr\sqrt{T_{\alpha\beta}(\rho)^{\dagger}T_{\alpha\beta}(\rho)}$,
$r\in\emph{R}^{M^{2}-1}$, $s\in\emph{R}^{N^{2}-1}$ and
$T(\rho)\in\emph{R}^{(M^{2}-1)(N^{2}-1)}$, we have

$T_{\alpha\beta}(\rho)^{\dagger}T_{\alpha\beta}(\rho)=\begin{pmatrix}(||\alpha||^{2}_{2}+||r||^{2}_{2})\beta\beta^{t}&\beta(||\alpha||_{2}^{2}s^{t}+r^{t}T)\\\
(||\alpha||_{2}^{2}s+T^{t}r)\beta^{t}&||\alpha||_{2}^{2}ss^{t}+T^{t}T\end{pmatrix}.$

By using Lemma 1 we have the following corollary.

###### Corollary 1

For any quantum state $\rho$,
$||T_{\alpha\beta}(\rho)||_{KF}=||T_{||\alpha||_{2}||\beta||_{2}}(\rho)||_{KF}.$

From the Corollary 1, we see that we only need to consider the norm of
$\alpha$ and $\beta$ in dealing with the norm of $T_{\alpha\beta}(\rho)$.
Hence, we simplify our Theorem 1 to the following corollary.

###### Corollary 2

If the state $\rho\in H_{M}\otimes H_{N}$ is separable, then

$||T_{ab}(\rho)||_{KF}\leq\sqrt{a^{2}+\frac{M(M-1)}{2}}\sqrt{b^{2}+\frac{N(N-1)}{2}}$

for any non-negative real numbers $a$ and $b$.

Corollary 2 is equivalent to the Theorem 1 with $||\alpha||_{2}=a$ and
$||\beta||_{2}=b$.

Example 1: We consider the $2\otimes 4$ state,
$\rho_{x}=x|\xi\rangle\langle\xi|+(1-x)\rho,$ where
$|\xi\rangle=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$, $\rho$ is the bound
entangled state considered in shen ; Liming ,

$\displaystyle\rho$ $\displaystyle=\frac{1}{7d+1}$
$\displaystyle\begin{pmatrix}d&0&0&0&0&d&0&0\\\ 0&d&0&0&0&0&d&0\\\
0&0&d&0&0&0&0&d\\\ 0&0&0&d&0&0&0&0\\\
0&0&0&0&\frac{1+d}{2}&0&0&\frac{\sqrt{1-d^{2}}}{2}\\\ d&0&0&0&0&d&0&0\\\
0&d&0&0&0&0&d&0\\\ 0&0&d&0&\frac{\sqrt{1-d^{2}}}{2}&0&0&\frac{1+d}{2}\\\
\end{pmatrix}$

with $d\in(0,1)$. For simplicity, set $d=\frac{9}{10}$ and choose
$\alpha=(\frac{1}{2\sqrt{3}},\frac{1}{2\sqrt{3}})^{t}$ and $\beta=(1,0)^{t}$.
Then Theorem 1 detects the entanglement of $\rho_{x}$ for $x\in[0.223406,1]$.
One may also choose $\alpha=(a_{1},..,a_{n})^{t}$ and
$\beta=(b_{1},...,b_{m})^{t}$ in general, where
$\sum_{i=1}^{n}a_{i}^{2}=\frac{1}{6}$ and $\sum_{i=1}^{m}b_{i}^{2}=1$. The
result is the same.

Combining Theorem 1 and Corollary 2, we have the following theorem.

###### Theorem 2

If a state $\rho\in H_{M}\otimes H_{N}$ is separable, then

$||T_{ab}(\rho)||_{KF}\leq\sqrt{\frac{NM(N-1)(M-1)}{4}}+|ab|,$ (8)

where $a,b\in\textrm{R}$ and $|b|=|a|\sqrt{\frac{N(N-1)}{M(M-1)}}$.

[Proof] For a state $\rho\in H_{M}\otimes H_{N},$ we have

$||T_{ab}(\rho)||_{KF}=||\begin{pmatrix}ab&as^{t}\\\ br&T(\rho)\\\
\end{pmatrix}||_{KF}\geq|ab|+||T(\rho)||_{KF},$

where the first inequality is due to $||\begin{pmatrix}A&B\\\ C&D\\\
\end{pmatrix}||_{KF}\geq||A||_{KF}+||D||_{KF}$ for any complex matrices
$A,B,C$ and $D$ with adequate dimensionsVJ . If $\rho$ is separable, we have

$||T_{ab}(\rho)||_{KF}\leq\sqrt{a^{2}+\frac{M(M-1)}{2}}\sqrt{b^{2}+\frac{N(N-1)}{2}}$

and

$||T(\rho)||_{KF}\leq\sqrt{\frac{MN(M-1)(N-1)}{4}}.$

Setting

$\sqrt{a^{2}+\frac{M(M-1)}{2}}\sqrt{b^{2}+\frac{N(N-1)}{2}}=|ab|+\sqrt{\frac{MN(M-1)(N-1)}{4}},$

we have $|b|=|a|\sqrt{\frac{N(N-1)}{M(M-1)}}.$ $\Box$

From the proof of Theorem 2, for the separable quantum states one has

$||T(\rho)||_{KF}\leq||T_{ab}(\rho)||_{KF}-|ab|\leq\sqrt{\frac{MN(M-1)(N-1)}{4}}.$

Theorem 2 can detect more entanglement than the Theorem 1 given in VJ , see
the following example.

Example 2: Consider the following bipartite qubit state,
$\rho=p|\psi\rangle\langle\psi|+(1-p)|00\rangle\langle 00|,$ where $p\in[0,1]$
and $|\psi\rangle=\frac{1}{\sqrt{2}}(|01\rangle+|10\rangle).$ Let $b=a\not=0$.
We have $||T_{aa}(\rho)||_{KF}=2p+\sqrt{4a^{2}p^{2}+(2p-1-a^{2})^{2}},$ which
implies that $||T_{aa}(\rho)||_{KF}>1+a^{2}$ for $p\in(0,1]$. Namely, the
entanglement is detected for $p\in(0,1]$, which is better than the result
$p\in(\frac{1}{2},1]$ from the Theorem 1 in VJ .

##  III Separability Conditions from the Bloch Representation based on
$W{ab,\alpha\beta}(\rho)$

Next we define

$W_{ab,\alpha\beta}(\rho)=\begin{pmatrix}ab&a\alpha^{t}\otimes s^{t}\\\
b\beta\otimes r&\beta\alpha^{t}\otimes T(\rho)\end{pmatrix},$ (9)

where $a$ and $b$ are real numbers. Using $W_{ab,\alpha\beta}(\rho)$, we get
the following separability criterion for bipartite states.

###### Theorem 3

If the state $\rho\in H_{M}\otimes H_{N}$ is separable, then

$||W_{ab,\alpha\beta}(\rho)||_{KF}\leq\sqrt{a^{2}+||\beta||^{2}_{2}\frac{M(M-1)}{2}}\sqrt{b^{2}+||\alpha||^{2}_{2}\frac{N(N-1)}{2}},$
(10)

where $||\cdot||_{2}$ is the Euclidean norm on $R^{N^{2}-1}$.

[Proof] A bipartite quantum state with Bloch representation (2) is separable
if and only if there exist vectors $\mu_{i}\in R^{M^{2}-1}$ and $\nu_{i}\in
R^{N^{2}-1}$ with $||\mu_{i}||_{2}=\sqrt{\frac{M(M-1)}{2}}$ and
$||\nu_{i}||_{2}=\sqrt{\frac{N(N-1)}{2}}$, $0<p_{i}\leq 1$ with
$\sum_{i}p_{i}=1$ such that $T(\rho)=\sum_{i}p_{i}\mu_{i}\nu^{t}_{i}$,
$r=\sum_{i}p_{i}\mu_{i}$ and $s=\sum_{i}p_{i}\nu_{i}$. Therefore, for
separable states $\rho$ the matrix $W_{ab,\alpha\beta}(\rho)$ reduces to

$\displaystyle W_{ab,\alpha\beta}(\rho)$ $\displaystyle=$
$\displaystyle\begin{pmatrix}ab&a\alpha^{t}\otimes s^{t}\\\ b\beta\otimes
r&\beta\alpha^{t}\otimes T(\rho)\end{pmatrix}$ $\displaystyle=$
$\displaystyle\sum_{i}p_{i}\begin{pmatrix}ab&a\alpha^{t}\otimes\nu_{i}^{t}\\\
b\beta\otimes\mu_{i}&\beta\alpha^{t}\otimes\mu_{i}\nu_{i}^{t}\end{pmatrix}$
$\displaystyle=$ $\displaystyle\sum_{i}p_{i}\begin{pmatrix}a\\\
\beta\otimes\mu_{i}\end{pmatrix}\begin{pmatrix}b&\alpha^{t}\otimes\nu^{t}_{i}\end{pmatrix}.$

Hence one gets

$\displaystyle||W_{ab,\alpha\beta}(\rho)||_{KF}$ $\displaystyle\leq$
$\displaystyle\sum_{i}p_{i}\left|\left|\begin{pmatrix}a\\\
\beta\otimes\mu_{i}\end{pmatrix}\right|\right|_{2}\cdot\left|\left|\begin{pmatrix}b&\alpha^{t}\otimes\nu^{t}_{i}\end{pmatrix}\right|\right|_{2}$
$\displaystyle=$
$\displaystyle\sqrt{a^{2}+||\beta||^{2}_{2}\frac{M(M-1)}{2}}\sqrt{b^{2}+||\alpha||^{2}_{2}\frac{N(N-1)}{2}},$

which proves the theorem. $\Box$

Example 3: For the quantum state $\rho_{x}$ with $d=\frac{9}{10}$ in Example
1, if we take $a=\frac{1}{\sqrt{6}}$, $b=1$, $\beta^{t}=(1,-2)$ and
$\alpha^{t}=(1,3)$, Theorem 3 can detect the entanglement of $\rho_{x}$ for
$x\in[0.22325,1]$, which is better than the result $x\in[0.2234,1]$ from
tinggui .

Below we provide another example of PPT state whose entanglement is not
detected by the filtered CMC 151  but detected by our Theorem 3.

Example 4: Consider a two qubit state,

$\displaystyle\rho$ $\displaystyle=\frac{1}{2}$
$\displaystyle\begin{pmatrix}1+a_{1}&0&0&a_{3}\\\ 0&0&0&0\\\
0&0&a_{2}-a_{1}&0\\\ t&0&0&1-a_{2}\\\ \end{pmatrix},$

where the real parameters $\\{a_{1},a_{2},a_{3}\\}$ are taken such that
$\rho\geq 0.$ We choose $\alpha=(1,1)^{t}$, $\beta=(1,1)^{t}$, $a=\sqrt{2}x$
and $b=\sqrt{2}y$ in $W_{\alpha\beta}(\rho)$. From Theorem 3, we have that if
$\rho$ is separable, then

$|a_{3}|+\sqrt{\lambda_{+}}+\sqrt{\lambda_{-}}\leq\sqrt{\frac{1+x^{2}}{2}}\sqrt{\frac{1+y^{2}}{2}},$
(11)

where
$\lambda_{\pm}=\frac{1}{8}\left((1+a_{1}-a_{2})^{2}+a_{2}^{2}x^{2}+a_{1}^{2}y^{2}+x^{2}y^{2}\pm\sqrt{((1+a_{1}-a_{2})^{2}+a_{2}^{2}x^{2}+a_{1}^{2}y^{2}+x^{2}y^{2})^{2}-4(1+a_{1})^{2}(1-a_{2})^{2}x^{2}y^{2}}\right).$
The inequality (11) is the same as the one from 2020 , which recovers the
$PPT$ condition for $\rho$.

Furthermore, we consider the family of $3\otimes 3$ bound entangled states
$\rho^{x}_{PH}$ introduced by P. HorodeckiP ; S .

Example 5: Consider the mixtures of $\rho^{x}_{PH}$ with the white noise,
$\rho(x,q)=q\rho^{x}_{PH}+(1-q)\frac{I}{9}$, where $0\leq q\leq 1$ and

$\displaystyle\rho^{x}_{PH}$ $\displaystyle=\frac{1}{8x+1}$
$\displaystyle\begin{pmatrix}x&0&0&0&x&0&0&0&x\\\ 0&x&0&0&0&0&0&0&0\\\
0&0&x&0&0&0&0&0&0\\\ 0&0&0&x&0&0&0&0&0\\\ 0&0&0&0&0&x&0&0&0\\\
0&0&0&0&0&0&\frac{1+x}{2}&0&\frac{\sqrt{1-x^{2}}}{2}\\\ 0&0&0&0&0&0&0&x&0\\\
x&0&0&0&x&0&\frac{\sqrt{1-x^{2}}}{2}&0&\frac{1+x}{2}\\\ \end{pmatrix}.$

For simplicity, we let $x=0.9$. From the fig 4 of S , $\rho(0.9,q)$ is
entangled with $q>0.997$. We take $a=\frac{1}{12}$, $b=\frac{1}{6}$,
$\alpha=(\frac{1}{8},\frac{1}{8})^{t}$ and $\beta=\frac{1}{8}$ in
$W_{ab,\alpha\beta}(\rho(0.9,q))$. From our Theorem 3, $\rho(0.9,q)$ is
entangled when $q>0.9867$, which is better than S . See Fiq.1, where
$\Delta=||W_{ab,\alpha\beta}(\rho(0.9,q))||_{KF}-\sqrt{a^{2}+3||\beta||^{2}_{2}}\sqrt{b^{2}+3||\alpha||^{2}_{2}}.$

Fig. 1: Entanglement detection of $\rho(0.9,q)$.

Next, we give the relation Corollary 2 and Theorem 3.

###### Corollary 3

For quantum state $\rho\in H_{A}\otimes H_{B}$,
$||W_{ab,\alpha\beta}(\rho)||_{KF}=||W_{ab,||\alpha||_{2}||\beta||_{2}}(\rho)||_{KF}$
for any non-negative real numbers $a$ and $b$.

[Proof] For $W_{ab,\alpha\beta}(\rho)$, we have

$\displaystyle W^{{\dagger}}_{ab,\alpha\beta}(\rho)W_{ab,\alpha\beta}(\rho)$
$\displaystyle=$
$\displaystyle\begin{pmatrix}ab^{2}+b||\beta||_{2}||r||_{2}&b\alpha^{t}\otimes(a^{2}s^{t}+||\beta||_{2}r^{t}T)\\\
b\alpha\otimes(a^{2}s+||\beta||_{2}T^{t}r)&\alpha\alpha^{t}\otimes(a^{2}ss^{t}+||\beta||_{2}T^{t}T)\\\
\end{pmatrix}.$ (12)

From (12), we have
$||W_{ab,\alpha\beta}(\rho)||_{KF}=||W_{ab,\alpha||\beta||_{2}}(\rho)||_{KF}$.
For a given matrix $A$, one has
$||A||_{KF}=Tr\sqrt{A^{{\dagger}}A}=Tr\sqrt{AA^{{\dagger}}}$. Next, we have
$||W_{ab,\alpha\beta}(\rho)||_{KF}=||W_{ab,||\alpha||_{2}\beta}(\rho)||_{KF}$
due to $W_{ab,\alpha\beta}(\rho)W^{{\dagger}}_{ab,\alpha\beta}(\rho)$. Then we
obtain
$||W_{ab,\alpha\beta}(\rho)||_{KF}=||W_{ab,||\alpha||_{2}||\beta||_{2}}(\rho)||_{KF}$.

For two positive numbers $k$ and $l$, we have

$\displaystyle W_{ab,kl}(\rho)$ $\displaystyle=$
$\displaystyle\begin{pmatrix}ab&aks^{t}\\\ blr&klT\\\
\end{pmatrix}=klT_{\frac{a}{l}\frac{b}{k}}(\rho).$

If the state $\rho\in H_{M}\otimes H_{N}$ is separable, from Corollary 2, we
have

$T_{\left(\frac{a}{l}\right)\left(\frac{b}{k}\right)}(\rho)\leq\sqrt{\left(\frac{a}{l}\right)^{2}+\frac{M(M-1)}{2}}\sqrt{\left(\frac{b}{k}\right)^{2}+\frac{N(N-1)}{2}},$
(13)

and from Theorem 3, we have

$||W_{ab,kl}(\rho)||_{KF}\leq\sqrt{a^{2}+l^{2}\frac{M(M-1)}{2}}\sqrt{b^{2}+k^{2}\frac{N(N-1)}{2}}.$
(14)

Form (13) and (14), one has Theorem 3 is equivalent to Corollary 2 in
detecting entanglement.

Note that the family of bipartite separability criteria based on
$T_{\alpha\beta}(\rho)$ and $W_{ab,\alpha\beta}(\rho)$ come down to the
Corollary 2, which is only depend on real parameters $a$ and $b$. Proposition
1 of Ref.shen  shown that the result of shen  becomes more effective when $m$
gets larger. From Corollary 2 and the Proposition 1 of Ref.shen , we know that
Corollary 2 becomes more effective when $a$ and $b$ are selected large enough
and satisfy $b\sqrt{M(M-1)}=a\sqrt{N(N-1)}$.

Example 6: Let consider a generalization of well known $d_{1}\otimes d_{2}$
isotropic states2021

$\rho_{p}=\frac{1-p}{d_{1}d_{2}}I_{d_{1}}\otimes
I_{d_{2}}+p|\psi^{+}_{d_{1}}\rangle\langle\psi^{+}_{d_{1}}|,$ (15)

where
$|\psi^{+}_{d_{1}}\rangle=\frac{1}{\sqrt{d_{1}}}\sum_{i=1}^{d_{1}}|e_{i}\otimes
f_{i}\rangle$, $|e_{i}\rangle$ defines orthonormal basis in $H_{d_{1}}$ and
$|f_{i}\rangle$ defines orthonormal set in $H_{d_{2}}$.

It is well known that this state is separable if and only if it is $PPT$ which
is equivalent to $p\leq\frac{1}{d_{2}+1}$. For simplicity, we take $d_{1}=2$
and $d_{2}=3$ for $\rho_{p}$ in the example 6. We show that Corollary 2
detects more entangled state than de Vicente criterionVJ , realignment
criterion r1 ; r2  and criterion based on SIC POMVs(ESIC)S  for $\rho_{p}$.
And, we show that Corollary 2 becomes more effective when $a$ and $b$ get
larger with $\frac{b}{a}=\sqrt{3}$.

We take $a=\sqrt{2}$ and $b=\sqrt{6}$ of Corollary 2 for $\rho_{p}$. Then
Corollary 2 can detect the entanglement in $\rho_{p}$ for $p\geq 0.378054$,
while the de Vicente criterion, realignment criterion and ESIC criterion can
only detect the entanglement in $\rho_{p}$ for $p\geq 0.3849$, $p\geq 0.3846$
and $p\geq 0.3819$, respectively. At last, we choose $a=\sqrt{2}t$ and
$b=\sqrt{6}t$ with $t>0$, Then Corollary 2 can detect the entanglement in
$\rho_{p}$ for $p\geq 0.379712$ with $t=\frac{1}{10}$, $p\geq 0.378139$ with
$t=\frac{1}{2}$, $p\geq 0.378032$ with $t=2$, $p\geq 0.378025$ with $t=10$,
respectively.

##  IV Conclusions and Remarks

In summary, based on the Bloch representation of a bipartite quantum state
$\rho$, we have introduced the matrices $T_{\alpha\beta}(\rho)$ and show that
$||T_{\alpha\beta}(\rho)||_{KF}=||T_{||\alpha||_{2}||\beta||_{2}}(\rho)||_{KF}.$
i.e., the value of $||T_{\alpha\beta}(\rho)||_{KF}$ only depends on the norm
of $\alpha$ and $\beta$. Thus the Theorem 1 is equivalent to the Theorem 1 of
shen  and can be further simplified to the Corollary 2 which has a very
simpler form. Meanwhile we have shown that the Corollary 2 is more effective
than the existing formula (3). In addition, we have presented a separability
criteria based on $W_{ab,\alpha\beta}(\rho)$, and show that
$||W_{ab,\alpha\beta}(\rho)||_{KF}=||W_{ab,||\alpha||_{2}||\beta||_{2}}(\rho)||_{KF}$.
i.e., the value of $||W_{ab,\alpha\beta}(\rho)||_{KF}$ only depends on the
norm of $\alpha$ and $\beta$ for given $a$ and $b$. At last, the three
separability criteria: Theorem 1 of shen , Theorem 1 and Theorem 3 can be
simplified to the Corollary 2 which has a very simpler form.

Acknowledgments and Data Availability Statements This work is supported by the
Research Award Fund for Natural Science Foundation of Shandong Province No.
ZR2021LLZ002, National Natural Science Foundation of China under grant Nos.
12075159 and 12171044, Beijing Natural Science Foundation (Z190005), Academy
for Multidisciplinary Studies, Capital Normal University, Shenzhen Institute
for Quantum Science and Engineering, Southern University of Science and
Technology (SIQSE202001), and the Academician Innovation Platform of Hainan
Province. All data generated or analysed during this study are included in
this published article.

Conflict of interest statement The authors declared that they have no
conflicts of interest to this work.

References

## References

  * (1) Mintert, F., Kuś, M., and Buchleitner, A.: Concurrence of Mixed Bipartite Quantum States in Arbitrary Dimensions, Phys. Rev. Lett. 92, 167902 (2004).
  * (2) Chen, K., Albeverio, S., and Fei, S. M.: Concurrence of Arbitrary Dimensional Bipartite Quantum States,Phys. Rev. Lett. 95, 040504 (2005).
  * (3) Breuer, H. P.: Optimal Entanglement Criterion for Mixed Quantum States,Phys. Rev. Lett. 97, 080501 (2006).
  * (4) de Vicente, J. I.: Lower bounds on concurrence and separability conditions, Phys. Rev. A 75, 052320 (2007).
  * (5) Zhang, C. J., Zhang, Y. S., Zhang, S., and Guo, G. C.: Optimal entanglement witnesses based on local orthogonal observables, Phys. Rev. A 76, 012334(2007).
  * (6) Nielsen, M. A., and Chuang, I. L.: Quantum Computation and Quantum Information (Cambridge University Press, Cambridge,(2000).
  * (7) Peres, A.: Separability criterion for density matrices. Phys. Rev. Lett.77, 1413 (1996).
  * (8) Horodecki, M., Horodecki, P., and Horodecki, R.: Separability of mixed states: necessary and sufficient conditions. Phys. Lett. A 223, 1-8 (1996).
  * (9) Zhang, C. J., Zhang,Y. S., Zhang, S., and Guo, G. C.: Entanglement detection beyond the computable cross-norm or realignment criterion. Phys. Rev. A 77, 060301(R) (2008).
  * (10) Aniello, P., and Lupo, C.: A class of inequalities inducing new separability criteria for bipartite quantum systems. J. Phys. A: Math. Theor. 41, 355303 (2008).
  * (11) O. Gühne., P. Hyllus., O. Gittsovich., and J. Eisert.:Covariance Matrices and the Separability Problem. Phys. Rev. Lett. 99,130504 (2007).
  * (12) Gühne, O., Hyllus, P., Gittsovich, O., and Eisert, J.: Covariance matrices and the separability problem. Phys. Rev. Lett.99, 130504 (2007).
  * (13) Gittsovich, O., Gühne, O., Hyllus, P., and Eisert, J.: Unifying several separability conditions using the covariance matrix criterion. Phys. Rev. A 78, 052319 (2008).
  * (14) Gittsovich, O., Hyllus, P., and Guhne, O.: Multiparticle covariance matrices and the impos Bsibility of detecting graph-state entanglement with two-particle correlations. Phys. Rev. A 82, 032306 (2010).
  * (15) Shang, J., Ali, A., Zhu, H., et al.: Enhanced entanglement criterion via symmetric informationally complete measurements. Phys. Rev. A, 98,022309(2018).
  * (16) de Vicente, J. I.: Separability criteria based on the Bloch representation of density matrices. Quantum Inf. Comput. 7, 624-638(2007).
  * (17) Shen, S. Q., Yu, J., Li, M., and Fei, S. M.: Improved separability criteria based on bloch representation of density matrices. Scientific Reports. 6, 28850(2016).
  * (18) Li, M., Wang, J., Fei, S. M., and Li-Jost, X.: Quantum separability criteria for arbitrary-dimensional multipartite states. Phys. Rev. A 89,022325 (2014).
  * (19) Sarbicki, G., Scala, G., and Chruciński, D .: Family of multipartite separability criteria based on a correlation tensor. Phys. Rev. A 101, 012341 (2020).
  * (20) Chang, J., Cui, M., Zhang, T. G., Fei, S. M.: Separability criteria based on heisenberg-weyl representation of density matrices. Chinese Physics B, 27(3), 030302(2018).
  * (21) Horodecki. P.: Separability criterion and inseparable mixed states with positive partial transpo-sition. Phys. Lett. A 232, 333 (1997).
  * (22) Sarbicki, G., Scala. G., and Chruciński. D.: Detection Power of Separability Criteria Based on a Correlation Tensor: A Case Study. Open Systems and Information Dynamics 28(2021).


& \frac{18 E \beta^2 \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{6 \beta^2 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs \rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs\rs  \alpha_u  \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg]\sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] \nonumber\\
% &= \frac{2}{\eta K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \left(\mathbb{E} [f(\mathbf{w}^k)] - \mathbb{E} [f(\mathbf{w}^{k+1})] \right) + \frac{2 \beta \eta \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k}\Bigg[ \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} + 4 E \mathrm{L} \beta \eta \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \left(\alpha_u\right)^2 \mathrm{L}_u^{k,e} + \nonumber\\
% &60 \beta^3 \eta^3 E^3 \mathrm{L}^4 + 3 \beta \eta E \mathrm{L}^2 \Bigg] + \frac{18 E \beta^2 \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \big[1 + 20 \beta^2 \eta^2 E^2 \mathrm{L}^2 \big] + \frac{20 \mathrm{L} \beta^2 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\
% &\frac{2 \beta \eta}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \Bigg[ E \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} + 3 \beta \eta \mathrm{L}^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs \rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs\rs  \alpha_u + 4 \beta \eta E \mathrm{L} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \left(\alpha_u + 15 E \beta^2 \eta^2 \mathrm{L}^3 \right) \Bigg] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] \nonumber\\
&\leq \frac{2}{\eta K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \left(\mathbb{E} [f(\mathbf{w}^k)] - \mathbb{E} [f(\mathbf{w}^{k+1})] \right) + \frac{2 \beta \eta \mathrm{L} \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k}\Bigg[ 60 \beta^3 \eta^3 E^3 \mathrm{L}^3 + 3 \beta \eta E \mathrm{L} +  \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b  \left(\alpha_b + 4 E \mathrm{L} \beta \eta \right) \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs\rs \left(\alpha_u\right)^2 \Bigg] + \nonumber\\
&\squad \frac{18 E \beta^2 \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \big[1 + 20 \beta^2 \eta^2 E^2 \mathrm{L}^2 \big] + \frac{20 \mathrm{L} \beta^2 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{2 \beta \eta \mathrm{L}}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \big[ E + 3 \beta \eta \mathrm{L} + \nonumber\\
&\squad  4 \beta \eta E \left(\alpha_u + 15 E \beta^2 \eta^2 \mathrm{L}^3 \right) \big] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] \nonumber\\
&=\frac{2}{\eta K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \left(\mathbb{E} [f(\mathbf{w}^k)] - \mathbb{E} [f(\mathbf{w}^{k+1})] \right) + \frac{2 \beta \eta \mathrm{L} \sigma^2}{K} \sum_{k=0}^{K-1} \frac{\mathrm{N}_1^k}{\Omega^k} + \frac{18 E \beta^2 \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{\mathrm{N}_2}{\Omega^k} + \frac{20 \mathrm{L} \beta^2 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\
&\squad \frac{2 \beta \eta \mathrm{L}}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs \rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs\rs \alpha_u \mathrm{N}_u  \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right],
\end{align}

where $\mathrm{N}_1^k \coloneqq  60 \beta^3 \eta^3 E^3 \mathrm{L}^3 + 3 \beta \eta E \mathrm{L} +  \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b  \left(\alpha_b + 4 E \mathrm{L} \beta \eta \right) \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u\right)^2$, $\mathrm{N}_2 \coloneqq \big[1 + 20 \beta^2 \eta^2 E^2 \mathrm{L}^2 \big]$ and $\mathrm{N}_{u} \coloneqq  E + 3 \beta \eta \mathrm{L} + 4 \beta \eta E \left(\alpha_u + 15 E \beta^2 \eta^2 \mathrm{L}^3 \right)$.

This concludes the proof of Theorem <ref>.

§ MISSING PROOF OF LEMMA <REF> AND LEMMA <REF>

§.§ Proof of Lemma <ref>

\begin{align}
\label{proofLocal_BS_Div}
&\frac{1}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right] \nonumber\\
&\overset{(a)}{=}\frac{\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert  \sum_{l'=0}^{l-1} g (\mathbf{w}_{u}^{k, e, l'}) - \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \frac{\mathrm{1}_{u',\mathrm{sc}}^{k,e}}{\mathrm{p}_{u',\mathrm{sc}}^{k,e}} \sum_{l'=0}^{l-1} g (\mathbf{w}_{u'}^{k, e, l'}) \right\Vert^2 \right] \nonumber\\
&=\frac{\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[ \Bigg\Vert \sum_{l'=0}^{l-1} g (\mathbf{w}_u^{k,e,l'}) \pm \sum_{l'=0}^{l-1} \nabla f_u (\mathbf{w}_u^{k,e,l'}) -  \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \frac{\mathrm{1}_{u',\mathrm{sc}}^{k,e}}{\mathrm{p}_{u',\mathrm{sc}}^{k,e}} \sum_{l'=0}^{l-1} g (\mathbf{w}_{u'}^{k,e,l'}) \nonumber\\
&\mquad \pm \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \sum_{l'=0}^{l-1} \mathrm{g} (\mathbf{w}_{u'}^{k,e,l}) \pm \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \sum_{l'=0}^{l-1} \nabla f_u (\mathbf{w}_{u'}^{k,e,l'}) \Bigg\Vert^2 \Bigg] \nonumber\\
&\leq \frac{3\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[ \Bigg\Vert \sum_{l'=0}^{l-1} \left[ g (\mathbf{w}_u^{k,e,l'}) -  \nabla f_u (\mathbf{w}_u^{k,e,l'}) \right] - \nonumber\\
&\mquad \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \sum_{l'=0}^{l-1} \left[ \mathrm{g} (\mathbf{w}_{u'}^{k,e,l'}) - \nabla f_u (\mathbf{w}_{u'}^{k,e,l'}) \right] \Bigg\Vert^2 \Bigg] + \nonumber\\
&\mquad \frac{3\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[ \Bigg\Vert \sum_{l'=0}^{l-1} \nabla f_u (\mathbf{w}_u^{k,e,l'}) - \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \sum_{l'=0}^{l-1} \nabla f_{u'} (\mathbf{w}_{u'}^{k,e,l'}) \Bigg\Vert^2 \Bigg] + \nonumber\\
&\mquad \frac{3\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[ \Bigg\Vert \sum_{u' \in \mathcal{U}_b} \alpha_{u'}  \sum_{l'=0}^{l-1} g (\mathbf{w}_{u'}^{k,e,l'}) \left[ 1 - \frac{\mathrm{1}_{u',\mathrm{sc}}^{k,e}}{\mathrm{p}_{u',\mathrm{sc}}^{k,e}} \right] \Bigg\Vert^2 \Bigg],
\end{align}

where we get $(a)$ due to the fact that the client received the same model from the es during the synchronization time.
Besides, the change in the es' model is captured for all $0 \leq l'\leq l-1$ sgd rounds, and the aggregation rule follows (<ref>) to indicate whether these gradients are received at the es.

The first term of (<ref>) is upper bounded as

\begin{align}
\label{proofLocal_BS_Div_Term1}
&\frac{3\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[ \Bigg\Vert \sum_{l'=0}^{l-1} \bigg[\left( g (\mathbf{w}_u^{k,e,l'}) - \nabla f_u (\mathbf{w}_u^{k,e,l'}) \right)  -  \sum_{u' \in \bar{\mathcal{U}}_b^{k,e}} \alpha_{u'} \left( g (\mathbf{w}_{u'}^{k,e,l'}) - \nabla f_u (\mathbf{w}_{u'}^{k,e,l'}) \right) \bigg] \Bigg\Vert^2 \Bigg] \nonumber\\
&= \frac{3\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[ \sum_{l'=0}^{l-1} \Bigg\Vert \left( g (\mathbf{w}_u^{k,e,l'}) - \nabla f_u (\mathbf{w}_u^{k,e,l'}) \right) -  \sum_{u' \in \bar{\mathcal{U}}_b^{k,e}} \alpha_{u'} \left( g (\mathbf{w}_{u'}^{k,e,l'}) - \nabla f_u (\mathbf{w}_{u'}^{k,e,l'}) \right) \Bigg\Vert^2 + \nonumber\\
&\sum_{l'=0}^{l-1} \bigg\{\left( g (\mathbf{w}_u^{k,e,l'}) - \nabla f_u (\mathbf{w}_u^{k,e,l'}) \right) -  \sum_{u' \in \bar{\mathcal{U}}_b^{k,e}} \alpha_{u'} \left( g (\mathbf{w}_{u'}^{k,e,l'}) - \nabla f_u (\mathbf{w}_{u'}^{k,e,l'}) \right) \bigg\} \times \sum_{l''=0, l' \neq l''}^{l-1} \bigg\{\left( g (\mathbf{w}_u^{k,e,l''}) - \nabla f_u (\mathbf{w}_u^{k,e,l''}) \right) - \nonumber\\
&\bquad \bquad \bquad \qquad \sum_{u' \in \bar{\mathcal{U}}_b^{k,e}} \alpha_{u'} \left( g (\mathbf{w}_{u'}^{k,e,l''}) - \nabla f_u (\mathbf{w}_{u'}^{k,e,l''}) \right) \bigg\} \Bigg] \nonumber\\
&\overset{(a)}{=} \frac{3\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \sum_{l'=0}^{l-1} \mathbb{E} \Bigg[ \Bigg\Vert \left( g (\mathbf{w}_u^{k,e,l'}) - \nabla f_u (\mathbf{w}_u^{k,e,l'}) \right)  -  \sum_{u' \in \bar{\mathcal{U}}_b^{k,e}} \alpha_{u'} \left( g (\mathbf{w}_{u'}^{k,e,l'}) - \nabla f_u (\mathbf{w}_{u'}^{k,e,l'}) \right) \Bigg\Vert^2 \Bigg] \nonumber\\
&\overset{(b)}{\leq} \frac{3 \mathrm{L} \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u  \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \bigg[ \bigg\Vert \left( g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \right)  - \sum_{u' \in \bar{\mathcal{U}}_b^{k,e}} \alpha_{u'} \left( g (\mathbf{w}_{u'}^{k,e,l}) - \nabla f_u (\mathbf{w}_{u'}^{k,e,l}) \right) \bigg\Vert^2 \bigg] \nonumber\\
&\overset{(c)}{=} \frac{3 \mathrm{L} \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathbb{E} \left[ \left\Vert g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \right\Vert^2 \right]  - \nonumber\\
&\bquad \mquad \frac{3 \mathrm{L} \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert \sum_{u' \in \bar{\mathcal{U}}_b^{k,e}} \alpha_{u'} \left( g (\mathbf{w}_{u'}^{k,e,l}) - \nabla f_u (\mathbf{w}_{u'}^{k,e,l}) \right) \right\Vert^2 \right] \nonumber\\
&\overset{(d)}{\leq} \frac{3 \mathrm{L} \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sigma^2 - \frac{3 \mathrm{L} \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \sum_{u' \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_{u'} \right)^2 \mathbb{E} \left[ \left\Vert g (\mathbf{w}_{u'}^{k,e,l}) - \nabla f_u (\mathbf{w}_{u'}^{k,e,l}) \right\Vert^2 \right] \nonumber\\
&\overset{(e)}{\leq} \frac{3 E \mathrm{L}^2 \eta^2 \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k}  - \frac{3 \mathrm{L}^2 \eta^2 \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b
\nonumber\\
&\leq \frac{3 E \mathrm{L}^2 \eta^2 \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k},
\end{align}

where $(a)$ stems from time independence of the mini-batch gradients and $\mathbb{E} [g_u(\mathbf{w}_u^{k,e,l})] = \nabla f_u (\mathbf{w}_u^{k,e,l})$, which makes the expectation of the cross product terms $0$.
Besides, we used the fact that $l \leq \mathrm{L}_u^{k,e}$ and $1 \leq \mathrm{L}_u^{k,e} \leq \mathrm{L}$ in $(b)$.
In $(c)$, $\sum_{j=1}^J \alpha_j \Vert \mathbf{x}_j - \bar{\mathbf{x}} \Vert^2 = \sum_{j=1}^J \alpha_j \Vert \mathbf{x}_j \Vert^2 - \Vert \bar{\mathbf{x}} \Vert^2$, where $\bar{\mathbf{x}} = \sum_{j=1}^J \alpha_j \mathbf{x}_j$.
In $(d)$ and $(e)$, we use the bounded variance of the SGD assumptions and independence of SGDs in different epochs.

For the second term of (<ref>), we write

\begin{align}
\label{proofLocal_BS_Div_Term2}
&\frac{3\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[ \Bigg\Vert \sum_{l'=0}^{l-1} \left(\nabla f_u (\mathbf{w}_u^{k,e,l'}) - \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \nabla f_{u'} (\mathbf{w}_{u'}^{k,e,l'}) \right) \Bigg\Vert^2 \Bigg] \nonumber\\
&\leq \frac{3 \mathrm{L} \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \sum_{l'=0}^{l-1} \mathbb{E} \left[ \left\Vert \nabla f_u (\mathbf{w}_u^{k,e,l'}) - \sum\nolimits_{u' \in \mathcal{U}_b} \alpha_{u'} \nabla f_{u'} (\mathbf{w}_{u'}^{k,e,l'}) \right\Vert^2 \right] \nonumber \\
&\leq \frac{3 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1}  \mathbb{E} \left[ \left\Vert \nabla f_u (\mathbf{w}_u^{k,e,l}) \pm \nabla f_u (\mathbf{w}_b^{k,e}) \pm \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \nabla f_{u'} (\mathbf{w}_{b}^{k,e}) - \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \nabla f_{u'} (\mathbf{w}_{u'}^{k,e,l}) \right\Vert^2 \right] \nonumber\\
&\leq \frac{9 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1}  \mathbb{E} \left[ \left\Vert \nabla f_u (\mathbf{w}_u^{k,e,l}) - \nabla f_u (\mathbf{w}_b^{k,e}) \right\Vert^2 \right] + \nonumber\\
&\mquad \frac{9 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1}  \mathbb{E} \Bigg[ \Bigg\Vert \nabla f_u (\mathbf{w}_b^{k,e}) - \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \nabla f_{u'} (\mathbf{w}_{b}^{k,e}) \Bigg\Vert^2\Bigg] + \nonumber\\
&\mquad \frac{9 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1}  \mathbb{E} \Bigg[ \Bigg\Vert \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \nabla f_{u'} (\mathbf{w}_{b}^{k,e}) - \sum_{u' \in \mathcal{U}_b} \alpha_{u'} \nabla f_{u'} (\mathbf{w}_{u'}^{k,e,l}) \Bigg\Vert^2 \Bigg] \nonumber\\
&\leq \frac{9 \mathrm{L}^2 \beta^2\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1}  \mathbb{E} \left[ \left\Vert \mathbf{w}_b^{k,e} - \mathbf{w}_u^{k,e,l} \right\Vert^2 \right] + \nonumber\\
&\mquad \frac{9 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1}  \mathbb{E} \left[ \left\Vert \nabla f_u (\mathbf{w}_b^{k,e}) - \nabla f_b (\mathbf{w}_{b}^{k,e}) \right\Vert^2\right] + \nonumber\\
&\mquad \frac{9 \mathrm{L}^2 \beta^2\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1}  \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right] \nonumber\\
&\leq \frac{18 \mathrm{L}^2 \beta^2\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1}  \mathbb{E} \left[ \left\Vert \mathbf{w}_b^{k,e} - \mathbf{w}_u^{k,e,l} \right\Vert^2 \right] + \frac{9 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \epsilon_0^2 \nonumber\\
&\leq \frac{9 E \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{18 \mathrm{L}^2 \beta^2\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1}  \mathbb{E} \left[ \left\Vert \mathbf{w}_b^{k,e} - \mathbf{w}_u^{k,e,l} \right\Vert^2 \right] .
\end{align}

For the third term of (<ref>), we write

\begin{align}
\label{proofLocal_BS_Div_Term3}
&\frac{3 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[ \Bigg\Vert \sum_{u' \in \mathcal{U}_b} \alpha_{u'}  \sum_{l'=0}^{l-1} g (\mathbf{w}_{u'}^{k,e,l'}) \left[ 1 - \frac{\mathrm{1}_{u',\mathrm{sc}}^{k,e}}{\mathrm{p}_{u',\mathrm{sc}}^{k,e}} \right] \Bigg\Vert^2 \Bigg] \nonumber\\
&\leq \frac{3 \mathrm{L} \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \sum_{l'=0}^{l-1} \mathbb{E} \Bigg[ \Bigg\Vert   g (\mathbf{w}_{u}^{k,e,l'}) \left[ 1 - \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \right] \Bigg\Vert^2 \Bigg] \nonumber\\
&\leq \frac{3 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[ \Bigg\Vert g_u (\mathbf{w}_u^{k, e, l}) \left[ 1 - \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \right] \Bigg\Vert^2 \Bigg] \nonumber\\
&= \frac{3 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg]\sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert g_u (\mathbf{w}_u^{k, e, l})  \right\Vert^2 \right]
\end{align}

To this end, plugging (<ref>), (<ref>) and (<ref>) into (<ref>), and rearranging the terms, we get

\begin{align}
\label{proofLocal_BS_Div_1}
&\frac{1}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right] \nonumber\\
&\leq \frac{ \frac{3 E \mathrm{L}^2 \eta^2 \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{9 E \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{3 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \left[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \right]\sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert g_u (\mathbf{w}_u^{k, e, l})  \right\Vert^2 \right]}{1 - 18 \beta^2 \eta^2 \mathrm{L}^2}
\end{align}

Notice that, when learning rate $\eta < \frac{1}{3\sqrt{2} \beta \mathrm{L}}$, we have $0 < (1 - 18\beta^2\eta^2\mathrm{L}^2) <1$.
Besides, we can assume that $\eta < \mathrm{min}\left\{\frac{1}{3\sqrt{2} \beta \mathrm{L}}, \frac{1}{\beta E \mathrm{L}} \right\}$ to satisfy all assumptions for the learning rate.
As such, we write the upper bound as

\begin{align}
&\frac{1}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right] \nonumber\\
&\leq \frac{3 E \mathrm{L}^2 \eta^2 \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{9 E \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{3 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \left[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \right]\sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert g_u (\mathbf{w}_u^{k, e, l})  \right\Vert^2 \right].
\end{align}

This concludes the proof of Lemma <ref>.

§.§ Proof of Lemma <ref>

\begin{align}
\label{lemma_bs_server_eqn_0}
&\frac{1}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \left[ \left\Vert \mathbf{w}^k - \mathbf{w}_{b}^{k,e} \right\Vert^2 \right] \nonumber\\
&=\frac{ \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{e'=0}^{e-1} \sum_{u \in \bar{\mathcal{U}}_b^{k,e'}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e'}} \mathrm{g}_u^{k,e'} - \sum_{e'=0}^{e-1} \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e'}} \alpha_{u'} \frac{\mathrm{1}_{u',\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u',\mathrm{sc}}^{k,e'}} \mathrm{g}_{u'}^{k,e'} \Bigg\Vert^2 \Bigg] \nonumber\\
&=\frac{\eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{e'=0}^{e-1} \Bigg\{\sum_{u \in \bar{\mathcal{U}}_b^{k,e'}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e'} - 1} \bigg( \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e'}}  g_u (\mathbf{w}_u^{k, e', l}) \pm \nabla f_u( \mathbf{w}_u^{k,e',l}) \bigg) - \nonumber \\
&\bquad \bquad \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e'}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e'} - 1} \bigg(\frac{\mathrm{1}_{u',\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u',\mathrm{sc}}^{k,e'}} g (\mathbf{w}_{u'}^{k,e',l}) \pm \nabla f_{u'} (\mathbf{w}_{u'}^{k,e',l}) \bigg) \Bigg\} \Bigg\Vert^2 \Bigg] \nonumber\\
&\leq \frac{2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{e'=0}^{e-1} \Bigg\{\sum_{u \in \bar{\mathcal{U}}_b^{k,e'}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e'} - 1} \bigg( \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e'}}  g_u (\mathbf{w}_u^{k, e', l}) - \nabla f_u( \mathbf{w}_u^{k,e',l}) \bigg) - \nonumber\\
&\bquad \mquad \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e'}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e'} - 1} \bigg(\frac{\mathrm{1}_{u',\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u',\mathrm{sc}}^{k,e'}} g (\mathbf{w}_{u'}^{k,e',l}) - \nabla f_{u'} (\mathbf{w}_{u'}^{k,e',l}) \bigg) \Bigg\} \Bigg]\Bigg\Vert^2 + \nonumber\\
&\qquad \quad \frac{2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{e'=0}^{e-1} \Bigg\{\sum_{u \in \bar{\mathcal{U}}_b^{k,e'}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e'} - 1} \nabla f_{u} (\mathbf{w}_{u}^{k,e',l}) - \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e'}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e'} - 1} \nabla f_{u'} (\mathbf{w}_{u'}^{k,e',l}) \Bigg\}\Bigg\Vert^2 \Bigg],
\end{align}

The first part of (<ref>) is simplified as

\begin{align}
\label{lemma_bs_server_eqn_0_0}
&\frac{2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{e'=0}^{e-1} \Bigg\{\sum_{u \in \bar{\mathcal{U}}_b^{k,e'}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e'} - 1} \bigg( \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e'}}  g_u (\mathbf{w}_u^{k, e', l}) - \nabla f_u( \mathbf{w}_u^{k,e',l}) \bigg) - \nonumber\\
&\bquad \mquad \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e'}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e'} - 1} \bigg(\frac{\mathrm{1}_{u',\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u',\mathrm{sc}}^{k,e'}} g (\mathbf{w}_{u'}^{k,e',l}) - \nabla f_{u'} (\mathbf{w}_{u'}^{k,e',l}) \bigg) \Bigg\} \Bigg]\Bigg\Vert^2 \nonumber\\
&\overset{(a)}{=} \frac{2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{e'=0}^{e-1} \Bigg\{\sum_{u \in \bar{\mathcal{U}}_b^{k,e'}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e'} - 1} \bigg( \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e'}}  g_u (\mathbf{w}_u^{k, e', l}) - \nabla f_u( \mathbf{w}_u^{k,e',l}) \bigg) \Bigg\Vert^2\Bigg] - \nonumber\\
&\bquad \frac{2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \mathbb{E} \Bigg[\Bigg\Vert \sum_{e'=0}^{e-1} \Bigg\{\sum_{b=0}^B \alpha_b \sum_{u \in \bar{\mathcal{U}}_{b}^{k,e'}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e'} - 1} \bigg(\frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e'}} g_u (\mathbf{w}_u^{k, e', l}) - \nabla f_{u} (\mathbf{w}_{u}^{k,e',l}) \bigg) \Bigg\} \Bigg]\Bigg\Vert^2 \nonumber\\
&\overset{(b)}{=} \frac{2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{e'=0}^{e-1} \mathbb{E} \Bigg[\Bigg\Vert \sum_{u \in \bar{\mathcal{U}}_b^{k,e'}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e'} - 1} \bigg( \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e'}}  g_u (\mathbf{w}_u^{k, e', l}) - \nabla f_u( \mathbf{w}_u^{k,e',l}) \bigg) \Bigg\Vert^2\Bigg] -  \nonumber\\
&\bquad \frac{2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{e'=0}^{e-1} \mathbb{E} \Bigg[\Bigg\Vert \sum_{b=0}^B \alpha_b \sum_{u \in \bar{\mathcal{U}}_{b}^{k,e'}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e'} - 1} \bigg(\frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e'} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e'}} g_u (\mathbf{w}_u^{k, e', l}) - \nabla f_{u} (\mathbf{w}_{u}^{k,e',l}) \bigg) \Bigg]\Bigg\Vert^2  \nonumber\\
&\overset{(c)}{\leq} \frac{2 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg( \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e}}  g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u( \mathbf{w}_u^{k,e,l}) \bigg) \Bigg\Vert^2\Bigg] -  \nonumber\\
&\bquad \frac{2 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \mathbb{E} \Bigg[\Bigg\Vert \sum_{b=0}^B \alpha_b \sum_{u \in \bar{\mathcal{U}}_{b}^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e} - 1} \bigg(\frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_{u} (\mathbf{w}_{u}^{k,e,l}) \bigg) \Bigg]\Bigg\Vert^2  \nonumber\\
&\overset{(d)}{=} \frac{2 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u\right)^2 \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[\Bigg\Vert \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e}}  g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u( \mathbf{w}_u^{k,e,l}) \Bigg\Vert^2\Bigg] - \nonumber\\
&\bquad \frac{2 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^B \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_{b}^{k,e}} \left(\alpha_u\right)^2 \sum_{l=0}^{\mathrm{L}_{u}^{k,e} - 1}  \mathbb{E} \Bigg[\Bigg\Vert \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_{u'} (\mathbf{w}_{u}^{k,e,l}) \Bigg]\Bigg\Vert^2 \nonumber\\
&= \frac{2 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u\right)^2 \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e}}  g_u (\mathbf{w}_u^{k, e, l}) \pm g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u( \mathbf{w}_u^{k,e,l}) \right\Vert^2\right] - \nonumber\\
&\bquad \frac{2 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^B \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_{b}^{k,e}} \left(\alpha_u \right)^2 \sum_{l=0}^{\mathrm{L}_{u}^{k,e} - 1} \mathbb{E} \left[\left\Vert \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} g_u (\mathbf{w}_u^{k, e, l}) \pm g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_{u} (\mathbf{w}_{u}^{k,e,l}) \right]\right\Vert^2 \nonumber\\
&\overset{(e)}{\leq} \frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u\right)^2 \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert \left(\frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \right) g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2\right] + \nonumber\\
&\bquad \frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u\right)^2 \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left \Vert  g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u( \mathbf{w}_u^{k,e,l}) \right\Vert^2\right] - \nonumber\\
&\bquad \frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^B \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_{b}^{k,e}} \left(\alpha_u \right)^2 \sum_{l=0}^{\mathrm{L}_{u}^{k,e} - 1} \mathbb{E} \left[\left\Vert \left(\frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e} }{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \right) g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] - \nonumber \\
&\bquad \frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^B \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_{b}^{k,e}} \left(\alpha_u \right)^2 \sum_{l=0}^{\mathrm{L}_{u}^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_{u} (\mathbf{w}_{u}^{k,e,l}) \right]\right\Vert^2 \nonumber \\
&\overset{(f)}{\leq} \frac{4 E \eta^2 \sigma^2} {K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u\right)^2 \mathrm{L}_u^{k,e} + \frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u\right)^2 \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2\right] - \nonumber\\
&\frac{4 E \eta^2 \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^B \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_{b}^{k,e}} \left(\alpha_u \right)^2 \mathrm{L}_{u}^{k,e} - \frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^B \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_{b}^{k,e}} \left(\alpha_u \right)^2 \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \sum_{l=0}^{\mathrm{L}_{u}^{k,e} - 1}  \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] \nonumber \\
&\leq \frac{4 E \eta^2 \sigma^2} {K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \left(\alpha_u\right)^2 \mathrm{L}_u^{k,e} + \frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \left(\alpha_u\right)^2 \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2\right],
\end{align}

where $(a)$ stems from the fact that $\sum_{j=1}^J \alpha_j \Vert \mathbf{x}_j - \bar{\mathbf{x}} \Vert^2 = \sum_{j=1}^J \alpha_j \Vert \mathbf{x}_j \Vert^2 - \Vert \bar{\mathbf{x}} \Vert^2$, where $\bar{\mathbf{x}} = \sum_{j=1}^J \alpha_j \mathbf{x}_j$.
Besides, $(b)$ appears from the independent mini-batch gradients and $\mathbb{E} [g_u(\mathbf{w}_u^{k,e,l})] = \nabla f_u (\mathbf{w}_u^{k,e,l})$ assumptions, which make the expectation of the cross product terms $0$.
Besides, $(c)$ is true since $(e-1)- e' \leq E$.
Furthermore, we use the independent mini-batch gradients and $\mathbb{E} [g_u(\mathbf{w}_u^{k,e,l})] = \nabla f_u (\mathbf{w}_u^{k,e,l})$ assumptions in step $(d)$.
In $(e)$, we use the fact that $\Vert \sum_{j=1}^J \mathbf{x}_j \Vert^2 \leq J \sum_{j=1}^J \Vert \mathbf{x}_j \Vert^2$.
Moreover, $(f)$ appears from bounded variance of the gradients.
Finally, we drop the negative second term of $(f)$ in the last inequality.

The second part of (<ref>) is simplified as

\begin{align}
\label{lemma_bs_server_eqn_0_1}
&\frac{2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{e'=0}^{e-1} \Bigg\{\sum_{u \in \bar{\mathcal{U}}_b^{k,e'}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e'} - 1} \nabla f_{u} (\mathbf{w}_{u}^{k,e',l}) - \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e'}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e'} - 1} \nabla f_{u'} (\mathbf{w}_{u'}^{k,e',l}) \Bigg\}\Bigg\Vert^2 \Bigg] \nonumber\\
&\overset{(a)}{\leq}\frac{2 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{e'=0}^{e-1} \mathbb{E} \Bigg[\Bigg\Vert  \sum_{u \in \bar{\mathcal{U}}_b^{k,e'}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e'} - 1} \nabla f_{u} (\mathbf{w}_{u}^{k,e',l}) - \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e'}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e'} - 1} \nabla f_{u'} (\mathbf{w}_{u'}^{k,e',l}) \Bigg\Vert^2 \Bigg] \nonumber \\
&\overset{(b)}{\leq} \frac{2 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert  \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \nabla f_{u} (\mathbf{w}_{u}^{k,e,l}) - \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e} - 1} \nabla f_{u'} (\mathbf{w}_{u'}^{k,e,l}) \Bigg\Vert^2 \Bigg] \nonumber\\
&= \frac{2 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert  \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \big[\nabla f_{u} (\mathbf{w}_{u}^{k,e,l}) - \nabla f_{u} (\mathbf{w}_b^{k,e}) \big] + \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \big[\nabla f_{u} (\mathbf{w}_{b}^{k,e}) - \nabla f_{u} (\mathbf{w}^{k}) \big] +\nonumber\\
&\squad \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \nabla f_{u} (\mathbf{w}^k) - \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e} - 1} \nabla f_{u'} (\mathbf{w}^k) + \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e} - 1} \big[\nabla f_{u'} (\mathbf{w}^k) - \nabla f_{u'} (\mathbf{w}_{b'}^{k,e}) \big] + \nonumber\\
&\squad \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e} - 1} \big[ \nabla f_{u'} (\mathbf{w}_{b'}^{k,e}) - \nabla f_{u'} (\mathbf{w}_{u'}^{k,e,l}) \big] \Bigg\Vert^2 \Bigg] \nonumber\\
&\overset{(c)}{\leq} \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \big[\nabla f_{u} (\mathbf{w}_{u}^{k,e,l}) - \nabla f_{u} (\mathbf{w}_b^{k,e}) \big] \Bigg\Vert^2\Bigg] + \nonumber\\
&\squad \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \big[\nabla f_{u} (\mathbf{w}_{b}^{k,e}) - \nabla f_{u} (\mathbf{w}^{k}) \big] \Bigg\Vert^2 \Bigg] + \nonumber\\
&\squad \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \nabla f_{u} (\mathbf{w}^k) - \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e} - 1} \nabla f_{u'} (\mathbf{w}^k) \Bigg\Vert^2 \Bigg] + \nonumber\\
&\squad \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e} - 1} \big[\nabla f_{u'} (\mathbf{w}^k) - \nabla f_{u'} (\mathbf{w}_{b'}^{k,e}) \big] \Bigg\Vert^2\Bigg] + \nonumber\\
&\squad \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'} \sum_{l=0}^{\mathrm{L}_{u'}^{k,e} - 1} \big[ \nabla f_{u'} (\mathbf{w}_{b'}^{k,e}) - \nabla f_{u'} (\mathbf{w}_{u'}^{k,e,l}) \big] \Bigg\Vert^2 \Bigg] \nonumber\\
&\overset{(d)}{\leq} \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathbb{E} \Bigg[\Bigg\Vert \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \big[\nabla f_{u} (\mathbf{w}_{u}^{k,e,l}) - \nabla f_{u} (\mathbf{w}_b^{k,e}) \big] \Bigg\Vert^2\Bigg] + \nonumber\\
&\squad \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathbb{E} \Bigg[\Bigg\Vert \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \big[\nabla f_{u} (\mathbf{w}_{b}^{k,e}) - \nabla f_{u} (\mathbf{w}^{k}) \big] \Bigg\Vert^2 \Bigg] + \nonumber\\
&\squad \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Bigg[\Bigg\Vert \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \nabla \tilde{f}_{u} (\mathbf{w}^k) - \sum_{b'=0}^B \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'} \nabla \tilde{f}_{u'} (\mathbf{w}^k) \Bigg\Vert^2 \Bigg] + \nonumber\\
&\squad \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathbb{E} \Bigg[\Bigg\Vert \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \big[\nabla f_u (\mathbf{w}^k) - \nabla f_u (\mathbf{w}_b^{k,e}) \big] \Bigg\Vert^2\Bigg] + \nonumber\\
&\squad \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b  \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathbb{E} \Bigg[\Bigg\Vert \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \big[ \nabla f_u (\mathbf{w}_b^{k,e}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \big] \Bigg\Vert^2 \Bigg] \nonumber\\
&\overset{(e)}{\leq} \frac{10 \mathrm{L} \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Big[\left\Vert \nabla f_{u} (\mathbf{w}_{u}^{k,e,l}) - \nabla f_{u} (\mathbf{w}_b^{k,e}) \right\Vert^2\Big] + \nonumber\\
&\squad \frac{10 \mathrm{L} \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Big[\left\Vert \nabla f_{u} (\mathbf{w}_{b}^{k,e}) - \nabla f_{u} (\mathbf{w}^{k}) \right\Vert^2 \Big] + \frac{10 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \cdot \epsilon_1^2 + \nonumber\\
&\squad \frac{10 \mathrm{L} \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Big[\left\Vert \nabla f_u (\mathbf{w}^k) - \nabla f_u (\mathbf{w}_b^{k,e}) \right\Vert^2\Big] + \nonumber\\
&\squad \frac{10 \mathrm{L}\eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b  \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1}  \mathbb{E} \Big[\left\Vert \nabla f_u (\mathbf{w}_b^{k,e}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \right\Vert^2 \Big] \nonumber\\
&\overset{(f)}{\leq} \frac{10 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{20 \mathrm{L} \beta^2 \eta^2 E^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Big[\left\Vert  \mathbf{w}_b^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2\Big] + \nonumber\\
&\squad \frac{20 \beta^2 \eta^2 E^2 \mathrm{L}^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Big[\left\Vert \mathbf{w}^k - \mathbf{w}_b^{k,e} \right\Vert^2\Big] \nonumber\\
&\overset{(g)}{\leq} \frac{10 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{20 \beta^2 \eta^2 E^2 \mathrm{L}^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Big[\left\Vert \mathbf{w}^k - \mathbf{w}_b^{k,e} \right\Vert^2\Big] + 20 \mathrm{L} \beta^2 \eta^2 E^2 \times \Bigg[ \frac{3 E \mathrm{L}^2 \eta^2 \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\
&\squad \frac{9 E \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{3 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \left[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \right]\sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert g_u (\mathbf{w}_u^{k, e, l})  \right\Vert^2 \right] \Bigg] \nonumber\\
&= \frac{180 \beta^2 \epsilon_0^2 E^3 \mathrm{L}^4 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{10 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{60 \beta^2 \sigma^2 E^3 \mathrm{L}^3 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\
&\squad \frac{60 \beta^2 E^2 \mathrm{L}^3 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \left[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \right]\sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert g_u (\mathbf{w}_u^{k, e, l})  \right\Vert^2 \right] + \nonumber\\
&\squad \frac{20 \beta^2 \eta^2 E^2 \mathrm{L}^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \Big[\left\Vert \mathbf{w}^k - \mathbf{w}_b^{k,e} \right\Vert^2\Big],
\end{align}

where $(a)$ and $c$ stem from the fact that $\Vert \sum_{j=1}^J \mathbf{x}_j \Vert^2 \leq J \sum_{j=1}^J \Vert \mathbf{x}_j \Vert^2$.
Besides, we used $(e-1) - e' \leq E$ in step $(a)$ and step $(b)$.
In $(d)$, we use the fact that $\Vert \sum_{j=1}^J \alpha_j \mathbf{x}_j \Vert^2 \leq \sum_{j=1}^J \alpha_j \Vert \mathbf{x}_j \Vert^2$ and the definition of $\nabla \tilde{f}_u(\mathbf{w}^k) \coloneqq \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \nabla f_u(\mathbf{w}^k)$.
Furthermore, $\Vert \sum_{j=1}^J \mathbf{x}_j \Vert^2 \leq J \sum_{j=1}^J \Vert \mathbf{x}_j \Vert^2$ and the bounded divergence assumption in (<ref>) yield $(e)$.
Moreover, the inequality in $(f)$ stems from the $\beta$-smoothness property.
Finally, we use Lemma <ref> in step $(g)$.

Now, plugging (<ref>) and (<ref>) into (<ref>), we get

\begin{align}
\label{lemma_bs_server_eqn_1}
&\left(1 - 20 \beta^2 \eta^2 E^2 \mathrm{L}^2 \right) \frac{1}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \left[ \left\Vert \mathbf{w}^k - \mathbf{w}_{b}^{k,e} \right\Vert^2 \right] \nonumber\\
&\leq \frac{4 E \eta^2 \sigma^2} {K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \left(\alpha_u\right)^2 \mathrm{L}_u^{k,e} + \frac{60 \beta^2 \sigma^2 E^3 \mathrm{L}^3 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{180 \beta^2 \epsilon_0^2 E^3 \mathrm{L}^4 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{10 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\
&\squad \frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \left(\alpha_u + 15 E \beta^2 \eta^2 \mathrm{L}^3 \right) \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2\right].
\end{align}

It is worth noting that when $\eta < \frac{1}{2\sqrt{5} \beta E \mathrm{L}}$, we have $0 < (1 - 20\beta^2\eta^2E^2 \mathrm{L}^2) < 1$.
In order to satisfy the previous assumptions on the learning rate, we let $\eta < \mathrm{min}\left\{\frac{1}{2\sqrt{5} \beta \mathrm{L}}, \frac{1}{\beta E \mathrm{L}} \right\}$.
As such, we re-write (<ref>) as follows:

\begin{align}
\label{lemma_bs_server_eqn_pf}
&\frac{1}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \left[ \left\Vert \mathbf{w}^k - \mathbf{w}_{b}^{k,e} \right\Vert^2 \right] \nonumber\\
&\leq \frac{4 E \eta^2 \sigma^2} {K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \left(\alpha_u\right)^2 \mathrm{L}_u^{k,e} + \frac{60 \beta^2 \sigma^2 E^3 \mathrm{L}^3 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{180 \beta^2 \epsilon_0^2 E^3 \mathrm{L}^4 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{10 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\
&\squad \frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \left(\alpha_u + 15 E \beta^2 \eta^2 \mathrm{L}^3 \right) \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2\right].
\end{align}

This concludes the proof of Lemma <ref>.