# Joint Optimization of Resource Allocation and Data Selection for Fast and
Cost-Efficient Federated Edge Learning

Yunjian Jia, Zhen Huang, Jiping Yan, Yulu Zhang, Kun Luo, and Wanli Wen  The
work is sponsored by the National Natural Science Foundation of China under
Grant 62201101, the Project funded by China Postdoctoral Science Foundation
under Grant 2022M720020, the Natural Science Foundation of Chongqing, China
under Grant cstc2021jcyj-msxmX0458, and the Special Key Projects for
Technological Innovation and Application Development in Chongqing Municipality
under Grant CSTB2022TIAD-KPX0059. The authors are with the School of
Microelectronics and Communication Engineering, Chongqing University,
Chongqing 400044, China<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>wanli_wen@cqu.edu.cn). _(Corresponding author: Wanli Wen)_

###### Abstract

Deploying federated learning at the wireless edge introduces federated edge
learning (FEEL). Given FEEL’s limited communication resources and potential
mislabeled data on devices, improper resource allocation or data selection can
hurt convergence speed and increase training costs. Thus, to realize an
efficient FEEL system, this paper emphasizes jointly optimizing resource
allocation and data selection. Specifically, in this work, through rigorously
modeling the training process and deriving an upper bound on FEEL’s one-round
convergence rate, we establish a problem of joint resource allocation and data
selection, which, unfortunately, cannot be solved directly. Toward this end,
we equivalently transform the original problem into a solvable form via a
variable substitution and then break it into two subproblems, that is, the
resource allocation problem and the data selection problem. The two
subproblems are mixed-integer non-convex and integer non-convex problems,
respectively, and achieving their optimal solutions is a challenging task.
Based on the matching theory and applying the convex-concave procedure and
gradient projection methods, we devise a low-complexity suboptimal algorithm
for the two subproblems, respectively. Finally, the superiority of our
proposed scheme of joint resource allocation and data selection is validated
by numerical results.

###### Index Terms:

Federated edge learning, mislabeling, data selection, training cost, resource
allocation.

##  I Introduction

It is estimated that there will be 29.3 billion networked devices, such as
smart phones, pads, wearable devices and other consumer electronics, by 2024
around the world [1]. These devices will inevitably generate huge amounts of
data at the wireless edge that can be applicable for multifarious machine
learning (ML) tasks, e.g., autonomous driving and product recommendation.
Traditional ML algorithms need to expose the raw data to third-party entities
for model training, which, however, may compromise data privacy [2]. To tackle
such privacy issue, researchers in the field of wireless communications
integrate federated leaning with mobile edge computing, thus forming a concept
known as federated edge learning (FEEL) [3, 4, 5, 6]. In the training process
of FEEL, the devices must send their local training results such as gradients
or model parameters, instead of the raw data, via wireless channels. Since the
available radio resources such as bandwidth and time at the network edge are
constrained, it is necessary to allocate appropriate radio resources for each
device during model training. In addition, the data owned by the devices may
be mislabeled in practice, for example, a hand-written digit “1” may be
labeled as “0”, and an image “t-shirt” may be labeled as “trouser”. Training
ML models on such mislabeled data can seriously deteriorate the convergence of
FEEL, so it is necessary to select local data appropriately during model
training[7].

To date, there have been many research efforts on the resource allocation for
FEEL, among which some representative researches are [8, 9, 10, 11, 12, 13,
14, 15, 16, 17, 18, 19, 20, 21, 22, 23]. Specifically, the authors in [8, 9,
10, 11, 12, 13, 14, 15] developed an efficient joint device scheduling and
wireless resource allocation scheme respectively, aiming to minimize devices’
total energy cost [8, 10, 9] and learning time cost [9], maximize the weighted
sum data rate [11], or speed up the convergence of FEEL [12, 13, 14, 15, 16].
The authors in [17] and [18] established a resource allocation problem to
reduce the weighted sum of FEEL training time and total energy cost of all
devices. A joint device scheduling and resource management strategy is
developed in [19], which can significantly speed up model training and save
energy costs. Additionally, a joint optimization of the processing-rate, the
uplink Non-orthogonal Multiple Access (NOMA) transmission duration, and the
broadcasting duration, as well as the accuracy of the local training was
proposed in [20], with the aim of minimizing the system-wise cost including
the total energy consumption and the FEEL convergence latency. It is worth
noting that excessive energy cost may prevent devices from participating in
model training, thus reducing the performance of FEEL. However, how to deal
with this issue has not been well studied in the literature [8, 9, 10, 11, 12,
13, 14, 15, 16, 17, 18, 19, 20]. There are several ways to encourage devices
to join in the model training process, such as rewarding the devices
appropriately to compensate for their energy costs, as done in [21, 22, 23].
More specifically, the authors in [21, 22, 23] proposed to reward all devices
based on the number of CPU cycles [21] or the quantity of available training
samples [22, 23] that they are willing to contribute, and the greater the
contribution, the higher the reward. On this basis, they further focused on
how to achieve the desirable resource allocation. Note that the above works
have never considered the design of data selection in the FEEL system, so the
training algorithm they proposed may not be applicable for scenarios in which
some local data are mislabeled.

As for the design of the data selection in FEEL, there are not many works in
this direction recently, and some representative works include [24, 25, 26,
27, 28]. Specifically, the work in [24] demonstrated the negative influence of
data mislabeling on training performance and proposed an efficient data
selection method. The authors in [25] first evaluated the relevance of data
samples and then proposed to filter out all irrelevant data before model
training. In [26, 27, 28], the authors built a joint data selection and
resource allocation problem to either speed up model training [26] or minimize
the energy cost of FEEL [27, 28]. Note that although the above works in [24,
25, 26, 27, 28] have proposed several efficient schemes to speed up model
training and reduce the cost of the FEEL system from various perspectives,
there are still some limitations. _First_ , the works in [24] and [25]
overlooked the resource allocation of the FEEL system. _Second_ , the authors
in [26, 27, 28] did not analyze the convergence of the training process.
_Third_ , the studies in [24, 25, 26, 27, 28] assumed that all devices can
always participate in model training, which, however, may not hold in
practice, since the edge devices may fail to upload local gradients due to the
loss of connections. As a result, the proposed schemes therein may not be
suitable for practical FEEL systems.

In this work, we would like to address the above issues. We investigate a
generic FEEL system consisting of multiple devices and an edge server, where
each device connect to the server via wireless channels. It is worth noting
that to simulate the practical scenarios, we assume that the devices may not
always be available to connect to the server. In addition, some devices may be
not willing to conduct model training due to the high energy cost. Thus, to
entice devices to join in model training, the server will reward the devices
to compensate for the energy cost. Particularly, in the FEEL system, we
consider that the communication resources are limited and each device may have
some mislabeled data samples. On these bases, we would like to analyze the
convergence of FEEL and jointly optimize the resource allocation and data
selection to speed up model training while reducing the net cost (i.e., the
energy cost minus the reward) of all devices. Our contributions are listed
below.

  * •

By mathematically modeling the training process of FEEL, we derive an
analytical expression for the net cost of all devices. In addition, we propose
a new gradient aggregation method and derive an upper bound on FEEL’s one-
round convergence rate. On this basis, we obtain a mathematical expression
that can be used to speed up the convergence of FEEL.

  * •

To accelerate the convergence of FEEL while minimizing the net cost of all
devices, we establish a joint resource allocation and data selection problem.
Since the formulated problem is unsolvable on the server side, we equivalently
transform it into a more solvable form with some appropriate transformations
and then separate the original problem into two subproblems: the resource
allocation problem and the data selection problem. These two subproblems are
mixed-integer non-convex and integer non-convex problems, respectively, and it
is very challenging to obtain their optimal solutions.

  * •

Based on the matching theory and applying the convex-concave procedure and
gradient projection methods, we propose a low-complexity suboptimal algorithm
for the resource allocation problem and the data selection problem,
respectively.

##  II System Model

We investigate a generic FEEL system, which consists of one edge server and
$K$ devices, as depicted in Fig. 1. To maintain the simplicity of analysis and
optimization, we assume that both the BS and devices are equipped with a
single antenna. Let $\mathcal{K}=\left\\{1,2,\cdots,K\right\\}$ denote the
user set. Note that we assume that all devices are legitimate, with no
malicious devices. Let
$\mathcal{D}_{k}=\\{(\mathbf{x}_{j},y_{j})\\}_{j=1}^{|\mathcal{D}_{k}|}$
denote the dataset of the $k$-th device. Here,
$\mathbf{x}_{j}\in\mathbb{R}^{d}$ is the $d$-dimensional data sample,
$y_{j}\in\mathbb{R}$ denotes the data label, and $\left|\cdot\right|$ depicts
the cardinality of a set. We define
$\mathcal{D}=\cup_{k\in\mathcal{K}}\mathcal{D}_{k}$ as the whole dataset
resided on all devices. Table I summarized the main notations used in this
paper.

Figure 1: System model. Device $k$ has $|\mathcal{D}_{k}|=6$ images, two of which are mislabeled. The text above each image represents the corresponding label, with black text and red text representing correct and incorrect labels, respectively. TABLE I: List of Notations Notation |  Definition
---|---
$\mathcal{N}$; $\mathcal{K}$; $N$; $K$ |  Set of resource blocks (RBs); set of devices; number of RBs; number of devices
$\mathcal{D}_{k}$; $\mathcal{D}$; $\left|\mathcal{D}_{k}\right|$; $\left|\mathcal{D}\right|$ |  Dataset on device $k$; the whole dataset; cardinality of $\mathcal{D}_{k}$; cardinality of $\mathcal{D}$
$\mathbf{w}^{(i)}$; $\mathbf{x}_{j}$; $y_{j}$ |  ML model at round $i$; data sample $j$; label of data sample $j$
$L(\cdot)$; $L_{k}(\cdot)$; $\ell(\cdot)$ |  Global loss function; local loss function of device $k$; loss function of each data sample
$\hat{\mathbf{g}}^{(i)}$; $\hat{\mathbf{g}}_{k}^{(i)}$; $\mathbf{g}_{k,j}^{(i)}$ |  Global gradient at round $i$; local gradient of device $k$ at round $i$; gradient of the $j$-th data sample on device $k$ at round $i$
$q_{k}$; $c_{k}$ |  Reward per data sample for device $k$; cost per unit energy consumption of device $k$
$F_{k}$; $f_{k}$; $\kappa$ |  Number of CPU cycles required for computing $\mathbf{g}_{k,j}^{(i)}$; CPU frequency of device $k$; energy capacitance coefficient
$R(\cdot)$; $C^{\rm cmp}$; $C^{\rm com}$; $C(\cdot)$ |  Total reward received by all devices; total cost of performing gradient computing on all devices; total cost of performing local gradient uploading from all devices; net cost of all devices
$\alpha_{k}^{(i)}$; $\epsilon_{k}$ |  Availability indicator of device $k$ at round $i$; probability that device $k$ is available for gradient uploading
$B$; $L$; $T$; $r_{k,n}^{(i)}$ |  Bandwidth of each RB; size of gradient; time duration for uploading; achievable data rate of device $k$ on RB $n$ at round $i$
$\bm{\mathcal{M}}^{(i)}$; $\bm{\rho}^{(i)}$; $\mathbf{p}^{(i)}$ |  Data selection at round $i$; RB assignment at round $i$; power allocation at round $i$

###  II-A Learning Model

The FEEL system can learn an ML model $\mathbf{w}\in\mathbb{R}^{d}$ over the
datasets of all devices by solving the problem below

