#  To Talk or to Work: Flexible Communication Compression for Energy Efficient
Federated Learning over Heterogeneous Mobile Edge Devices

Liang Li12, Dian Shi3, Ronghui Hou12, Hui Li1, Miao Pan3, and Zhu Han3
1School of Cyber Engineering, Xidian University, Xi’an, China  2State Key
Laboratory of Computer Architecture, Institute of Computing Technology,
Chinese Academy of Sciences, China  3Department of Electrical and Computer
Engineering, University of Houston, Houston, TX, USA  Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>{mpan2<EMAIL_ADDRESS>
###### Abstract

Recent advances in machine learning, wireless communication, and mobile
hardware technologies promisingly enable federated learning (FL) over massive
mobile edge devices, which opens new horizons for numerous intelligent mobile
applications. Despite the potential benefits, FL imposes huge communication
and computation burdens on participating devices due to periodical global
synchronization and continuous local training, raising great challenges to
battery constrained mobile devices. In this work, we target at improving the
energy efficiency of FL over mobile edge networks to accommodate heterogeneous
participating devices without sacrificing the learning performance. To this
end, we develop a convergence-guaranteed FL algorithm enabling flexible
communication compression. Guided by the derived convergence bound, we design
a compression control scheme to balance the energy consumption of local
computing (i.e., “working”) and wireless communication (i.e., “talking”) from
the long-term learning perspective. In particular, the compression parameters
are elaborately chosen for FL participants adapting to their computing and
communication environments. Extensive simulations are conducted using various
datasets to validate our theoretical analysis, and the results also
demonstrate the efficacy of the proposed scheme in energy saving.

###### Index Terms:

Federated Learning over Wireless Networks, Gradient Compression, Local SGD,
Edge Computing on GPUs.

##  I Introduction

The growing prevalence of mobile smart devices and the rapid advancement of
social networking applications result in the phenomenal growth of the data
generated at the edge network. To draw useful information from such
geographically distributed data, federated learning (FL) has emerged as a
promising paradigm that allows participating users to collaboratively learn a
shared model, while keeping all the private training data on their edge
devices. In particular, all the participants are allowed to run stochastic
gradient descent (SGD) locally and send the intermediate gradients to the
server periodically for global synchronization. The recent advances in mobile
edge computing further facilitate the implementation of FL in mobile networks,
since modern smart mobile devices are now armed with high-performance central
processing units (CPUs) and graphics processing units (GPUs) to handle
intensive computations of intelligent applications. With the technical
advantages and implemental feasibilities, FL has seen recent successes in
several applications, including next word prediction in Google’s Gboard [1],
vocal classifier for “Hey Siri” [2], mobile augmented reality [3], etc.

However, to practically deploy FL in wireless networks still faces several
critical challenges. On the one hand, both transmitting the gradient updates
and performing the local optimizations are resource-hungry, leading to
considerable energy consumption at mobile edge devices during the training
process. Despite improving computing capacity, mobile edge devices are
generally subject to the limited battery lifetime, which hinders their
applications in training complex models and supporting continuous learning. On
the other hand, the mismatch between the heavy communication loads and the
constrained wireless bandwidth hampers the efficient exchange of locally
computed updates. The current trend of going deeper in the depth of neural
networks has resulted in high-dimensional models with millions of parameters,
which inevitably involves significant wireless traffic in global model
synchronization. Things can only worsen when considering the heterogeneity of
communication environments across different devices, where the learning
efficiency may severely depend on a few stragglers with poor channel
conditions.

Several pioneering works have been done to manage system resources for
efficient FL in wireless networks [4, 5, 6, 7, 8]. However, these studies
overlooked reducing resource consumption intrinsically from the learning
algorithm’s perspective, hindering a substantial performance boost in resource
utilization and training efficiency. A promising solution suggested in recent
works in distributed learning is to incorporate state-of-the-art communication
compression strategies into FL algorithms, which can considerably reduce the
communication cost with little impacts on learning outcomes [9, 10, 11, 12,
13, 14]. Yet the existing compressed distributed learning algorithms and the
corresponding convergence analysis typically require identical compressor
across all the participants, which ignores the heterogeneity in participants’
communication capacity and thereby exhibits less flexibility. More
importantly, this line of works mainly focuses on alleviating communication
burdens in FL. However, the ever-increasing deployment of 5G networks that
provides data rates as high as 1Gbps has shown a great potential to eliminate
the communication bottleneck in FL, let alone the forthcoming 6G revolution
[15]. For example, to transmit a Resnet-50, a commonly used deep network for
image classification, with approximately 100MB parameters via 1Gbps wireless
links typically consumes 0.16J, which is comparable to the energy consumption
of performing a single-step local training on one GPU (e.g., 0.2J for NVIDIA
Tesla V100 [16, 17]). In light of this fact, it is worthwhile to investigate
the impacts of both “working” (i.e., local computing) and “talking” (i.e.,
wireless transmission) and strike a balance between them via flexible
compression control.

In designing a compression control scheme, we would like to communicate as few
times and bits as possible to reduce the communication cost. At the same time,
we attempt to incur as little distortion to the gradient information as
possible towards fast convergence. However, these two goals are fundamentally
in conflicts since deeper compression will naturally lead to more distortion
on the gradients and more potential communication rounds to converge. When
taking energy consumption of edge devices as the measure, this can be further
interpreted as follows: Compressing the gradients severely and performing
single-step local updates all the time could minimize the energy consumption
per communication round. This may require extra communications to attain the
targeted model accuracy, or even make the model fail to converge, and thereby
impair the overall energy efficiency.

To tackle the challenges above, in this work, we study to improve the energy
efficiency of FL over heterogeneous mobile edge devices. Considering the
heterogeneous environments across participating wireless edge devices, we
propose a flexibly compressed learning algorithm integrating local
computation, gradient sparsification, error compensation, and batch size
increment. Based on the convergence rate of the algorithm, we develop a
compression control scheme that adapts the compression parameters to minimize
all the devices’ energy consumption on computing and communication. Our
salient contributions are summarized as follows:

  * •

We propose a convergence-guaranteed FL algorithm enabling flexible
communication compression, which allows participants to compress the gradients
to different levels before uploading. The convergence rate is analyzed
theoretically and some insightful results are highlighted.

  * •

From the long-term learning perspective, we formulate a compression control
problem using the derived convergence bound, where the goal is to achieve
energy efficient federated training on edge GPUs over wireless networks.

  * •

Capturing the heterogeneity of participating edge devices in their computing
and communication environments, we develop a control algorithm integrating
Benders decomposition and inner convex approximation to determine the
compression parameters for each participant.

  * •

We evaluate the performance of the proposed control scheme via extensive
simulations, which verify the efficacy of our algorithms with various data
sources, learning architectures, and system configurations.

The remainder of the paper is organized as follows. Section II reviews related
work. Section III elaborates on the flexibly compressed FL procedures and
provides the convergence analysis. Section IV presents an energy-efficient
compression control algorithm. Section V gives the performance evaluation, and
Section VI finally concludes the paper.

##  II Related Work

FL over wireless networks has recently gained tremendous attention, whose
system design is entangled with training acceleration, network optimization,
and on-device resource allocation. Recognizing the limited computing and
communication resources at edge computing systems, Wang et al. in [4]
dynamically controlled the frequency of global synchronization to minimize the
learning loss in real-time adapting to the resource budget. By exploring the
unique properties of wireless multiple-access channels, Yang et al. in [5]
developed a fast model aggregation approach with joint device selection and
beamforming design, which considers only one communication round, and thus
cannot guarantee the long-term training performance. To accelerate the
training process, Chen et al. in [6] scheduled the participants of high
significance for model uploading per communication round while allocating the
uplink wireless resources properly. Capturing the trade-off between training
time and participants’ energy consumption, authors in [7] and [8] formulated
optimization problems to jointly allocate the computing and communication
resources by considering the heterogeneity of environments. While properly
managing the system resources to enable FL in mobile edge networks, these
studies overlook reducing resource consumption intrinsically in the essence of
learning algorithm itself, thus hindering the substantial boost in training
efficiency and resource utilization.

Some recent efforts on distributed learning algorithm design have been devoted
to mitigating the communication bottleneck, which can be categorized into two
directions: communication round reduction and communication traffic reduction.
Specifically, McMahan et al. in [18] proposed the FedAvg algorithm (also known
as local SGD) to reduce the frequency of global synchronization, which allows
every participant to perform multiple local SGD iterations in a communication
round, other than communicating after every local iteration. Authors in [19]
and [20] used dynamically increasing batch sizes in distributed SGD to reduce
the required number of communication rounds. In [21], a momentum SGD method
was adopted to accelerate the convergence where the involved communications
during training can be reduced accordingly. To reduce the traffic per
communication round, one could let each participant communicate the compressed
gradients rather than raw gradients for every global synchronization. For
example, sparsified SGD studied in [10, 11] followed the idea that only a
small subset of gradients with large magnitude are required to upload.
Quantized SGD studied in [12, 14] allowed each participant to quantize the
gradients into low-precision values before sending. Despite reduced
communication complexity, the huge computing cost remains hinder FL on
resource-constrained edge devices. Besides, most of the current gradient
sparsification methods require identical sparsity levels across all the
participants, ignoring the heterogeneity of participants and thereby
exhibiting less flexibility. This work fills this gap by redesigning the
compressed-federated learning algorithm with flexible and well-controlled
compression parameters (e.g., global synchronization frequency and gradient
sparsity). Simultaneously, heterogeneous computing and communication
environments of participants are jointly considered to make the compression
strategy suitable for mobile edge networks in practice.

##  III Federated Learning with Compression

###  III-A Federated Learning Algorithm Design

We consider an edge computing powered wireless network in which one base
station and a set of mobile participants, denoted by
$\mathcal{M}=\\{1,2,...,m,...,M\\}$, collaboratively train a deep neural
network model via FL. We follow the common settings of synchronous FL as in
[18] and assume that each participant maintains a locally collected dataset.
The goal of collaborative training is to learn a global model that achieves
uniformly good performance over all the participants, which can be formally
described as minimizing a finite-sum non-convex objective
$F:\mathbb{R}^{d}\rightarrow\mathbb{R}$ of the form

$F(\boldsymbol{w})\triangleq\frac{1}{M}\sum\limits_{m=1}^{M}f_{m}(\boldsymbol{w}).$
(1)

Here, $f_{m}(\boldsymbol{w})$ is the loss function defined by the participant
$m$’s local dataset $\mathcal{D}_{m}$ and the parameter vector
$\boldsymbol{w}$. Specifically,

$f_{m}(\boldsymbol{w})=\frac{1}{|\mathcal{D}_{m}|}\sum\limits_{i\in\mathcal{D}_{m}}f_{m}^{i}(\boldsymbol{w};x_{m}^{i},y_{m}^{i}),$
(2)

where $|\mathcal{D}_{m}|$ is the size of $\mathcal{D}_{m}$ and
$(x_{m}^{i},y_{m}^{i})$ is the $i$-th sample in $\mathcal{D}_{m}$. Note here
that we usually have $\mathcal{D}_{m}\neq\mathcal{D}_{j}$ and $\nabla
f_{m}(\boldsymbol{w}_{m})\neq\nabla f_{j}(\boldsymbol{w}_{j})$ for any $m\neq
j$ since data are usually heterogeneously-distributed across participants in
typical FL applications.

Aiming at reducing the communication cost during FL, we propose the Flexible
${\rm\textbf{T}op}_{k}$ Local Stochastic Gradient Descent with Dynamic Batch
sizes (FT-LSGD-DB) algorithm by integrating two state-of-the-art communication
compression strategies, namely, local computations and gradient
sparsification. The former allows each participant to perform more local
computations on the edge device between every two global synchronizations,
thereby reducing the total number of communication rounds. The latter lets
participants explicitly sparsify the updated gradient tensors before uploading
by retaining only a fraction of components, thereby reducing the size of
communication payload in each round. Here, we use “${\rm Top}_{k}$”
compressor, a commonly used gradient sparsification approach, to take the
sparsified top-$k$ gradients. Specifically, for a vector
$\boldsymbol{x}\in\mathbb{R}^{d}$, ${\rm
Top}_{k}(\boldsymbol{x})\in\mathbb{R}^{d}$, and the $i^{th}(i=1,2,...,d)$
element of ${\rm Top}_{k}(\boldsymbol{x})$ is defined by:

${\rm Top}_{k}(\boldsymbol{x}^{{}^{i}})=\left\\{\begin{aligned}
\boldsymbol{x}^{{}^{i}},&&{|\boldsymbol{x}^{{}^{i}}|\geq thr},\\\ 0\ \
,&&{\text{otherwise},}\end{aligned}\right.$ (3)

where $\boldsymbol{x}^{{}^{i}}$ denotes the $i^{th}$ element of
$\boldsymbol{x}$ and $thr$ is the $k$-th largest absolute value of the
elements in $\boldsymbol{x}$. In practice, $k$ can be two to three orders of
magnitude smaller than $d$ while only sacrificing the model accuracy to a mild
extent. In this case, the communication overhead involved in gradient
transmission can be dramatically saved [11, 22].

Algorithm 1 FT-LSGD-DB Algorithm

Input: The dataset $\\{\mathcal{D}_{m}\\}_{\forall m}$; The initialized mini-
batch size: $b^{(0)}$; The mini-batch size scaling factor: $\rho>1$; The
number of participants: $M$; The number of iterations to train: $T$
Output: Final model parameter $\boldsymbol{w}^{(T)}$
Initialization:
$\boldsymbol{w}^{(0)}=\widehat{\boldsymbol{w}}_{m}^{(0)}=\boldsymbol{e}_{m}^{(0)},\
\forall m\in\mathcal{M}$

1:for $t=0,1,2,...,T-1$ do

2: On Edge Devices:

3: for $m\in\mathcal{M}$ in parallel do

4: $b^{(t)}\leftarrow\lfloor\rho^{t}b^{(0)}\rfloor$

5: Sampling a mini-batch $\mathcal{D}_{m}^{(t)}$ of size $b^{(t)}$ from
$\mathcal{D}_{m}$

6:
$\widehat{\boldsymbol{w}}_{m}^{(t+\frac{1}{2})}\leftarrow\widehat{\boldsymbol{w}}_{m}^{(t)}-\eta^{(t)}\nabla
f_{m}(\boldsymbol{w}^{(t)};\mathcal{D}_{m}^{(t)})$

7: if $t+1$ is an integer multiple of $H$ then

8:
$\boldsymbol{u}_{m}^{(t)}\leftarrow\boldsymbol{e}_{m}^{(t)}+\boldsymbol{w}^{(t)}-\widehat{\boldsymbol{w}}_{m}^{(t+\frac{1}{2})}$

9: $\boldsymbol{g}_{m}^{(t)}={\rm Top}_{k_{m}}(\boldsymbol{u}_{m}^{(t)})$ and
upload $\boldsymbol{g}_{m}^{(t)}$

10:
$\boldsymbol{e}_{m}^{(t+1)}\leftarrow\boldsymbol{e}_{m}^{(t)}+\boldsymbol{w}^{(t)}-\widehat{\boldsymbol{w}}_{m}^{(t+\frac{1}{2})}-\boldsymbol{g}_{m}^{(t)}$

11: Receive $\boldsymbol{w}^{(t+1)}$ and
$\widehat{\boldsymbol{w}}_{m}^{(t+1)}\leftarrow\boldsymbol{w}^{(t+1)}$

12: else

13:
$\widehat{\boldsymbol{w}}_{m}^{(t+1)}\leftarrow\widehat{\boldsymbol{w}}_{m}^{(t+\frac{1}{2})}$

14: $\boldsymbol{w}^{(t+1)}\leftarrow\boldsymbol{w}^{(t)}$

15: $\boldsymbol{e}^{(t+1)}\leftarrow\boldsymbol{e}^{(t)}$

16: At Central Server:

17: if $t+1$ is an integer multiple of $H$ then

18: Collect $\boldsymbol{g}_{m}^{(t)},\forall m$ and
$\boldsymbol{g}^{(t)}=\frac{1}{M}\sum_{m=1}^{M}\boldsymbol{g}_{m}^{(t)}$

19: $\boldsymbol{w}^{(t+1)}=\boldsymbol{w}^{(t)}-\boldsymbol{g}^{(t)}$ and
broadcast $\boldsymbol{w}^{(t+1)}$

20: else

21: $\boldsymbol{w}^{(t+1)}\leftarrow\boldsymbol{w}^{(t)}$

22:return $\boldsymbol{w}^{(T)}$

Unlike previous studies requiring identical sparsity level across all the
participants, FT-LSGD-DB injects more flexibility into training procedures by
allowing the participating devices to perform gradient sparsification with
different values of “$k$”. This indeed helps to accommodate stragglers with
poor channel conditions and thus mitigates the impacts of stale updates.
Besides, FT-LSGD-DB novelly incorporates error compensation and batch size
increment into FL procedures, which are two effective methods adopted and
verified by practitioners recently. Specifically, error compensation is used
to accelerate the global convergence by accumulating the error that arises
from only uploading sparse approximations of the gradient updates, which
ensures all gradient information does get eventually aggregated [10]. Using
dynamically increasing batch sizes during training can maintain the known
convergence rate with fewer communication rounds [20]. The pseudocode of our
FT-LSGD-DB algorithm is given in Algorithm 1, and the details are described in
the following.

Let $\\{1,2,...,t,...T\\}$ denote a set of iteration indices and assume that
each participant performs $H$ steps of local updates between every two global
synchronizations. In each iteration $t$, evey participant $m\in\mathcal{M}$
performs:

  1. 1.

Batch size increment: Exponentially increases its own SGD batch size with a
factor $\rho$.

  2. 2.

Local update: Update local parameter $\boldsymbol{w}_{m}$ using the stochastic
gradient $\nabla f_{m}(\boldsymbol{w};\mathcal{D}_{m}^{(t)})$, where
$\mathcal{D}_{m}^{(t)}$ is a mini-batch of size $b$ sampled uniformly from
$\mathcal{D}_{m}$ at the $t$-th iteration.

If aggregation is performed at iteration $t$ (i.e., $t$ is an integer multiple
of $H$), every participant $m\in\mathcal{M}$ performs:

  1. 3.

Error compensation: Add the local error $\boldsymbol{e}_{m}^{(t)}$ from the
previous iteration into the gradient $\boldsymbol{g}_{m}^{(t)}$.

  2. 4.

Gradient sparsification: Truncate the gradient sum to its top $k_{m}$
components, sorted in decreasing order of absolute magnitude.

  3. 5.

Gradient upload: Send the sparsified error-compensated gradient
$\boldsymbol{g}_{m}^{(t)}$ to the base station.

  4. 6.

Error accumulation: Update the local error $\boldsymbol{e}_{m}^{(t)}$.

Upon receiving $\boldsymbol{g}_{m}^{(t)}$ from all the participants, the base
station aggregates them, updates the global model, and broadcasts the new
model $\boldsymbol{w}^{(t+1)}$ to participants. Every participant
$m\\!\in\\!\mathcal{M}$ set its local parameter $\boldsymbol{w}^{(t+1)}_{m}$
to be equal to the global parameter $\boldsymbol{w}^{(t+1)}$. The training
process above is repeated until achieving satisfactory accuracy. The following
section further shows the convergence rate achieved by Algorithm 1 and derives
the corresponding communication complexity.

###  III-B Convergence Analysis and Discussion

We consider the following two standard assumptions on the local loss functions
$f_{m}:\mathbb{R}^{d}\rightarrow\mathbb{R},\forall m\in\mathcal{M}$.

######  Assumption 1 (Smoothness)

$f_{m}(\cdot)$ is $L$-smooth, i.e., for every
$\boldsymbol{w},\boldsymbol{w}^{\prime}\in\mathbb{R}^{d}$, we have

$f_{m}(\boldsymbol{w})\leq f_{m}(\boldsymbol{w}^{\prime})+<\nabla
f_{m}(\boldsymbol{w}),\boldsymbol{w}^{\prime}-\boldsymbol{w}>+\frac{L}{2}||\boldsymbol{w}^{\prime}-\boldsymbol{w}||^{2}.$
(4)

######  Assumption 2 (Bounded variances and second momentum)

For every $\boldsymbol{w}_{m}^{(t)}\in\mathbb{R}^{d}$ and
$t\in\mathbb{Z}^{+}$, there exists constants $\sigma>0$ and $G\geq\sigma$ such
that:

$\mathbb{E}_{\mathcal{D}_{m}^{(t)}\subset\mathcal{D}_{m}}[||\nabla
f_{m}(\boldsymbol{w}_{m}^{(t)};\mathcal{D}_{m}^{(t)})\\!-\\!\nabla
f_{m}(\boldsymbol{w}_{m}^{(t)}||^{2}]\leq\sigma^{2},\ \forall m,$ (5)
$\mathbb{E}_{\mathcal{D}_{m}^{(t)}\subset\mathcal{D}_{m}}[||\nabla
f_{m}(\boldsymbol{w}_{m}^{(t)};\mathcal{D}_{m}^{(t)})||^{2}]\leq G^{2},\
\forall m.$ (6)

Let $\delta_{m}=d/k_{m}\geq 1$ be the gradient sparsity chosen by the $m$-th
participant. Under the assumptions above, the following theorem hold when
Algorithm 1 is run with the sparsity series $\\{\delta_{m}\\}_{\forall m}$.

###### Theorem 1

Suppose a constant learning rate
$\eta_{t}=\eta=\frac{\theta\sqrt{M}}{\sqrt{T}},\forall t\geq 0$ is chosen
where $\theta>0$ is a constant satisfying
$\frac{\theta\sqrt{M}}{\sqrt{T}}\leq\frac{1}{2L}$, we have the convergence
rate for Algorithm 1:

$\begin{split}&\mathbb{E}[||\boldsymbol{z}_{T}||^{2}]\\\
\leq&\frac{4(\mathbb{E}[F(\boldsymbol{w}^{(0)})]-F^{*})}{\theta\sqrt{MT}}\\\
&+\frac{8\rho\theta
L\sigma^{2}}{(\rho-1)b^{(0)}\sqrt{M}T^{3/2}}+(4\delta^{2}+1)\frac{8M\theta^{2}L^{2}G^{2}H^{2}}{T},\end{split}$
(7)

where $\delta=\sqrt{\frac{1}{M}\sum\limits_{m=1}^{M}\delta_{m}^{2}}$ is the
root mean square of the sparsity series $\\{\delta_{m}\\}_{\forall m}$ and
$\boldsymbol{z}_{T}$ is a random variable which samples a previous parameter
$\widehat{\boldsymbol{w}}_{m}^{(t)}$ with probability $1/MT$.

###### Proof:

Please refer to Appendix for the proof. ∎

In Theorem 1, we settle for a weaker notion of convergence and use the average
expected squared gradient norm to characterize the convergence rate due to the
non-convex settings as [11] does. Based on this, we further give the following
corollary on communication complexity of our FT-LSGD-DB algorithm.

###### Corollary 1

Let $\rho=\frac{T}{T-1}$,
$\theta^{2}=\frac{b^{(0)}(\mathbb{E}[F(\boldsymbol{w}^{(0)})]-F^{*})}{\sigma^{2}L}$
and $\mathbb{E}[F(\boldsymbol{w}^{(0)})]-F^{*}\leq J^{2}$ where $J\leq\infty$
is a constant. The maximum number of global communication rounds required for
achieving an $\varepsilon$-global model convergence, i.e., satisfying
$\mathbb{E}[||\boldsymbol{z}_{T}||^{2}]\leq\varepsilon$, is given by

$\begin{split}K(\delta,H)=&\mathcal{O}\left(MH\delta^{2}\right)+\mathcal{O}\left(\frac{1}{\sqrt{M}H}\right).\end{split}$
(8)

###### Proof:

Substituting $\rho=\frac{T}{T-1}$,
$\theta^{2}=\frac{b^{(0)}(\mathbb{E}[F(\boldsymbol{w}^{(0)})]-F^{*})}{\sigma^{2}L}$
and $\mathbb{E}[F(\boldsymbol{w}^{(0)})]-F^{*}\leq J^{2}$ into (7) yields

$\begin{split}\mathbb{E}[||\boldsymbol{z}_{T}||^{2}]\leq\frac{12\sigma
J\sqrt{L}}{\sqrt{MTb^{(0)}}}+(4\delta^{2}+1)\frac{8b^{(0)}MLG^{2}H^{2}J^{2}}{\sigma^{2}T}.\end{split}$
(9)

According to the convergence criterion, we suppose that

$\begin{split}\varepsilon=&\frac{12\sigma
J\sqrt{L}}{\sqrt{MTb^{(0)}}}+(4\delta^{2}+1)\frac{8b^{(0)}MLG^{2}H^{2}J^{2}}{\sigma^{2}T}.\end{split}$
(10)

Rearranging the terms, we get the maximum number of iterations as follows:

$\displaystyle T(\delta,H)=$
$\displaystyle\frac{8b^{(0)}MLG^{2}J^{2}H^{2}(4\delta^{2}+1)}{\varepsilon\sigma^{2}}+\frac{72L\sigma^{2}J^{2}}{\varepsilon^{2}b^{(0)}M}$
(11)
$\displaystyle+\sqrt{\frac{8b^{(0)}MLG^{2}J^{2}H^{2}(4\delta^{2}+1)}{\varepsilon\sigma^{2}}+\frac{36L\sigma^{2}J^{2}}{\varepsilon^{2}b^{(0)}M}}.$

In Algorithm 1, communications are only needed to aggregate individual
gradient-update and happen only once every $H$ iterations. Hence, the total
number of necessary communication rounds is given by $K=T/H$, i.e.,

$\displaystyle K(\delta,H)=$
$\displaystyle\frac{8b^{(0)}MLG^{2}J^{2}H(4\delta^{2}+1)}{\varepsilon\sigma^{2}}+\frac{72L\sigma^{2}J^{2}}{\varepsilon^{2}b^{(0)}MH}$
$\displaystyle+\sqrt{\frac{8b^{(0)}MLG^{2}J^{2}(4\delta^{2}+1)}{\varepsilon\sigma^{2}}+\frac{36L\sigma^{2}J^{2}}{\varepsilon^{2}b^{(0)}MH^{2}}}$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(MH\delta^{2}\right)+\mathcal{O}\left(\frac{1}{\sqrt{M}H}\right).$
(12)

∎

The results in (7) and (8) indicate that the gradient sparsity magnitudes of
all the participants jointly take impacts on global convergence and
communication complexity. Given a target model accuracy (i.e., $\varepsilon$),
a higher $\delta$ results in a larger bound of communication rounds. Besides,
aggressively enlarging $H$ (i.e., “working” more) can also impair the learning
efficiency as more communications may be involved.

##  IV Energy-efficient Federated Learning on GPUs: Problem Formulation and
Control Algorithm

The theoretical results above reveal that both gradient sparsity levels
$\\{\delta_{m}\\}_{\forall m}$ and global update frequency $H$ play critical
roles in convergence rate and communication efficiency from the learning
perspective. Considering a realistic edge computing environment, we highlight
that $\\{\delta_{m}\\}_{\forall m}$ and $H$ also have great impacts on the
energy consumption of participating edge devices, because they affect the
payload required for transmitting and the workload required for processing,
respectively. In this section, we aim to tune these two types of compression
parameters accommodating heterogeneous FL participants for optimizing overall
energy efficiency.

###  IV-A System Model and Problem Formulation

####  IV-A1 Communication model

Let $S_{m}$ denote the total number of bits communicated by the $m$-th
participant per global round. Using the “${\rm Top}_{k}$” compressor defined
in (3), one needs to send the values and the positions of the non-zero
gradients in the flattened tensors after sparsification. Let ${\rm FPP}$
denote the floating-point precision, e.g., ${\rm FPP}=32$ for single-precision
floating-points and ${\rm FPP}=64$ for double-precision floating-points. With
the sparsity $\delta_{m}=d/k_{m}$, participant $m$ needs ${\rm FPP}$ bits to
represent the absolute value of each non-zero gradient with one extra bit
indicating its sign, i.e.,

$S_{m,val}=({\rm FPP}+1)\times k_{m}\ \ \text{bits}.$ (13)

The positions of the non-zero entries can be identified by enumerating all
possible sparsity patterns, which require

$S_{m,pos}=\log_{2}\binom{d}{k_{m}}\ \ \text{bits}$ (14)

to represent. Accordingly, we define $S_{m}$ as

$S_{m}=s_{1}(S_{m,val}+S_{m,pos})+s_{0}\ \ \text{bits},$ (15)

where $s_{0}$ and $s_{1}$ are coefficients indicating extra communication
overhead involved in wireless transmitting [23]. Note that a federated
training task usually lasts for a time duration in tens of minutes due to the
huge volume of data required for transferring as well as the high
computational complexity in running SGD. Thus, the channel conditions of
participants may suffer from great fluctuations during a training period. For
this reason, it is expected to consider the energy consumption of a training
task from a long-term learning perspective. Here, we employ the average
transmission rate of every participant $m\in\mathcal{M}$, which is evaluated
by

$R_{m}=W_{m}\mathbb{E}_{h_{m}}[\log_{2}(1+\frac{P_{m}|h_{m}|^{2}}{N_{0}})],$
(16)

where the expectation is taken over channel fading $h_{m}$ between participant
$m$ and the base station; $N_{0}$ indicates the power of additive white
Gaussian noise; $W_{m}$ and $P_{m}$ denote the bandwidth and the transmitting
power of participant $m$, respectively [24]. Afterward, the energy consumed to
transmit the sparsified gradients by participant $m$ is calculated as

$E_{m}^{com}=\frac{P_{m}S_{m}}{R_{m}}.$ (17)

####  IV-A2 Computational model

On-device learning, especially for training deep network models, is a compute-
intensive task that has proved challenging to achieve adequate performance
when running merely on CPUs of commodity mobile devices. Fueled by the recent
advances in mobile hardware technology, GPU has become a ubiquitous hardware
accelerator integrated virtually in every smart device to offer significantly
more compute power. A typical GPU chip includes a multi-core GPU module and an
associated GPU memory module where the voltage and frequency of GPU cores and
GPU memory can be controlled separately. We model the energy consumed to
execute a single iteration of GPU-accelerated mini-batch SGD at the $m$-th
edge device as the product of the runtime power and the execution time, i.e.,

$E_{m,ite}^{cmp}=P_{m}^{cmp}\cdot T_{m}^{cmp},$ (18)

where $P_{m}^{cmp}$ and $T_{m}^{cmp}$ are two functions of the core voltage
and the core/memory frequency [25], which are given by

$P_{m}^{cmp}=P_{m}^{0}+\alpha
f_{m}^{mem}+\beta(v_{m}^{core})^{2}f_{m}^{core},$ (19)
$T_{m}^{cmp}=T_{m}^{0}+\frac{a}{f_{m}^{mem}}+\frac{b}{f_{m}^{core}}.$ (20)

Here, $P_{m}^{0}$ and $T_{m}^{0}$ represent the static power consumption and
static time consumption; $v_{m}^{core},f_{m}^{core},f_{m}^{mem}$ denote the
GPU core voltage, GPU core frequency, and GPU memory frequency, respectively;
$\alpha$, $\beta$, $a$ and $b$ are constant coefficients indicating the
sensitivity to memory frequency scaling and the core voltage/frequency
scaling, which depend on the hardware and the application characteristics. In
this work, the value of $\alpha$, $\beta$, $a$, and $b$ are derived from
platform-based experiments by measuring the average runtime energy
consumption. Specifically, we measure the energy consumed to execute single-
step SGD and estimate the parameters that appeared in the energy model in
(18). For simplicity, we shall assume that $E_{m,ite}^{cmp}$ keeps unchanged
during training in spite of the incremental batch sizes used in Algorithm 1.
This is reasonable due to the fact that GPUs are capable of parallel
execution. When the training batch size remains under a threshold, GPUs can
process the whole-batch samples simultaneously, leading to a near-constant
execution time [26, 16]. In this case, the total energy111The computational
complexity of the gradient sparsification algorithm is so low compared with
running local SGD that the corresponding computational workload and the
involved energy consumption can be omitted [26]. consumed between every two
global synchronizations including $H$ local iterations can be computed as

$E_{m}^{cmp}=E_{m,ite}^{cmp}\cdot H.$ (21)

####  IV-A3 Problem Formulation

Given the communication model and the computational model above, we compute
the total energy consumption of all the participating edge devices between
every two global synchronizations as

$E=\sum\limits_{m=1}^{M}\left(E_{m}^{com}+E_{m}^{cmp}\right),$ (22)

which captures the heterogeneity of participants on their communication
conditions and GPU capacities. Exploiting Corollary 1 and plugging
$\delta=\sqrt{\frac{1}{M}\sum_{m=1}^{M}\delta_{m}^{2}}$, we model the overall
energy consumed during the whole training process as

$\Gamma(\delta_{1},\delta_{2},...,\delta_{M},H)=E\cdot\sum\limits_{m=1}^{M}\left(\alpha
H\delta_{m}^{2}+\frac{\beta}{M^{3/2}H}\right),$ (23)

where $\alpha$ and $\beta$ are constants used to approximate the
big-$\mathcal{O}$ notion in (8). With the goal of overall energy consumption
minimization, we jointly determine the gradient sparsity $\delta_{m}$ for each
participant $m\in\mathcal{M}$ and the global update frequency $H$ by solving
the following optimization problem:

$\displaystyle\min\limits_{\\{\delta_{m},H\\}}\quad$
$\displaystyle\Gamma(\delta_{1},\delta_{2},...,\delta_{M},H)$ (24a)
$\displaystyle s.t.\quad$
$\displaystyle\delta_{lb}\leq\delta_{m}\leq\delta_{ub},\ \forall m,$ (24b)
$\displaystyle H\in\mathcal{H}.$ (24c)

Here, constraints (24b) and (24c) restrict the feasible range of $\delta_{m}$
and $H$ with $\mathcal{H}\subset\mathbb{Z}^{+}$, respectively. The formulated
problem in (24) exhibits a certain trade-off between compression and
convergence in the considered communication-compressed FL setting. To minimize
the energy consumption in single global iteration, one will severely compress
the gradient tensor and decide to perform a single-step local update all the
time, which would greatly impact the convergence rate and increase the number
of global synchronizations. As a result, total energy consumption may increase
considerably. In practice, the participants with excellent communication
environments are expected to adopt slight gradient compression schemes for
accelerating the convergence, while the others with poor channel conditions
should be allowed to sparsify the gradients more severely to save the energy.
In light of this, global update frequency and gradient sparsity should be
carefully determined by considering the heterogeneity of participants for
achieving energy-efficient FL.

###  IV-B Compression Control Algorithm

We develop a compression parameter control algorithm by approximately solving
the formulated optimization problem in (24) that falls into the category of
mixed-integer non-linear programming. It is non-trivial to solve since the
integer variable $H$ is highly coupled with the continuous variables
$\\{\delta_{m}\\}_{\forall m}$. In the following, we first transform the
permutation operator in (15) into a tractable form. Then we propose an
efficient algorithm integrating generalized Benders decomposition and inner
convex approximation to find a satisfactory solution of the considered
compression control problem.

###### Corollary 2

Let $\delta_{m}\\!=\\!d/k_{m}$ be the chosen gradient sparsity and
$\kappa\\!=\\!{\rm FPP}\\!+\\!1$. The total number of bits required to be
transmitted by participant $m$ per global round, i.e., $S_{m}$, can be
approximated to

$S_{m}(\delta_{m})=\frac{s_{1}d}{\delta_{m}}(\log_{2}\delta_{m}+\kappa)+s_{0}$
(25)

###### Proof:

$\displaystyle
S_{m,pos}=\log_{2}\binom{d}{k_{m}}=\log_{2}\frac{d!}{(d-k_{m})!k_{m}!}$
$\displaystyle=$ $\displaystyle\log_{2}d!-\log_{2}k_{m}!-\log_{2}(d-k_{m})!$
$\displaystyle\overset{(a)}{\approx}$ $\displaystyle
d\log_{2}d-k_{m}\log_{2}k-(d-k_{m})\log_{2}(d-k_{m})$ $\displaystyle=$
$\displaystyle
d\log_{2}d-\frac{d}{\delta_{m}}\log_{2}\frac{d}{\delta_{m}}-(d-\frac{d}{\delta_{m}})\log_{2}(d-\frac{d}{\delta_{m}})$
$\displaystyle=$ $\displaystyle
d[\log_{2}\delta_{m}+(\frac{1}{\delta_{m}}-1)\log_{2}(\delta_{m}-1)]\overset{(b)}{\approx}\frac{d}{\delta_{m}}\log_{2}\delta_{m}.$

Here, $(a)$ is by Stirling formula that gives precise estimate for factorials,
i.e., $\log_{2}{n!}\\!\approx\\!n\log_{2}{n}\\!-\\!n\log_{2}{e}$, and $(b)$ is
due to $\delta_{m}\\!=\\!d/k_{m}\\!\gg\\!1$. Substituting $S_{m,pos}$ into
(15) yields (25). ∎

We can easily verify that $S_{m}(\delta_{m})$ is strongly convex w.r.t.
$\delta_{m}$, when $\delta_{m}\geq e^{3/2}$ by calculating its second order
derivative:

$\begin{split}\frac{\mathrm{d}^{2}S_{m}(\delta_{m})}{\mathrm{d}\delta_{m}^{2}}=\frac{s_{1}d(2\ln\delta_{m}-3)}{\delta_{m}^{3}\ln
2}+\frac{2s_{1}d\kappa}{\delta_{m}^{3}}>0.\end{split}$ (26)

Extensive empirical evidence reveals that $\delta_{m}\\!\geq\\!e^{3/2}$ always
holds in practice so that gradient sparsification can considerably reduce the
communication overhead. In the following, we assume that $\delta_{lb}$ is set
to be no less than $e^{3/2}$ and view $S_{m}(\delta_{m})$ as a strongly convex
function without extra conditions. Using Corollary 2, we substitute
$\Gamma(\cdot)$ by an approximated energy cost function and rewrite the
problem in (24) as:

$\displaystyle\min\limits_{\\{\delta_{m},H\\}}\quad$
$\displaystyle\sum\limits_{m=1}^{M}\left(\alpha
H\delta_{m}^{2}+\frac{\beta}{M^{3/2}H}\right)$
$\displaystyle\cdot\sum\limits_{m=1}^{M}\left(\frac{P_{m}s_{1}d(\log_{2}\delta_{m}+\kappa)}{R_{m}\delta_{m}}+\frac{P_{m}s_{0}}{R_{m}}+E_{m}^{0}H\right)$
$\displaystyle s.t.\quad$ $\displaystyle(\ref{c1})\ \text{and}\ (\ref{c2}).$
(27)

To solve (IV-B), we propose an algorithm integrating generalized Benders
decomposition and inner convex approximation. Specifically, generalized
Benders decomposition performs as the outer-loop algorithm to decompose the
problem above into two sub-problems: a primal problem w.r.t. the continuous
variables $\\{\delta_{m}\\}_{\forall m}$ and a master problem w.r.t. the
integer variable $H$ [27]. As the inner-loop algorithm, inner convex
approximation is used to solve the primal problem by successively optimizing
the approximants of the non-convex objective. We solve the primal problem and
the master problem in an alternative and iterative manner, as detailed in
Algorithm 2. In each outer-loop iteration, solving the primary problem with
given $H$ yields an upper bound for the optimal value of (IV-B) while solving
the master problem provides its lower bound. Particularly, we formulate the
primal problem in the $i$-th iteration with fixed $H^{(i)}$ as follows:

$\displaystyle\min\limits_{\\{\delta_{m}\\}}\quad$
$\displaystyle\sum\limits_{m=1}^{M}\left(\alpha
H^{(i)}\delta_{m}^{2}+\frac{\beta}{M^{3/2}H^{(i)}}\right)$ (28a)
$\displaystyle\cdot\sum\limits_{m=1}^{M}\left(\frac{P_{m}s_{1}d(\log_{2}\delta_{m}+\kappa)}{R_{m}\delta_{m}}+\frac{P_{m}s_{0}}{R_{m}}+E_{m}^{0}H^{(i)}\right)$
$\displaystyle s.t.\quad$ $\displaystyle(\ref{c1}).$

Note that the primal problem above is always feasible for all $H^{(i)}$ since
the continuous variables $\\{\delta_{m}\\}_{\forall m}$ are independent of
$H^{(i)}$ in the constraint. Thus, we do not need to check the feasibility of
the current $H^{(i)}$ as conventional Benders decomposition methods do [28].
Let $\\{\lambda_{m1}\\}_{\forall m}$ and $\\{\lambda_{m2}\\}_{\forall m}$
denote two sets of Lagrange multiplier corresponding to the constraints in
(24b). We solve the primal problem to get the solutions of
$\\{\delta_{m}\\}_{\forall m}$, $\\{\lambda_{m1}\\}_{\forall m}$ and
$\\{\lambda_{m2}\\}_{\forall m}$, which are denoted by
$\\{\delta_{m}^{(i)}\\}_{\forall m}$, $\\{\lambda_{m1}^{(i)}\\}_{\forall m}$
and $\\{\lambda_{m2}^{(i)}\\}_{\forall m}$, respectively. We also update $UBD$
with the objective value of (28a). Afterwards, a feasibility cut can be
generated and added to the master problem as a new constraint. In particular,
the master problem in the $i$-th iteration is given as follows:

$\displaystyle\min\limits_{H}\quad$ $\displaystyle\eta$ (29a) $\displaystyle
s.t.\quad$ $\displaystyle\eta\geq\sum\limits_{m=1}^{M}\left(\alpha
H(\delta_{m}^{(l)})^{2}+\frac{\beta}{M^{3/2}H}\right)$ (29b)
$\displaystyle\cdot\sum\limits_{m=1}^{M}\left(\frac{P_{m}s_{1}d(\log_{2}\delta_{m}^{(l)}+\kappa)}{R_{m}\delta_{m}^{(l)}}+\frac{P_{m}s_{0}}{R_{m}}+E_{m}^{0}H\right)$
$\displaystyle+\\!\sum\limits_{m=1}^{M}\\!\left(\lambda_{m1}^{(l)}\\!(\delta_{lb}\\!-\\!\delta_{m}^{(l)})+\\!\lambda_{m2}^{(l)}(\delta_{m}^{(l)}\\!-\\!\delta_{ub})\right),\forall
l\\!=1,...,i,$ $\displaystyle H\in\mathcal{H}.$ (29c)

Algorithm 2 Compression Control Algorithm

Initialization: $H^{(1)}\in\mathcal{H}$; $I_{out}$; $\epsilon=10^{-5}$;
$\iota=10^{-5}$; $\xi=10^{-5}$; $LBD=-\infty$; $UBD=\infty$; $i=1$;

1:repeat

2: Set inner-loop iteration index $\nu=0$

3: Set step size $\gamma^{0}\in(0,1]$ and start with
$\delta_{m}^{0}=\delta_{lb},\forall m$

4: repeat

5: Compute $\delta_{m}^{*}(\delta_{m}^{\nu}),\forall m$ via (35)

6: Set
$\delta_{m}^{\nu+1}=\delta_{m}^{\nu}+\gamma^{0}(\delta_{m}^{*}(\delta_{m}^{\nu})-\delta_{m}^{\nu}),\forall
m$

7: Set $\nu=\nu+1$

8: Set $\gamma^{\nu}=\gamma^{\nu-1}(1-\xi\gamma^{\nu-1})$

9: until
$||\boldsymbol{\delta}^{\nu}-\boldsymbol{\delta}^{\nu-1}||_{2}^{2}\leq\iota$

10: Save $\delta_{m}^{(i)}=\delta_{m}^{\nu}$ for all $m\in\mathcal{M}$ as the
current solution of the primal problem in (28).

11: Obtain the Lagrangian multiplier $\lambda$ and the objective value
$\Gamma^{(i)}$

12: Update the upper bound value with $UBD=\Gamma^{(i)}$

13: Solve the master problem in (29)

14: Obtain intermediate solutions of $H^{(i)}$ and $\eta^{(i)}$

15: Update the upper bound value with $LBD=\eta^{(i)}$

16: Save $H^{(i+1)}=H^{(i)}$

17: if $UBD-LBD\leq\epsilon$ then

18: return The current solutions of $\\{\delta_{m}\\}_{\forall m}$ and $H$.

19: else Set $i=i+1$

20:until $i=I_{out}$

21:return The current solutions of $\\{\delta_{m}\\}_{\forall m}$ and $H$.

The master problem in (29) is a small-scale mixed-integer programming problem
and can be solved using classical optimization algorithms, e.g., Branch-and-
Bound. After solving it, we update $LBD$ with the value of $\eta$. Now we
focus on solving the non-convex primal problem (28), which is specified by the
inner-loop procedures in Algorithm 2. Here, we use the inner convex
approximation method to find the stationary points iteratively. The main idea
is to successively optimize certain approximations of the non-convex objective
function in (28a) while maintaining feasibility at each iteration. This
requires us to derive a strongly convex approximant of (28a) around each
feasible iteration. With a slight abuse of notation, we denote the objective
function in (28a) by $\Gamma(\boldsymbol{\delta})$ with
$\boldsymbol{\delta}\\!=\\!(\delta_{1},...,\delta_{M})$ and rewrite it as the
product of two functions, i.e.,

$\Gamma(\boldsymbol{\delta})=\Gamma_{1}(\boldsymbol{\delta})\cdot\Gamma_{2}(\boldsymbol{\delta}),$
(30)

where

$\displaystyle\Gamma_{1}(\boldsymbol{\delta})\\!=\\!\\!\sum\limits_{m=1}^{M}\\!\left(\alpha
H^{(i)}\delta_{m}^{2}+\frac{\beta}{M^{3/2}H^{(i)}}\\!\right),$ (31)
$\displaystyle\Gamma_{2}(\boldsymbol{\delta})\\!=\\!\\!\sum\limits_{m=1}^{M}\\!\left(\\!\frac{P_{m}s_{1}d(\log_{2}\\!\delta_{m}\\!\\!+\\!\kappa)}{R_{m}\delta_{m}}\\!+\\!\frac{P_{m}s_{0}}{R_{m}}\\!+\\!E_{m}^{0}H^{(i)}\\!\right).$
(32)

Note that both $\Gamma_{1}(\boldsymbol{\delta})$ and
$\Gamma_{2}(\boldsymbol{\delta})$ are positive and strongly convex since
non–negative combinations of convex functions preserve convexity. Capturing
such the “product of convexity” property of (30), we built an approximation
for $\Gamma(\boldsymbol{\delta})$ as:

$\tilde{\Gamma}(\boldsymbol{\delta};\boldsymbol{\delta}^{\nu})=\Gamma_{1}(\boldsymbol{\delta})\cdot\Gamma_{2}(\boldsymbol{\delta}^{\nu})+\Gamma_{1}(\boldsymbol{\delta}^{\nu})\cdot\Gamma_{2}(\boldsymbol{\delta}),$
(33)

where
$\boldsymbol{\delta}^{\nu}\triangleq(\delta_{1}^{\nu},\delta_{2}^{\nu},...,\delta_{M}^{\nu})$
denote the current intermediate $\boldsymbol{\delta}$ obtained in the $\nu$-th
inner iteration [29]. Obviously, the approximated objective function in (33)
is strongly convex and the corresponding approximations of the primal problem
in (28) can be solved optimally, which is in the form of:

$\begin{split}\boldsymbol{\delta}^{*}(\boldsymbol{\delta}^{\nu})=\mathop{\text{argmin}}\limits_{\\{\delta_{m}\\}_{\forall
m}}&\quad\tilde{\Gamma}(\boldsymbol{\delta};\boldsymbol{\delta}^{\nu})\\\
s.t.&\quad(\ref{c1}).\end{split}$ (34)

(a) Impact of system scale (b) Impact of user heterogeneity (c) Impact of
comm. capacity (d) Impact of comp. capacity

Figure 1: Impact of system parameters.

(a) Training accuracy vs epochs (b) Test error vs consumed energy (c) Training
accuracy vs epochs (d) Test error vs consumed energy

Figure 2: Performance on various architectures and datasets. ((a-b): ResNet20
trained on CIFAR-10; (c-d): LeNet5-Caffe trained on MNIST.)

######  Corollary 3 (Closed form of
$\delta_{m}^{*}(\boldsymbol{\delta}^{\nu}),\forall m$)

Let $\delta_{m}^{*}(\boldsymbol{\delta}^{\nu})$ be the optimal solution of
$\delta_{m}$ given the current $\boldsymbol{\delta}^{\nu}$. Then, each
$\delta_{m}^{*}(\boldsymbol{\delta}^{\nu})$ has the following expression:

$\delta_{m}^{*}(\boldsymbol{\delta}^{\nu})=\left\\{\begin{aligned}
\delta_{lb},&&{\overline{\delta}_{m}\leq\delta_{lb}}\\\
\overline{\delta}_{m}(\boldsymbol{\delta}^{\nu}),&&{\delta_{lb}}<\overline{\delta}_{m}\leq\delta_{ub}\\\
\delta_{ub},&&{\overline{\delta}_{m}\geq\delta_{ub}}\end{aligned}\right.$ (35)

where $\overline{\delta}_{m}(\boldsymbol{\delta}^{\nu})$ is given by

$\overline{\delta}_{m}(\boldsymbol{\delta}^{\nu})\\!=\\!exp\left(-\frac{1}{3}W\left(-\frac{6AE\cdot
exp\left(3B\right)}{DC_{m}}\right)+B\right)$ (36)

with

$\displaystyle A=\alpha H^{(i)},\ B=1-\kappa\ln{2},\ C_{m}=P_{m}s_{1}d/R_{m},$
$\displaystyle D\\!=\\!\sum_{m}\left(\alpha
H^{(i)}(\delta_{m}^{\nu})^{2}+\frac{\beta}{M^{3/2}H^{(i)}}\right),$
$\displaystyle
E\\!=\\!\sum_{m}\left(\frac{P_{m}s_{1}d(\log_{2}\delta_{m}^{\nu}+\kappa)}{R_{m}\delta_{m}^{\nu}}+\frac{P_{m}s_{0}}{R_{m}}+E_{m}^{0}H^{(i)}\right)\ln
2.$

Here, $W(\cdot)$ denotes the Lambert function.

###### Proof:

This is derived by using the Karush-Kuhn-Tucker conditions. We omit the proof
due to space limitation. ∎

Thanks to the closed-formula for $\delta_{m}^{*}(\boldsymbol{\delta}^{\nu})$,
Algorithm 2 can solve the inner-loop primal problem into optimality without
resorting to any iterative solver that can provide approximate solutions only.
We adopt the branch-and-bound algorithm to solve the master problem in (29)
with computational complexity $O(2^{|\mathcal{H}|})$. When solving the primal
problem takes $I_{in}$ inner-loop iterations in total, the overall complexity
of Algorithm 2 is $O(I_{out}\max\\{O(2^{|\mathcal{H}|}),I_{in}\\})$ in the
worst case where $I_{out}$ denotes the number of iterations required by the
outer loops.

##  V Performance Evaluation

We evaluate the performance of the proposed compression control scheme,
denoted by “FlexibleSpars”, via extensive simulations. Particularly, we
compare with the following three schemes: 1) SynSgdSpars allows participants
to sparsify their gradients flexibly, and follows the typical setting of
synchronous distributed gradient descent to perform global aggregation after
every local update. 2) GreedySpars greedily makes the compression control
decisions by minimizing the energy cost in the current round, which is
oblivious to the impact of the trade-off relationship between the number of
global rounds and the cost in a single round on the total energy consumption.
3) UnifiedSpar forces every participant to compress the gradients with a
unified sparsity, regardless of the heterogeneous communication condition.
Compression parameters are determined by solving a simplified version of the
problem in (IV-B).

