# Wireless Quantized Federated Learning: A Joint Computation and Communication
Design

Pavlos S. Bouzinis, , Panagiotis D. Diamantoulakis, , and George K.
Karagiannidis P. S. Bouzinis, P. Diamantoulakis, and G.K. Karagiannidis are
with Wireless Communication and Information Processing Group (WCIP),
Department of Electrical and Computer Engineering, Aristotle University of
Thessaloniki, Greece, E-mails: {mpouzinis, padiaman<EMAIL_ADDRESS>
###### Abstract

Recently, federated learning (FL) has sparked widespread attention as a
promising decentralized machine learning approach which provides privacy and
low delay. However, communication bottleneck still constitutes an issue, that
needs to be resolved for an efficient deployment of FL over wireless networks.
In this paper, we aim to minimize the total convergence time of FL, by
quantizing the local model parameters prior to uplink transmission. More
specifically, the convergence analysis of the FL algorithm with stochastic
quantization is firstly presented, which reveals the impact of the
quantization error on the convergence rate. Following that, we jointly
optimize the computing, communication resources and number of quantization
bits, in order to guarantee minimized convergence time across all global
rounds, subject to energy and quantization error requirements, which stem from
the convergence analysis. The impact of the quantization error on the
convergence time is evaluated and the trade-off among model accuracy and
timely execution is revealed. Moreover, the proposed method is shown to result
in faster convergence in comparison with baseline schemes. Finally, useful
insights for the selection of the quantization error tolerance are provided.

###### Index Terms:

wireless federated learning, quantization, convergence time minimization

##  I Introduction

Future wireless networks are envisioned to support ubiquitous artificial
intelligent services [1]. Conventional machine learning techniques are usually
conducted in a centralized manner, where the data are uploaded and processed
at a single entity, e.g., a central server [2]. However, the growing computing
capabilities of devices have paved the way for realizing distributed learning
frameworks. Among the decentralized approaches, federated learning (FL) has
shown great promise in preserving data privacy and providing low delay [3],
[4]. In FL, users collaboratively build a shared learning model, without
exposing their raw data to the server or any other residual participant. The
servers’ role is to redistribute the global model back to the users, while the
whole procedure is repeated until the convergence of the global model. In this
manner, FL is inherently privacy-preserving and reduces the communication
load. However, the wireless environment imposes some distinctive challenges,
owing to the limited wireless resources, unreliable links, etc., which degrade
the performance of FL and need to be efficiently addressed [5, 6, 7, 8].

###  I-A Related Works and Motivation

In the context of wireless networks, several works examined and optimized the
performance of FL in various aspects, such as model accuracy, timely execution
and energy efficiency. More specifically, in [9], a joint learning and
communication framework was proposed, in order to minimize the training loss
in the presence of packet errors, while in [10] the objective was to minimize
the total energy consumption by optimizing both the computation and
communication resources. Moreover in [11], authors focus on minimizing the
convergence time of the FL process by efficiently scheduling the participating
devices, while in [12], the convergence time was minimized by considering both
the impact of training and communication. In [13], the FL global loss function
was minimized under total convergence time constraints, by jointly allocating
the bandwidth and scheduling the users, while in [14], the impact of various
scheduling policies on the FL convergence rate was examined.

Due to communication bottleneck incurred by the limited bandwidth and the
large size of the local training parameters, gradient compression techniques,
such as quantization, have been proposed to further improve the communication
efficiency in FL [15, 16, 17]. Through this technique, a quantized version of
the local model is being transmitted to the server, aiming to achieve faster
communication without deteriorating the FL model accuracy. In this direction,
authors in [18], examined quantization schemes for the uplink and downlink
communication in FL and rigorously proved the respective convergence rate
upper bounds. In [19], a lossy FL scheme is introduced where both global and
local updates are quantized before being transmitted, while the convergence
behavior is analyzed. It is concluded that the performance loss compared to an
ideal model, is negligible. Moreover, in [20], the minimization of the
convergence bound was performed, in a multiple access channel scenario of FL,
while an efficient utilization of the quantization levels was proposed. In
[21], the quantization error was minimized subject to uplink transmission
delay and outage constraints per round, in a wireless environment. In [22],
authors proposed a one-bit quantization scheme for over-the-air FL, while they
also examined the convergence rate under fading channels.

At this point, we clarify that none of the aforementioned works [18, 19, 20,
21, 22], who applied quantization methods, focused on minimizing the total
convergence time of the FL, which is a metric of paramount importance for
meeting the low latency requirements of the next generation of wireless
networks. Regarding the works who performed optimization methods, [20] and
[21] focused on minimizing the quantization error without jointly considering
the computation, the communication resources, as well as the quantization
policy. Specifically, [20] did not consider the wireless factors, while in
[21], the local computation time and subsequently the adjustment of users’
local CPU frequency were neglected. Therefore, guarantying fast convergence
and high model accuracy of FL, when applying quantization techniques, by
efficiently utilizing the available computation, radio resources and
quantization strategy, is an issue that has not been yet resolved.
Furthermore, the trade-off among model accuracy and fast convergence, owing to
the local updates’ quantization, is not well-examined in the previous works,
where the convergence rate is mainly investigated with regards to the global
communication rounds and not the total evolution of time. Specifically, a
large number of quantization bits may increase precision, in the expense of
slow communication with the server per FL round, since the training
parameters’ size also increases and leads to higher transmission delay. On the
contrary, smaller quantization level may lead to slightly decreased model
performance, though, with lower delay per round and potentially faster
convergence. However, low precision updates may be communication efficient in
terms of latency per round, but require increased number of communication
rounds until convergence. Therefore, it is not evident that the utilization of
few quantization bits can always lead to faster convergence, with respect to
the evolution of time. The aforementioned fact is not clearly presented in the
literature and needs further investigation.

###  I-B Contributions

Driven by the aforementioned considerations, we study the quantization of the
local model parameters of each user and aim to minimize the total convergence
time of FL, under energy consumption and quantization error constraints. The
latter aims to retain the model accuracy in desirable levels. Moreover, the
considered minimization is conducted with respect to the unit of time, and not
purely the evolution of global FL rounds, since the wireless factors, the
available resources and the quantization policy affect the duration of each
round, which is critical for the evaluation of the total convergence time.

The main contributions of this paper are summarized as:

  * •

We present a rigorous convergence analysis of the FL process by considering
stochastic quantization of the local parameters. The impact of the
quantization error on the convergence bound is revealed, while useful insights
for the optimality gap are provided. Moreover, the derivation of the resulted
bound does not enforce the quantization bits to take specific values, which is
requisite for performing optimization methods subject to various constraints,
and thus, allowing the adjustment of the quantization bits accordingly.

  * •

We minimize the total convergence time of the FL across all global rounds,
subject to energy consumption and quantization error constraints. The latter
have resulted from the convergence analysis and aim to guarantee sufficiently
high precision and subsequently high model accuracy. To this end, we jointly
optimize the computation and communication resources, as well as the number of
quantization bits of each user. After some mathematical manipulations, the
resulted convex problem is solved with the Lagrange dual decomposition and
closed-form solutions are derived, in terms of the Lagrange multipliers (LMs).

  * •

Through simulations, the performance of local parameters’ quantization is
evaluated. Specifically, we investigate the impact of the quantization error
tolerance on the convergence time and model accuracy, while the trade-off
among model accuracy and fast convergence is exhibited. In addition to this,
it is shown that low precision quantization cannot always achieve fast
convergence. Moreover, numerical results validate the effectiveness of the
proposed optimization towards minimizing the convergence time, in comparison
with baseline schemes. Finally, driven by the theoretical convergence
analysis, we study the effects of decaying the quantization error tolerance
along with the evolution of the training, instead of keeping it constant. The
simulation results corroborate the effectiveness of this approach, which
demonstrates increased convergence rate without model accuracy degradation. In
essence, this observation coincides with the concept of “later-is-better”
[23], which implies that reserving FL-related resources in the early stages of
the training process and spending them in the final stages, may be beneficial
for the performance.

##  II System model

###  II-A FL model

We consider a wireless FL system, consisting of $N$ users, indexed as
$n\in\mathcal{N}=\\{1,2,...,N\\}$ and a base station (BS) co-located with a
server, while hereinafter we use the terms BS and server interchangeably. Each
user $n$, poses a local dataset
$\mathcal{D}^{\mathrm{L}}_{n}=\\{\boldsymbol{x}_{n,k},y_{n,i}\\}^{D^{\mathrm{L}}_{n}}_{k=1}$,
where $D^{\mathrm{L}}_{n}=|\mathcal{D}^{\mathrm{L}}_{n}|$,
$\boldsymbol{x}_{n,k}$ is the $k$-th input data vector of user $n$, while
$y_{n,k}$ is the corresponding output. The whole dataset is denoted as
$\mathcal{D}=\underset{n\in\mathcal{N}}{\cup}\mathcal{D}^{\mathrm{L}}_{n}$,
while the size of all training data is $D=\sum_{n=1}^{N}D^{\mathrm{L}}_{n}$.
The loss function of user $n$, is defined as [8]

$F_{n}(\boldsymbol{w})\triangleq\frac{1}{D^{\mathrm{L}}_{n}}\sum_{k\in\mathcal{D}^{\mathrm{L}}_{n}}\phi(\boldsymbol{w},\boldsymbol{x}_{n,k},y_{n,k}),\quad\forall
n\in\mathcal{N},$ (1)

where $\phi(\boldsymbol{w},\boldsymbol{x}_{n,k},y_{n,k})$ captures the error
of the $d$-dimensional model parameter $\boldsymbol{w}\in\mathbb{R}^{d}$ for
the input-output pair $\\{\boldsymbol{x}_{n,k},y_{n,k}\\}$. The goal of the
training process is to find the global parameter $\boldsymbol{w}$, which
minimizes the loss function on the whole dataset

$F(\boldsymbol{w})=\sum_{n=1}^{N}p_{n}F_{n}(\boldsymbol{w}),$ (2)

where $p_{n}=\frac{D^{\mathrm{L}}_{n}}{D}$, i.e., to find
$\boldsymbol{w}^{*}=\underset{\boldsymbol{w}}{\mathrm{argmin}}\,F(\boldsymbol{w}).$

We assume that the whole FL process consists of $T$ global rounds, denoted as
$t\in\mathcal{T}=\\{0,...,T-1\\}$. During the $t$ -th global round, each user
receives the global parameter $\boldsymbol{w}(t)$ from the server, and
performs $\tau$ steps of the stochastic gradient descent (SGD) method. The
$i$-th step of SGD, $\forall n\in\mathcal{N}$, is given as

$\boldsymbol{w}^{i}_{n}(t)=\boldsymbol{w}^{i-1}_{n}(t)-\eta(t)\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t)),\,\,i=1,...,\tau\,,$
(3)