$\displaystyle\mathbf{w}^{*}=\arg\min_{\mathbf{w}}L(\mathbf{w}).$ (1)

Here,
$L(\mathbf{w})=\frac{1}{\left|\mathcal{D}\right|}\sum_{k\in\mathcal{K}}{\left|\mathcal{D}_{k}\right|L_{k}(\mathbf{w})}$
is the loss function with

$\displaystyle
L_{k}(\mathbf{w})=\frac{1}{\left|\mathcal{D}_{k}\right|}\sum_{j\in\mathcal{D}_{k}}{\ell(\mathbf{w},\mathbf{x}_{j},y_{j})},$
(2)

denoting the loss function for device $k$ and $\ell(\cdot)$ being an
appropriate sample-wise loss function.

Training an ML model in the FEEL system usually is an iterative procedure, in
which the iteration is also known as the communication round. Define
$\mathbf{w}^{(i)}$ to be the global model at round $i=1,2,\cdots$. Then, the
training process of FEEL at each round consists of three stages, i.e., _Local
Gradient Computing_ , _Local Gradient Uploading_ , and _Global Model
Updating_. We will detail these stages in the following subsections.

###  II-B Local Gradient Computing

The $k$-th device will compute the local gradient, denoted by
$\hat{\mathbf{g}}_{k}^{(i)}$, of $L_{k}(\mathbf{w})$ at
$\mathbf{w}=\mathbf{w}^{(i)}$, where $\mathbf{w}^{(i)}$ is received from the
edge server. The computed gradient $\hat{\mathbf{g}}_{k}^{(i)}$ is uploaded to
the server subsequently in the stage of _Local Gradient Uploading_. Note that,
most of the current literature on FEEL implicitly assumes that the device’s
data samples are always labeled correctly [8, 11, 17, 10, 18, 12, 13, 14, 16,
20, 19], and thus the gradient $\hat{\mathbf{g}}_{k}^{(i)}$ is

$\displaystyle\hat{\mathbf{g}}_{k}^{(i)}=\nabla
L_{k}(\mathbf{w}^{(i)})=\frac{1}{\left|\mathcal{D}_{k}\right|}\sum_{(\mathbf{x}_{j},y_{j})\in\mathcal{D}_{k}}\mathbf{g}_{k,j}^{(i)},\
{\forall k\in\mathcal{K}}$ (3)

where
$\mathbf{g}_{k,j}^{(i)}=\nabla\ell(\mathbf{w}^{(i)},\mathbf{x}_{j},y_{j})$ and
$L_{k}(\mathbf{w}^{(i)})$ is given by (2). Nevertheless, in practice, some
data samples in $\mathcal{D}_{k}$ may be mislabeled, for example, a hand-
written digit “1” may be labeled as “0”, and an image “t-shirt” may be labeled
as “trouser”. Such mislabeling may degenerate the training performance of FEEL
if directly sending $\mathbf{\hat{g}}_{k}^{(i)}$ in (3) to the edge server. To
this end, we consider a data selection design,111Note that the data selection
mechanism discussed in this paper does not necessitate the capability of the
user devices or the edge server to detect data with incorrect labels. in which
only a subset $\mathcal{M}_{k}^{(i)}$ of the data samples in $\mathcal{D}_{k}$
are selected to compute the local gradient. Specifically, a subdataset is
first sampled from $\mathcal{D}_{k}$ with size $|\hat{\mathcal{D}}_{k}|$,
where $\hat{\mathcal{D}}_{k}\subseteq\mathcal{D}_{k}$. Then, the gradient norm
square of each data sample in $\hat{\mathcal{D}}_{k}$ is computed and sent to
the BS. On this basis, a subset $\mathcal{M}_{k}^{(i)}$ is chosen from
$\hat{\mathcal{D}}_{k}$ to compute the local gradient. On this basis, with a
slight abuse of notation, we reexpress (3) as

$\displaystyle\mathbf{\hat{g}}_{k}^{(i)}=\frac{1}{|\mathcal{M}_{k}^{(i)}|}\sum_{(\mathbf{x}_{j},y_{j})\in\mathcal{M}_{k}^{(i)}}\mathbf{g}_{k,j}^{(i)},\
{\forall k\in\mathcal{K}}$ (4)

where $\mathcal{M}_{k}^{(i)}$ satisfies the following constraints

$\displaystyle\mathcal{M}_{k}^{(i)}\subseteq\hat{\mathcal{D}}_{k},\quad{\forall}k\in\mathcal{K},$
(5)
$\displaystyle\mathcal{M}_{k}^{(i)}\neq\emptyset,\quad{\forall}k\in\mathcal{K}.$
(6)

Let $\bm{\mathcal{M}}^{(i)}=\\{\mathcal{M}_{k}^{(i)}\\}_{k\in\mathcal{K}}$
denote the data selection design. Note that the data selection design
$\bm{\mathcal{M}}^{(i)}$ can be applicable in smart healthcare systems for
disease diagnosis [5] and in autonomous vehicles for enhanced driving process
safety [6]. After completing the local gradient calculation, device $k$ will
send the local gradient $\mathbf{\hat{g}}_{k}^{(i)}$ given in (4) instead of
(3) to the edge server.

As done in [22] and [4], to compensate for the cost of user participation in
training and attract them to participate in model training, we consider that
the server will reward each device. Let $q_{k}$ denote the reward per data
sample for device $k$.222Determining the specific value of $q_{k}$ is a
strategic process that takes into account a range of factors, including but
not limited to data volume and privacy concerns. Then, the total reward
received by all devices in $\mathcal{K}$ is

$\displaystyle
R(\bm{\mathcal{M}}^{(i)})=\sum_{k\in\mathcal{K}}q_{k}|\mathcal{M}_{k}^{(i)}|.$
(7)

On the other hand, the local calculation will consume a certain amount of
energy of each device. To be specific, we define $F_{k}$ as the CPU
computational power required by device $k$ to compute the gradient norm square
of a single data sample, which is quantified in terms of CPU cycles per
sample. Concurrently, let $f_{k}$ denote the CPU frequency of device $k$,
measured in CPU cycles per second. Then, the computation time at device $k$
for computing the gradient norm square of the data samples in
$\hat{\mathcal{D}}_{k}$ is given by

$\displaystyle\tau_{k}=\frac{F_{k}|\hat{\mathcal{D}}_{k}|}{f_{k}},\
{\forall}k\in\mathcal{K}.$ (8)

Based on [29], the energy consumption for gradient computing at device $k$ is

$\displaystyle E_{k}^{\rm{cmp}}=\kappa F_{k}|\hat{\mathcal{D}}_{k}|f_{k}^{2},\
{\forall k\in\mathcal{K}}.$ (9)

Here $\kappa$ denotes the energy capacitance coefficient which is dependent on
the chip architecture. Let $c_{k}$ denote the cost per unit energy consumption
of device $k$.333Note that accurately quantifying $c_{k}$ in real-world FEEL
systems is complex, as it involves various factors including the energy
efficiency of the hardware, the energy required for data transfer, and the
operational efficiency of the model on specific devices [9]. Thus, the total
cost of performing gradient computing on all devices is given by

$\displaystyle C^{\rm cmp}=\sum_{k\in\mathcal{K}}{c_{k}E_{k}^{\rm{cmp}}}.$
(10)

###  II-C Local Gradient Uploading

In this stage, each device needs to submit its gradient to the edge server.
Due to the resource limitation of wireless transmission, we consider a grant-
based NOMA system that has a set $\mathcal{N}=\left\\{1,2,\cdots,N\right\\}$
of $N$ resource blocks (RBs). To support the gradient uploading, these RBs in
$\mathcal{N}$ should be carefully allocated to the devices in $\mathcal{K}$.
Define $\rho_{k,n}$ to be the RB assignment indicator, where $\rho_{k,n}=1$
indicates that the $n$-th RB is assigned to the $k$-th device, and
$\rho_{k,n}=0$, otherwise. Consider that each RB can be allocated to $Q\geq 1$
devices at most, while each device can occupy only one RB [30, 31], i.e., the
following constraints should be satisfied

$\displaystyle\rho_{k,n}^{(i)}\in\\{0,1\\},~{}{\forall}k\in\mathcal{K},~{}{\forall}n\in\mathcal{N},$
(11) $\displaystyle\sum_{k\in\mathcal{K}}{\rho_{k,n}^{(i)}}\leq
Q,~{}{\forall}n\in\mathcal{N},$ (12)
$\displaystyle\sum_{n\in\mathcal{N}}{\rho_{k,n}^{(i)}}\leq
1,~{}{\forall}k\in\mathcal{K}.$ (13)

Additionally, as mentioned earlier, not all devices are available to transmit
their gradients to the server. To reflect such behavior, let
$\alpha_{k}\in\\{0,1\\}$ denote device $k$’s availability state, where
$\alpha_{k}=1$ indicates that device $k$ can be available to upload its
gradient $\hat{\mathbf{g}}_{k}^{(i)}$, and $\alpha_{k}=0$, otherwise. Then, we
reform the uploaded local gradient of device $k$ as
$\alpha_{k}^{(i)}\hat{\mathbf{g}}_{k}^{(i)}$, and the following constraint
should be satisfied

$\displaystyle\rho_{k,n}^{(i)}\leq\alpha_{k}^{(i)},~{}{\forall}k\in\mathcal{K},\;{\forall}n\in\mathcal{N}.$
(14)

According to the NOMA transmission protocol [32, 33, 34, 35], the uplink
signals from the devices occupying the same RB will be superposed. Let
$\mathcal{S}_{n}^{(i)}$ denote the set of devices occupying RB $n$. Then, the
received signal at the edge server on RB $n$ can be expressed as

$\displaystyle
u_{n}^{(i)}=\sum_{k\in\mathcal{S}_{n}^{(i)}}{\sqrt{\rho_{k,n}^{(i)}p_{k,n}^{(i)}h_{k,n}^{(i)}}\alpha_{k}^{(i)}v_{k,n}^{(i)}}+m,\
{\forall n\in\mathcal{N}}$

where $v_{k,n}^{(i)}$ denotes the signal transmitted from device $k$ on the
$n$-th RB with $\mathbb{E}\\{|v_{k,n}^{(i)}|^{2}\\}=1$ and
$\mathbb{E}\\{\cdot\\}$ being the expectation operator, $h_{k,n}^{(i)}$ is the
channel power gain of device $k$ on RB $n$, $m$ denotes the zero-mean Gaussian
noise with variance $N_{0}$, $p_{k,n}^{(i)}$ denotes the transmission power of
device $k$ on RB $n$. Let $p_{k}^{\rm{max}}$ represent the maximum power limit
of device $k$. Then, we have

$\displaystyle 0\leq p_{k,n}^{(i)}\leq\rho_{k,n}^{(i)}p_{k}^{\rm max},\
{\forall}k\in\mathcal{K},\ {\forall}n\in\mathcal{N},$ (15)