Fig. 1(a) demonstrates the average energy consumption with the varying number
of participating devices. We see that the average energy consumption decreases
with the growing scale of the FL system under all the schemes, while all the
curves tend to be flat. This is due to the fact that increasing the number of
participants can help to speed up the convergence of the training process and
thereby save the resources at each edge device. Yet such speed-ups will be
slight when the participating devices are enough to well capture the whole
dataset’s information and characteristics $\bigcup_{m}\mathcal{D}_{m}$ for
training. Among the four schemes, “SynSgdSpars” is shown to consume the most
energy since it increases the communication complexity significantly. As
expected, our proposed scheme “FlexibleSpar” outperforms the others as it
injects more foresight than “GreedySpar” and more flexibility than UnifiedSpar
into the compression decision-making, to better fit the heterogeneous
communication conditions across participants. Fig. 1(b) further gives an
insight into the impact of the heterogeneity level of participants’
communication capacity on the system energy efficiency. Here, we set the
number of participants 12 and divide them into four groups, corresponding to
four capacity levels. Assume that participants belonging to the same group use
the same wireless bandwidth for gradient exchanges. Let $L$ be the level of
heterogeneity that controls the variations in bandwidth among different
groups. Fixing the average bandwidth $\overline{W}=1$GHz, we set the bandwidth
adopted by the four groups as $\overline{W}-0.03L$ (GHz), $\overline{W}-0.01L$
(GHz), $\overline{W}+0.01L$ (GHz), and $\overline{W}+0.03L$ (GHz),
respectively. We set the value of $L$ to vary in $\\{0,1,...,14\\}$, where
larger $L$ indicates higher level of heterogeneity. Fig. 1(b) elucidates that
the high level of communication heterogeneity has a negative impact on FL and
indeed impairs the system energy efficiency. Notice that we omit the
examination of “SynSgdSpars” in this setting since it performs so poorly that
it is incomparable to the other schemes. Thanks to the flexible compression,
our proposed scheme, as we would expect, exhibits more resilience than the
others to cope with the scenario with high heterogeneity across participants
in terms of wireless channel conditions.