where $\boldsymbol{w}^{0}_{n}(t)\triangleq\boldsymbol{w}(t)$. Moreover,
$\eta(t)$ represents the learning rate, while
$\boldsymbol{\xi}^{i-1}_{n}(t)\subseteq\mathcal{D}^{\mathrm{L}}_{n}$ is a
mini-batch, which is sampled uniformly at random from the local dataset
$\mathcal{D}^{\mathrm{L}}_{n}$ of user $n$. Therefore, it holds
$\mathbb{E}[\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t))]=\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t))$, where the expectation is taken with
respect to the randomness of the stochastic gradient function. Furthermore, we
assume that at the first global round, the server initializes
$\boldsymbol{w}(0)$. After terminating the local training, user $n$ transmits
the weight differential to the server, given as

$\begin{split}\Delta\boldsymbol{w}_{n}(t)&=\boldsymbol{w}^{\tau}_{n}(t)-\boldsymbol{w}^{0}_{n}(t)=\boldsymbol{w}^{\tau}_{n}(t)-\boldsymbol{w}(t)\\\
&=-\eta(t)\sum_{i=1}^{\tau}\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t)).\end{split}$
(4)

The selection of transmitting the weight differential instead of simply
transmitting the latest local weight $\boldsymbol{w}^{\tau}_{n}(t)$, is
related with the quantization scheme that will be used and discussed later on
this work. Following that, the global model at the server’s side, in round
$t$, is updated as follows

$\boldsymbol{w}(t+1)=\boldsymbol{w}(t)+\sum_{n=1}^{N}p_{n}\Delta\boldsymbol{w}_{n}(t).$
(5)

At last, the global model is broadcast to the devices, while the whole process
is repeated for $T$ rounds, until the convergence of the global model.

###  II-B Quantization model

As mentioned previously, at time step $t$, each user $n\in\mathcal{N}$
calculates its local model $\Delta\boldsymbol{w}_{n}(t)=(\Delta
w_{n,1}(t),...,\Delta w_{n,d}(t))^{\top}$. In order to prevent a wasteful
overuse of resources, we assume that users send to the server a quantized
version of $\Delta\boldsymbol{w}_{n}(t)$, which is denoted as
$Q(\Delta\boldsymbol{w}_{n}(t))$, where $Q(\cdot)$ denotes the quantization
function. Therefore, the global model update at the server, is actually given
as

$\boldsymbol{w}(t+1)=\boldsymbol{w}(t)+\sum_{n=1}^{N}p_{n}Q(\Delta\boldsymbol{w}_{n}(t)).\vspace{0.2cm}$
(6)

We also highlight that in [18] it was shown that by transmitting the weight
differential $\Delta\boldsymbol{w}_{n}(t)$, a faster convergence is achieved,
while it is also adopted in our work. Following that, for each element
$j\in\\{1,2,...,d\\}$ of $\Delta\boldsymbol{w}_{n}(t)$, it holds $|\Delta
w_{n,j}(t)|\in[\Delta w^{\mathrm{min}}_{n}(t),\Delta
w^{\mathrm{max}}_{n}(t)]$, where $\Delta
w^{\mathrm{min}}_{n}(t)\triangleq\mathrm{min}\\{|\Delta\boldsymbol{w}_{n}(t)|\\}$
and $\Delta
w^{\mathrm{max}}_{n}(t)\triangleq\mathrm{max}\\{|\Delta\boldsymbol{w}_{n}(t)|\\}$.
Moreover, we assume that $\Delta w_{n,j}(t)$ is quantized according to the
stochastic quantization method [18]. That is, with $B_{n}(t)$ quantization
bits, user $n$ can divide the interval $[\Delta w^{\mathrm{min}}_{n}(t),\Delta
w^{\mathrm{max}}_{n}(t)]$ into the following $\varsigma$ intervals:
$I_{1}=[s_{0},s_{1}],\,I_{2}=[s_{1},s_{2}],...,I_{\varsigma}=[s_{\varsigma-1},s_{\varsigma}]$,
where $\varsigma=2^{B_{n}(t)}-1$ and

$s_{k}=\Delta w^{\mathrm{min}}_{n}(t)+k\frac{\Delta
w^{\mathrm{max}}_{n}(t)-\Delta w^{\mathrm{min}}_{n}(t)}{2^{B_{n}(t)}-1},$ (7)

where $k=0,1,...,2^{B_{n}(t)}-1.$ Therefore, if the parameter $\Delta
w_{n,j}(t)$ falls into the interval $I_{k}$, it will be quantized as

$Q(\Delta w_{n,j}(t))=\begin{cases}s_{k-1}\cdot\mathrm{sign}(\Delta
w_{n,j}(t)),\quad\mathrm{w.p.}\,\tfrac{s_{k}-|\Delta
w_{n,j}(t)|}{s_{k}-s_{k-1}}\\\ s_{k}\cdot\mathrm{sign}(\Delta
w_{n,j}(t)),\quad\mathrm{w.p.}\,\tfrac{|\Delta
w_{n,j}(t)|-s_{k-1}}{s_{k}-s_{k-1}}\end{cases}$ (8)

where w.p. stands for “with probability”. Furthermore, the overall
$d$-dimensional quantized local model is denoted as

$Q(\Delta\boldsymbol{w}_{n}(t))=(Q(\Delta w_{n,1}(t)),...,Q(\Delta
w_{n,d}(t)))^{\top},\quad\forall n,t.$ (9)

while its size is given by

$S_{n}(t)=d(B_{n}(t)+1)+m\quad\mathrm{(bits)},$ (10)

since each element of the quantized model vector is represented by $B_{n}(t)$
bits plus one bit for the sign specification. Furthermore, $m$ bits are needed
to specify the values of $\Delta w^{\mathrm{max}}_{n}(t)$ and $\Delta
w^{\mathrm{min}}_{n}(t)$.

Figure 1: Federated learning with local model quantization.

###  II-C Computation and Communication model

During the $t$-th global round, the server is broadcasting the global model
$\boldsymbol{w}(t)$ to all users. We consider that the downlink transmission
latency is negligible, since the transmit power of the BS is much larger than
that of the devices, while also the same message is broadcast to all users. In
addition to this, we assume that the downlink is error-free, i.e., all users
correctly receive the global model updates. In the continue, for ease of
presentation, we slightly abuse the notation by dropping $t$, while the
following expressions could refer to any arbitrary round. The dedicated time
for local computations by each device $n$, for $\tau$ SGD steps, in order to
generate the local model, is given as

$l^{\mathrm{c}}_{n}=\tau\frac{c_{n}D_{n}}{f_{n}},\quad\forall
n\in\mathcal{N},$ (11)

where $f_{n}$ is the CPU cycle frequency of user $n$, $D_{n}$ is the size of
the mini-batch (in bits), while $c_{n}$ denotes the number of CPU cycles for
user $n$ to perform one sample of data during the local model training. The
corresponding energy consumption for the local computations, is given as

$E^{\mathrm{c}}_{n}=\tau\zeta c_{n}D_{n}f^{2}_{n},\quad\forall
n\in\mathcal{N},\vspace{0.1cm}$ (12)

where $\zeta$ is a constant parameter related with the hardware architecture
of device $n$.

Following the local training, each device uploads the quantized training
parameters, $Q(\Delta\boldsymbol{w}_{n}(t))$, to the BS. Similarly to [24], we
assume that the considered transmission is carried out via time-division
multiple access (TDMA), while this choice is not restrictive, since other
schemes such as frequency-division multiple access (FDMA) can also be applied.
To successfully upload the training parameters within $l^{\mathrm{up}}_{n}$
uplink time duration, the $n$-th user should satisfy the condition

$l^{\mathrm{up}}_{n}W\log_{2}\left(1+\frac{g_{n}E_{n}}{l^{\mathrm{up}}_{n}WN_{0}}\right)\geq
S_{n},\quad\forall n\in\mathcal{N},\vspace{0.1cm}$ (13)

where $W$ is the available bandwidth, $E_{n}$ is the transmit energy, $S_{n}$
is the size of the quantized training parameters and $N_{0}$ is the power of
the additive white Gaussian noise (AWGN). Moreover,
$g_{n}=|h_{n}|^{2}d_{n}^{-\beta}$ denotes the channel gain, where the complex
random variable $h_{n}\sim\mathcal{CN}(0,1)$ is the small scale fading,
$d_{n}$ is the distance between user $n$ and the BS and $\beta$ is the path
loss exponent. Moreover, we assume that the channel gain is quasi-static and
stays unchanged during a global round, while we also consider perfect CSI both
in BS’s and users’ side. Following that, we assume that the parameter
transmission phase begins after the termination of the local computations
phase by each user. Therefore, for the local computation duration
$l^{\mathrm{c}}$, it holds that

$l^{\mathrm{c}}\geq
l^{\mathrm{c}}_{n}=\tau\frac{c_{n}D_{n}}{f_{n}},\quad\forall n\in\mathcal{N}.$
(14)

Since all users should terminate the computation and uplink transmission
phases, so as the server can receive each local model and subsequently update
the global model, the total duration of a FL global round is given as

$l^{\mathrm{r}}=l^{\mathrm{c}}+\sum_{n=1}^{N}l^{\mathrm{up}}_{n},$ (15)

which is the sum of the computation latency and the transmission latency among
all users and is depicted in Fig. 2.

Figure 2: Duration of a global FL round.

##  III Convergence Analysis

In this section we investigate the convergence behavior of FL with stochastic
quantization ans stochastic gradient function. Firstly, with regards to the
stochastic quantization scheme, we proceed to the formulation of the following
lemma:

###### Lemma 1

$Q(\Delta\boldsymbol{w}_{n}(t))$ is an unbiased estimator of
$\Delta\boldsymbol{w}_{n}(t)$, i.e.,

$\mathbb{E}\left[Q(\Delta\boldsymbol{w}_{n}(t))\right]=\Delta\boldsymbol{w}_{n}(t),$
(16)

while it also holds that

$\mathbb{E}\left[\left\lVert
Q(\Delta\boldsymbol{w}_{n}(t))-\Delta\boldsymbol{w}_{n}(t)\right\rVert_{2}^{2}\right]\leq\frac{\delta^{2}_{n}(t)}{\left(2^{B_{n}(t)}-1\right)^{2}}\triangleq
J^{2}_{n}(t),$ (17)