We consider that the successive interference cancellation is applied at the
edge server. Specifically, for each RB, the edge server first decodes the
signal from the device with the highest channel power gain and treats the
signals of others as interference. Then, the edge server subtracts the decoded
signal from the superposed signal. This iterative process continues until the
signals from all users have been successfully decoded. On this basis, we can
calculate the achievable rate of device $k$ on RB $n$ as follows,
$r_{k,n}^{(i)}=B\log_{2}\left(1+\frac{\rho_{k,n}^{(i)}p_{k,n}^{(i)}h_{k,n}^{(i)}}{\sum_{t\in\mathcal{S}_{n}^{(i)}}{\mathbbm{1}\left[h_{t,n}^{(i)}<h_{k,n}^{(i)}\right]\rho_{t,n}^{(i)}p_{t,n}^{(i)}h_{t,n}^{(i)}}+N_{0}}\right),\quad{\forall}k\in\mathcal{K},\quad{\forall}n\in\mathcal{N}$.
Here, $B$ represents the bandwidth of each RB and
$\mathbbm{1}\left[\cdot\right]$ denotes an indicator function. Let $L$ and $T$
represent the size of the local gradient $\mathbf{\hat{g}}_{k}^{(i)}$ in (4)
and the time duration for gradient uploading, respectively. To ensure that
$\mathbf{\hat{g}}_{k}^{(i)}$ can be uploaded to the server successfully, we
have

$\displaystyle\sum_{n\in\mathcal{N}}{r_{k,n}^{(i)}}T\geq\alpha_{k}^{(i)}L,~{}{\forall}k\in\mathcal{K}.$
(16)

Finally, the energy consumption of device $k$ for local gradient uploading is
$E^{\rm{com}}_{k}\left(\bm{\rho}^{(i)},\mathbf{p}^{(i)}\right)=\sum_{n\in\mathcal{N}}{\rho_{k,n}^{(i)}}p_{k,n}^{(i)}T$,
and the total cost of performing local gradient uploading from all devices can
be expressed as

$\displaystyle C^{\rm
com}\left(\bm{\rho}^{(i)},\mathbf{p}^{(i)}\right)=\sum_{k\in\mathcal{K}}{c_{k}E_{k}^{\rm{com}}\left(\bm{\rho}^{(i)},\mathbf{p}^{(i)}\right)},$
(17)

where $\bm{\rho}^{(i)}=(\rho_{k,n}^{(i)})_{k\in\mathcal{K},n\in\mathcal{N}}$
and $\mathbf{p}^{(i)}=(p_{k,n}^{(i)})_{k\in\mathcal{K},n\in\mathcal{N}}$
denote the design parameters of RB assignment and transmission power
allocation, respectively. Finally, based on the reward in (7), and the total
costs in (10) and (17), we can compute the net cost (i.e., the energy cost
minus the reward) of all devices as follows.

$\displaystyle
C(\bm{\mathcal{M}}^{(i)},\bm{\rho}^{(i)},\mathbf{p}^{(i)})=C^{\rm
com}\left(\bm{\rho}^{(i)},\mathbf{p}^{(i)}\right)+C^{\rm
cmp}-R(\bm{\mathcal{M}}^{(i)}).$ (18)

###  II-D Global Model Updating

In this stage, by aggregating the gradients from the devices, the edge server
will generate a new global model for the next round of model training. Let
$\epsilon_{k}=\Pr[\alpha_{k}^{(i)}=1]$ denote the probability that device $k$
is available to submit its local gradient. Then, we propose that at round $i$,
the server aggregates the local gradients based on

$\displaystyle\mathbf{\hat{g}}^{(i)}=\frac{1}{|\hat{\mathcal{D}}|}\sum_{k\in\mathcal{K}}{\frac{|\hat{\mathcal{D}}_{k}|}{\epsilon_{k}}\alpha_{k}^{(i)}\mathbf{\hat{g}}_{k}^{(i)}},$
(19)

where $\hat{\mathcal{D}}=\sum{{}_{k=1}^{K}\hat{\mathcal{D}}_{k}}$, and
$\hat{\mathbf{g}}^{(i)}$ denotes the global gradient generated on the edge
server side.

The following lemma shows the unbiasedness of $\mathbf{\hat{g}}^{(i)}$, which
can greatly facilitate us to prove FEEL’s convergence rate.

######  Lemma 1.

The expectation of $\hat{\mathbf{g}}^{(i)}$ is equal to the ground-truth
gradient $\mathbf{g}^{(i)}=\nabla L(\mathbf{w}^{(i)})$.

The proof can be found in Appendix A. Based on (19), the edge server generates
a new global model $\mathbf{w}^{(i+1)}$ for the next round of model training
according to

$\displaystyle\mathbf{w}^{(i+1)}=\mathbf{w}^{(i)}-\eta^{(i)}\mathbf{\hat{g}}^{(i)}.$
(20)

Here, $\eta^{(i)}>0$ denotes the learning rate at round $i$.

###  II-E Convergence Analysis

The above three stages will be repeated several times until FEEL converges. We
now analysis the convergence behaviour of FEEL under the proposed data
selection scheme.

####  II-E1 One-round convergence rate

Using Lemma 1, we first derive an upper bound on FEEL’s one-round convergence
rate.

######  Lemma 2.

If $\nabla L(\mathbf{w})$ is Lipschitz continuous, we obtain

$\displaystyle\mathbb{E}\left[L\left(\mathbf{w}^{(i+1)}\right)-L(\mathbf{w}^{*})\right]\leq\mathbb{E}\left[L\left(\mathbf{w}^{(i)}\right)-L(\mathbf{w}^{*})\right]$
$\displaystyle-\eta^{(i)}\left\|\mathbf{g}^{(i)}\right\|^{2}+\frac{\beta\left(\eta^{(i)}\right)^{2}}{2|\hat{\mathcal{D}}|^{2}}\Delta(\bm{\mathcal{M}}^{(i)}).$
(21)

Here, $\beta>0$ is the Lipschitz modulus and $\Delta(\bm{\mathcal{M}}^{(i)})$
is given by (22), shown at the bottom of next page, where
$\sigma_{k,j}^{(i)}=\|\mathbf{g}_{k,j}^{(i)}\|^{2}$.

$\displaystyle\Delta(\bm{\mathcal{M}}^{(i)})=\sum_{k\in\mathcal{K}}{\left(\frac{|\hat{\mathcal{D}}_{k}|^{2}}{\epsilon_{k}|\mathcal{M}_{k}^{(i)}|}\sum_{(\mathbf{x}_{j},y_{j})\in\mathcal{M}_{k}^{(i)}}{\sigma_{k,j}^{(i)}}+\sum_{t\in\mathcal{K}\setminus\\{k\\}}{\frac{|\hat{\mathcal{D}}_{k}||\hat{\mathcal{D}}_{t}|}{|\mathcal{M}_{t}^{(i)}|}\sum_{(\mathbf{x}_{j},y_{j})\in\mathcal{M}_{t}^{(i)}}{\sigma_{t,j}^{(i)}}}\right)}.$
(22)

The proof can be found in Appendix B.

####  II-E2 Convergence upper bound

Based on Lemma 2, we can derive the convergence upper bound in the $i$-th
communication round.

######  Lemma 3.

If $\nabla L(\mathbf{w})$ is strongly convex with a positive parameter $\mu$,
we have

$\displaystyle\mathbb{E}[L(\mathbf{w}^{(i+1)})-L(\mathbf{w}^{*})]\leq\prod\limits_{t=1}^{i}(1-2\mu\eta^{(t)})\mathbb{E}[L(\mathbf{w}^{(1)})-L(\mathbf{w}^{*})]$
$\displaystyle+\frac{\beta}{2|\hat{\mathcal{D}}|^{2}}\sum_{t=1}^{i}{A^{(t)}(\eta^{(t)})^{2}\Delta(\bm{\mathcal{M}}^{(t)})},$
(23)

where $A^{(t)}=\prod\limits_{j=t+1}^{i}(1-2\mu\eta^{(j)})$ is a weight
coefficient.

The proof can be found in Appendix C. Lemmas 2 and 3 indicate that
$\Delta(\bm{\mathcal{M}}^{(i)})$ directly relates to the data selection
$\bm{\mathcal{M}}^{(i)}$ and the decrease of $\Delta(\bm{\mathcal{M}}^{(i)})$
will speed up the convergence of FEEL.

##  III Problem Formulation and Transformation

In the sequel, we first establish a joint resource allocation and data
selection problem. Then, we conduct some necessary transformations to
facilitate solving the original problem.

###  III-A Problem Formulation

According to (18) and (2), we see that the variables
$(\bm{\rho}^{(i)},\mathbf{p}^{(i)})$ and $\bm{\mathcal{M}}^{(i)}$ can affect
both the convergence of FEEL and the net cost of all devices. Therefore, a
question naturally arises: how to design an appropriate joint resource
allocation and data selection scheme to accelerate the convergence of FEEL
while minimizing the net cost of all devices? To answer this question, the
following problem is established.

######  Problem 1 (Joint Resource Allocation and Data Selection).

$\displaystyle\min_{\bm{\mathcal{M}}^{(i)},\bm{\rho}^{(i)},\mathbf{p}^{(i)}}\
$
$\displaystyle\lambda\Delta(\bm{\mathcal{M}}^{(i)})+(1-\lambda)C(\bm{\mathcal{M}}^{(i)},\bm{\rho}^{(i)},\mathbf{p}^{(i)})$
$\displaystyle\mathrm{s.t.}\quad$
$\displaystyle(\ref{consOfDataSel01}),(\ref{consOfDataSel02}),(\ref{consOfrho01}),(\ref{consOfrho02}),(\ref{consOfrho03}),(\ref{consOfrho04}),(\ref{consOfMaxPow01}),(\ref{consOfRate01}).$

Problem 1 should be tackled on the server side, not on the device side. In
particular, due to the constraints in (5) and (6), all users’ local data
should be uploaded to the server when solving Problem 1. However, to protect
data privacy, FEEL does not allow the server to directly access the raw data
of each device, so Problem 1 cannot be solved at the edge server. In the
following subsection, we will transform Problem 1 into a solvable form through
variable substitution. Subsequently, we will decompose it into two
subproblems. Due to the transformation, the server can address Problem 1
without compromising user data confidentiality.

###  III-B Problem Transformation

Let $\delta_{k,j}^{(i)}\in\\{0,1\\}$ denote the data selection indicator,
where $\delta_{k,j}^{(i)}=1$ represents that the $j$-th data sample in
$\mathcal{D}_{k}$ is selected into the set $\mathcal{M}_{k}^{(i)}$, and
$\delta_{k,j}^{(i)}=0$, otherwise. Define the variable
$\bm{\delta}^{(i)}=(\bm{\delta}_{k}^{(i)})_{k\in\mathcal{K}}$, where
$\bm{\delta}_{k}^{(i)}=(\delta_{k,j}^{(i)})_{j\in\mathcal{J}_{k}}$ and
$\mathcal{J}_{k}=\\{1,2,\cdots,|\hat{\mathcal{D}}_{k}|\\}$. Then, by replacing
$\mathcal{M}_{k}$ with $\bm{\delta}^{(i)}$, we transform Problem 1 into an
equivalent problem as follows.

######  Problem 2 (Joint Resource Allocation and Data Selection).

$\displaystyle\min_{\bm{\delta}^{(i)},\bm{\rho}^{(i)},\mathbf{p}^{(i)}}$
$\displaystyle\lambda\hat{\Delta}(\bm{\delta}^{(i)})+(1-\lambda)\hat{C}(\bm{\delta}^{(i)},\bm{\rho}^{(i)},\mathbf{p}^{(i)})$
$\displaystyle\mathrm{s.t.}\ $
$\displaystyle{(\ref{consOfrho01}),(\ref{consOfrho02}),(\ref{consOfrho03}),(\ref{consOfrho04}),(\ref{consOfMaxPow01}),(\ref{consOfRate01}),}$
$\displaystyle\delta_{k,j}^{(i)}\in\\{0,1\\},\;\;j\in\mathcal{J}_{k},~{}{\forall}k\in\mathcal{K},$
(24) $\displaystyle
0<\sum_{j\in\mathcal{J}_{k}}{\delta_{k,j}^{(i)}}\leq|\hat{\mathcal{D}}_{k}|,~{}{\forall}k\in\mathcal{K},$
(25)