We define $\zeta_{com}=\frac{1}{M}\sum_{m}\frac{P_{m}s_{1}}{R_{m}}$ (J/bit)
and $\zeta_{cmp}=\frac{1}{M}\sum_{m}E_{m,ite}^{cmp}$ (J/iteration)
representing the average energy intensity in terms of transmitting and
computing, respectively. Keeping the above group setting of 12 participants
with $L=10$, we further examine the impacts of $\zeta_{com}$ and $\zeta_{cmp}$
on the optimal values of gradient sparsity $\\{\delta\\}_{\forall m}$ and
synchronization frequency $H$ obtained from our control algorithm. The results
are shown in Fig. 1(c)-1(d). Note that $H$ can be viewed as the level of
temporal sparsity in the sense that performing multiple local iterations
between every two synchronizations implicitly sparsifies the communications in
the temporal domain. In Fig. 1(c), “Sparsity-G1/2/3/4” denotes the decision of
gradient sparsity for the participants in the group 1/2/3/4, respectively.
“LocIteration” denotes the decision of their temporal sparsity $H$. When
$\zeta_{com}$ is small, participants are allowed to sparsify the gradients at
a relatively low degree without adding to the total energy cost significantly.
In this case, the number of global rounds is dominantly affected by the second
term in (8), and a large temporal sparsity $H$ is needed to reduce the number
of necessary global rounds. As $\zeta_{com}$ grows, all the participants tend
to increase the gradient sparsity to fit the worsening communication
conditions. We observe that the participants in Group 1 suffering the worst
channel conditions generally prefer higher gradient sparsity than the
participants in the other groups. When $\zeta_{com}$ is large enough, the
impact of communication on the total energy consumption becomes more profound
than that of computing, forcing the participants to compress the gradients
severely with the large $\\{\delta_{m}\\}_{\forall m}$ to alleviate the
communication burden. Accordingly, the first term in (8) begins to take
effects, resulting in the decreasing degree of temporal sparsity $H$. The
analysis above can also be verified by Fig. 1(d), where we vary $\zeta_{cmp}$
while keeping $\zeta_{com}$ unchanged. We find that the curves in Fig. 1(d)
are somewhat symmetrical to the curves in Fig. 1(c). The reason lies in that
increasing $\zeta_{cmp}$ can be viewed as decreasing $\zeta_{com}$ in our
system, both of which imply the process of computing cost becoming the
bottleneck. Fig. 1(c)-1(d) reveal that there is a trade-off between gradient
sparsity and temporal sparsity, which indeed corresponds to less “talking” and
less “working”. As expected, our flexible compression scheme allows
participants to balance these two types of sparsity smoothly against one
another for saving energy during training.