where $\delta_{n}(t)\triangleq\sqrt{\frac{d}{4}\left(\Delta
w^{\mathrm{max}}_{n}(t)-\Delta w^{\mathrm{min}}_{n}(t)\right)^{2}}$.

###### Proof:

The proof can be found in [18],[21]. ∎

Next, we make the following common assumptions for the functions
$F_{1},F_{2},...,F_{N}$, in order to facilitate the convergence analysis [25]:

###### Assumption 1

$F_{n},\,\forall n\in\mathcal{N},$ are all L-smooth, i.e.,
$\forall\boldsymbol{w}^{\prime},\boldsymbol{w}\in\mathbb{R}^{d}$:
$F_{n}(\boldsymbol{w}^{\prime})\leq
F_{n}(\boldsymbol{w})+\langle\boldsymbol{w}^{\prime}-\boldsymbol{w},\nabla
F_{n}(\boldsymbol{w})\rangle+\frac{L}{2}\left\lVert\boldsymbol{w}^{\prime}-\boldsymbol{w}\right\rVert_{2}^{2}$.

###### Assumption 2

$F_{n},\,\forall n\in\mathcal{N},$ are all $\mu$-strongly convex, i.e.,
$\forall\boldsymbol{w}^{\prime},\boldsymbol{w}\in\mathbb{R}^{d}$:
$F_{n}(\boldsymbol{w}^{\prime})\geq
F_{n}(\boldsymbol{w})+\langle\boldsymbol{w}^{\prime}-\boldsymbol{w},\nabla
F_{n}(\boldsymbol{w})\rangle+\frac{\mu}{2}\left\lVert\boldsymbol{w}^{\prime}-\boldsymbol{w}\right\rVert_{2}^{2}$.

###### Assumption 3

The expected squared norm of stochastic gradients is uniformly bounded
$\forall n,t,i$, i.e., $\mathbb{E}\left[\left\lVert\nabla
F_{n}(\boldsymbol{w}^{i}_{n}(t),\boldsymbol{\xi}^{i}_{n}(t))\right\rVert_{2}^{2}\right]\leq
G^{2}$.

###### Assumption 4