where $\hat{\Delta(\bm{\delta}^{(i)})}$ is given in (26), shown at the bottom
of next page, and the net cost of devices is given by

$\displaystyle\hat{\Delta}(\bm{\delta}^{(i)})=\sum_{k\in\mathcal{K}}{\left(\frac{|\hat{\mathcal{D}}_{k}|^{2}}{\epsilon_{k}\sum_{j\in\mathcal{J}_{k}}{\delta_{k,j}^{(i)}}}\sum_{j\in\mathcal{J}_{k}}{\delta_{k,j}^{(i)}\sigma_{k,j}^{(i)}}+\sum_{t\in\mathcal{K}\setminus\\{k\\}}{\frac{|\hat{\mathcal{D}}_{k}||\hat{\mathcal{D}}_{t}|}{\sum_{j\in\mathcal{J}_{t}}{\delta_{t,j}^{(i)}}}\sum_{j\in\mathcal{J}_{t}}{\delta_{t,j}^{(i)}\sigma_{t,j}^{(i)}}}\right)}.$
(26)

$\displaystyle\hat{C}(\bm{\delta}^{(i)},\bm{\rho}^{(i)},\mathbf{p}^{(i)})=C^{\rm{com}}\left(\bm{\rho}^{(i)},\mathbf{p}^{(i)}\right)+C^{\rm{cmp}}-\sum_{k\in\mathcal{K}}{q_{k}\sum_{j\in\mathcal{J}_{k}}{\delta_{k,j}^{(i)}}}.$
(27)

Compared to the original Problem 1, Problem 2 is a solvable problem, since it
is only required to send the cardinality of $\hat{\mathcal{D}}_{k}$ to the
server, instead of $\hat{\mathcal{D}}_{k}$ itself. Nonetheless, it is still
difficult to achieve an optimal point of Problem 2 for the following reasons.
First, the variables $\bm{\rho}^{(i)}$ and $\bm{\delta}^{(i)}$ are binary.
Second, the objective function and the constraint in (16) are non-convex.
Thus, Problem 2 is recognized as a highly challenging mixed-integer non-convex
problem. To tackle Problems 3, we decompose Problem 2 into it and 4
equivalently.

######  Problem 3 (Resource Allocation Problem).

$\displaystyle\min_{\bm{\rho}^{(i)},\mathbf{p}^{(i)}}C^{\rm
com}\left(\bm{\rho}^{(i)},\mathbf{p}^{(i)}\right)+C^{\rm cmp}$
$\displaystyle\mathrm{s.t.}\quad(\ref{consOfrho01}),(\ref{consOfrho02}),(\ref{consOfrho03}),(\ref{consOfrho04}),(\ref{consOfMaxPow01}),(\ref{consOfRate01}).$

######  Problem 4 (Data Selection Problem).

$\displaystyle\min_{\bm{\delta}^{(i)}}\
\lambda\hat{\Delta}(\bm{\delta}^{(i)})+(1-\lambda)\hat{C}(\bm{\delta}^{(i)},\bm{\rho}^{(i)},\mathbf{p}^{(i)})$
$\displaystyle\mathrm{s.t.}\quad(\ref{consOfDataSelDelta01}),(\ref{consOfDataSelDelta02}).$

In the sequel, we will solve Problem 2 by solving Problem 3 and Problem 4, as
illustrated in Fig. 2. The details of solving Problem 2 are summarized in
Algorithm 1.444Note that in Algorithm 1, each user performs a single iteration
over their local data to compute the local gradient. Consequently, Algorithm 1
can be considered a variant of the widely-employed FedSGD algorithm [7] in
federated learning. The analysis and optimization presented herein can be
adapted to scenarios utilizing the FedAvg algorithm [7], wherein users
typically execute multiple iterations on their local data and upload model
parameters instead of gradients to the edge server. Specifically, the edge
server first solves Problem 3 to obtain the resource allocation design,
denoted by $(\bm{\rho}^{*(i)},\mathbf{p}^{*(i)})$, via Algorithm 2 (see
Section IV), as shown in Step 2. Then, Problem 4 is solved to obtain the data
selection, denoted by $\bm{\delta}^{*(i)}$, via Algorithm 5 (see Section V),
as shown in Step 3. Note that, the edge server sends
$(\bm{\delta}^{*(i)},\bm{\rho}^{*(i)},\mathbf{p}^{*(i)})$ back to all devices
in $\mathcal{K}$, and each device can then determine $\bm{\mathcal{M}}^{*(i)}$
according to $\bm{\delta}^{*(i)}$ and select all data samples in
$\bm{\mathcal{M}}^{*(i)}$ for local gradient computation. We remark that
Algorithm 1 yields a locally optimal solution for Problem 1, not a global
optimum. When dealing with a non-convex optimization problem, attaining a
globally optimal solution is typically not guaranteed. In such scenarios, the
pursuit of a locally optimal solution becomes the conventional objective[36].

Algorithm 1 The Algorithm for Solving Problem 2

1: Input: $N$, $K$, $B$, $L$, $T$, $U$, $N_{0}$, $\lambda$, $f_{k}$, $F_{k}$,
$\kappa$, $q_{k}$, $c_{k}$, $|\hat{\mathcal{D}}_{k}|$, $\alpha_{k}^{(i)}$,
$\epsilon_{k}$, $h_{k,n}^{(i)}$, $p_{k}^{\rm{max}}$, and $\sigma_{k,j}^{(i)}$.

2: Solve Problem 3 via Algorithm 2 to obtain
$(\bm{\rho}^{*(i)},\mathbf{p}^{*(i)})$.

3: Solve Problem 4 via Algorithm 5 to obtain $\bm{\delta}^{*(i)}$.

4: Output: $(\bm{\delta}^{*(i)},\bm{\rho}^{*(i)},\mathbf{p}^{*(i)})$.

Figure 2: A schematic diagram for solving Problem 2.

##  IV Solution of Problem 3

Like Problem 2, Problem 3 is also a highly challenging mixed-integer non-
convex problem. In the sequel, based on the matching theory and convex-concave
procedure (CCP), we will propose a low-complexity algorithm to solve Problem
3.

###  IV-A Proposed Algorithm

In this subsection, we first define a matching model. Then we give the details
of the proposed matching-based algorithm. Finally, the convergence and
complexity of our proposed algorithm will be analyzed.

####  IV-A1 Matching Formulation

To rationally utilize the limited communication resources, we only allocate
RBs to the available devices. Let $\mathcal{U}^{(i)}$ denote the set of
$U^{(i)}$ available devices. To devise a low-complexity algorithm, we consider
the devices in $\mathcal{U}^{(i)}$ and RBs in $\mathcal{N}$ as two sets of
nodes in a bipartite graph. Then, our goal is to match the devices to the RBs
and allocate power appropriately to minimize the net cost, i.e., the objective
function value of Problem 3. In the following, we define a matching model.

######  Definition 1 (Matching Model).

Given two disjoint sets, i.e., $\mathcal{U}^{(i)}$ and $\mathcal{N}$, a
matching $\Psi$ is a mapping from the set $\mathcal{U}^{(i)}\cup\mathcal{N}$
into the set of all subsets of $\mathcal{U}^{(i)}\cup\mathcal{N}$, satisfying
i) $\Psi(u)\in\mathcal{N}$, ii) $\Psi(n)\subseteq\mathcal{U}^{(i)}$, iii)
$\left|\Psi(u)\right|=1$ with $|\cdot|$ denoting the size of the matching, iv)
$\left|\Psi(n)\right|\leq Q$, and v) $n=\Psi(u)\Leftrightarrow u=\Psi(n)$, for
each $u\in\mathcal{U}^{(i)}$ and $n\in\mathcal{N}$. Here, conditions i) and
iii) mean that each available device can match only one RB, and conditions ii)
and iv) represent that each RB can accommodate up to $Q$ available devices.

####  IV-A2 Algorithm Detail

Motivated by the housing assignment problem in [37], we introduce the concept
of swap matching into the matching formulated in Definition 1 and devise a
matching-based algorithm to solve Problem 3. A swapping operation means that
two available devices matched with different RBs exchange their matches, while
the matches of other available devices remain unchanged. The corresponding
power allocation and net cost under the given RB assignment is then updated
via Algorithm 3, which will be detailed in Section IV-B. To guarantee the
reduction of the net cost, a swapping operation is approved and the matching
is updated only when the net cost for the given RB assignment decreases after
the swap. The above swapping operation will be repeated several times until no
swapping is further approved. The proposed matching algorithm is detailed in
Algorithm 2 and its convergence and complexity will be analyzed in the sequel.

Algorithm 2 Matching-based Algorithm for Solving Problem 3

1: Initialize the matching $\Psi$ using $\Psi_{0}$ and set $l\to 1$.

2: repeat

3: for $u\in\mathcal{U}^{(i)}$ do

4: for $k\in\mathcal{U}^{(i)}$ do

5: if $\Psi_{l-1}(k)\neq\Psi_{l-1}(u)$ then

6: Compute and compare the cost before and after the swap using Algorithm 3.

7: if net cost decreases then

8: Update the matching, i.e., set $\Psi_{l-1}\to\Psi_{l}$.

9: end if

10: end if

11: end for

12: end for

13: Set $l\to l+1$.

14: until convergence

15: Output $\left(\bm{\rho}^{*(i)},\mathbf{p}^{*(i)}\right)$.

####  IV-A3 Convergence

After multiple swapping operations, the matching situation between RBs and
available devices changes as follows:
$\Psi_{0}\rightarrow\Psi_{1}\rightarrow\Psi_{2}\rightarrow\cdots$, where
$\Psi_{l}$ with $l=1,2,\cdots$ denotes the matching at the $l$-th swapping
operation and $\Psi_{0}$ represents the initial matching. At swapping
operation $l$, the matching changes from $\Psi_{l-1}$ to $\Psi_{l}$. Let
$\hat{C}_{l-1}$ and $\hat{C}_{l}$ denote the net costs at matching
$\Psi_{l-1}$ and matching $\Psi_{l}$, respectively. Then, we have
$\hat{C}_{l}<\hat{C}_{l-1}$, namely, the net cost decreases after the swap.
Since there is a certain positive net cost to the available devices to
guarantee the successful uploading of the local gradients, the net cost has a
lower bound, which implies that Algorithm 2 will converge after a finite
number of swapping operations.

####  IV-A4 Complexity

Finally, we discuss the computational complexity of Algorithm 2. For each
swapping operation, we should consider all possible swapping combinations,
which requires $\mathcal{O}({U^{(i)}}^{2})$ operations. For each swapping
attempt, we need to allocate the power, and calculate and compare the net cost
before and after the swapping of the available devices under the given RB
assignment. Let $\mathcal{O}(X)$ represent the complexity of the power
allocation algorithm (i.e., Algorithm 3), which will be analyzed in Section
IV-B. Assume that the matching remains unchanged after $V$ swapping
operations. Then, the computational complexity of Algorithm 2 is
$\mathcal{O}({U^{(i)}}^{2}VX)$.

###  IV-B Power Allocation

In line 6 of Algorithm 2, the net cost is minimized by optimizing the power
allocation under a given RB assignment via Algorithm 3. In this subsection, we
focus on how to construct Algorithm 3. Given the RB assignment, Problem 3
becomes the problem in (28), shown at the top of next page.