Fig. 2 further presents the training results on several commonly used deep
models and datasets. Specifically, Fig. 2(a)-2(b) show the convergence rate in
terms of epochs and consumed energy respectively for ResNet20 [30] trained on
CIFAR-10, while Fig. 2(c)-2(d) show the same things for LeNet5-Caffe [22]
trained on MNIST. Here, we take ordinary distributed SGD as the baseline in
which each participant transmits full gradients to the server after every
local update. From Fig. 2(a) and Fig. 2(c), we observe that “FlexibleSpar”
exhibits very similar behavior with “UnifiedSpar” in terms of convergence rate
and final accuracy, both of which slightly underperform “SynSgdSpar”. This
also implies that temporal sparsity has a more profound impact on convergence
rate than gradient sparsity in our setting. Due to delayed synchronization and
imprecise gradient information, both “UnifiedSpar” and “FlexibleSpar” are
shown to slow down the convergence at initial, which is consistent with our
convergence analysis. In spite of this, “FlexibleSpar” is validated to be
capable of saving energy for on-device training. As reported in Fig. 2(b) and
Fig. 2(d), “FlexibleSpar” consumes $\times 1.5\\!-\\!\times 100$ less energy
than the other schemes to reach a given target accuracy.

##  VI Conclusion

In this work, we have presented a holistic communication compression solution
to reduce the energy consumption of FL over heterogeneous participating edge
devices without sacrificing the model accuracy. We have developed a FL
algorithm enabling flexible communication compression and provided the
convergence analysis from a theoretical perspective. Considering the
heterogeneous computing and communication conditions across edge devices, we
have further designed an energy-efficiency oriented compression control scheme
guided by the derived convergence bound. Extensive simulations have been
conducted to verify the theoretical analysis and evaluate the algorithm’s
performance. The results have shown that our flexibly compressed FL scheme
exhibits great potentials in accommodating heterogeneous mobile edge devices
and improving the energy efficiency of FL over those edge devices.