The variance of stochastic gradients in each user is bounded $\forall n,t,i$,
i.e., $\mathbb{E}\left[\left\lVert\nabla
F_{n}(\boldsymbol{w}^{i}_{n}(t),\boldsymbol{\xi}^{i}_{n}(t)-\nabla
F_{n}(\boldsymbol{w}^{i}_{n}(t))\right\rVert_{2}^{2}\right]\leq\sigma^{2}_{n}$.

Moreover, we define $\Gamma\triangleq
F(\boldsymbol{w}^{*})-\sum_{n=1}^{N}p_{n}F^{*}_{n}$, where $F^{*}_{n}$ denotes
the minimum value of $F_{n}(\cdot)$, while $\Gamma$ quantifies the degree of
NON-IID, among users’ datasets. Taking these into account, we introduce the
following theorem:

###### Theorem 1

Let Assumptions 1 to 4 hold. By selecting a diminishing learning rate
$\eta(t)=\frac{2}{\mu(\gamma+t)}$ and
$\gamma>\mathrm{max}\big{\\{}2,\frac{2}{\mu},\frac{L}{\mu}\big{\\}}$, the
upper bound of
$\mathbb{E}\left[F(\boldsymbol{w}(T))-F(\boldsymbol{w}^{*})\right]$ is given
by

$\begin{split}&\mathbb{E}\left[F(\boldsymbol{w}(T))\right]-F(\boldsymbol{w}^{*})\leq\\\\[2.0pt]
&\qquad\quad\frac{L}{2}\frac{1}{\gamma+T}\left(\frac{4U}{\mu^{2}}+\gamma\mathbb{E}\left[\left\lVert\boldsymbol{w}(0)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\right)\\\\[5.0pt]
&\qquad+\underbrace{\frac{L}{2}\sum_{j=0}^{T-1}\Bigg{[}\sum_{n=1}^{N}p_{n}\frac{\delta^{2}_{n}(j)}{\left(2^{B_{n}(j)}-1\right)^{2}}\prod_{i=j+1}^{T-1}\left(1-\frac{2}{\gamma+i}\right)\Bigg{]}}_{\text{Impact
of the quantization error on the convergence}},\end{split}$ (18)

where

$U=\tau^{2}\sum_{n=1}^{N}\sigma^{2}_{n}+\tau
G^{2}+2L\tau^{2}\Gamma+(\mu+2)\frac{\tau(\tau-1)(2\tau-1)}{6}G^{2},$ (19)

while the expectation is taken with respect to the stochastic gradient
function and the stochastic quantization scheme.

###### Proof:

See Appendix A. ∎

As one can observe, for large $T$, the first term of the upper bound tends to
zero. However, the second term which is related with the quantization error,
creates a gap between $\mathbb{E}\left[F(\boldsymbol{w}(T))\right]$ and
$F(\boldsymbol{w}^{*})$. Inspired by [19], we present the following
interesting comment. For small $j$, the term
$\prod_{i=j+1}^{T-1}\left(1-\frac{2}{\gamma+i}\right)$ tends to zero, since
$1-\frac{2}{\gamma+i}<1$, $\forall i$. Therefore, the effect of the
quantization error in the early stages of the training process vanishes over
time. Hence, it is discernible that during the early training rounds, the
quantization error would not contribute in increasing the optimality gap.
Nevertheless, in order to further mitigate the impact of the quantization
error, an increased number of quantization bits $B_{n}$ may be selected.
However, such choice may result to increased latency during the local
parameter transmission phase, while the considered trade-off is studied later.
Finally, note that when $B_{n}(j)\rightarrow\infty,\,\forall n,j$, the
optimality gap is zero and the convergence bound of Theorem 1 coincides with
that of a lossless FL model.

At this point, it should be highlighted that in the convergence analysis of
[18], where a stochastic quantization scheme was also considered, authors
concluded that the quantization error does not create an optimality gap, i.e.,
$\mathbb{E}\left[F(\boldsymbol{w}(T))-F(\boldsymbol{w}^{*})\right]$ tends
asymptotically to zero. However, in their analysis, they selected specific
values for the quantization bits $B_{n}(t)$, given as a function of the
learning rate $\eta(t)$. In opposition to this, in our analysis we do not
restrict $B_{n}(t)$ to take certain values. In this manner, the values of
$B_{n}(t)$ are not being enforced by $\eta(t)$. This fact is of significant
importance, since the constraints imposed by the wireless environment, could
affect the selection of $B_{n}(t)$, i.e., it cannot be always feasible or
communication efficient to pre-assign specific values to $B_{n}(t)$ based on
the learning rate. The constraints on $B_{n}(t)$, would be obvious through the
optimization problem that is formulated in the subsequent section.

##  IV Convergence Time Minimization

###  IV-A Problem Formulation

Our objective goal is to minimize the total convergence time of the FL task,
i.e., the overall latency across all FL rounds, under energy and quantization
error constraints, with the latter aiming to retain the optimality gap of the
upper bound of
$\mathbb{E}\left[F(\boldsymbol{w}(T))\right]-F(\boldsymbol{w}^{*})$, at small
levels. Note that the upper bound is affected by the quantization error
through the term
$\sum_{n=1}^{N}p_{n}\frac{\delta^{2}_{n}(t)}{\left(2^{B_{n}(t)}-1\right)^{2}}$,
as concluded in Theorem 1. Therefore, it is obvious that by increasing the
number of quantization bits $B_{n}(t)$, the quantization error decreases.
However, this strategy increases the size $S_{n}(t)$ of the local model
parameters and thus, may result in increased transmission latency. Taking this
into account, it is important to balance the considered trade-off, among model
accuracy and fast convergence. Hence, we formulate the following optimization
problem

$\displaystyle\underset{l^{\mathrm{c}},\boldsymbol{E},\boldsymbol{B},\boldsymbol{f},\boldsymbol{l}^{\mathrm{up}}}{\text{min}}\quad\text{\emph{{$\sum_{t=0}^{T-1}l^{\mathrm{r}}(t)$}}}$
(20)
$\displaystyle\textbf{\emph{s.t.}}\quad\mathrm{C}_{1}:l^{\mathrm{up}}_{n}(t)W\log_{2}\left(1+\frac{g_{n}(t)E_{n}(t)}{l^{\mathrm{up}}_{n}(t)WN_{0}}\right)$
$\displaystyle\qquad\qquad\geq d(B_{n}(t)+1)+m,\quad\forall
n\in\mathcal{N},\forall t,$ $\displaystyle\qquad\mathrm{C}_{2}:\tau\zeta
c_{n}D_{n}f^{2}_{n}(t)+E_{n}(t)\leq E^{\mathrm{max}}_{n}(t),\,\,\forall
n\in\mathcal{N},\forall t,$
$\displaystyle\qquad\mathrm{C}_{3}:\sum_{n=1}^{N}p_{n}\frac{\delta^{2}_{n}(t)}{\left(2^{B_{n}(t)}-1\right)^{2}}\leq\epsilon(t),\quad\forall
t,$
$\displaystyle\qquad\mathrm{C}_{4}:l^{\mathrm{c}}(t)\geq\tau\frac{c_{n}D_{n}}{f_{n}(t)},\quad\forall
n\in\mathcal{N},\quad\forall t,$ $\displaystyle\qquad\mathrm{C}_{5}:0\leq
f_{n}(t)\leq f^{\mathrm{max}}_{n}(t),\quad
B_{n}(t)\in\mathbb{Z}_{+},\quad\forall t,$

where $\mathrm{C}_{1}$ is related with the successful transmission of the
local training parameters, $\mathrm{C}_{2}$ indicates that the dedicated
energy both for computation and transmission purposes, cannot exceed the
maximum available energy of the $n$-th user at the $t$-th round, i.e.,
$E^{\mathrm{max}}_{n}(t)$. Moreover, $\mathrm{C}_{3}$ implies that the
quantization error should not exceed a required tolerance, $\epsilon(t)$, at
the respective round. We also clarify that it is reasonable to constrain the
quantization error per global FL round $t$, since there is no coupling of the
error among different global rounds, as observed in (18). Finally,
$\mathrm{C}_{4}$ stems from (14), while $f^{\mathrm{max}}_{n}$ denotes the
maximum CPU clock speed of user $n$. Also, note that the quantization bits
$B_{n}(t)$ are positive integers. Moreover, we highlight that the selection of
increased number of bits $B_{n}(t)$, leads to better model precision, which is
reflected in $\mathrm{C}_{3}$ through the selection of the error tolerance
$\epsilon(t)$. However, it is observed from $\mathrm{C}_{1}$ that such policy
also increases the transmission delay and subsequently the total convergence
time.

###  IV-B Proposed Solution

It should be highlighted that problem (20) is intractable in the current
formulation, since at the $t$-th round the channel gains
$g(t^{\prime}),\,\forall t^{\prime}>t$ are unknown. However, this is not
restricting, since we can address this issue by solving the problem round-by-
round, in an online fashion. In addition to this, we relax
$B_{n}\in\mathbb{Z}_{+}$ to $B_{n}\geq 1,\,\forall n\in\mathcal{N}$. Thus, the
problem in (20) should be solved in each global round, while hereinafter the
$t$ notation is dropped for simplicity.

Next, by observing that $\mathrm{C}_{4}$ is equivalent to:
$f_{n}\geq\tau\frac{c_{n}D_{n}}{l^{\mathrm{c}}},\,\forall n\in\mathcal{N}$, we
introduce the following proposition:

###### Proposition 1

The optimal $f_{n},\forall n\in\mathcal{N}$, satisfy

$f^{*}_{n}=\tau\frac{c_{n}D_{n}}{l^{\mathrm{c}*}},\quad\forall
n\in\mathcal{N},$ (21)

with $l^{\mathrm{c*}}\geq
a_{1}\triangleq\underset{n\in\mathcal{N}}{\mathrm{max}}\left\\{\frac{\tau
c_{n}D_{n}}{f^{\mathrm{max}}_{n}}\right\\}$.

###### Proof:

Firstly, by manipulating $\mathrm{C}_{4}$, it is straightforward to show that
$l^{\mathrm{c}}\geq a_{1}$. Following that, let consider a known
$\bar{l^{\mathrm{c}}}$. By observing $\mathrm{C}_{2}$, it is obvious that the
selection of larger $f_{n}$ decreases the value of $E_{n}$. Moreover, it easy
to verify that
$l^{\mathrm{up}}_{n}W\log_{2}\left(1+\frac{g_{n}E_{n}}{l^{\mathrm{up}}_{n}WN_{0}}\right)$
in $\mathrm{C}_{1}$, is an increasing function w.r.t. both $E_{n}$ and
$l^{\mathrm{up}}_{n}$. Therefore, the selection of smaller $E_{n}$ will lead
to increased $l^{\mathrm{up}}_{n}$, while the objective is to minimize
$l^{\mathrm{up}}_{n}$. From the aforementioned, $f_{n}$ should be selected as
small as possible, given the local computation duration, concluding to (21). ∎

Proposition 1 implies that the CPU clock speed $f_{n}$ should be selected in
such way that all users terminate the computation phase concurrently. By
exploiting Proposition 1, the problem can be re-written as

$\displaystyle\underset{l^{\mathrm{c}},\boldsymbol{E},\boldsymbol{B},\boldsymbol{l}^{\mathrm{up}}}{\text{min}}\quad\text{\emph{{$l^{\mathrm{c}}+\sum_{n=1}^{N}l^{\mathrm{up}}_{n}$}}}$
(22)
$\displaystyle\textbf{\emph{s.t.}}\quad\mathrm{C}_{1}:l^{\mathrm{up}}_{n}W\log_{2}\left(1+\frac{g_{n}E_{n}}{l^{\mathrm{up}}_{n}WN_{0}}\right)$
$\displaystyle\qquad\qquad\geq d(B_{n}+1)+m,\quad\forall n\in\mathcal{N},$
$\displaystyle\qquad\mathrm{C}_{2}:\frac{\zeta\tau^{3}c^{3}_{n}D^{3}_{n}}{{l^{\mathrm{c}}}^{2}}+E_{n}\leq
E^{\mathrm{max}}_{n},\quad\forall n\in\mathcal{N},$
$\displaystyle\qquad\mathrm{C}_{3}:\sum_{n=1}^{N}p_{n}\frac{\delta^{2}_{n}}{\left(2^{B_{n}}-1\right)^{2}}\leq\epsilon,$
$\displaystyle\qquad\mathrm{C}_{4}:l^{\mathrm{c}}\geq a_{1},\quad
E_{n},l^{\mathrm{up}}_{n}\geq 0,\,\forall n\in\mathcal{N},$
$\displaystyle\qquad\mathrm{C}_{5}:B_{n}\geq 1,\,\forall n\in\mathcal{N}.$

It can be easily shown that the problem in (22) is jointly convex w.r.t. all
the considered variables, while the proof is omitted due to space limitations.

The problem in (22) will be solved via the Lagrange dual decomposition.
Firstly, the Lagrangian function can be written as

$\begin{split}&\mathcal{L}(l^{\mathrm{c}},\boldsymbol{l}^{\mathrm{up}},\boldsymbol{E},\boldsymbol{B},\boldsymbol{\lambda})=l^{\mathrm{c}}+\sum_{n=1}^{N}l^{\mathrm{up}}_{n}\\\
&\quad+\sum_{n=1}^{N}\lambda_{1,n}\left(d(B_{n}+1)+m-l^{\mathrm{up}}_{n}W\log_{2}\left(1+\tfrac{g_{n}E_{n}}{l^{\mathrm{up}}_{n}WN_{0}}\right)\right)\\\
&\quad+\sum_{n=1}^{N}\lambda_{2,n}\left(\frac{\zeta\tau^{3}c^{3}_{n}D^{3}_{n}}{{l^{\mathrm{c}}}^{2}}+E_{n}-E^{\mathrm{max}}_{n}\right)\\\
&\quad+\lambda_{3}\left(\sum_{n=1}^{N}p_{n}\frac{\delta^{2}_{n}}{\left(2^{B_{n}}-1\right)^{2}}-\epsilon\right)+\lambda_{4}(a_{1}-l^{\mathrm{c}})\\\
&\quad+\sum_{n=1}^{N}\lambda_{5,n}(1-B_{n}),\end{split}$ (23)

where
$\boldsymbol{\lambda}=(\lambda_{1,1},...,\lambda_{2,1},...,\lambda_{5,N})\geq
0$ (’$\geq$’ denotes the component-wise inequality) is the LM vector and
$\lambda_{1,n},\lambda_{2,n},\lambda_{3},\lambda_{4},\lambda_{5,n},\,\forall
n\in\mathcal{N}$, are associated with the constraints
$\mathrm{C}_{i},\,i=1,...,5$, respectively. Following that, the dual function
is given as

$\mathcal{G}(\boldsymbol{\lambda})=\underset{l^{\mathrm{c}},\boldsymbol{E},\boldsymbol{B},\boldsymbol{l}^{\mathrm{up}}}{\text{min}}\mathcal{L}(l^{\mathrm{c}},\boldsymbol{l}^{\mathrm{up}},\boldsymbol{E},\boldsymbol{B},\boldsymbol{\lambda}),$
(24)

while the corresponding dual problem can be written as

$\underset{\boldsymbol{\lambda}\,}{\text{max
\,}}\mathcal{G}(\boldsymbol{\lambda}).$ (25)

Since the primal problem is convex and the Slater’s conditions are satisfied,
strong duality holds, i.e., solving the dual is equivalent to solving the
primal problem [26]. According to the Karush-Kuhn-Tucker (KKT) conditions, the
optimal solution to the problem should satisfy

$\nabla\mathcal{L}(l^{\mathrm{c*}},\boldsymbol{l}^{\mathrm{up}*},\boldsymbol{E}^{*},\boldsymbol{B}^{*},\boldsymbol{\lambda}^{*})=0.$
(26)

Thus, by taking $\frac{\partial\mathcal{L}}{\partial l^{\mathrm{c}}}=0$ and
$\frac{\partial\mathcal{L}}{\partial E_{n}}=0,\,\forall n\in\mathcal{N}$,
leads to

$l^{\mathrm{c*}}=\sqrt[3]{\frac{2\zeta\tau^{3}\sum_{n=1}^{N}\lambda^{*}_{2,n}c^{3}_{n}D^{3}_{n}}{1-\lambda^{*}_{4}}},$
(27)

and

$E^{*}_{n}=l^{\mathrm{up*}}_{n}W\left(\frac{\lambda^{*}_{1,n}}{\lambda^{*}_{2,n}\ln(2)}-\frac{N_{0}}{g_{n}}\right),\,\forall
n\in\mathcal{N}.$ (28)

From (28), we observe that $\lambda^{*}_{2,n}\neq 0,\,\forall
n\in\mathcal{N}$. Taking this into account, according to the complementary
slackness conditions which require

$\lambda^{*}_{2,n}\left(\frac{\zeta\tau^{3}c^{3}_{n}D^{3}_{n}}{{l^{\mathrm{c}*}}^{2}}+E^{*}_{n}-E^{\mathrm{max}}_{n}\right)=0,\quad\forall
n\in\mathcal{N},$ (29)

the constraint $\mathrm{C}_{2}$ should be satisfied with equality [26],
leading to

$E^{*}_{n}=E^{\mathrm{max}}-\frac{\zeta\tau^{3}c^{3}_{n}D^{3}_{n}}{l^{\mathrm{c*}^{2}}},\quad\forall
n\in\mathcal{N}.$ (30)

This is reasonable, since it indicates that users should utilize their whole
available energy, towards minimizing the objective function. Following that,
$\frac{\partial\mathcal{L}}{\partial l^{\mathrm{up}}_{n}}=0,\forall
n\in\mathcal{N}$, it holds that

$\frac{W\lambda^{*}_{1,n}}{\ln(2)}\frac{-(1+\frac{b}{l^{\mathrm{up*}}_{n}})+1+(1+\frac{b}{l^{\mathrm{up*}}_{n}})\ln\left(1+\frac{b}{l^{\mathrm{up*}}_{n}}\right)}{1+\frac{b}{l^{\mathrm{up*}}_{n}}}=1,$
(31)

where $b=\frac{E^{*}_{n}g_{n}}{WN_{0}}$. The manipulation of (31), results to

$l^{\mathrm{up*}}_{n}=-\frac{g_{n}E^{*}_{n}}{WN_{0}(1+\mathcal{W}^{-1}_{0}(\psi_{n}))},\quad\forall
n\in\mathcal{N},$ (32)

where $\mathcal{W}_{0}$ is the principal branch of the Lambert W function [27]
and $\psi_{n}$ is given by

$\psi_{n}=-\frac{2^{-\frac{1}{W\lambda^{*}_{1,n}}}}{e},\quad\forall
n\in\mathcal{N}.$ (33)

Furthermore, it is easy to verify from (31) that $\lambda^{*}_{1,n}\neq
0,\,\forall n\in\mathcal{N}$, since the case $\lambda^{*}_{1,n}=0$, leads to a
contradiction. This result indicates that users should spend their resources
so as to transmit exactly $S_{n}$ bits to the server, which is observed from
the right-hand-side of $\mathrm{C}_{1}$. Thus, $\mathrm{C}_{1}$ is satisfied
with equality, yielding

$B^{*}_{n}=\frac{l^{\mathrm{up*}}_{n}W}{d}\log_{2}\left(1+\frac{g_{n}E^{*}_{n}}{l^{\mathrm{up*}}_{n}WN_{0}}\right)-\frac{m}{d}-1,\quad\forall
n\in\mathcal{N}.$ (34)

Finally, by taking $\frac{\partial\mathcal{L}}{\partial B_{n}}=0,\,\forall
n\in\mathcal{N}$, yields

$\left(2^{B^{*}_{n}}-1\right)^{3}=\frac{2\lambda^{*}_{3}\ln(2)p_{n}\delta^{2}_{n}}{d\lambda^{*}_{1,n}-\lambda^{*}_{5,n}}2^{B^{*}_{n}}.$
(35)

From (35), it is obvious that $\lambda^{*}_{3}\neq 0$, since the case
$\lambda^{*}_{3}=0$ leads to $B^{*}_{n}=0$, which is infeasible. Therefore,
also constraint $C_{3}$ is satisfied with equality.

According to the previous analysis, the optimal variables
$l^{\mathrm{c}*},\boldsymbol{E}^{*},\boldsymbol{l}^{\mathrm{up*}},\boldsymbol{B}^{*}$
have been given in closed forms, in terms of the LMs, by the equations
(27),(30),(32),(34), respectively. Note that given the LMs, each optimization
variable can be directly calculated, with the aforementioned order of
appearance, by using the respective equations. Subsequently, the LMs can be
updated iteratively via a subgradient method, while the optimal variables can
be calculated through the LMs. Note that the equations which have not been
used for calculating the primal variables, can be utilized for updating the
LMs.

Following this analysis, recall that $B_{n},\,\forall n\in\mathcal{N}$, should
finally take integer values. Therefore, after obtaining the solutions to the
problem, $B^{*}_{n}$ should be rounded to the smallest integer which is
greater or equal to $B^{*}_{n}$. Thus we set $\tilde{B}^{*}_{n}=\lceil
B^{*}_{n}\rceil$, in order to guarantee that $\mathrm{C}_{3}$ is still
satisfied, i.e., the quantization error tolerance constraint is not violated.
However, since with the selection of $B^{*}_{n}$ it was previously shown that
$\mathrm{C}_{1}$ is satisfied with equality, by plugging $\tilde{B}^{*}_{n}$
into the problem, $\mathrm{C}_{1}$ will be now violated, due to the fact that
$\tilde{B}^{*}_{n}>B^{*}_{n}$. Therefore, to address this issue, the problem
in (22) has to be solved once again for a fixed value of $\tilde{B}^{*}_{n}$,
i.e.,

$\displaystyle\underset{l^{\mathrm{c}},\boldsymbol{E},\boldsymbol{l}^{\mathrm{up}};\tilde{\boldsymbol{B}}^{*}}{\text{min}}\quad\text{\emph{{$l^{\mathrm{c}}+\sum_{n=1}^{N}l^{\mathrm{up}}_{n}$}}}$
(36)
$\displaystyle\textbf{\emph{s.t.}}\quad\mathrm{C}_{1},\mathrm{C}_{2},\mathrm{C}_{4}$

and finally the optimal variables can be obtained. It should be clarified that
(36) can be solved similarly to (22) for a fixed $\tilde{\boldsymbol{B}}^{*}$.
To this end, $\boldsymbol{f}^{*}$ is given by (21), which concludes the
overall solution to the problem.

##  V Numerical Experiments and Performance Evaluation

For the simulation results, we assume that $N=10$ users are uniformly
distributed in a circle with radius 1000m, while the server/BS is located at
the center of the circle. The rest of the simulation parameters are presented
in Table I, and retain their respective values unless specified otherwise.

TABLE I: Simulation Parameters Parameter |  Value |  Parameter |  Value
---|---|---|---
$f^{\mathrm{max}}_{n}$ |  $1.5\,\mathrm{GHz}$ |  $D_{n}$ |  1 Mbit
$W$ |  0.3 MHz |  $N_{0}$ |  -174 dBm/Hz
$\zeta$ |  $10^{-27}$ |  $c_{n}$ |  $\sim\mathcal{U}(10,40)$
$N$ |  10 users |  $d_{n}$ |  $\sim\mathcal{U}(0,1000\mathrm{m})$
$E_{n}^{\mathrm{max}}$ |  0.3 Joule |  m |  64 bits
$d$ |  23820 |  $\beta$ |  3.75

We select the FL task to be the image classification on the widely-known MNIST
dataset [28]. We assume that each user carries 200 data samples and trains a
fully-connected feed-forward neural network with a single hidden layer,
consisting of 30 nodes, while the softmax is utilized as an activation
function at the output layer. Thus, the total model parameters are $d=23860$
(i.e., $784\times 30+30\times 10=23820$ weights and $30+10=40$ biases). The
mini-batch size has been set as $|\boldsymbol{\xi}^{i}_{n}(t)|=50,\,\forall
n,i,t.$ Moreover, the Adam optimizer is utilized for the local training [29].
Following that, we consider two different cases of training data
distributions. Firstly, for the case of IID data distribution among users, the
training data is shuffled and randomly assigned to each user. Secondly, for
the non-IID scenario, the training data is sorted by labels and each user is
equipped only with 5 labels. For both cases, the datasets among users are non-
overlapping.

###  V-A Effects of the quantization error tolerance on the convergence time
and model accuracy

In Fig. 3 and Fig. 4, the testing accuracy and training loss, respectively,
are evaluated for various values of the quantization error tolerance,
$\epsilon$. Note that the proposed optimization method has been utilized in
order to extract all figures. In the considered simulations, we set $\tau=2$
local iterations for each user, while we set the total number of global
communication rounds equal to $T=225$. It should be highlighted though, that
the x axis illustrates the time in seconds, and not purely the evolution of
the global rounds. We made this choice, since for different tolerance values,
the duration of a global round also varies. In this manner, the comparison on
the convergence time between various values of $\epsilon$ can be fairly
conducted. Also, we clarify that total the training time in seconds, given the
$T$ global rounds, differs among different choices of $\epsilon$. From Fig. 3,
it is evident that for smaller $\epsilon$, higher testing accuracy is
achieved, which also approximates the performance of the lossless model, i.e.,
the FL model without applying quantization. Moreover, high values of
$\epsilon$ may lead to decreased model accuracy, e.g., when $\epsilon=5$.
Another interesting observation comes as follow. The case $\epsilon=0.1$,
demonstrates the highest convergence rate in the early stages of the training
process, which is also greater than the case $\epsilon=0.01$. This outcome is
related with the duration of each global communication round. Smaller values
of $\epsilon$, translate to the selection of more quantization bits, which in
turn result in increased transmission latency during each communication round.
More specifically, in Fig. 5, the average delay per global round and the
average number of quantization bits per user per global round are presented.
It can been seen that the case $\epsilon=0.01$ presents the highest average
delay per round, among the rest choices of $\epsilon$. Therefore, this fact
can slow down the convergence speed in the early stages of the training,
although finally the highest accuracy is achieved, owing this to the selection
of more quantization bits which guaranty high precision.

At this point, it is significant to highlight the following observation. The
cases $\epsilon=1$ and $\epsilon=5$ do not really contribute neither in model
accuracy nor in fast convergence, since they are totally outperformed by the
cases $\epsilon=0.1$ and $\epsilon=0.01$, in both aspects. Even when targeting
smaller accuracy values, the higher-$\epsilon$ cases fail to converge faster
than the cases $\epsilon=0.1$ and $\epsilon=0.01$. An interpretation of this
result is the following: The large number of communication rounds until
convergence, which occur from the low precision quantization, prevails over
the low-latency per round. Therefore, by selecting a relatively loose
quantization error tolerance, which is equivalent to utilizing a few
quantization bits, may not result in any gains or offer any benefits. This
contradicts the fact which implies that by using a small number of
quantization bits, communication efficiency is always achieved.

Accordingly, in Fig. 6 and Fig. 7, the testing accuracy and training loss are
evaluated for the NON-IID scenario. For this example, we set $\tau=3$ and
$T=150$. Similar behavior in comparison with the IID case is observed, while
the model accuracy is degraded.

Figure 3: Testing accuracy versus time, for the IID scenario. Figure 4:
Training loss versus time, for the IID scenario. Figure 5: Average delay per
round and average quantization bits per user per round, for the IID scenario.
Figure 6: Testing accuracy versus time, for the NON-IID scenario. Figure 7:
Training loss versus time, for the NON-IID scenario.

###  V-B Comparison with baseline schemes

In Fig. 8, we compare the performance of the proposed optimization scheme,
with some baseline schemes. Firstly, we consider the fixed bits allocation
baseline scheme, where the same optimization method is adopted, but the number
of quantization bits is pre-assigned as $\tilde{B}_{n}=16,\,\forall
n\in\mathcal{N}$, in each global round. Moreover, the equal slots allocation
scheme also exploits the proposed optimizations’ method, however it assigns
equal duration uplink time slots to all users. Finally, the equal energy
allocation scheme assigns equal energy values for both the computation and
transmission phase, while the rest of the optimization is conducted according
to the proposed method. For the considered simulation, we set the quantization
error tolerance $\epsilon=0.01$, consider an IID scenario and set $T=225$
global rounds. By observing Fig. 8, it can be seen that all schemes
demonstrate almost identical testing accuracy, which is related with the
selected quantization error tolerance. However, it is clearly seen that the
proposed scheme dominates all baseline schemes, in terms of convergence time,
which is the objective goal of the proposed optimization. Thus, Fig. 8
highlights the significance of the proposed scheme, which jointly takes into
account the communication and computation resources, as well as the
quantization bits allocation. Also, the case of fixed bits allocation leads to
very high latency until convergence, without offering further accuracy gain.
Therefore, it is evident that when aiming towards fast convergence of the FL
process, the number of quantization bits ought to be wisely selected.

###  V-C The dynamical adjustment of quantization error tolerance

In the continue, we examine the effects of dynamically adjusting the
quantization error tolerance $\epsilon$ throughout the training process.
Recall that in Theorem 1, it was evident that in the early training stages,
the quantization error has not large impact in the optimality gap. Driven by
this fact, we now focus on decaying $\epsilon$ along with the evolution of the
global rounds, i.e., allowing higher values of tolerance in the early stages
of the training and gradually decreasing it. Specifically, we consider that
the relation between the error tolerance in the $(i+1)$-th and $i$-th global
round, is given as

$\epsilon(i+1)=r\cdot\epsilon(i),$ (37)

where $0<r<1$ is a constant, $i=1,...,223$, while we initialize
$\epsilon(0)=0.1$. By setting $r=10^{-1/224}$, it is easy to verify that
$\epsilon(224)=0.01$, i.e., $\epsilon$ is equal to 0.1 in the first round and
equal to 0.01 in the final round, given that $T=225$. Following that, in Fig.
9, we compare the performance of the considered technique, i.e., decaying
$\epsilon$, with the standard cases of a constant $\epsilon$ throughout the
training. It can be observed that by dynamically decreasing $\epsilon$, the
convergence rate is significantly increased. More specifically, in the very
early stages of the training, higher $\epsilon$ values contribute to fast
communication with the server, while along with the reduction of $\epsilon$,
the precision is gradually increased. This policy results in fast convergence
and notable performance, in comparison with the rest fixed $\epsilon$ cases
and especially with the stringent case, where $\epsilon=0.01$. Specifically,
although the testing accuracy is almost identical between the decaying
$\epsilon$ policy and the case $\epsilon=0.01$, the former converges after 22
seconds of training, while the latter after about 40 seconds. Therefore, the
effectiveness of decreasing the quantization error tolerance along with the
evolution of the training, which is equivalent to gradually increasing the
number of quantization bits throughout the training, is corroborated.

Figure 8: Comparison of the proposed scheme with baseline schemes. Figure 9:
The impact of dynamically adjusting $\epsilon$, on the convergence rate and
testing accuracy.

##  VI Conclusions

In this paper, we studied and optimized the performance of FL over wireless
networks by considering the quantization of the local model parameters. More
specifically, we have jointly optimized the communication and computation
resources, as well as the quantization bits allocation, focusing on minimizing
the total convergence time of FL subject to energy constraints and
quantization error tolerance. The optimization problem was coupled with the
convergence analysis, aiming to control the impact of the quantization error
and subsequently balance the trade-off between model accuracy and fast
convergence. Simulations are conducted, where the considered trade-off is
examined and the effectiveness of the proposed method in accelerating the
convergence speed, is verified. Also, the results indicate that the selection
of the quantization error tolerance is critical for achieving enhanced
performance in FL, while efficient techniques are presented which result in
increased convergence rate.

## Appendix A
Proof of Theorem 1

For proving Theorem 1, we adopt the methodologies of [25] and [30]. Firstly,
we define the auxiliary variable $\boldsymbol{v}(t)$ as

$\boldsymbol{v}(t+1)=\boldsymbol{w}(t)+\sum_{n=1}^{N}p_{n}\Delta\boldsymbol{w}_{n}(t),$
(38)

which represents a lossless model’s update during the $(t+1)$-th round. Recall
that

$\boldsymbol{w}(t+1)=\boldsymbol{w}(t)+\sum_{n=1}^{N}p_{n}Q(\Delta\boldsymbol{w}_{n}(t)).$
(39)

Following that, we have

$\begin{split}&\left\lVert\boldsymbol{w}(t+1)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\\\
&\qquad=\left\lVert\boldsymbol{w}(t+1)-\boldsymbol{v}(t+1)+\boldsymbol{v}(t+1)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\\\
&\qquad=\left\lVert\boldsymbol{w}(t+1)-\boldsymbol{v}(t+1)\right\rVert_{2}^{2}+\left\lVert\boldsymbol{v}(t+1)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\\\
&\qquad\quad+2\langle\boldsymbol{w}(t+1)-\boldsymbol{v}(t+1),\boldsymbol{v}(t+1)-\boldsymbol{w}^{*}\rangle.\end{split}$
(40)

In the continue, the average of the right-hand-side terms in (40) are bounded
and presented in Lemmas 2-4 respectively.

###### Lemma 2

We have

$\mathbb{E}\left[\left\lVert\boldsymbol{w}(t+1)-\boldsymbol{v}(t+1)\right\rVert_{2}^{2}\right]\leq\sum_{n=1}^{N}p_{n}J^{2}_{n}(t).$

###### Proof:

$\begin{split}&\mathbb{E}\left[\left\lVert\boldsymbol{w}(t+1)-\boldsymbol{v}(t+1)\right\rVert_{2}^{2}\right]\\\
&\qquad=\mathbb{E}\left[\left\lVert\sum_{n=1}^{N}p_{n}(Q(\Delta\boldsymbol{w}_{n}(t))-\Delta\boldsymbol{w}_{n}(t))\right\rVert_{2}^{2}\right]\\\
&\qquad\overset{(a)}{\leq}\sum_{n=1}^{N}p_{n}\mathbb{E}\left[\left\lVert(Q(\Delta\boldsymbol{w}_{n}(t))-\Delta\boldsymbol{w}_{n}(t))\right\rVert_{2}^{2}\right]\\\
&\qquad\overset{(b)}{\leq}\sum_{n=1}^{N}p_{n}J^{2}_{n}(t),\end{split}$ (41)

where (a) follows from the convexity of $\left\lVert\cdot\right\rVert_{2}^{2}$
and the fact that $\sum_{n=1}^{N}p_{n}=1$, while (b) follows from Lemma 1. ∎

###### Lemma 3

We have

$\mathbb{E}\left[\left\lVert\boldsymbol{v}(t+1)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\leq-\mu\eta(t)\mathbb{E}\left[\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]+\eta^{2}(t)U$
(42)

where

$U=\tau^{2}\sum_{n=1}^{N}\sigma^{2}_{n}+\tau
G^{2}+2L\tau^{2}\Gamma+(\mu+2)\frac{\tau(\tau-1)(2\tau-1)}{6}G^{2}.$ (43)

###### Proof:

See Appendix B. ∎

###### Lemma 4

We have

$\mathbb{E}\left[2\langle\boldsymbol{w}(t+1)-\boldsymbol{v}(t+1),\boldsymbol{v}(t+1)-\boldsymbol{w}^{*}\rangle\right]=0.$
(44)

###### Proof:

Since it holds

$\mathbb{E}\left[Q(\Delta\boldsymbol{w}_{n}(t))\right]=\Delta\boldsymbol{w}_{n}(t),$
(45)

and

$\boldsymbol{w}(t+1)-\boldsymbol{v}(t+1)=\sum_{n=1}^{N}p_{n}(Q(\Delta\boldsymbol{w}_{n}(t))-\Delta\boldsymbol{w}_{n}(t)),$
(46)

it is straightforward to conclude to (44). ∎

Following that, by combining the results in Lemmas 2-4, (40) leads to

$\begin{split}\mathbb{E}\left[\left\lVert\boldsymbol{w}(t+1)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]&\leq(1-\eta(t)\mu)\mathbb{E}\left[\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\\\
&\quad+\eta^{2}(t)U+\sum_{n=1}^{N}p_{n}J^{2}_{n}(t).\end{split}$ (47)

Let
$\Delta_{t}=\mathbb{E}\left[\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]$.
(47) can be re-written as

$\Delta_{t+1}\leq(1-\eta(t)\mu)\Delta_{t}+\eta^{2}(t)U+\sum_{n=1}^{N}p_{n}J^{2}_{n}(t).$
(48)

Next, we will show that $\Delta_{t}\leq\frac{\nu}{\gamma+t}+\Psi(t)$ where

$\Psi(x)\triangleq\sum_{j=0}^{x-1}\sum_{n=1}^{N}p_{n}J^{2}_{n}(j)\prod_{i=j+1}^{x-1}(1-\eta(i)\mu),\quad
x\geq 1,$ (49)

by selecting a diminishing learning rate $\eta(t)=\frac{\beta}{\gamma+t}$,
with $\beta\geq\frac{1}{\mu},\,\gamma\geq\beta$ such that $\eta(0)\leq 1$,
$\gamma\geq\beta\mu$ such that $\eta(0)\leq\frac{1}{\mu}$ and
$\nu\leq\mathrm{max}\left\\{\frac{\beta^{2}U}{\beta\mu-1},\gamma\Delta_{0}\right\\}$.
Also, since we required $\eta(t)\leq\frac{1}{L\tau}$, it should also hold
$\gamma\geq\frac{L}{\mu}$. Similarly to [25], via induction we have

$\begin{split}\Delta_{t+1}&\leq(1-\eta(t)\mu)\Delta_{t}+\eta^{2}(t)U+\sum_{n=1}^{N}p_{n}J^{2}_{n}(t)\\\
&\leq\left(1-\frac{\beta\mu}{\gamma+t}\right)\left(\frac{\nu}{\gamma+t}+\Psi(t)\right)+\frac{\beta^{2}U^{2}}{(\gamma+t)^{2}}\\\
&=\frac{t+\gamma-1}{(t+\gamma)^{2}}\nu+\left(\frac{\beta^{2}U^{2}}{(\gamma+t)^{2}}-\frac{\beta\mu-1}{(t+\gamma)^{2}}\nu\right)\\\
&\quad+\Psi(t+1)\\\ &\leq\frac{\nu}{t+\gamma+1}+\Psi(t+1).\end{split}$ (50)

Following that, we have

$\begin{split}\nu&\leq\mathrm{max}\left\\{\frac{\beta^{2}U}{\beta\mu-1},\gamma\Delta_{0}\right\\}\leq\frac{\beta^{2}U}{\beta\mu-1}+\gamma\Delta_{0}\\\
&\overset{\beta=\frac{2}{\mu}}{\leq}\frac{4U}{\mu^{2}}+\gamma\mathbb{E}\left[\left\lVert\boldsymbol{w}(0)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right].\\\
\end{split}$ (51)

By substituting (51) in (50) and by using the fact that $F(\cdot)$ is
L-smooth, which gives

$\begin{split}F(\boldsymbol{w}(T))-F(\boldsymbol{w}^{*})&\leq\langle\boldsymbol{w}(T)-\boldsymbol{w}^{*},\nabla
F(\boldsymbol{w}^{*})\rangle\\\
&\quad+\frac{L}{2}\left\lVert\boldsymbol{w}(T)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\\\
&\leq\frac{L}{2}\left\lVert\boldsymbol{w}(T)-\boldsymbol{w}^{*}\right\rVert_{2}^{2},\end{split}$
(52)

since $\nabla F(\boldsymbol{w}^{*})=0$, the proof of Theorem 1 is completed.

## Appendix B
Proof of Lemma 3

Firstly, we have

$\begin{split}&\mathbb{E}\left[\left\lVert\boldsymbol{v}(t+1)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\\\
&\qquad=\mathbb{E}\left[\left\lVert\boldsymbol{w}(t)+\sum_{n=1}^{N}p_{n}\Delta\boldsymbol{w}_{n}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\\\
&\qquad=\mathbb{E}\left[\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]+\underbrace{\mathbb{E}\left[\left\lVert\sum_{n=1}^{N}p_{n}\Delta\boldsymbol{w}_{n}(t)\right\rVert_{2}^{2}\right]}_{A_{1}}\\\
&\qquad\quad+\underbrace{2\mathbb{E}\left[\Big{\langle}\boldsymbol{w}(t)-\boldsymbol{w}^{*},\sum_{n=1}^{N}p_{n}\Delta\boldsymbol{w}_{n}(t)\Big{\rangle}\right]}_{A_{2}}.\end{split}$
(53)

For $A_{1}$, we have that

$\begin{split}A_{1}&=\mathbb{E}\left[\left\lVert\sum_{n=1}^{N}p_{n}\left(-\eta(t)\sum_{i=1}^{\tau}\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t))\right)\right\rVert_{2}^{2}\right]\\\
&\overset{(a)}{\leq}\eta^{2}(t)\tau\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\left\lVert\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t))\right\rVert_{2}^{2}\right]\\\
&=\eta^{2}(t)\tau\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\Big{[}\|\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t))\\\
&\quad-\nabla F_{n}(\boldsymbol{w}^{i-1}_{n}(t))+\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t))\|^{2}_{2}\Big{]}\\\
&\overset{(b)}{\leq}\eta^{2}(t)\tau\left(\tau\sum_{n=1}^{N}\sigma^{2}_{n}+\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\left\lVert\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t))\right\rVert_{2}^{2}\right]\right)\\\
&\overset{(c)}{\leq}\eta^{2}(t)\tau^{2}\sum_{n=1}^{N}\sigma^{2}_{n}\\\
&\quad+2L\eta^{2}(t)\tau\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}^{i-1}_{n}(t))-F^{*}_{n}\right],\end{split}$
(54)