$\displaystyle\min_{\bm{p}^{(i)}}\ C^{\rm
com}\left(\bm{\rho}^{*(i)},\bm{p}^{(i)}\right)+C^{\rm cmp}$ (28)
$\displaystyle\mathrm{s.t.}\;\sum_{n\in\mathcal{N}}{B\log\left(1+\frac{\rho_{k,n}^{*(i)}p_{k,n}^{(i)}h_{k,n}^{(i)}}{\sum_{t\in\mathcal{S}_{n}^{(i)}}{\mathbbm{1}\left[h_{t,n}^{(i)}<h_{k,n}^{(i)}\right]\rho_{t,n}^{*(i)}p_{t,n}^{(i)}h_{t,n}^{(i)}}+N_{0}}\right)}T\geq\alpha_{k}^{(i)}L,~{}{\forall}k\in\mathcal{K},$
(29) $\displaystyle\qquad 0\leq p_{k,n}^{(i)}\leq\rho_{k,n}^{*(i)}p_{k}^{\rm
max},~{}{\forall}k\in\mathcal{K},~{}{\forall}n\in\mathcal{N}.$ (30)

Due to the non-convexity of the constraint in (29), the problem in (28) is a
non-convex problem. To solve it in a more tractable manner, we perform some
transformations as detailed below.

Specifically, we assume that the devices in the set $\mathcal{S}_{n}^{(i)}$
occupying RB $n$ are arranged in ascending order according to their channel
power gains. Then, the term
$\sum_{t\in\mathcal{S}_{n}^{(i)}}\mathbbm{1}[h_{t,n}^{(i)}<h_{k,n}^{(i)}]\rho_{t,n}^{*(i)}p_{t,n}^{(i)}h_{t,n}^{(i)}+N_{0}$
can be re-expressed as
s$I_{k,n}\left(\mathbf{p}^{(i)}\right)=\sum_{t=1}^{k-1}{\rho_{t,n}^{*(i)}p_{t,n}^{(i)}h_{t,n}^{(i)}}+N_{0}$.
On this basis, the constraint in (29) can be rewritten as

$\displaystyle\sum_{n\in\mathcal{N}}{B\log\left(1+\frac{\rho_{k,n}^{*(i)}p_{k,n}^{(i)}h_{k,n}^{(i)}}{I_{k,n}\left(\mathbf{p}^{(i)}\right)}\right)}T\geq\alpha_{k}^{(i)}L,~{}{\forall}k\in\mathcal{K}.$
(31)

In addition, based on the property of the logarithmic function, (31) can be
further equivalently transformed into (32), shown at the top of next page.

$\displaystyle\sum_{n\in\mathcal{N}}\log\left(\rho_{k,n}^{*(i)}p_{k,n}^{(i)}h_{k,n}^{(i)}+I_{k,n}\left(\bm{p}^{(i)}\right)\right)-\sum_{n\in\mathcal{N}}\log\left(I_{k,n}\left(\bm{p}^{(i)}\right)\right)\geq\frac{\alpha_{k}^{(i)}L}{BT},\
{\forall}k\in\mathcal{K}.$ (32)

As a result, by replacing the constraint in (29) with (32), we can transform
(28) to an equivalent problem as follows

$\displaystyle\min_{\mathbf{p}^{(i)}}\ C^{\rm
com}\left(\bm{\rho}^{*(i)},\mathbf{p}^{(i)}\right)+C^{\rm cmp}$ (33)
$\displaystyle\mathrm{s.t.}\ (\ref{maxpower02}),(\ref{DCofPowAll}).$

Since the left-hand side of (32) can be regarded as a difference of two
concave functions, (33) is a standard difference-of-concave (DC) problem.
Using the CCP method, we can achieve a stationary point of the problem in
(33). The key idea of the CCP method is to linearize
$\sum_{n\in\mathcal{N}}\log\left(I_{k,n}\left(\mathbf{p}^{(i)}\right)\right)$
of the constraint in (32) to obtain a convex constraint, so as to generate a
series of convex subproblems that approximately solves the the non-convex
problem in (33). The CCP is an iterative procedure. Let $v=0,1,2,\cdots$ be
the iteration index. At iteration $v$, the convex subproblem is given by the
problem in (34), shown at the bottom of next page.

$\displaystyle\bm{p}^{(i)}(v+1)\triangleq\arg\min_{\bm{p}}\ C^{\rm
com}\left(\bm{\rho}^{*(i)},\bm{p}\right)+C^{\rm cmp}$ (34)
$\displaystyle\mathrm{s.t.}\ (\ref{maxpower02}),$
$\displaystyle\sum_{n\in\mathcal{N}}{\log\left(\rho_{k,n}^{*(i)}p_{k,n}h_{k,n}^{(i)}+I_{k,n}\left(\bm{p}\right)\right)}-\sum_{n\in\mathcal{N}}{\log\left(I_{k,n}\left(\bm{p}^{(i)}(v)\right)\right)}-\sum_{n\in\mathcal{N}}{\frac{1}{I_{k,n}\left(\bm{p}^{(i)}(v)\right)}\sum_{t=1}^{k-1}{\rho_{t,n}^{*(i)}h_{t,n}^{(i)}}\left(p_{t,n}-p_{t,n}^{(i)}(v)\right)}\geq\frac{\alpha_{k}^{(i)}L}{BT},~{}{\forall}k\in\mathcal{K}.$

Here, $\mathbf{p}^{(i)}(v)$ represents a solution of the problem in (34) at
iteration $v$. Since the problem in (34) is convex, its optimal solution can
be achieved via CVX [38].

Algorithm 3 Power Allocation Algorithm

1: Require a feasible point $\mathbf{p}^{(i)}(0)$.

2: Set $v=0$.

3: repeat

4: Solve (34) using CVX to obtain $\mathbf{p}^{(i)}(v+1)$.

5: Set $v=v+1$.

6: until convergence.

Finally, Algorithm 3 details the procedure for solving the problem in (33).
According to [39], Algorithm 3 converges to a stationary point of (33). Fig. 3
plots the convergence trajectory of Algorithm 3 under five randomly generated
initial points. From Fig. 3, we can see that the objective function value
decreases with the increase of the number of iteration index and remains
unchanged after several iterations (e.g., $v\geq 4$), that is Algorithm 3
converges. Furthermore, we can observe that Algorithm 3 can converge to the
identical objective value under different initial points, which indicates that
Algorithm 3 can adapt to the change of initial points robustly. Algorithm 3’s
complexity is dominated by solving (34), which, therefore, can be calculated
as $\mathcal{O}((KN)^{3.5}\log(1/\varepsilon))$.

Figure 3: The convergence curves of Algorithm 3 under different initial
points.

##  V Solution of Problem 4

Solving Problem 4 optimally is NP-hard due to the existence of integer
variables and the fractional form of the objective function. Toward this end,
a low-complexity suboptimal algorithm for Problem 4 will be proposed in this
section. Our algorithm consists of two stages, that is, _continuous
relaxation_ and _binary recovery_. In the first phase, we solve the continuous
relaxation of Problem 4 via the gradient projection method. In the second
stage, we achieve a feasible integer solution of Problem 4 using the
$\lambda$-representation method.

###  V-A Continuous Relaxation

We first relax the integer constraint in (24) to

$\displaystyle\delta_{k,j}^{(i)}\in[0,1],{\forall}k\in\mathcal{K},\
{\forall}j\in\mathcal{J}_{k}.$ (35)

Based on (35), the continuous relaxation of Problem 4 is written as

$\displaystyle\min_{\bm{\delta}^{(i)}}\
\lambda\hat{\Delta}(\bm{\delta}^{(i)})+(1-\lambda)\hat{C}(\bm{\delta}^{(i)},\bm{\rho}^{*(i)},\mathbf{p}^{*(i)})$
(36)
$\displaystyle\mathrm{s.t.}\quad(\ref{consOfDataSelDelta02}),(\ref{consOfDataSelDelta03}).$

This is a non-convex continuous problem, and we can solve it efficiently by
using the gradient projection method, as summarized in Algorithm 4.
Particularly, in Step 3 of Algorithm 4, $f(\bm{\delta}^{(i)})$ is the
objective function of the problem in (36), $v$ represents the iteration index,
and $\alpha(v)$ denotes the diminishing stepsize at the $v$-th iteration,
satisfying $\alpha(v)\to 0$ as $v\to\infty$,
$\sum_{v=0}^{\infty}\alpha(v)=\infty$, and
$\sum_{v=0}^{\infty}\alpha^{2}(v)<\infty$. In Step 4, the projection of
$\hat{\bm{\delta}}^{(i)}(v+1)$ onto the feasible set of the problem in (36)
can be achieved through tackling the following problem

$\displaystyle{\bm{\delta}}^{(i)}(v+1)=$
$\displaystyle\arg\min_{\bm{\delta}}\left\|\bm{\delta}-\hat{\bm{\delta}}^{(i)}(v+1)\right\|^{2}$
(37)
$\displaystyle\mathrm{s.t.}\quad(\ref{consOfDataSelDelta02}),(\ref{consOfDataSelDelta03}).$

The problem in (37) is convex and we can achieve an optimal solution of it via
CVX. Steps 3 and 4 will be repeated serval times until Algorithm 4 converges.
According to [40], we know that
${\bm{\delta}}^{(i)}(v)\to{\bm{\delta}}^{{\dagger}(i)}$ as $v\to\infty$, where
${\bm{\delta}}^{{\dagger}(i)}$ is a stationary point of (36). Algorithm 4’s
complexity is dominated by solving (37), which can be expressed as
$\mathcal{O}((|\hat{\mathcal{D}}|)^{3.5}\log(1/\varepsilon))$.

Algorithm 4 The Algorithm to Solve (36)

1: Require a feasible initial point $\bm{\delta}^{(i)}{(0)}$.

2: Set $v=0$.

3: repeat

4: Compute
$\hat{\bm{\delta}}^{(i)}(v+1)=\bm{\delta}^{(i)}{(v)}-\alpha(v)\nabla
f(\bm{\delta}^{(i)}{(v)})$.

5: Compute ${\bm{\delta}}^{(i)}(v+1)$ by projecting
$\hat{\bm{\delta}}^{(i)}(v+1)$ onto the feasible set of the problem in (36).

6: Set $v=v+1$.

7: until convergence

###  V-B Binary Recovery

The obtained solution $\bm{\delta}^{{\dagger}(i)}$ is generally continuous and
hence is an infeasible solution of Problem 4. In the sequel, based on
$\bm{\delta}^{{\dagger}(i)}$, we construct a feasible solution of Problem 4.
Let
$\mathcal{B}=\\{(\ref{consOfDataSelDelta01}),(\ref{consOfDataSelDelta02})\\}$
be the constraint set. By projecting $\bm{\delta}^{{\dagger}(i)}$ onto
$\mathcal{B}$, we establish the following problem

$\displaystyle\bm{\delta}^{*(i)}\triangleq\arg\min_{\bm{\delta}^{(i)}\in\mathcal{B}}\left\|\bm{\delta}^{(i)}-\bm{\delta}^{{\dagger}(i)}\right\|^{2}.$
(38)

The problem in (38) is an integer nonlinear programming. By using the
$\lambda$-representation technique [41], we can transform it into a linear
programming problem as follows.