## Acknowledgment

The work of L. Li, R. Hou and H. Li was partially supported by National
Natural Science Foundation of China (Grant No. 61571351), State Key Laboratory
of Computer Architecture (ICT, CAS) under Grant No. CARCH201904, the Major
Research plan of the Shaanxi Science Foundation of China (2019ZDLGY12-08), the
111 project (grant No. B16037), and OPPO funding. The work of D. Shi and M.
Pan was supported in part by the U.S. National Science Foundation under grants
US CNS-1646607, CNS-1801925, and CNS-2029569. The work of Z. Han was partially
supported by NSF EARS-1839818, CNS-1717454, CNS-1731424, and CNS-1702850.

## References

  * [1] A. Hard, K. Rao, R. Mathews, S. Ramaswamy, F. Beaufays, S. Augenstein, H. Eichner, C. Kiddon, and D. Ramage, “Federated learning for mobile keyboard prediction,” _arXiv preprint arXiv:1811.03604_ , 2018.
  * [2] S. Team, “Hey siri: An on-device dnn-powered voice trigger for apple’s personal assistant,” https://machinelearning.apple.com/research/hey-siri, accessed July, 2020\.
  * [3] D. Chen, L. J. Xie, B. Kim, L. Wang, C. S. Hong, L.-C. Wang, and Z. Han, “Federated learning based mobile edge computing for augmented reality applications,” in _Proc. of International Conference on Computing, Networking and Communications (ICNC)_ , Big Island, HA, February 2020.
  * [4] S. Wang, T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan, “Adaptive federated learning in resource constrained edge computing systems,” _IEEE Journal on Selected Areas in Communications_ , vol. 37, no. 6, pp. 1205–1221, 2019.
  * [5] K. Yang, T. Jiang, Y. Shi, and Z. Ding, “Federated learning via over-the-air computation,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 3, pp. 2022–2035, March 2020.
  * [6] M. Chen, H. V. Poor, W. Saad, and S. Cui, “Convergence time optimization for federated learning over wireless networks,” _arXiv preprint arXiv:2001.07845_ , 2020.
  * [7] N. H. Tran, W. Bao, A. Zomaya, N. M. NH, and C. S. Hong, “Federated learning over wireless networks: Optimization model design and analysis,” in _Proc. of IEEE Conference on Computer Communications (INFOCOM)_ , Paris, France, April 2019.
  * [8] C. Dinh, N. H. Tran, M. N. Nguyen, C. S. Hong, W. Bao, A. Zomaya, and V. Gramoli, “Federated learning over wireless networks: Convergence analysis and resource allocation,” _arXiv preprint arXiv:1910.13067_ , 2019.
  * [9] H. Yu, S. Yang, and S. Zhu, “Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning,” in _Proc. of AAAI Conference on Artificial Intelligence_ , Honolulu, HA, January 2019.
  * [10] S. U. Stich, J.-B. Cordonnier, and M. Jaggi, “Sparsified SGD with memory,” in _Proc. of Advances in Neural Information Processing Systems (NIPS)_ , Vancouver, Canada, December 2018.
  * [11] D. Alistarh, T. Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli, “The convergence of sparsified gradient methods,” in _Proc. of Advances in Neural Information Processing Systems (NIPS)_ , Vancouver, Canada, December 2018.
  * [12] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, “Qsgd: Communication-efficient SGD via gradient quantization and encoding,” in _Proc. of Advances in Neural Information Processing Systems (NIPS)_ , Long Beach, CA, December 2017.
  * [13] J. Ding, G. Liang, J. Bi, and M. Pan, “Differentially private and communication efficient collaborative learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , Virtual Conference, February 2021\.
  * [14] H. Tang, S. Gan, C. Zhang, T. Zhang, and J. Liu, “Communication compression for decentralized training,” in _Proc. of Advances in Neural Information Processing Systems (NIPS)_ , Vancouver, Canada, December 2018.
  * [15] W. Saad, M. Bennis, and M. Chen, “A vision of 6g wireless systems: Applications, trends, technologies, and open research problems,” _IEEE network_ , vol. 34, no. 3, pp. 134–142, February 2019.
  * [16] T. Lin, S. U. Stich, K. K. Patel, and M. Jaggi, “Don’t use large mini-batches, use local SGD,” in _Proc. of International Conference on Learning Representations (ICLR)_ , Addis Ababa, Ethiopia, April 2020.
  * [17] P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He, “Accurate, large minibatch SGD: Training imagenet in 1 hour,” _arXiv preprint arXiv:1706.02677_ , 2017.
  * [18] H. B. McMahan, E. Moore, D. Ramage, S. Hampson _et al._ , “Communication-efficient learning of deep networks from decentralized data,” in _Proc. of International Conference on Artificial Intelligence and Statistics (AISTATS)_ , Fort Lauderdale, FL, April 2017.
  * [19] S. L. Smith, P.-J. Kindermans, C. Ying, and Q. V. Le, “Don’t decay the learning rate, increase the batch size,” in _Proc. of 6th International Conference on Learning Representations (ICLR)_ , Vancouver, Canada, April 2017\.
  * [20] H. Yu and R. Jin, “On the computation and communication complexity of parallel SGD with dynamic batch sizes for stochastic non-convex optimization,” in _Proc. of 36th International Conference on Machine Learning (ICML)_ , Long Beach, CA, June 2019.
  * [21] H. Yu, R. Jin, and S. Yang, “On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization,” in _Proc. of 36th International Conference on Machine Learning (ICML)_ , Long Beach, CA, June 2019.
  * [22] F. Sattler, S. Wiedemann, K.-R. Müller, and W. Samek, “Sparse binary compression: Towards distributed deep learning with minimal communication,” in _2019 International Joint Conference on Neural Networks (IJCNN)_ , Budapest, Hungary, July 2019.
  * [23] S. Khirirat, S. Magnússon, A. Aytekin, and M. Johansson, “Communication efficient sparsification for large scale machine learning,” _arXiv:2003.06377_ , June 2020.
  * [24] M. Pan, C. Zhang, P. Li, and Y. Fang, “Joint routing and link scheduling for cognitive radio networks under uncertain spectrum supply,” in _Proc. IEEE Conference on Computer Communications (INFOCOM)_ , Shanghai, China, April 2011\.
  * [25] X. Mei, X. Chu, H. Liu, Y.-W. Leung, and Z. Li, “Energy efficient real-time task scheduling on cpu-gpu hybrid clusters,” in _Proc. of IEEE Conference on Computer Communications (INFOCOM)_ , Atlanta, GA, May 2017.
  * [26] J. Ren, G. Yu, and G. Ding, “Accelerating dnn training in wireless federated edge learning system,” _arXiv preprint arXiv:1905.09712_ , 2019.
  * [27] A. M. Geoffrion, “Generalized benders decomposition,” _Journal of optimization theory and applications_ , vol. 10, no. 4, pp. 237–260, May 1972\.
  * [28] L. Li, D. Shi, R. Hou, R. Chen, B. Lin, and M. Pan, “Energy-efficient proactive caching for adaptive video streaming via data-driven optimization,” _IEEE Internet of Things Journal_ , vol. 7, no. 6, pp. 5549–5561, March 2020.
  * [29] G. Scutari, F. Facchinei, and L. Lampariello, “Parallel and distributed methods for constrained nonconvex optimization—part i: Theory,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 8, pp. 1929–1944, April 2017\.
  * [30] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proc. of the IEEE conference on computer vision and pattern recognition (CVPR)_ , Las Vegas, NV, June 2016.
  * [31] D. Basu, D. Data, C. Karakus, and S. Diggavi, “Qsparse-local-SGD: Distributed SGD with quantization, sparsification and local computations,” in _Proc. of Advances in Neural Information Processing Systems (NIPS)_ , Vancouver, Canada, December 2019.