where (a) follows from the convexity of
$\left\lVert\cdot\right\rVert_{2}^{2}$, (b) from Assumption 4 and
$\mathbb{E}[\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t))]=\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t))$, while (c) from the L-smoothness of
$F_{n}$, which implies that [26]:

$\left\lVert\nabla F_{n}(\boldsymbol{w}^{i-1}_{n}(t))\right\rVert_{2}^{2}\leq
2L(F_{n}(\boldsymbol{w}^{i-1}_{n}(t))-F^{*}_{n}).$ (55)

In the following we bound the last term in (53), $A_{2}$, as:

$\begin{split}&A_{2}=2\sum_{n=1}^{N}p_{n}\mathbb{E}\left[\langle\boldsymbol{w}(t)-\boldsymbol{w}^{*},\Delta\boldsymbol{w}_{n}(t)\rangle\right]\\\
&=2\eta(t)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\langle\boldsymbol{w}^{*}-\boldsymbol{w}(t),\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t))\rangle\right]\\\
&=2\eta(t)\times\\\
&\quad\Bigg{[}\underbrace{\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\langle\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t),\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t))\rangle\right]}_{B_{1}}\\\
&\,+\underbrace{\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\langle\boldsymbol{w}^{*}-\boldsymbol{w}^{i-1}_{n}(t),\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t))\rangle\right]}_{B_{2}}\Bigg{]}.\end{split}$
(56)