$\displaystyle\min_{\bm{\delta}^{(i)},\bm{a},\bm{b}}\sum_{k\in\mathcal{K}}{\sum_{j\in\mathcal{J}_{k}}}{\left[(\delta_{k,j}^{{\dagger}(i)})^{2}a_{k,j}+(1-\delta_{k,j}^{{\dagger}(i)})^{2}b_{k,j}\right]}$
(39) $\displaystyle\mathrm{s.t.}\
(\ref{consOfDataSelDelta02}),(\ref{consOfDataSelDelta03}),$
$\displaystyle\quad b_{k,j}=\delta_{k,j}^{(i)},\ {\forall}k\in\mathcal{K},\
{\forall}j\in\mathcal{J}_{k},$ (40) $\displaystyle\quad a_{k,j}+b_{k,j}=1,\
{\forall}k\in\mathcal{K},\ {\forall}j\in\mathcal{J}_{k},$ (41)
$\displaystyle\quad a_{k,j}\geq 0,\ b_{k,j}\geq 0,\ {\forall}k\in\mathcal{K},\
{\forall}j\in\mathcal{J}_{k},$ (42)

where $\bm{a}=(a_{k,j})_{k\in\mathcal{K},j\in\mathcal{J}_{k}}$ and
$\bm{b}=(b_{k,j})_{k\in\mathcal{K},j\in\mathcal{J}_{k}}$. Lemma 4 indicates
the relationship between the problems in (39) and (38).

######  Lemma 4.

The problems in (39) and (38) are equivalent.

Please refer to Appendix D for the proof. Based on Lemma 4, we know that to
solve the problem in (38), it is only required to solve the linear problem in
(39) by using CVX. Thus, the corresponding computational complexity for
solving the problem in (39) can be expressed as
$\mathcal{O}((3|\hat{\mathcal{D}}|)^{3.5}\log(1/\varepsilon))$.

###  V-C Algorithm Summary

Finally, Algorithm 5 summarizes the details of solving Problem 4, whose
complexity is the summation of the complexity of the _continuous relaxation_
stage and the _binary recovery_ stage, which is given by
$\mathcal{O}((1+3^{3.5})|\hat{\mathcal{D}}|^{3.5}\log(1/\varepsilon))$. In
summary, the complexity of Algorithm 1 is given by
$\mathcal{O}(U^{(i)^{2}}V(KN)^{3.5}\log(1/\varepsilon)+(1+3^{3.5})|\hat{\mathcal{D}}|^{3.5}\log(1/\varepsilon))$.

Algorithm 5 The Algorithm to Solve Problem 4

1: Obtain $\bm{\delta}^{{\dagger}(i)}$ using Algorithm 4.

2: Obtain $\bm{\delta}^{*(i)}$ by solving the problem in (38) via CVX.

3: Output: $\bm{\delta}^{*(i)}$.

##  VI Simulation Results

Extensive simulations will be conducted in this section to show the
superiority of our proposed scheme (obtained by Algorithm 1). In the
following, we will first introduce the simulation setup and then detail the
performance evaluation.

###  VI-A Simulation Setup

Unless otherwise stated, the simulation parameters are set as follows. We
consider that the FEEL system has $K=10$ devices. For device $k$, we set the
cost per Joule and the reward for each data sample, respectively, to $c_{k}=5$
and $q_{k}=0.002$, if $k$ is odd, and $c_{k}=10$ and $q_{k}=0.005$, otherwise.
The CPU frequency, the number of CPU cycles to handle a sample, and the
capacitance coefficient are set to $f_{k}=\\{0.1,0.2,\cdots,1.0\\}$ GHz,
$F_{k}=20$ cycles/sample, and $\kappa=1\times 10^{-28}$, respectively. The
probability of local gradient uploading is $\epsilon_{k}=0.2$ if $k$ is odd,
and $\epsilon_{k}=0.8$, otherwise [19]. The maximum power limit of device $k$
is set to $p_{k}^{\rm{max}}=10$ W [15]. In addition, we set $N=5$, $Q=2$,
$B=2$ MHz, $N_{0}=10^{-9}$ W, $T=500$ ms, $\lambda=1\times 10^{-3}$. The
channel power gain $h_{k,n}$ follows an exponential distribution with mean
$10^{-5}$.

We train an image classification model with the proposed FEEL algorithm. The
corresponding datasets are MNIST and Fashion-MNIST. The MNIST dataset has
$70000$ handwritten grayscale images of the digits 0 to 9, and the Fashion-
MNIST dataset comprises $70000$ grayscale images of fashion items from ten
classes, e.g., “t-shirt”, “pants”, and “bag”. For each dataset, $60000$ images
are used for model training and the rest are the test dataset. To simulate
non-IID distribution, we randomly allocate $|\mathcal{D}_{k}|=1000$ figures of
one label to device $k$ in set $\mathcal{K}$, and then randomly choose
$|\hat{\mathcal{D}}_{k}|=200$ samples from $\mathcal{D}_{k}$ in each
communication round. We assume that some data samples on each device are
mislabeled. Let $\varrho_{k}$ denote the proportion of mislabeled data on
device $k$. To simulate the scenario of data mislabeling, we randomly select
$\varrho_{k}\cdot\left|\mathcal{D}_{k}\right|$ of the data samples on device
$k$ and then mislabel each of them, such as labeling the digit “1” as “0”, or
labeling the item “t-shirt” as “pants”. In the simulations, we set the
mislabeled proportion $\varrho_{k}$ to $10\%$ for all $k\in\mathcal{K}$. We
apply the convolutional neural network (CNN) to conduct the image
classification task. The CNN model has seven layers, two $5\times 5$
convolution layers (the first and second layers have 10 and 20 channels,
respectively, each followed by $2\times 2$ max pooling), and three full
connection layers with ReLu activation. Then using Python, the size of the
gradient $\mathbf{\hat{g}}_{k}^{n}$ is estimated to be $\ell=0.56\times
10^{6}$ bits (MNIST) or $\ell=1\times 10^{6}$ bits (Fashion-MNIST). We choose
Adam as the optimizer and set the learning rate $\eta$ to $0.001$. Please note
that the hyper-parameters employed in this study have been selected based on
prior experimental experience and analogous experimental configurations,
rather than through a process of fine-tuning.

To demonstrate the superior of our proposed scheme, the following four
representative baseline schemes are investigated [12, 19, 26]:

  * •

Baseline 1: Device $k$ randomly selects half of the local data samples for
gradient computing and uploads the gradient using one RB with minimal channel
power gain.

  * •

Baseline 2: Device $k$ randomly selects half of the local data samples for
gradient computing and uploads the gradient using one RB with maximal channel
power gain.

  * •

Baseline 3: Device $k$ selects all of the local data samples for gradient
computing and uploads the gradient using one RB with minimal channel power
gain.

  * •

Baseline 4: Device $k$ selects all of the local data samples for gradient
computing and uploads the gradient using one RB with maximal channel power
gain.

Note that the power allocation of the four baseline schemes can be achieved
via Algorithm 3.

###  VI-B Evaluation Details

(a) Convergence on the MNIST dataset. (b) Cumulative net cost on the MNIST
dataset.

(c) Convergence on the Fashion-MNIST dataset. (d) Cumulative net cost on the
Fashion-MNIST dataset.

Figure 4: Convergence and cumulative net cost of FEEL under different schemes.

Fig. 4 depicts the convergence of model training and the cumulative net cost
under the proposed scheme and the baseline schemes. Here, the cumulative net
cost at communication round $i$ refers to the sum of the net costs of the
first $i$ rounds. From Fig. 4, we have some observations. First, the test
accuracy of all schemes increases in a fluctuating manner as the iteration
goes on because the local and global models are trained on the user devices
and the edge server, respectively. Second, as the iteration proceeds, the
proposed scheme can achieve significant performance gain in terms of test
accuracy and cumulative net cost compared to the four baselines. For example,
at the $600$th communication round, the test accuracy of the proposed scheme
on the MNIST dataset (resp. Fashion-MNIST dataset) can be improved by about
20% (resp. 51%), but the cumulative net cost is reduced by at least 19% (resp.
32%). Such performance gain stems from the fact that the proposed scheme can
wisely select training data samples and appropriately allocate radio resources
at each communication round. Note that the negative cumulative net costs in
Fig. 4 indicate that users are profitable under these schemes, which can
encourage them to participate in model training more actively. Finally, we
find that the difference in test accuracy between the four baseline schemes is
not so significant, indicating that if the mislabeled data samples of each
device are not excluded during model training, FEEL can only maintain a
relatively low level of test accuracy. The reason is that the mislabeled data
samples will produce incorrect gradient information, which will mislead the
convergence behavior of FEEL.

(a) Test accuracy on the MNIST dataset. (b) Cumulative net cost on the MNIST
dataset.

(c) Test accuracy on the Fashion-MNIST dataset. (d) Cumulative net cost on the
Fashion-MNIST dataset.

Figure 5:  Effect of the mislabeled proportion.

Fig. 5 shows the effect of the mislabeled proportion under the proposed scheme
and the baseline schemes. All results in Fig. 5 are obtained when the training
process of FEEL stops at the $300$th communication round. As expected, we can
see that the test accuracy under all schemes significantly decreases as the
mislabeled proportion increases, but this does not hold for the net cost which
is independent of the mislabeled proportion (see Problem 1). In addition, we
can also see that our solution is dramatically better than the baseline
schemes, indicating that the proposed scheme is more robust than the baseline
schemes in combating data mislabeling.

(a) Test accuracy on the MNIST dataset. (b) Cumulative net cost on the MNIST
dataset.

(c) Test accuracy on the Fashion-MNIST dataset. (d) Cumulative net cost on the
Fashion-MNIST dataset.

Figure 6: Effect of the device availability.

Fig. 6 shows the effect of the device availability under the proposed scheme
and the baseline schemes. All results in Fig. 6 are obtained when the training
process of FEEL stops at the $300$th communication round. From Fig. 6, we can
see that the test accuracy improves with the device availability, but the more
devices participate in local gradient uploading, the greater the cumulative
cost. Note that when all devices are unavailable to upload gradients, i.e.,
the device availability $\epsilon_{k}=0$ for all $k\in\mathcal{K}$, the test
accuracy under each scheme is zero since the server cannot aggregate any
gradients from the devices. Our scheme in the case of $\epsilon_{k}=0$ may
underperform the baseline schemes because the baselines can contribute more
data samples than ours. However, when some devices become available for
gradient uploading (e.g., when $\epsilon_{k}\geq 0.2$), the proposed scheme
becomes superior to the baselines, indicating that our solution can better
adapt to the changes in device availability.

##  VII Conclusions

In this paper, we first rigorously model the training process of FEEL and
derive its one-round convergence bound. Then, we formulate a joint resource
allocation and data selection optimization problem, which, unfortunately,
cannot be solved directly. To tackle this problem, we equivalently transform
it into a more tractable form with some appropriate transformations and then
break it into the resource allocation problem and the data selection problem.
Both subproblems are mixed-integer non-convex and integer non-convex
optimization problems, respectively, and it is very challenging to obtain
their optimal solutions. Based on the matching theory and applying the convex-
concave procedure and gradient projection methods, we propose a low-complexity
suboptimal algorithm for the resource allocation problem and the data
selection problem, respectively. At last, the superiority of the proposed
scheme is demonstrated via extensive numerical results. In future work, we aim
to extend the results proposed in this paper to multi-task FEEL systems.
Specifically, we will explore how machine learning methods can be leveraged to
achieve cross-domain data selection within this system. By doing so, we seek
to enhance the system’s adaptability and efficiency across different domains
while ensuring that data selection remains optimized for each specific task.

##  Appendix A Proof of Lemma 1

The derivative of $L(\mathbf{w})$ at $\mathbf{w}=\mathbf{w}^{(i)}$ is
calculated as