## Appendix

###  VI-A Proof of Theorem 1

Inspired by the perturbed iterate analysis framework in [31], we first define
the following auxiliary sequences for all $t\geq 0$:

1)

$\tilde{\boldsymbol{w}}_{m}^{(t)}=\left\\{\begin{aligned}
\widehat{\boldsymbol{w}}_{m}^{(0)}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\
,&&{t=0}\\\ \tilde{\boldsymbol{w}}_{m}^{(t-1)}-\eta\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t-1)};\mathcal{D}_{m}^{(t-1)})\ \
,&&{t\geq 1}\end{aligned}\right.$ (38)

2) $\boldsymbol{q}^{(t)}\triangleq\frac{1}{M}\sum\limits_{m=1}^{M}\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)};\mathcal{D}_{m}^{(t)})$

3)
$\overline{\boldsymbol{q}}^{(t)}\triangleq\mathbb{E}_{\mathcal{D}_{m}^{(t)}}[\boldsymbol{q}^{(t)}]=\frac{1}{M}\sum\limits_{m=1}^{M}\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})$

4)
$\tilde{\boldsymbol{w}}^{(t)}\triangleq\frac{1}{M}\sum\limits_{m=1}^{M}\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)};\mathcal{D}_{m}^{(t)})=\tilde{\boldsymbol{w}}^{(t-1)}-\eta\boldsymbol{q}^{(t-1)}$