Next, for $B_{1}$ we have

$\begin{split}B_{1}&\overset{(a)}{\leq}\eta(t)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\Big{[}\frac{1}{\eta(t)}\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\\\
&\quad+\eta(t)\left\lVert\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t),\boldsymbol{\xi}^{i-1}_{n}(t))\right\rVert_{2}^{2}\Big{]}\\\
&\overset{(b)}{\leq}\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\right]+\eta^{2}(t)\tau
G^{2},\end{split}$ (57)

where (a) follows from the Cauchy-Schwarz inequality in combination with the
inequality

$2\left(\frac{x}{\sqrt{\eta(t)}}\right)(\sqrt{\eta(t)}y)\leq\frac{x^{2}}{\eta(t)}+\eta(t)y^{2},$
(58)

while (b) follows from Assumption 3. Next, we bound $B_{2}$ from (56) as:

$\begin{split}B_{2}&\leq
2\eta(t)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\langle\boldsymbol{w}^{*}-\boldsymbol{w}^{i-1}_{n}(t),\nabla
F_{n}(\boldsymbol{w}^{i-1}_{n}(t))\rangle\right]\\\
&\overset{(a)}{\leq}2\eta(t)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\Big{[}F_{n}(\boldsymbol{w}^{*})-F_{n}(\boldsymbol{w}^{i-1}_{n}(t))\\\
&\quad-\frac{\mu}{2}\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\Big{]},\\\
\end{split}$ (59)