$\displaystyle\mathbf{g}^{(i)}$ $\displaystyle=\nabla
L\left(\mathbf{w}^{(i)}\right)$
$\displaystyle=\frac{1}{|\mathcal{D}|}\sum_{k\in\mathcal{K}}{|\mathcal{D}_{k}|\nabla
L_{k}\left(\mathbf{w}^{(i)}\right)}$
$\displaystyle=\frac{1}{|\mathcal{D}|}\sum_{k\in\mathcal{K}}{|\mathcal{D}_{k}|\mathbf{g}_{k}^{(i)}}.$
(43)

Here, $\mathbf{g}_{k}^{(i)}\triangleq\nabla
L_{k}(\mathbf{w}^{(i)})=\frac{1}{|\mathcal{D}_{k}|}\sum_{(\mathbf{x}_{j},y_{j})\in\mathcal{D}_{k}}{\nabla\ell(\mathbf{w}^{(i)},\mathbf{x}_{j},y_{j})}$
denotes the ground-truth local gradient of the $k$-th device.

The expectation of $\mathbf{\hat{g}}^{(i)}$ is calculated as

$\displaystyle\mathbb{E}\left[\mathbf{\hat{g}}^{(i)}\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{|\hat{\mathcal{D}}|}\sum_{k\in\mathcal{K}}{\frac{|\hat{\mathcal{D}}_{k}|}{\epsilon_{k}}\alpha_{k}^{(i)}\mathbf{\hat{g}}_{k}^{(i)}}\right]$
$\displaystyle\mathop{=}\limits^{(\mathrm{a})}\frac{1}{|\hat{\mathcal{D}}|}\sum_{k\in\mathcal{K}}{|\hat{\mathcal{D}}_{k}|\mathbb{E}\left[\frac{\alpha_{k}^{(i)}}{\epsilon_{k}}\right]\mathbb{E}\left[\mathbf{\hat{g}}_{k}^{(i)}\right]}$
$\displaystyle\mathop{=}\limits^{(\mathrm{b})}\frac{1}{|\hat{\mathcal{D}}|}\sum_{k\in\mathcal{K}}{|\hat{\mathcal{D}}_{k}|\mathbb{E}\left[\mathbf{\hat{g}}_{k}^{(i)}\right]}.$
(44)

Here, (a) follows from the independence between the random variables
$\alpha_{k}^{(i)}$ and $\mathbf{\hat{g}}_{k}^{(i)}$ and (b) follows from
$\mathbb{E}[\alpha_{k}^{(i)}]=\epsilon_{k}$. According to [12],
$\mathbf{\hat{g}}_{k}^{(i)}$ is unbiased, making their average in (A) to be an
unbiased estimation of $\mathbf{g}^{(i)}$, which completes the proof.

##  Appendix B Proof of Lemma 2

First, based on the Lipschitz continuity of $\nabla L(\mathbf{w})$, we obtain

$\displaystyle L(\mathbf{u})\leq L(\mathbf{v})+(\nabla
L(\mathbf{v}))^{\rm{T}}(\mathbf{u}-\mathbf{v})+\frac{\beta}{2}\|\mathbf{u}-\mathbf{v}\|^{2},$
(45)

where $\beta>0$ is a modulus, $(\cdot)^{\rm{T}}$ denotes the transposition
operator. Based on (45), we have the following inequality:

$\displaystyle L\left(\mathbf{w}^{(i+1)}\right)\leq
L\left(\mathbf{w}^{(i)}\right)+\left(\nabla
L\left(\mathbf{w}^{(i)}\right)\right)^{\rm{T}}\left(-\eta^{(i)}\hat{\mathbf{g}}^{(i)}\right)$
$\displaystyle+\frac{\beta}{2}\left\|-\eta^{(i)}\hat{\mathbf{g}}^{(i)}\right\|^{2}$
$\displaystyle=L\left(\mathbf{w}^{(i)}\right)-\eta^{(i)}\left(\mathbf{g}^{(i)}\right)^{\rm{T}}\hat{\mathbf{g}}^{(i)}+\frac{\beta}{2}\left(\eta^{(i)}\right)^{2}\left\|\hat{\mathbf{g}}^{(i)}\right\|^{2}.$
(46)

Next, by taking the expectation on both sides of (B), we can obtain

$\displaystyle\mathbb{E}\left[L\left(\mathbf{w}^{(i+1)}\right)-L(\mathbf{w}^{*})\right]\leq\mathbb{E}\left[L\left(\mathbf{w}^{(i)}\right)-L(\mathbf{w}^{*})\right]$
$\displaystyle-\eta^{(i)}\left(\mathbf{g}^{(i)}\right)^{\rm{T}}\mathbb{E}\left[\mathbf{\hat{g}}^{(i)}\right]+\frac{\beta\left(\eta^{(i)}\right)^{2}}{2}\mathbb{E}\left[\left\|\mathbf{\hat{g}}^{(i)}\right\|^{2}\right]$
$\displaystyle\mathop{=}\limits^{(\mathrm{a})}\mathbb{E}\left[L\left(\mathbf{w}^{(i)}\right)-L(\mathbf{w}^{*})\right]-\eta^{(i)}\left\|\mathbf{g}^{(i)}\right\|^{2}+\frac{\beta\left(\eta^{(i)}\right)^{2}}{2}\mathbb{E}\left[\left\|\hat{\mathbf{g}}^{(i)}\right\|^{2}\right],$
(47)

where (a) is due to the unbiasedness of $\hat{\mathbf{g}}^{(i)}$ (see Lemma
1).

Finally, by applying the generalized triangle inequality
$\lVert\sum_{j=1}^{n}{x_{j}}\rVert^{2}\leq n\sum_{j=1}^{n}{\lVert
x_{j}\rVert^{2}}$ [42], we further have

$\displaystyle\mathbb{E}\left[\left\|\hat{\mathbf{g}}^{(i)}\right\|^{2}\right]=\mathbb{E}\left[\left\|\frac{1}{|\mathcal{D}|}\sum_{k\in\mathcal{K}}{\frac{\alpha_{k}^{(i)}|\mathcal{D}_{k}|}{\epsilon_{k}}\hat{\mathbf{g}}_{k}^{(i)}}\right\|^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{|\mathcal{D}|^{2}}\left(\sum_{k\in\mathcal{K}}{\frac{\alpha_{k}^{(i)}|\mathcal{D}_{k}|}{\epsilon_{k}}}\right)\left(\sum_{k\in\mathcal{K}}{\frac{\alpha_{k}^{(i)}|\mathcal{D}_{k}|}{\epsilon_{k}}}\left\|\hat{\mathbf{g}}_{k}^{(i)}\right\|^{2}\right)\right]$
$\displaystyle\leq\frac{1}{|\mathcal{D}|^{2}}\mathbb{E}\left[\left(\sum_{k\in\mathcal{K}}{\frac{\alpha_{k}^{(i)}|\mathcal{D}_{k}|}{\epsilon_{k}}}\right)\left(\sum_{k\in\mathcal{K}}{\frac{\alpha_{k}^{(i)}|\mathcal{D}_{k}|}{\epsilon_{k}|\mathcal{M}_{k}^{(i)}|}\sum_{(\mathbf{x}_{j},y_{j})\in\mathcal{M}_{k}^{(i)}}{\left\|g_{k,j}^{(i)}\right\|^{2}}}\right)\right]$
$\displaystyle=\frac{1}{|\mathcal{D}|^{2}}\sum_{k\in\mathcal{K}}{\Delta(\bm{\mathcal{M}}^{(i)})},$
(48)

where $\Delta(\bm{\mathcal{M}}^{(i)})$ is given in (22). Substituting (48)
into (B), we obtain Lemma 2.

##  Appendix C Proof of Lemma 3

Since $L(\mathbf{w})$ is strongly convex, we obtain

$\displaystyle L(\mathbf{w}^{(i+1)})$ $\displaystyle\geq
L(\mathbf{w}^{(i)})+\left(\mathbf{g}^{(i)}\right)^{T}\left(\mathbf{w}^{(i+1)}-\mathbf{w}^{(i)}\right)$
$\displaystyle+\frac{\mu}{2}\|\mathbf{w}^{(i+1)}-\mathbf{w}^{(i)}\|^{2}.$ (49)

Minimizing both sides of (C) with respect to $\mathbf{w}^{(i+1)}$, it follows

$\displaystyle\min_{\mathbf{w}^{(i+1)}}L(\mathbf{w}^{(i+1)})$
$\displaystyle\geq\min_{\mathbf{w}^{(i+1)}}[L(\mathbf{w}^{(i)})+\left(\mathbf{g}^{(i)}\right)^{T}\left(\mathbf{w}^{(i+1)}-\mathbf{w}^{(i)}\right)$
$\displaystyle+\frac{\mu}{2}\|\mathbf{w}^{(i+1)}-\mathbf{w}^{(i)}\|^{2}].$
(50)

The minimization of the left-hand side of (C) is achieved when
$\mathbf{w}^{(i+1)}=\mathbf{w}^{*}$, while the right-hand side of (C) is
minimized when
$\mathbf{w}^{(i+1)}=\mathbf{w}^{(i)}-\frac{1}{\mu}\mathbf{g}^{(i)}$. Based on
this, we have

$\displaystyle\|\mathbf{g}^{(i)}\|^{2}\geq
2\mu\left(L(\mathbf{w}^{(i)})-L(\mathbf{w}^{*})\right).$ (51)

Combining (C) with the one-round convergence rate in (2), we obtain

$\displaystyle\mathbb{E}\\{L(\mathbf{w}^{(i+1)})-L(\mathbf{w}^{*})\\}\leq\mathbb{E}\\{L(\mathbf{w}^{(i)})-L(\mathbf{w}^{*})\\}$
$\displaystyle-2\mu\eta^{(i)}\mathbb{E}\\{L(\mathbf{w}^{(i)})-L(\mathbf{w}^{*})\\}+\frac{\beta(\eta^{(i)})^{2}}{2|\hat{\mathcal{D}}|^{2}}\Delta(\bm{\mathcal{M}}^{(i)})$
$\displaystyle=(1-2\mu\eta^{(i)})\mathbb{E}\\{L(\mathbf{w}^{(i)})-L(\mathbf{w}^{*})\\}+\frac{\beta(\eta^{(i)})^{2}}{2|\hat{\mathcal{D}}|^{2}}\Delta(\bm{\mathcal{M}}^{(i)})$
$\displaystyle\mathop{\leq}\limits^{(\mathrm{recursively})}\prod\limits_{t=1}^{i}(1-2\mu\eta^{(t)})\mathbb{E}\\{L(\mathbf{w}^{(1)})-L(\mathbf{w}^{*})\\}$
$\displaystyle+\frac{\beta}{2|\hat{\mathcal{D}}|^{2}}\sum_{t=1}^{i}{A^{(t)}(\eta^{(t)})^{2}\Delta(\bm{\mathcal{M}}^{(t)})},$
(52)

with $A^{(t)}=\prod\limits_{j=t+1}^{i}(1-2\mu\eta^{(j)})$, we obtain Lemma 3.

##  Appendix D Proof of Lemma 4

We first point out that the term of
$\left\|\bm{\delta}^{(i)}-\bm{\delta}^{{\dagger}(i)}\right\|^{2}$ can be
represented as
$\left\|\bm{\delta}^{(i)}-\bm{\delta}^{{\dagger}(i)}\right\|^{2}=\sum_{k\in\mathcal{K}}{\sum_{j\in\mathcal{J}_{k}}{\left(\delta_{k,j}^{(i)}-\delta_{k,j}^{{\dagger}(i)}\right)^{2}}}$.
Based on the $\lambda$-representation technique [43], the integer convex
function ${\left(\delta_{k,j}^{(i)}-\delta_{k,j}^{{\dagger}(i)}\right)^{2}}$
is equivalent to the following linear problem