5)
$\widehat{\boldsymbol{w}}^{(t)}=\frac{1}{M}\sum\limits_{m=1}^{M}\widehat{\boldsymbol{w}}_{m}^{(t)}$

By the smoothness of $F:\mathbb{R}^{d}\rightarrow\mathbb{R}$, we have

$\begin{split}&F(\tilde{\boldsymbol{w}}^{(t+1)})-F(\tilde{\boldsymbol{w}}^{(t)})\\\
\leq&<\nabla
F(\tilde{\boldsymbol{w}}^{(t)}),\tilde{\boldsymbol{w}}^{(t+1)}-\tilde{\boldsymbol{w}}^{(t)}>+\frac{L}{2}||\tilde{\boldsymbol{w}}^{(t+1)}-\tilde{\boldsymbol{w}}^{(t)}||^{2}\\\
=&-\eta<\nabla
F(\tilde{\boldsymbol{w}}^{(t)}),\boldsymbol{q}^{(t)}>+\frac{\eta^{2}L}{2}||\boldsymbol{q}^{(t)}||^{2}\\\
\overset{(a)}{\leq}&-\eta<\nabla
F(\tilde{\boldsymbol{w}}^{(t)}),\boldsymbol{q}^{(t)}>+\eta^{2}L||\boldsymbol{q}^{(t)}-\overline{\boldsymbol{q}}^{(t)}||^{2}+\eta^{2}L||\overline{\boldsymbol{q}}^{(t)}||^{2}\\\
=&-\frac{\eta}{M}\sum\limits_{m=1}^{M}<\nabla
F(\tilde{\boldsymbol{w}}^{(t)}),\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)};\mathcal{D}_{m}^{(t)})>\\\
&+\eta^{2}L||\boldsymbol{q}^{(t)}-\overline{\boldsymbol{q}}^{(t)}||^{2}+\eta^{2}L||\frac{1}{M}\sum\limits_{m=1}^{M}\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)};\mathcal{D}_{m}^{(t)})||^{2},\end{split}$
(39)

where $(a)$ is by Jensen’s inequality. Taking expectation with respect to the
sampling mini-batch $\mathcal{D}_{m}^{(t)}$ by each edge device at time $t$
gives

$\begin{split}&\mathbb{E}[F(\tilde{\boldsymbol{w}}^{(t+1)})]-F(\tilde{\boldsymbol{w}}^{(t)})\\\
\overset{(a)}{\leq}&-\frac{\eta}{2}(||\nabla
F(\tilde{\boldsymbol{w}}^{(t)})||^{2}+||\frac{1}{M}\sum\limits_{m=1}^{M}\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2})\\\ &+\frac{\eta}{2}||\nabla
F(\tilde{\boldsymbol{w}}^{(t)})-\frac{1}{M}\sum\limits_{m=1}^{M}\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}\\\
&+\eta^{2}L||\frac{1}{M}\sum\limits_{m=1}^{M}\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}+\frac{\eta^{2}L\sigma^{2}}{Mb^{(t)}}\\\
\overset{(b)}{\leq}&-\frac{\eta}{2M}\sum\limits_{m=1}^{M}(||\nabla
F(\tilde{\boldsymbol{w}}^{(t)})||^{2}-L^{2}||\tilde{\boldsymbol{w}}^{(t)}-\widehat{\boldsymbol{w}}_{m}^{(t)}||^{2})\\\
&+\frac{2\eta^{2}L-\eta}{2}||\frac{1}{M}\sum\limits_{m=1}^{M}\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}+\frac{\eta^{2}L\sigma^{2}}{Mb^{(t)}}\\\
=&-\frac{\eta}{2M}\sum\limits_{m=1}^{M}(||\nabla
F(\tilde{\boldsymbol{w}}^{(t)})||^{2}+L^{2}||\tilde{\boldsymbol{w}}^{(t)}-\widehat{\boldsymbol{w}}_{m}^{(t)}||^{2})\\\
&+\frac{2\eta^{2}L-\eta}{2M}\sum\limits_{m=1}^{M}||\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}+\frac{\eta^{2}L\sigma^{2}}{Mb^{(t)}}\\\
&+\frac{\eta
L^{2}}{M}||\tilde{\boldsymbol{w}}^{(t)}-\widehat{\boldsymbol{w}}_{m}^{(t)}||^{2}\end{split}$
(40)

where $(a)$ follows by applying two basic inequalities
$<\boldsymbol{a},\boldsymbol{a}>\leq
1/2||\boldsymbol{a}||^{2}+1/2||\boldsymbol{b}||^{2}$ and
$\mathbb{E}[||X||^{2}]=\mathbb{E}[||X-\mathbb{E}[X]||^{2}]+||\mathbb{E}[X]||^{2}$;
$(a)$ follows from the lipschitz continuity of the gradient of local
functions. The first term in (40) can be bounded in terms of $||\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}$ as follows:

$\begin{split}&||\nabla f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}\\\
\leq&2||\nabla f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})-\nabla
F(\tilde{\boldsymbol{w}}^{(t)})||^{2}+2||F(\tilde{\boldsymbol{w}}^{(t)})||^{2}\\\
\leq&2L^{2}||\widehat{\boldsymbol{w}}_{m}^{(t)}-\tilde{\boldsymbol{w}}^{(t)}||^{2}+||F(\tilde{\boldsymbol{w}}^{(t)})||^{2}\\\
\end{split}$ (41)

Using $\eta\leq\frac{1}{2L}$ and rearranging the terms in (40), we have

$\begin{split}&\frac{\eta}{4M}\sum\limits_{m=1}^{M}||\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}\\\
\leq&F(\tilde{\boldsymbol{w}}^{(t)})-\mathbb{E}[F(\tilde{\boldsymbol{w}}^{(t+1)})]+\frac{\eta^{2}L\sigma^{2}}{Mb^{(t)}}+\frac{\eta
L^{2}}{M}||\tilde{\boldsymbol{w}}^{(t)}-\widehat{\boldsymbol{w}}_{m}^{(t)}||^{2}\end{split}$
(42)

Taking expectation with respect to the entire process and using the basic
inequality $||\boldsymbol{a}+\boldsymbol{b}||^{2}\leq
2||\boldsymbol{a}||^{2}+2||\boldsymbol{b}||^{2}$ gives

$\begin{split}&\frac{\eta}{4M}\sum\limits_{m=1}^{M}\mathbb{E}[||\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}]\\\
\leq&\mathbb{E}[F(\tilde{\boldsymbol{w}}^{(t)})]-\mathbb{E}[F(\tilde{\boldsymbol{w}}^{(t+1)})]+\frac{\eta^{2}L\sigma^{2}}{Mb^{(t)}}\\\
&+2\eta
L^{2}\mathbb{E}[||\tilde{\boldsymbol{w}}^{(t)}-\widehat{\boldsymbol{w}}^{(t)}||^{2}]+\frac{2\eta
L^{2}}{M}\sum\limits_{m=1}^{M}\mathbb{E}[||\widehat{\boldsymbol{w}}^{(t)}-\widehat{\boldsymbol{w}}_{m}^{(t)}||^{2}]\\\
\overset{(a)}{\leq}&\mathbb{E}[F(\tilde{\boldsymbol{w}}^{(t)})]-\mathbb{E}[F(\tilde{\boldsymbol{w}}^{(t+1)})]+\frac{2\eta^{2}L\sigma^{2}}{M\rho^{t}b^{(0)}}\\\
&+2\eta
L^{2}\mathbb{E}[||\tilde{\boldsymbol{w}}^{(t)}-\widehat{\boldsymbol{w}}^{(t)}||^{2}]+\frac{2\eta
L^{2}}{M}\sum\limits_{m=1}^{M}\mathbb{E}[||\widehat{\boldsymbol{w}}^{(t)}-\widehat{\boldsymbol{w}}_{m}^{(t)}||^{2}],\end{split}$
(43)

where $(a)$ follows by recalling $b^{(t)}=\lfloor\rho^{t}b^{(0)}\rfloor$ and
noting $\lfloor x\rfloor>x/2$ as long as $x\geq 2$.