where (a) follows from the $\mu$-strong convexity of $F_{n},\,\forall
n\in\mathcal{N}$. By combining (54) and (56) we conclude to

$\begin{split}A_{1}&+A_{2}\\\
&\leq\eta^{2}(t)\tau^{2}\sum_{n=1}^{N}\sigma^{2}_{n}+\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\right]\\\
&\quad+\eta^{2}(t)\tau
G^{2}-2\eta(t)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\frac{\mu}{2}\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\\\
&\quad+2L\eta^{2}(t)\tau\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}^{i-1}_{n}(t))-F^{*}_{n}\right]\\\
&\quad-2\eta(t)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}^{i-1}_{n}(t))-F_{n}(\boldsymbol{w}^{*})\right].\\\
\end{split}$ (60)

Next, we bound the last two terms in (60), which we denote as $C$. That gives

$\begin{split}C&=2L\eta^{2}(t)\tau\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}^{i-1}_{n}(t))-F^{*}_{n}\right]\\\
&\quad-2\eta(t)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}^{i-1}_{n}(t))-F_{n}(\boldsymbol{w}^{*})\right]\\\
&=-2\eta(t)(1-L\eta(t)\tau)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}^{i-1}_{n}(t))-F^{*}_{n}\right]\\\
&\quad+2\eta(t)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}^{*})-F^{*}_{n}\right].\\\
\end{split}$ (61)

We can now write $C$ as

$\begin{split}C&=-2\eta(t)(1-L\eta(t)\tau)\\\
&\quad\times\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}^{i-1}_{n}(t))-F(\boldsymbol{w}^{*})\right]\\\
&\quad+\left(2\eta(t)-2\eta(t)(1-L\eta(t)\tau)\right)\\\
&\quad\times\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F(\boldsymbol{w}^{*})-F^{*}_{n}\right]\\\
&\leq-2\eta(t)(1-L\eta(t)\tau)\\\
&\quad\times\underbrace{\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}^{i-1}_{n}(t))-F(\boldsymbol{w}^{*})\right]}_{D}\\\
&\quad+2L\eta^{2}(t)\tau^{2}\Gamma.\\\ \end{split}$ (62)

To bound $D$ from (62), we write

$\begin{split}D&\overset{(a)}{=}\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}^{i-1}_{n}(t))-F(\boldsymbol{w}(t))\right]\\\
&\quad+\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[F_{n}(\boldsymbol{w}(t))-F(\boldsymbol{w}^{*})\right]\\\
&\geq\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\langle\nabla
F_{n}(\boldsymbol{w}(t)),\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\rangle\right]\\\
&\quad+\tau\mathbb{E}\left[(F(\boldsymbol{w}(t))-F(\boldsymbol{w^{*}}))\right]\\\
&\overset{(b)}{\geq}-\frac{1}{2}\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\Big{[}\left\lVert\eta(t)\nabla
F_{n}(\boldsymbol{w}(t))\right\rVert_{2}^{2}\\\
&+\frac{1}{\eta(t)}\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\Big{]}+\tau\mathbb{E}\left[F(\boldsymbol{w}(t))-F(\boldsymbol{w}^{*})\right]\\\
&\overset{(c)}{\geq}-\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\Big{[}\eta(t)L(F_{n}(\boldsymbol{w}(t))-F(\boldsymbol{w^{*}}))\\\
&+\frac{1}{2\eta(t)}\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\Big{]}+\tau\mathbb{E}\left[F(\boldsymbol{w}(t))-F(\boldsymbol{w}^{*})\right],\\\
\end{split}$ (63)

where in (a) we have used that
$\sum_{n=1}^{N}p_{n}F_{n}(\boldsymbol{w}(t))=F(\boldsymbol{w}(t))$, (b)
follows from Cauchy-Schwarz inequality and (c) from (55). Next, by plugging
$D$ in $C$ we get

$\begin{split}C&\leq
2\eta(t)(1-L\eta(t)\tau)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\Big{[}\eta(t)L(F_{n}(\boldsymbol{w}(t))\\\
&\quad-F(\boldsymbol{w^{*}}))+\frac{1}{2\eta(t)}\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\Big{]}+2L\eta^{2}(t)\tau^{2}\Gamma\\\
&\quad-2\eta(t)(1-L\eta(t)\tau)\mathbb{E}\left[\tau(F(\boldsymbol{w}(t))-F(\boldsymbol{w^{*}}))\right]\\\
&\overset{(a)}{\leq}2L\eta^{2}(t)\tau^{2}\Gamma+\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\right],\\\
\end{split}$ (64)

where (a) holds for $\eta(t)\leq\frac{1}{\tau L}$, since
$F(\boldsymbol{w}(t))-F(\boldsymbol{w^{*}})\geq 0,\,\forall t$.

By plugging (54) and (56) in (60), yields