$\displaystyle\min_{a_{k,j},b_{k,j}}\left(\delta_{k,j}^{{\dagger}(i)}\right)^{2}a_{k,j}+\left(1-\delta_{k,j}^{{\dagger}(i)}\right)^{2}b_{k,j}$
(53) $\displaystyle\mathrm{s.t.}\ b_{k,j}=\delta_{k,j},$ $\displaystyle\quad\
a_{k,j}+b_{k,j}=1,$ $\displaystyle\quad\ a_{k,j}\geq 0,\ b_{k,j}\geq 0.$

Then, on the basis of the problem in (53), we can equivalently rewrite the
problem in (38) as

$\displaystyle\min_{\bm{\delta}^{(i)},\bm{a},\bm{b}}\sum_{k\in\mathcal{K}}{\sum_{j\in\mathcal{J}_{k}}}{\left[(\delta_{k,j}^{{\dagger}})^{2}a_{k,j}+(1-\delta_{k,j}^{{\dagger}})^{2}b_{k,j}\right]}$
(54) $\displaystyle\mathrm{s.t.}\
(\ref{consOfDataSelDelta01}),(\ref{consOfDataSelDelta02}),(\ref{consOfrepresent01}),(\ref{consOfrepresent02}),(\ref{consOfrepresent03}).$

Note that (54) is a mixed integer problem and its constraint matrix is totally
unimodular. As such, we can relax the binary constraint in (24) to (35)
without any loss of optimality, that is, the problems in (54) and (39) are
equivalent. Given the equivalence between the problems in (38) and (54), we
can conclude that the problems in (38) and (39) are equivalent.

## References

  * [1] C. Syst. and S. Jose, “Cisco annual internet report (2018-2023),” CA, USA, Mar. 2020.
  * [2] 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. Surv. Tutor._ , vol. 22, no. 3, pp. 2031–2063, 2020.
  * [3] S. K. Lo, Q. Lu, C. Wang, H.-Y. Paik, and L. Zhu, “A systematic literature review on federated machine learning: From a software engineering perspective,” _ACM Comput. Surv._ , vol. 54, no. 5, 2021.
  * [4] W. Cheng, Y. Zou, J. Xu, and W. Liu, “Dynamic games for social model training service market via federated learning approach,” _IEEE Transactions on Computational Social Systems_ , vol. 9, no. 1, pp. 64–75, 2022.
  * [5] K. Guo, T. Chen, S. Ren, N. Li, M. Hu, and J. Kang, “Federated learning empowered real-time medical data processing method for smart healthcare,” _IEEE/ACM Transactions on Computational Biology and Bioinformatics_ , 2022\.
  * [6] J. Zhao, X. Chang, Y. Feng, C. H. Liu, and N. Liu, “Participant selection for federated learning with heterogeneous data in intelligent transport system,” _IEEE transactions on intelligent transportation systems_ , vol. 24, no. 1, pp. 1106–1115, 2022.
  * [7] 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.
  * [8] Q. Zeng, Y. Du, K. Huang, and K. K. Leung, “Energy-efficient radio resource allocation for federated edge learning,” in _Proc. IEEE Int. Conf. Commun. Workshops (ICC Workshops)_ , Jun. 2020, pp. 1–6.
  * [9] B. Luo, X. Li, S. Wang, J. Huang, and L. Tassiulas, “Cost-effective federated learning in mobile edge networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 12, pp. 3606–3621, 2021.
  * [10] X. Mo and J. Xu, “Energy-efficient federated edge learning with joint communication and computation design,” _J. Commun. Inf. Netw._ , vol. 6, no. 2, pp. 110–124, Jun. 2021.
  * [11] X. Ma, H. Sun, and R. Q. Hu, “Scheduling policy and power allocation for federated learning in noma based mec,” in _GLOBECOM 2020 - 2020 IEEE Global Communications Conference_ , 2020, pp. 1–7.
  * [12] J. Ren, Y. He, D. Wen, G. Yu, K. Huang, and D. Guo, “Scheduling for cellular federated edge learning with importance and channel awareness,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 11, pp. 7690–7703, Nov. 2020.
  * [13] W. Shi, S. Zhou, and Z. Niu, “Device scheduling with fast convergence for wireless federated learning,” in _Proc. IEEE Int. Conf. Commun. (ICC)_ , Jun. 2020, pp. 1–6.
  * [14] M. M. Wadu, S. Samarakoon, and M. Bennis, “Joint client scheduling and resource allocation under channel uncertainty in federated learning,” _IEEE Trans. Commun._ , vol. 69, no. 9, pp. 5962–5974, 2021.
  * [15] X. Cao, G. Zhu, J. Xu, Z. Wang, and S. Cui, “Optimized power control design for over-the-air federated edge learning,” _IEEE Journal on Selected Areas in Communications_ , vol. 40, no. 1, pp. 342–358, 2021.
  * [16] 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, 2021.
  * [17] 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, 2021.
  * [18] C. T. Dinh, N. H. Tran, M. N. H. Nguyen, C. S. Hong, W. Bao, A. Y. Zomaya, and V. Gramoli, “Federated learning over wireless networks: Convergence analysis and resource allocation,” _IEEE-ACM Trans. Netw._ , vol. 29, no. 1, pp. 398–409, 2021.
  * [19] W. Wen, Z. Chen, H. H. Yang, W. Xia, and T. Q. S. Quek, “Joint scheduling and resource allocation for hierarchical federated edge learning,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 8, pp. 5857–5872, 2022.
  * [20] Y. Wu, Y. Song, T. Wang, L. Qian, and T. Q. S. Quek, “Non-orthogonal multiple access assisted federated learning via wireless power transfer: A cost-efficient approach,” _IEEE Transactions on Communications_ , vol. 70, no. 4, pp. 2853–2869, 2022.
  * [21] X. Lin, J. Wu, J. Li, X. Zheng, and G. Li, “Friend-as-learner: Socially-driven trustworthy and efficient wireless federated edge learning,” _IEEE. Trans. Mob. Comput._ , vol. 22, no. 1, pp. 269–283, 2023.
  * [22] S. Feng, D. Niyato, P. Wang, D. I. Kim, and Y.-C. Liang, “Joint service pricing and cooperative relay communication for federated learning,” in _Proc. IEEE Int. Conf. Green Comput. Commun. (GreenCom)_ , 2019, pp. 815–820.
  * [23] W. Y. B. Lim, J. S. Ng, Z. Xiong, J. Jin, Y. Zhang, D. Niyato, C. Leung, and C. Miao, “Decentralized edge intelligence: A dynamic resource allocation framework for hierarchical federated learning,” _IEEE Trans. Parallel Distrib. Syst._ , vol. 33, no. 3, pp. 536–550, 2022.
  * [24] A. Li, L. Zhang, J. Tan, Y. Qin, J. Wang, and X.-Y. Li, “Sample-level data selection for federated learning,” in _Proc. IEEE INFOCOM_ , May 2021, pp. 1–10.
  * [25] T. Tuor, S. Wang, B. J. Ko, C. Liu, and K. K. Leung, “Overcoming noisy and irrelevant data in federated learning,” in _Proc. Int. Conf. Pattern Recognit (ICPR)_ , Jan. 2021, pp. 5020–5027.
  * [26] Y. He, J. Ren, G. Yu, and J. Yuan, “Importance-aware data selection and resource allocation in federated edge learning system,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 11, pp. 13 593–13 605, Nov. 2020.
  * [27] A. Albaseer, M. Abdallah, A. Al-Fuqaha, and A. Erbad, “Threshold-based data exclusion approach for energy-efficient federated edge learning,” in _Proc. IEEE Int. Conf. Commun. Workshops (ICC Workshops)_ , Jun. 2021, pp. 1–6.
  * [28] A. M. Albaseer, M. Abdallah, A. Al-Fuqaha, and A. Erbad, “Fine-grained data selection for improved energy efficiency of federated edge learning,” _IEEE Trans. Netw. Sci. Eng._ , vol. 9, no. 5, pp. 3258–3271, 2021.
  * [29] Y. Mao, J. Zhang, and K. B. Letaief, “Dynamic computation offloading for mobile-edge computing with energy harvesting devices,” _IEEE J. Sel. Areas Commun._ , vol. 34, no. 12, pp. 3590–3605, 2016.
  * [30] S. Han, X. Xu, X. Tao, and P. Zhang, “Joint power and sub-channel allocation for secure transmission in noma-based mmtc networks,” _IEEE Syst. J._ , vol. 13, no. 3, pp. 2476–2487, 2019.
  * [31] M. Zeng, A. Yadav, O. A. Dobre, and H. V. Poor, “Energy-efficient joint user-rb association and power allocation for uplink hybrid noma-oma,” _IEEE Internet Things J._ , vol. 6, no. 3, pp. 5119–5131, Jun. 2019.
  * [32] B. Zhu, K. Chi, J. Liu, K. Yu, and S. Mumtaz, “Efficient offloading for minimizing task computation delay of noma-based multiaccess edge computing,” _IEEE Transactions on Communications_ , vol. 70, no. 5, pp. 3186–3203, 2022\.
  * [33] S. Zhang, X. Wang, Z. Shi, and J. Liu, “Reinforcement learning based rss-threshold optimization for d2d-aided htc/mtc in dense noma systems,” _IEEE Transactions on Wireless Communications_ , 2023.
  * [34] Z. Shi, J. Liu, S. Zhang, and N. Kato, “Multi-agent deep reinforcement learning for massive access in 5g and beyond ultra-dense noma system,” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 5, pp. 3057–3070, 2021.
  * [35] Z. Shi and J. Liu, “Sparse code multiple access assisted resource allocation for 5g v2x communications,” _IEEE Transactions on Communications_ , vol. 70, no. 10, pp. 6661–6677, 2022.
  * [36] M. Avriel, _Nonlinear Programming: Analysis and Methods_ , ser. Prentice-Hall series in automatic computation. Englewood Cliffs, NJ, USA: Prentice-Hall, 1976.
  * [37] E. Bodine-Baron, C. Lee, A. Chong, B. Hassibi, and A. Wierman, “Peer effects and stability in matching markets,” in _Proc. Lect. Notes Comput. Sci. (LNCS)_ , 2011.
  * [38] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.1,” http://cvxr.com/cvx, Mar. 2014.
  * [39] T. Lipp and S. Boyd, “Variations and extension of the convex–concave procedure,” _Optim. Eng._ , vol. 17, no. 2, pp. 263–287, Jun. 2016.
  * [40] Y. Sun, P. Babu, and D. P. Palomar, “Majorization-minimization algorithms in signal processing, communications, and machine learning,” _IEEE Trans. Signal Process._ , vol. 65, no. 3, pp. 794–816, 2017.
  * [41] Y. Jiang, Z. Huang, and D. H. Tsang, “On power-peak-aware scheduling for large-scale shared clusters,” _IEEE Trans. Big Data_ , vol. 6, no. 2, pp. 412–426, 2020.
  * [42] C.-Y. Hsu, S.-Y. Shaw, and H.-J. Wong, “Refinements of generalized triangle inequalities,” _J. Math. Anal. Appl._ , vol. 344, no. 1, pp. 17–31, 2008\.
  * [43] R. R. Meyer, “A class of nonlinear integer programs solvable by a single linear program,” _SIAM J. Control Optim._ , vol. 15, no. 6, pp. 935–946, 1977.