Now we give three important lemmas where the first two are borrowed from [31]
and the last one is proved in the following.

######  Lemma 1 (Memory [31])

The accumulated error captures the distance between the true sequence and
virtual sequence. That is

$\widehat{\boldsymbol{w}}^{(t)}-\tilde{\boldsymbol{w}}^{(t)}=\frac{1}{M}\sum\limits_{m-1}^{M}\boldsymbol{e}_{m}^{(t)}$
(44)

######  Lemma 2 (Contracting Deviation of Local Sequences [31])

The deviation of the local sequences is bounded by

$\frac{1}{M}\sum\limits_{m-1}^{M}\mathbb{E}[||\widehat{\boldsymbol{w}}^{(t)}-\widehat{\boldsymbol{w}}_{m}^{(t)}||^{2}]\leq\eta^{2}G^{2}H^{2}$
(45)

######  Lemma 3 (Bounded Memory)

For worker $m$ who synchronizes with the server every $H$ local iterations, we
have

$\mathbb{E}[||e_{m}^{(t)}||^{2}]\leq 4\delta_{m}^{2}\eta^{2}G^{2}H^{2}$ (46)

###### Proof:

Note that Algorithm 1 average the gradients every $H$ iterations between which
the accumulated error $\boldsymbol{e}_{m}^{(t)}$ at any participant $m$ and
the global parameter vector $\boldsymbol{w}^{(t)}$ keep unchanged. For ease of
presentation, we assume that $T$ is an integer multiple of $H$. Let
$\mathcal{I}_{T}=\\{t_{1},t_{2},...,t_{T/H}=T\\}$ be the aggregation indices
satisfying $t_{i+1}-t_{i}=H$. For every $m\in\mathcal{M}$, we have

$\begin{split}&\mathbb{E}[||\boldsymbol{e}_{m}^{(t_{i+1})}||^{2}]\\\
=&\mathbb{E}[||\boldsymbol{e}_{m}^{(t_{i+1}-1)}+\boldsymbol{w}^{(t_{i+1}-1)}-\widehat{\boldsymbol{w}}_{m}^{(t_{i+1}-\frac{1}{2})}-\boldsymbol{g}_{m}^{(t_{i+1}-1)}||^{2}]\\\
\overset{(a)}{\leq}&(1-\frac{1}{\delta_{m}})\mathbb{E}[||\boldsymbol{e}_{m}^{(t_{i+1}-1)}+\boldsymbol{w}^{(t_{i+1}-1)}-\widehat{\boldsymbol{w}}_{m}^{(t_{i+1}-\frac{1}{2})}||^{2}]\\\
\overset{(b)}{=}&(1-\frac{1}{\delta_{m}})\mathbb{E}[||\boldsymbol{e}_{m}^{(t_{i})}+\widehat{\boldsymbol{w}}_{m}^{(t_{i})}-\widehat{\boldsymbol{w}}_{m}^{(t_{i+1}-\frac{1}{2})}||^{2}].\end{split}$
(47)

Here $(a)$ is due to the contraction property of ${\rm
Top}_{k}(\boldsymbol{x})$ operator [10], that is
$\mathbb{E}||\boldsymbol{x}-{\rm
Top}_{k}(\boldsymbol{x})||^{2}\leq(1-k/d)||\boldsymbol{x}||^{2},\
\forall\boldsymbol{x}\in\mathbb{R}^{d}$. In $(b)$, we use
$\boldsymbol{e}^{(t_{i+1}-1)}=\boldsymbol{e}^{(t_{i})}$ and
$\boldsymbol{w}^{(t_{i+1}-1)}=\boldsymbol{w}^{(t_{i})}=\widehat{\boldsymbol{w}}_{m}^{(t_{i})}$
that always hold. Since the inequality
$||\boldsymbol{a}+\boldsymbol{b}||^{2}\leq(1+\tau)||\boldsymbol{a}+(1+\frac{1}{\tau})||\boldsymbol{b}||^{2}$
holds for every $\tau\geq 0$, we take any $p>1$ and transform (47) as follows

$\begin{split}&\mathbb{E}[||\boldsymbol{e}_{m}^{(t_{i+1})}||^{2}]\\\
\leq&(1-\frac{1}{\delta_{m}})\\{(1+\frac{(p-1)}{p\delta_{m}})\mathbb{E}[||\boldsymbol{e}_{m}^{(t_{i})}||^{2}]\\\
&+(1+\frac{p\delta_{m}}{(p-1)})\mathbb{E}[||\widehat{\boldsymbol{w}}_{m}^{(t_{i})}-\widehat{\boldsymbol{w}}_{m}^{(t_{i+1}-\frac{1}{2})}||^{2}]\\}\\\
\leq&(1-\frac{1}{p\delta_{m}})\mathbb{E}[||\boldsymbol{e}_{m}^{(t_{i})}||^{2}]\\\
&+\frac{p(\delta_{m}^{2}-1)}{(p-1)\delta_{m}}\mathbb{E}[||\sum\limits_{j=t_{i}}^{t_{i+1}-1}\eta\nabla
f_{m}(\boldsymbol{w}_{m}^{(j)};\mathcal{D}_{m}^{(j)})||^{2}]\\\
\overset{(a)}{\leq}&(1-\frac{1}{p\delta_{m}})\mathbb{E}[||\boldsymbol{e}_{m}^{(t_{i})}||^{2}]+\frac{p(\delta_{m}^{2}-1)}{(p-1)\delta_{m}}\eta^{2}G^{2}H^{2},\end{split}$
(48)

where $(a)$ follows from Assumption 1. Iterating the above inequality from
$i=0\rightarrow l$ where $l=T/H$ yields:

$\begin{split}&\mathbb{E}[||\boldsymbol{e}_{m}^{(t_{i+1})}||^{2}]\\\
\leq&\frac{p(\delta_{m}^{2}-1)}{(p-1)\delta_{m}}\eta^{2}G^{2}H^{2}\sum\limits_{j=1}^{(l)}(1-\frac{1}{p\delta_{m}})^{l-j}\\\
\overset{(a)}{\leq}&\frac{p^{2}(\delta_{m}^{2}-1)}{p-1}\eta^{2}G^{2}H^{2}\\\
\overset{(b)}{\leq}&4\delta_{m}^{2}\eta^{2}G^{2}H^{2},\end{split}$ (49)

where $(a)$ is by the fact that
$\sum_{j=1}^{(l)}(1-\frac{1}{p\delta_{m}})^{l-j}\leq\sum_{j\geq
0}(1-\frac{1}{p\delta_{m}})^{j}=p\delta_{m}$, and $(b)$ is by plugging $p=2$.
Note the the right-hand-side does not depend on $t$, i.e., for every
$t=0,1,...,T$, the following holds:

$\mathbb{E}[||\boldsymbol{e}_{m}^{(t)}||^{2}]\leq
4\delta_{m}^{2}\eta^{2}G^{2}H^{2}.$ (50)

∎

Lemma 1 and Lemma 3 together imply:

$\mathbb{E}[||\widehat{\boldsymbol{w}}^{(t)}-\tilde{\boldsymbol{w}}^{(t)}||^{2}]\leq\frac{4\eta^{2}G^{2}H^{2}}{M}\sum\limits_{m=1}^{M}\delta_{m}^{2}.$
(51)

Applying Lemma 2 and (51) into (43), we get

$\begin{split}&\frac{\eta}{4M}\sum\limits_{m=1}^{M}\mathbb{E}[||\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}]\\\
\leq&\mathbb{E}[F(\tilde{\boldsymbol{w}}^{(t)})]-\mathbb{E}[F(\tilde{\boldsymbol{w}}^{(t+1)})]+\frac{2\eta^{2}L\sigma^{2}}{M\rho^{t}b^{(0)}}\\\
&+\frac{8\eta^{3}L^{2}G^{2}H^{2}}{M}\sum\limits_{m=1}^{M}\delta_{m}^{2}+2\eta^{3}L^{2}G^{2}H^{2},\end{split}$
(52)

Recursively applying the above inequality from $t=0$ to $t=T-1$ yields

$\begin{split}&\frac{1}{4MT}\sum\limits_{t=0}^{T-1}\sum\limits_{m=1}^{M}\mathbb{E}[||\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}]\\\
\leq&\frac{\mathbb{E}[F(\tilde{\boldsymbol{w}}^{(0)})]-F^{*}}{\eta
T}+\frac{2\eta
L\sigma^{2}}{MTb^{(0)}}\sum\limits_{t=0}^{T-1}\frac{1}{\rho^{t}}\\\
&+\frac{8\eta^{2}L^{2}G^{2}H^{2}}{M}\sum\limits_{m=1}^{M}\delta_{m}^{2}+2\eta^{2}L^{2}G^{2}H^{2}\\\
\overset{(a)}{\leq}&\frac{\mathbb{E}[F(\tilde{\boldsymbol{w}}^{(0)})]-F^{*}}{\eta
T}+\frac{2\eta\rho L\sigma^{2}}{(\rho-1)MTb^{(0)}}\\\
&+\frac{8\eta^{2}L^{2}G^{2}H^{2}}{M}\sum\limits_{m=1}^{M}\delta_{m}^{2}+2\eta^{2}L^{2}G^{2}H^{2},\end{split}$
(53)

where $(a)$ follows by simplifying the partial sum of geometric series and
noting that $0<\frac{1}{\rho}<1$. Let $\boldsymbol{z}_{T}$ be a random
variable sampled from $\\{\widehat{\boldsymbol{w}}_{m}^{(t)}\\}$ with
probability ${\rm
Pr}[\boldsymbol{z}_{T}=\widehat{\boldsymbol{w}}_{m}^{(t)}]=\frac{1}{MT}$. By
taking $\delta=\sqrt{\frac{1}{M}\sum\limits_{m=1}^{M}\delta_{m}^{2}}$ and
$\eta=\frac{\theta\sqrt{M}}{\sqrt{T}}$( where $\theta$ is a constant
satisfying $\frac{\theta\sqrt{M}}{\sqrt{T}}\leq\frac{1}{2L}$), we have

$\begin{split}\mathbb{E}[||\boldsymbol{z}_{T}||^{2}]=&\frac{1}{MT}\sum\limits_{t=0}^{T-1}\sum\limits_{m=1}^{M}\mathbb{E}[||\nabla
f_{m}(\widehat{\boldsymbol{w}}_{m}^{(t)})||^{2}]\\\
\leq&\frac{4(\mathbb{E}[F(\boldsymbol{w}^{(0)})]-F^{*})}{\theta\sqrt{MT}}+\frac{8\rho\theta
L\sigma^{2}}{(\rho-1)Mb^{(0)}\sqrt{M}T^{3/2}}\\\
&+(4\delta^{2}+1)\frac{8M\theta^{2}L^{2}G^{2}H^{2}}{T},\end{split}$ (54)

Until now we complete the proof of Theorem 1