$\begin{split}A_{1}&+A_{2}\leq\eta^{2}(t)\tau^{2}\sum_{n=1}^{N}\sigma^{2}_{n}+\eta^{2}(t)\tau
G^{2}+2L\eta^{2}(t)\tau^{2}\Gamma\\\
&\quad+2\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\right]\\\
&\quad-\mu\eta(t)\sum_{n=1}^{N}p_{n}\sum_{i=1}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\\\
&\overset{(a)}{\leq}\eta^{2}(t)\tau^{2}\sum_{n=1}^{N}\sigma^{2}_{n}+\eta^{2}(t)\tau
G^{2}+2L\eta^{2}(t)\tau^{2}\Gamma\\\
&\quad+2\sum_{n=1}^{N}p_{n}\sum_{i=2}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\right]\\\
&\quad-\mu\eta(t)\sum_{n=1}^{N}p_{n}\sum_{i=2}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\\\
&\quad-\mu\eta(t)\mathbb{E}\left[\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right],\\\
\end{split}$ (65)

and now we have

$\begin{split}A_{1}&+A_{2}\\\
&\overset{(b)}{\leq}\eta^{2}(t)\tau^{2}\sum_{n=1}^{N}\sigma^{2}_{n}+\eta^{2}(t)\tau
G^{2}+2L\eta^{2}(t)\tau^{2}\Gamma\\\
&\quad+2\sum_{n=1}^{N}p_{n}\sum_{i=2}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\right]\\\
&\quad+\mu\eta(t)(1-\eta(t))\Bigg{(}-(\tau-1)\mathbb{E}\left[\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\\\
&\quad+\frac{1}{\eta(t)}\sum_{n=1}^{N}p_{n}\sum_{i=2}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\right]\Bigg{)}\\\
&\quad-\mu\eta(t)\mathbb{E}\left[\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right],\\\
\end{split}$ (66)

where in (a) we used that
$\boldsymbol{w}^{0}_{n}(t)\triangleq\boldsymbol{w}(t)$, while (b) follows from
the fact that:

$\begin{split}-&\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\\\
&=-\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}-\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\\\
&\quad-2\langle\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t),\boldsymbol{w}(t)-\boldsymbol{w}^{*}\rangle\\\
&\overset{(c)}{\leq}-\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}-\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\\\
&\quad+\frac{1}{\eta(t)}\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}+\eta(t)\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\\\
&=\left(\frac{1}{\eta(t)}-1\right)\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\\\
&\quad-(1-\eta(t))\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2},\end{split}$
(67)

where (c) follows from Cauchy-Schwarz inequality, compined with the inequality
in (58). By further expanding (66), we get

$\begin{split}A_{1}&+A_{2}\\\
&\leq\eta^{2}(t)\tau^{2}\sum_{n=1}^{N}\sigma^{2}_{n}+\eta^{2}(t)\tau
G^{2}+2L\eta^{2}(t)\tau^{2}\Gamma\\\
&\quad-\mu\eta(t)(\tau-\eta(t)(\tau-1))\mathbb{E}\left[\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\\\
&\quad+(2+\mu-\mu\eta(t))\sum_{n=1}^{N}p_{n}\sum_{i=2}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\right],\\\
&\overset{(a)}{\leq}\eta^{2}(t)\tau^{2}\sum_{n=1}^{N}\sigma^{2}_{n}+\eta^{2}(t)\tau
G^{2}+2L\eta^{2}(t)\tau^{2}\Gamma\\\
&\quad-\mu\eta(t)\mathbb{E}\left[\left\lVert\boldsymbol{w}(t)-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\right]\\\
&\quad+(2+\mu)\sum_{n=1}^{N}p_{n}\sum_{i=2}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\right],\\\
\end{split}$ (68)

where in (a) we have used that $0<\eta(t)\leq 1$, which also implies that
$\tau-\eta(t)(\tau-1)\geq 1$. Finally, the last term in (68), can be bounded
as follows:

$\begin{split}&\sum_{n=1}^{N}p_{n}\sum_{i=2}^{\tau}\mathbb{E}\left[\left\lVert\boldsymbol{w}^{i-1}_{n}(t)-\boldsymbol{w}(t)\right\rVert_{2}^{2}\right]\\\
&\qquad=\eta^{2}(t)\sum_{n=1}^{N}p_{n}\sum_{i=2}^{\tau}\mathbb{E}\left[\left\lVert\sum_{j=1}^{i}\nabla
F_{n}(\boldsymbol{w}^{j-1}_{n}(t),\boldsymbol{\xi}^{j-1}_{n}(t))\right\rVert_{2}^{2}\right]\\\
&\qquad\overset{(a)}{\leq}\eta^{2}(t)\sum_{i=2}^{\tau}i^{2}G^{2}=\eta^{2}(t)\frac{\tau(\tau-1)(2\tau-1)}{6}G^{2},\end{split}$
(69)

where (a) follows from the convexity of $\left\lVert\cdot\right\rVert_{2}^{2}$
and Assumption 3. By substituting (69) in (68), the proof of Lemma 3 is
completed.

## References

  * [1] K. B. Letaief, W. Chen, Y. Shi, J. Zhang, and Y. A. Zhang, “The roadmap to 6G: AI empowered wireless networks,” _IEEE Commun. Mag._ , vol. 57, no. 8, pp. 84–90, 2019.
  * [2] Y. Sun, M. Peng, Y. Zhou, Y. Huang, and S. Mao, “Application of machine learning in wireless networks: Key techniques and open issues,” _IEEE Commun. Surveys Tuts._ , vol. 21, no. 4, pp. 3072–3108, 2019.
  * [3] J. Konečnỳ, H. B. McMahan, D. Ramage, and P. Richtárik, “Federated optimization: Distributed machine learning for on-device intelligence,” _arXiv preprint arXiv:1610.02527_ , 2016.
  * [4] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [5] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” _IEEE Signal Process. Mag._ , vol. 37, no. 3, pp. 50–60, 2020.
  * [6] P. S. Bouzinis, P. D. Diamantoulakis, and G. K. Karagiannidis, “Wireless federated learning (WFL) for 6G networks - Part I: Research challenges and future trends,” _IEEE Commun. Lett._ , pp. 1–1, 2021.
  * [7] ——, “Wireless federated learning (WFL) for 6G networks - Part II: The compute-then-transmit NOMA paradigm,” _IEEE Commun. Lett._ , vol. 26, no. 1, pp. 8–12, 2022.
  * [8] W. Y. B. Lim, N. C. Luong, D. T. Hoang, Y. Jiao, Y.-C. Liang, Q. Yang, D. Niyato, and C. Miao, “Federated learning in mobile edge networks: A comprehensive survey,” _IEEE Commun. Surveys Tuts._ , vol. 22, no. 3, pp. 2031–2063, 2020.
  * [9] M. Chen, Z. Yang, W. Saad, C. Yin, H. V. Poor, and S. Cui, “A joint learning and communications framework for federated learning over wireless networks,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 1, pp. 269–283, 2020.
  * [10] Z. Yang, M. Chen, W. Saad, C. S. Hong, and M. Shikh-Bahaei, “Energy efficient federated learning over wireless communication networks,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 3, pp. 1935–1949, 2020.
  * [11] M. Chen, H. V. Poor, W. Saad, and S. Cui, “Convergence time optimization for federated learning over wireless networks,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 4, pp. 2457–2471, 2020.
  * [12] S. Wan, J. Lu, P. Fan, Y. Shao, C. Peng, and K. B. Letaief, “Convergence analysis and system design for federated learning over wireless networks,” _IEEE J. Sel. Areas Commun._ , vol. 39, no. 12, pp. 3622–3639, 2021.
  * [13] W. Shi, S. Zhou, Z. Niu, M. Jiang, and L. Geng, “Joint device scheduling and resource allocation for latency constrained wireless federated learning,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 1, pp. 453–467, 2020.
  * [14] H. H. Yang, Z. Liu, T. Q. Quek, and H. V. Poor, “Scheduling policies for federated learning in wireless networks,” _IEEE Trans. on Commun._ , vol. 68, no. 1, pp. 317–333, 2019.
  * [15] J. Konečnỳ, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” _arXiv preprint arXiv:1610.05492_ , 2016.
  * [16] A. Reisizadeh, A. Mokhtari, H. Hassani, A. Jadbabaie, and R. Pedarsani, “FedPAQ: A communication-efficient federated learning method with periodic averaging and quantization,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2020, pp. 2021–2031.
  * [17] S. Caldas, J. Konečny, H. B. McMahan, and A. Talwalkar, “Expanding the reach of federated learning by reducing client resource requirements,” _arXiv preprint arXiv:1812.07210_ , 2018.
  * [18] S. Zheng, C. Shen, and X. Chen, “Design and analysis of uplink and downlink communications for federated learning,” _IEEE J. Sel. Areas Commun._ , 2020\.
  * [19] M. M. Amiri, D. Gunduz, S. R. Kulkarni, and H. V. Poor, “Federated learning with quantized global model updates,” _arXiv preprint arXiv:2006.10672_ , 2020.
  * [20] W.-T. Chang and R. Tandon, “Communication efficient federated learning over multiple access channels,” _arXiv preprint arXiv:2001.08737_ , 2020.
  * [21] Y. Wang, Y. Xu, Q. Shi, and T.-H. Chang, “Quantized federated learning under transmission delay and outage constraints,” _IEEE J. on Sel. Areas in Commun._ , vol. 40, no. 1, pp. 323–341, 2022.
  * [22] G. Zhu, Y. Du, D. Gündüz, and K. Huang, “One-bit over-the-air aggregation for communication-efficient federated edge learning: Design and convergence analysis,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 3, pp. 2120–2135, 2020.
  * [23] C. Shen, J. Xu, S. Zheng, and X. Chen, “Resource rationing for wireless federated learning: Concept, benefits, and challenges,” _IEEE Commun. Mag._ , vol. 59, no. 5, pp. 82–87, 2021.
  * [24] N. H. Tran, W. Bao, A. Zomaya, M. N. Nguyen, and C. S. Hong, “Federated learning over wireless networks: Optimization model design and analysis,” in _IEEE INFOCOM 2019-IEEE Conference on Computer Communications_. IEEE, 2019, pp. 1387–1395.
  * [25] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, “On the convergence of fedavg on non-iid data,” _arXiv preprint arXiv:1907.02189_ , 2019.
  * [26] S. Boyd, S. P. Boyd, and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [27] R. M. Corless, G. H. Gonnet, D. E. Hare, D. J. Jeffrey, and D. E. Knuth, “On the Lambert W function,” _Adv. Comput. Math._ , vol. 5, no. 1, pp. 329–359, 1996.
  * [28] Y. Lecun, C. Cortes, and C. Burges, “Mnist,” 1998.
  * [29] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [30] M. M. Amiri, D. Gündüz, S. R. Kulkarni, and H. V. Poor, “Convergence of update aware device scheduling for federated learning at the wireless edge,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 6, pp. 3643–3658, 2021\.