# Federated Learning via Unmanned Aerial Vehicle

Min Fu, , Yuanming Shi, , and Yong Zhou  M. Fu is with the Department of
Electrical and Computer Engineering, National University of Singapore,
Singapore 117583 (e-mail: fumin@u.nus.edu). Y. Shi and Y. Zhou are with School
of Information Science and Technology, ShanghaiTech University, Shanghai
201210, China (e-mail: {shiym, zhouyong}@shanghaitech.edu.cn).

###### Abstract

To enable communication-efficient federated learning (FL), this paper studies
an unmanned aerial vehicle (UAV)-enabled FL system, where the UAV coordinates
distributed ground devices for a shared model training. Specifically, by
exploiting the UAV’s high altitude and mobility, the UAV can proactively
establish short-distance line-of-sight links with devices and prevent any
device from being a communication straggler. Thus, the model aggregation
process can be accelerated while the cumulative model loss caused by device
scheduling can be reduced, resulting in a decreased completion time. We first
present the convergence analysis of FL without the assumption of convexity,
demonstrating the effect of device scheduling on the global gradients. Based
on the derived convergence bound, we further formulate the completion time
minimization problem by jointly optimizing device scheduling, UAV trajectory,
and time allocation. This problem explicitly incorporates the devices’ energy
budgets, dynamic channel conditions, and convergence accuracy of FL
constraints. Despite the non-convexity of the formulated problem, we exploit
its structure to decompose it into two sub-problems and further derive the
optimal solutions via the Lagrange dual ascent method. Simulation results show
that the proposed design significantly improves the tradeoff between
completion time and prediction accuracy in practical FL settings compared to
existing benchmarks.

###### Index Terms:

Federated leaning, UAV communications, completion time minimization, device
scheduling, and UAV trajectory design.

##  I Introduction

As the storage and computation capabilities of edge devices keep growing, it
becomes more attractive to process the data locally and push network
computation to the edge [1, 2, 3]. In the field of machine learning (ML),
distributed learning frameworks [4, 5] that keep the training data locally are
well developed to protect data privacy and reduce network energy/time costs.
Recently, federated learning (FL) [4, 5, 1] has been proposed as a promising
solution for distributed ML, which enables multiple devices to execute local
training on their own dataset and collaboratively build a shared ML model with
the coordination of a parameter server (PS) (e.g., access point and base
station). Since only model parameters rather than raw data are exchanged
between devices and the PS, FL significantly relieves the communication burden
and protects data privacy[4, 6] with wide-field applications, e.g., vehicle-
to-vehicle communications [7] and content recommendations for smartphones[5].

In contrast to the centralized ML, the PS in FL needs to exchange models with
multiple devices over hundreds to thousands of communication rounds to achieve
the desired training accuracy. However, the main challenge in realizing FL on
wireless networks arises from communication stragglers with unfavorable links
[8, 9]. For example, in over-the-air computation (AirComp)-based analog FL [6,
10], communication stragglers dominate the overall model aggregation error
caused by channel fading and communication noise since the devices with better
channel qualities have to reduce their transmit power for the local models’
alignment at the PS. Moreover, in digital synchronous FL [11, 8],
communication stragglers significantly slow down the model aggregation process
and dominate cumulative communication delay since the PS must wait until
receiving the training updates from all participants. If the number of
communication stragglers is high, the overall communication delay will be
unacceptable. The straggler issue is thus the main bottleneck to design
communication-efficient FL systems.

There have been many efforts to mitigate the communication straggler effect in
FL, such as device scheduling [6, 10, 11]. For instance, to reduce model
misalignment error incurred by stragglers in AirComp-based FL, the authors in
[6, 10] scheduled the devices with reliable channels for concurrent model
uploading. In addition, to reduce the communication delay incurred by
stragglers in digital FL, devices with large contributions to the global model
[11] or/and with favorable channel conditions [12, 13] are generally selected.
Nevertheless, because such device scheduling is biased, which results in a
smaller amount of training data utilized, this, in turn, may damage the update
of the global model and decrease the learning performance of FL. To alleviate
such communication-learning tradeoff, recent research has investigated the
integration of advanced technologies (i.e., relays [14], reconfigurable
intelligent surfaces [15, 16, 17]) into FL systems to improve stragglers’
communication qualities and thus further upgrade device scheduling policy for
the reduction of communication errors. These existing frameworks require a
terrestrial BS to provide network coverage to the devices for model
aggregation. However, many FL tasks need to be performed under the
circumstances when terrestrial networks are unavailable in remote areas. For
example, devices from multiple regions (e.g., forests and woodlands) can
collaborate through FL to build a learning model for fire monitoring [18].
Under these harsh environments, it is imperative to deploy a more flexible PS
that proactively establishes favorable communication links among devices.

As a viable complementary alternative to terrestrial networks, unmanned aerial
vehicles (UAVs) can provide coverage extension and seamless connectivity to
support various FL tasks, especially in distant and underdeveloped areas [19,
20, 21]. Inspired by this, this paper studies a UAV-enabled FL network, where
a UAV is dispatched as a flying PS to aggregate and update the digital FL
model parameters when no terrestrial BS is available. To mitigate the
communication straggler effect in UAV-enabled FL networks, we propose to
jointly design UAV trajectory and device scheduling. First, the qualities of
communication channels between the UAV and devices still differ since all
links’ channel conditions depend on the UAV’s location at each time slot. To
address this issue, device scheduling is necessary to prevent communication
stragglers. Furthermore, by utilizing its mobility, the UAV can establish
short-distance LoS links to scheduled devices. As a result, each scheduled
device achieves a high data rate for model uploading, resulting in faster
model uploads/downloads per round compared to the static UAV. In addition,
with its ability to dynamically adjust communication distances, the UAV can
prevent any device from being a communication straggler all the time, ensuring
that all devices have the opportunity to participate in FL training. As such,
incorporated with UAV trajectory planning, the optimized device scheduling
strategy focuses on data exploitation maximization, thereby reducing
cumulative model aggregation loss and accelerating FL convergence. Hence, such
join design in UAV-enabled FL networks is an appealing solution to address the
straggler issue and reduce communication time.

Motivated by the above observations, in this paper, we focus on the time
required for completing the FL training process [22, 23], which includes not
only the computation time but also the communication time of all scheduled
devices. The completion time is a critical design aspect in UAV-enabled
systems, as UAVs usually have a limited endurance due to the practical
physical constraints [24]. Additionally, devices generally have a limited
energy budget without battery replacement or recharging [9]. Thus, the
formulated optimization problem needs to consider not only the FL constraints
such as the target convergence accuracy level but also the devices’ dynamic
communication conditions such as energy consumption. As such, this paper aims
to minimize the completion time of UAV-enabled FL by jointly optimizing the
UAV trajectory, device scheduling, and time allocation for energy-constrained
devices, while ensuring that the FL algorithm can converge to a target
accuracy.

###  I-A Contributions

The main contributions of this paper are summarized as follows.

  * •

We consider a novel UAV-enabled FL framework, where a mobile UAV is dispatched
as a PS to exchange the model parameters with devices, thereby preventing
devices from being communication stragglers. Moreover, under the convergence
accuracy of FL constraint, we mainly focus on the completion time minimization
problem for UAV-enabled FL systems. This consideration is of paramount
importance for latency-critical FL applications and limited endurance UAV
systems.

  * •

We first derive an upper bound on the iterative norm of the global gradients
for non-convex loss functions, taking model update errors from device
selection into account. Specifically, the analytical bound shows that the
device selection loss causes convergence rate reduction and leads to a non-
diminishing gap between the initial model and the global optimum of the
training loss.

  * •

Based on the convergence bound, we formulate the completion time minimization
problem by jointly designing device scheduling, communication time allocation
for scheduled devices, and trajectory planning for UAV, taking into account
the target convergence accuracy of FL, energy budget at devices, and practical
constraints at the UAV. Besides, we quantitatively analyze the fundamental
tradeoff between learning accuracy and communication latency, and demonstrate
the importance of the mobile UAV in the proposed system.

  * •

Although the formulated mixed-integer nonconvex problem is high intractable,
we propose an efficient iterative block coordinate descent (BCD) algorithm to
solve the joint device scheduling and time allocation optimization subproblem
and the UAV trajectory optimization subproblem alternately, which is
guaranteed to converge. Moreover, to reduce computational complexity, each
optimization subproblem is solved optimally with a closed-form solution by
applying the Lagrange duality method.

Simulation results in realistic federated settings are provided to illustrate
the learning-communication tradeoff and validate the effectiveness of the
proposed scheme. Specifically, the proposed joint design scheme outperforms
existing benchmark schemes in terms of mission completion time, which is
appealing in light of the limited endurance of UAVs. Moreover, our proposed
scheme provides comparable performance to the full-scheduling ideal benchmark
in terms of prediction accuracy, even when the target convergence accuracy of
FL is relatively large.

###  I-B Related Work

####  I-B1 UAV Assisted FL Networks

Upon the completion of this work, the application of UAV in FL networks was
investigated in some parallel works [25, 26, 27, 28] Specifically, the authors
in [25] developed a novel FL framework with UAV swarms to improve the FL
learning efficiency. The authors in [26] proposed an FL-based sensing and
collaborative learning approach for UAV-enabled internet of vehicles (IoVs),
where UAVs as devices collect data and train ML models for IoVs. In addition,
[27] described using UAVs as flight relays to support wireless communication
between IoVs and the FL server, thus enhancing FL accuracy. The authors in
[28] studied the deployment of multiple UAVs as flying BSs to minimize the
weighted sum of FL execution time and function loss. Nevertheless, this work
does not consider device budget issues that may affect FL performance and
convergence cannot be guaranteed.

####  I-B2 Latency Minimization Problems in FL Networks

A few works have studied the completion time minimization problems in
different FL scenarios. The authors in [22] formulated an FL framework over a
wireless network as an optimization problem that minimizes the sum of FL
aggregation latency and total device energy consumption. In addition, the
authors in [29] investigated the tradeoff between the FL convergence time and
devices’ energy consumption. However, in [22, 29], all devices are assumed to
be involved in each round.

###  I-C Organization

The remainder of this paper is organized as follows. Section II describes the
FL via the UAV system model. In Section III, we provide the convergence
analysis of FL and completion time minimization problem formulation. In
Section IV, we propose a BCD method to solve the formulated problem. Section V
presents the numerical results to evaluate the performance of the proposed
algorithm. Finally, we conclude this paper in Section VI.

Notations: In this paper, scalars, column vectors and matrices are written in
italic letters, boldfaced lower-case letters and boldfaced upper-case letters
respectively, e.g., $a$, $\mathbf{a}$, $\mathbf{A}$. $\mathbb{R}^{M\times N}$
denotes the space of a real-valued matrix with $M$ rows and $N$ columns.
$\left\|\mathbf{a}\right\|_{2}$ denotes the Euclidean norm of vector
$\mathbf{a}$ and $\mathbf{a}^{T}$ represents its transpose. $|\mathcal{S}|$
denotes the cardinality of the set $\mathcal{S}$. $\langle\cdot,\cdot\rangle$
represents the inner product.

##  II System Model

We consider a UAV-assisted FL network that consists of a single-antenna UAV
and a set $\mathcal{K}$ of $K$ single-antenna devices, aiming to
collaboratively learn an ML model (e.g., logistic regression and linear
regression). Since the terrestrial BSs are usually sparsely deployed or
unavailable in rural, remote, and underdeveloped areas, we deploy an UAV with
a powerful processor to act as a PS in these harsh circumstances.

Each device $k$ has a local dataset $\mathcal{D}_{k}$ with size $D_{k}$. Local
dataset $\mathcal{D}_{k}$ is a collection of data samples
$\\{\bm{x}_{ki},y_{ki}\\}_{i=1}^{D_{k}}$, where $\bm{x}_{ki}\in\mathbb{R}^{d}$
is the input sample vector with $d$ features and $y_{ki}\in\mathbb{R}$ is the
label for sample $\bm{x}_{ki}$. The UAV-enabled FL system aims to
cooperatively learn an ML model under the coordination of the UAV in an
iterative manner while keeping the local training data on mobile devices. In
the sequel, we describe FL over UAV-enabled wireless networks, as summarized
in Algorithm 1.

1: Input: $\eta$, $\bm{w}_{0}=\bm{0}$, $n=0$;

2: repeat

3: Update $n=n+1$.

4: Device Scheduling: Denote the set of scheduled devices $k$ in the $n$-th
round as $\mathcal{A}_{n}$.

5: Computation: All devices in set $\mathcal{A}_{n}$ receive $\bm{w}_{n-1}$
from the server, and update their local FL models denoted as
$\bm{w}_{k,n},k\in\mathcal{A}_{n}$ according to (4) in parallel.

6: Communication: All the scheduled devices $k\in\mathcal{A}_{n}$ transmit
$\bm{w}_{k,n}$ to the UAV over TDMA.

7: Aggregation and Feedback: The UAV updates the global model $\bm{w}_{n}$ as
in (5), and then feed-back the updated global model to devices.

8: until $n=N$

9: Output: the global model $\bm{w}_{N}$

Algorithm 1 FL over UAV-enabled wireless networks

###  II-A FL Training Model

Let $\bm{w}\in\mathbb{R}^{d}$ and $\bm{w}_{k}\in\mathbb{R}^{d}$ be the global
model parameters at the UAV and the local model parameters at the $k$-th
device, respectively. The local loss function of device $k$ is defined as

$\displaystyle\mathcal{F}_{k}(\bm{w})=\frac{1}{D_{k}}\sum_{i=1}^{D_{k}}f(\bm{w};\bm{x}_{ki},y_{ki}),\forall
k\in\mathcal{K}.$ (1)

Accordingly, the global loss function at the UAV is given by

$\displaystyle\mathcal{F}(\bm{w}):=\frac{1}{D}\sum_{k=1}^{K}D_{k}\mathcal{F}_{k}(\bm{w}),$
(2)

where $D$ denotes the total size of data with $D=\sum_{k=1}^{K}D_{k}$. The
training of an FL algorithm aims to solve the following optimization problem:

$\displaystyle\mathop{\text{minimize}}_{\bm{w}_{1},\ldots,\bm{w}_{K}}$
$\displaystyle\frac{1}{D}\sum_{k=1}^{K}\sum_{i=1}^{D_{k}}f(\bm{w}_{k};\bm{x}_{ki},y_{ki})$
subject to $\displaystyle\bm{w}_{1}=\cdots=\bm{w}_{K}=\bm{w},$ (3)

where constraint (3) is used to ensure that all devices and the server have
the same model after the FL algorithm converges. To solve problem (II-A), the
training procedure of FL consists of multiple communication rounds. Therein,
in a communication round, the devices update the local models based on their
own data and a common model initialization from the PS. After that, they
contribute to the global model at the PS by uploading model updates over the
wireless channel, as described below.

First, the UAV determines the set of devices that participate in the current
round. Let $a_{k}[n]\in\\{0,1\\}$ denote the scheduling variable for device
$k$ in the $n$-th round. Therein, $a_{k}[n]=1$ indicates that device $k$ sends
its updated local model to the UAV at communication round $n$; otherwise we
have $a_{k}[n]=0$. $\mathcal{A}_{n}$ is defined as the set of scheduled
devices in the $n$-th round. Then, the UAV broadcasts the current global
model, denoted by $\bm{w}_{n-1}$, to all the scheduled devices.

Each scheduled device $k\in\mathcal{A}_{n}$ receives the global model and
updates its local model by applying the gradient descent algorithm [11, 8] on
its local dataset:

$\displaystyle\bm{w}_{k,n}=\bm{w}_{n-1}-\frac{\eta}{D_{k}}\sum_{(x_{ki},y_{ki})\in\mathcal{D}_{k}}\bigtriangledown
f(\bm{w}_{n-1};\bm{x}_{ki},y_{ki}),$ (4)

where $\eta$ is the learning rate and $\bigtriangledown
f(\bm{w}_{n-1};\bm{x}_{ki},y_{ki})$ is the gradient of
$f(\bm{w};\bm{x}_{ki},y_{ki})$ with respect to $\bm{w}$ at $\bm{w}_{n-1}$.

After all scheduled devices upload their local models, the UAV aggregates them
to obtain the following consolidated global model

$\displaystyle\bm{w}_{n}=\frac{\sum_{k=1}^{K}a_{k}[n]\bm{w}_{k,n}}{\sum_{k=1}^{K}a_{k}[n]},$
(5)

where $\bm{w}_{n}$ is the global model updated at the UAV in the $n$-th round.
With (4) and (5), the UAV and the devices can repeatedly update their models
until the maximum number of communication rounds reaches. As the local FL
models are updated at the scheduled devices and transmitted over wireless
cellular links, device scheduling determines both the learning performance and
communication delay. Furthermore, the channel conditions between the UAV and
devices vary over different time slots due to the mobility of the UAV. Hence,
device scheduling should be optimized along with the time allocation and UAV
trajectory to account for time-varying channel conditions and the target
convergence accuracy required of FL. In the next subsection, we elaborate on
the communication and computation models of FL over UAV-enabled networks.

###  II-B UAV-enabled Transmission

Without loss of generality, we consider a three-dimensional (3D) Cartesian
coordinate. Each ground device is fixed to the ground. The horizontal
coordinate of ground device $k$ is denoted as
$\mathbf{u}_{k}=[\tilde{x}_{k},\tilde{y}_{k}]\in\mathbb{R}^{1\times 2}$ with
$\tilde{x}_{k}$ and $\tilde{y}_{k}$ being $x$\- and $y$-coordinates,
respectively. We assume each ground device is known from the UAV, which flies
at a fixed height $H$ m above the ground. In practice, $H$ corresponds to the
minimum altitude at which obstacles can be avoided without needing frequent
aircraft ascended and descended.

In this paper, we suppose that the total number of communication rounds
denoted by $N$ is fixed. We focus on the time required for the UAV to complete
the FL process, wherein the corresponding variable is denoted as $T$. To
facilitate trajectory design, we adopt the time-discretization technique to
divide the mission duration $T$ into $N$ unequal time slots, wherein the
$n$-th slot duration is expressed as $\delta[n]$ with
$\sum_{n=1}^{N}\delta[n]=T$. Note that $\\{\delta[n]\\}$ and $T$ are variables
in this paper. We denote the location of the UAV at time slot $n$ projected on
the horizontal (ground) plane as $\bm{q}[n]=[x[n],y[n]]\in\mathbb{R}^{1\times
2}$, with $x[n]$ and $y[n]$ being $x$\- and $y$-coordinates at time slot $n$,
respectively. In addition, we consider the scenario where the initial location
of the UAV is pre-deployed, the horizontal coordinate of which is denoted as
$\bm{q}_{F}=[x_{F},y_{F}]\in\mathbb{R}^{1\times 2}$. This is because the
initial location corresponds to the practical mobility constraint on the UAV
such as the UAV’s launching location or its pre-mission flying paths, etc. We
assume that the link between each device and the UAV is dominated by the LoS
channel because UAVs usually fly at high altitudes for safety reasons, as most
existing studies on UAVs [30, 31, 21]. Following the free-space path loss
model [30], the channel gain between device $k$ and the UAV at time slot $n$
is given by

$\displaystyle{h}_{k}[n]=\beta_{0}d_{k}^{-2}[n]=\frac{\beta_{0}}{{H^{2}+\|\bm{q}[n]-\mathbf{u}_{k}\|_{2}^{2}}},$
(6)

where $\beta_{0}$ represents the channel gain at the reference distance of 1
meter and $d_{k}[n]$ is the distance between device $k$ and the UAV at time
slot $n$.

The distance moved by the UAV in the $n$-th slot is subject to the following
constraint

$\displaystyle\|\bm{q}[n]\\!-\\!\bm{q}[n-1]\|_{2}\\!\leq\\!\min\\{V_{\max}\delta[n],\Delta
q_{\max}\\},n=1,\ldots,N,$ (7)

where $V_{\max}$ is the maximum UAV speed, and $\Delta q_{\max}$ is an
appropriately chosen value with $\Delta q_{\max}\ll H$ such that channel gain
during each round is assumed to be unchanged.

Figure 1: The illustration of UAV-enabled transmission scheme to support FL.

Each time interval $\delta[n]$ consists of four stages, namely, the local
computation stage, the local model uploading stage, the global computation
stage, and the global model downloading stage, as shown in Fig. 1.

####  II-B1 Local Computation

We denote the required number of processing cycles for computing one data
sample at device $k$ by $c_{k}$, which can be measured offline and is known as
a prior. Since all samples $\\{\bm{x}_{ki},y_{ki}\\}_{i\in\mathcal{D}_{k}}$
have the same size (i.e., number of bits), the number of CPU cycles required
for device $k$ to run one local round is $c_{k}D_{k}$. By denoting the CPU-
cycle frequency of the device $k$ by $f_{k}$, the computation time per round
of device $k$ is given by

$\displaystyle t_{k}^{\text{comp}}=\frac{c_{k}D_{k}}{f_{k}}.$ (8)

The CPU energy consumption of device $k$ for the $n$-th round of local
computation is [22]

$\displaystyle
E_{k}^{\text{comp}}[n]=a_{k}[n]\sum_{i=1}^{c_{k}D_{k}}\frac{\alpha_{k}}{2}f_{k}^{2}=a_{k}[n]\frac{\alpha_{k}}{2}c_{k}D_{k}f_{k}^{2},$
(9)

where $\alpha_{k}/2$ is the effective capacitance coefficient of device $k$’s
computing chipset. Similar to [22], we consider the synchronous operation that
requires all scheduled devices to simultaneously train their local models and
complete their training before entering the communication phase. Thus, the
time cost for local model training at the $n$-th round is given by [22]

$\displaystyle t^{\text{comp}}[n]=\max_{k}\\{a_{k}[n]t_{k}^{\text{comp}}\\}.$
(10)

Hence, the computing time in one local round is determined by scheduled
devices with large date sizes and low CPU frequency.

####  II-B2 Local Model Uploading

In the local model uploading stage, to avoid interference among devices during
the uploading process, TDMA [22] is adopted as shown in Fig. 1. Specifically,
in the local model uploading stage, $|\mathcal{A}_{n}|$ devices send their
respective local models one by one during slot $n$. The achievable data rate
(bit/s) of devices $k$ at the $n$-th round is defined as

$\displaystyle
r_{k}[n]=B\log_{2}\Big{(}1+\frac{p_{k}[n]h_{k}[n]}{\sigma^{2}}\Big{)},$ (11)

where $B$ is the system bandwidth in Hertz, $p_{k}[n]$ is the transmit power
of device $k$ at the $n$-th round, and $\sigma^{2}$ is the power of the
additional complex Gaussian noise. Let $\tau_{k}[n]$ denote the duration in
which device $k$ transmits its local model to the UAV at the $n$-th round. We
assume that the dimension of the model parameter vector is fixed throughout
the FL process, denoted by $s$ (in bits). The uploading time of device $k$ can
be calculated as

$\displaystyle\tau_{k}[n]=\frac{a_{k}[n]s}{r_{k}[n]}.$ (12)

With a given data size, the larger the channel gain, the shorter the required
uploading time. The UAV can shorten the uploading time of scheduled devices by
establishing LoS connections and shortening communication distances with the
devices. By combining (11) and (12), to transmit $s$ within a time duration
$\tau_{k}[n]$, the device $k$’s energy consumption is

$\displaystyle
E_{k}^{\text{comm}}[n]=\frac{\tau_{k}[n]\sigma^{2}}{h_{k}[n]}\Big{(}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}-1\Big{)}.$
(13)

After all scheduled devices upload their local training models
$\\{\bm{w}_{k,n}\\}$ at the $n$-th slot, the UAV performs the global model
update and broadcasts the updated result of length $s$ bits to the devices.
Let $f_{0}$ denote the UAV processor’s fixed computing speed, $c_{0}$ denote
the required number of processing cycles for one local model at the UAV, and
$P_{0}$ denote the transmit power of the UAV. The time that spent on updating
global model and feeding the result back to devices at the UAV is expressed as

$\displaystyle
t^{\text{UAV}}[n]=\frac{Kc_{0}}{f_{0}}+\frac{s}{\min_{k\in\mathcal{A}_{n}}B\log_{2}\Big{(}1+\frac{P_{0}h_{k}[n]}{\sigma^{2}}\Big{)}}.$
(14)

One aspect, comparing to the time of local model computation at any device $k$
denoting $\frac{D_{k}c_{k}}{f_{k}}$, the first term in (14) is negligible. The
reasons are that the UAV has a higher computation capability $f_{0}$ than that
of the devices $f_{k}$ [31]. Moreover, the number of devices $K$ is much
smaller than the size of the local dataset $D_{k}$. The other aspect, the UAV
only needs to broadcast the global model to devices while all the scheduled
devices upload their local models via TDMA. Accordingly, we can infer that
$t^{\text{UAV}}[n]\ll\sum_{k=1}^{K}\tau_{k}[n]+t^{\text{comp}}[n]$, and the
global computation time and the global model downloading time at the UAV are
neglected as in [22], [31]. Thus, the total uploading time of devices can
occupy the rest of the time after local model training at the $n$-th round,
i.e.,

$\displaystyle\sum_{k=1}^{K}\tau_{k}[n]\leq\delta[n]-t^{\text{comp}}[n],\forall
n.$ (15)

##  III Convergence Analysis and Problem Formulation

In this section, we conduct the convergence analysis of UAV-enabled FL, which
characterizes the impact of key system parameters on the convergence
performance, and then formulate a completion time minimization problem, taking
into account communication resource constraints, UAV deployment constraints,
and target convergence accuracy of FL.

###  III-A Convergence Analysis of FL

We follow the literature and make two standard assumptions on the loss
function and local gradients as follows [32, 33, 34, 35, 16, 36, 37].

######  Assumption 1.

(Smoothness). The function $\mathcal{F}$:
$\mathbb{R}^{d}\rightarrow\mathbb{R}$ is $L$-smooth. That is,
$\forall\bm{w},\bm{w}^{\prime}\in\mathbb{R}^{d}$,

$\displaystyle\\!\\!\mathcal{F}(\bm{w})\leq\mathcal{F}(\bm{w}^{\prime})+\langle\nabla\mathcal{F}(\bm{w}^{\prime}),\bm{w}-\bm{w}^{\prime}\rangle+\frac{L}{2}\|\bm{w}^{\prime}-\bm{w}\|_{2}^{2}.$
(16)

And the loss function does not have to satisfy the convexity assumption, and
only needs to be lower-bounded, which is the minimal assumption required for
convergence [34, 35].

######  Assumption 2.

(Bounded Loss Function). For any parameter vector $\bm{w}$, the loss function
$\mathcal{F}(\bm{w})$ is lower-bounded by $F^{\star}$.

The following assumption is also standard in the literature [16, 36, 37].

######  Assumption 3.

(Bounded Sample-wise Gradient Norm). For a constant $\kappa>0$, the sample-
wise gradients at local devices are bounded

$\displaystyle\|\nabla f(\bm{w}_{n};\bm{x},y)\|_{2}^{2}\leq\kappa.$ (17)

We use the average gradient norm as an indicator of convergence for FL, which
is widely adopted in the convergence analysis for non-convex loss function
[38, 32]. According to the above assumptions, the average gradient norm can be
bound, explained as follows.

######  Theorem 1.

Suppose that the loss functions satisfy assumptions 1-3, given the learning
rate $0\leq\eta\leq\frac{1}{L}$, after $N$ rounds, the average norm of the
global gradients is upper bounded by

$\displaystyle\frac{1}{N}\sum_{n=0}^{N-1}\|\nabla\mathcal{F}(\bm{w}_{n})\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{2}{N\eta}(\mathcal{F}(\bm{w}_{0})-F^{\star})+\frac{4K\kappa}{ND^{2}}\sum_{n=0}^{N-1}\sum_{k=1}^{K}(1-a_{k}[n+1])D_{k}^{2}.$
(18)

Given rounds $N$, the FL algorithm achieves an $\epsilon$-approximation
solution if [32]

$\displaystyle\frac{1}{N}\sum_{n=0}^{N-1}\|\nabla\mathcal{F}(\bm{w}_{n})\|_{2}^{2}\leq\epsilon,$
(19)

where $\epsilon>0$ is the convergence threshold.

######  Remark 1.

As we can see, the expression (18) comprises two terms. The first term is the
initial optimality gap. For the first term, when the number of communication
rounds, the learning step-size, and the initial model parameter are given, the
initial optimality gap is a constant. The second term is the time-average
aggregation error resulting from the effect of device scheduling. For the
second term, the time-average aggregation error decreases as the number of
scheduled devices increases, particularly when large data-size devices are
scheduled. However, scheduling more devices in one round for model uploading
increases the communication burden and may significantly slow down the model
aggregation process, especially if there are communication stragglers. Thus,
it is crucial to schedule a proper subset of devices to balance training
performance and time consumption.

###  III-B Problem Formulation

Let $\bm{A}=\\{a_{k}[n],\forall n\in\mathcal{N},\forall k\in\mathcal{K}\\}$,
$\bm{\Gamma}=\\{\tau_{k}[n],\forall n\in\mathcal{N},\forall
k\in\mathcal{K}\\}$, $\bm{Q}=\\{\bm{q}[n],\forall n=0,\ldots,N\\}$, and
$\bm{\delta}=\\{\delta[n],\forall n=1,\ldots,N\\}$. In this paper, given the
number of communication rounds $N$, we aim to minimize the completion time of
the FL training process under the target convergence accuracy requirements by
jointly optimizing the devices’ scheduling variables $\bm{A}$, time allocation
$\bm{\Gamma}$, UAV trajectory $\bm{Q}$, and slot intervals $\bm{\delta}$. To
satisfy the convergence requirement in (19), we ensure that the upper bound in
Theorem 1 is less than $\epsilon$. Therefore, the corresponding optimization
problem is formulated as

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\mathop{\text{minimize}}_{\bm{A},\bm{\Gamma},\bm{Q},\bm{\delta}}$
$\displaystyle\sum_{n=1}^{N}\delta[n]$ subject to $\displaystyle
a_{k}[n]\in\\{0,1\\},\forall k\in\mathcal{K},\forall n\in\mathcal{N},$ (20f)
$\displaystyle\sum_{n=1}^{N}\Big{(}E_{k}^{\text{comm}}[n]+E_{k}^{\text{comp}}[n]\Big{)}\leq{E}_{k},\forall
k\in\mathcal{K},$
$\displaystyle\sum_{k=1}^{K}\tau_{k}[n]\\!+\\!\max_{k}a_{k}[n]t_{k}^{\text{comp}}\leq\delta[n],\forall
n\in\mathcal{N},$
$\displaystyle\frac{2}{N\eta}(\mathcal{F}(\bm{w}_{0})-F^{\star})+\frac{4K\kappa}{ND^{2}}\sum_{n=0}^{N-1}\sum_{k=1}^{K}(1-a_{k}[n+1])D_{k}^{2}\leq\epsilon,$
$\displaystyle\bm{q}[0]=\bm{q}_{F},$
$\displaystyle\text{Constraints}~{}\eqref{Cons:Q distance}.$

Constraints (20f) are integer constraints with respect to the devices’
scheduling variables. Constraints (20f) represent the devices’ energy budgets.
Constraints (20f) ensure that the communication and computation time per round
cannot exceed the duration of each time slot. Constraint (20f) denotes the
target convergence accuracy requirement of FL. Constraint (20f) is subject to
the initial location of the UAV. Problem (20) is challenging to solve due to
the following reasons. First, the optimization variables $\bm{A}$ for device
scheduling are binary and thus (20f)-(20f) involve integer constraints.
Second, $E_{k}^{\text{comm}}[n]$ in constraints (20f) are not jointly convex
with respect to the optimization variables $\bm{A},\bm{\Gamma},\bm{Q}$, and
$\bm{\delta}$. Therefore, problem (20) is a mixed-integer non-convex problem,
which is difficult to be optimally solved in general.

###  III-C Problem Analysis

In this subsection, we take a close look at problem (20) and compare our
formulation with those in the existing literature. Furthermore, we discuss
properties of the considered problem formulation and emphasize the necessity
of introducing flying UAVs into the FL system.

The existing works on wireless FL with static terrestrial BS [39, 11, 23] have
made attempts to minimize the completion time under the convergence accuracy
requirements by optimizing device scheduling. Comparing our proposed
formulation with the frameworks in [39, 11, 23], the following differences can
be seen:

  * •

Problem (20) not only considers the learning and adaptive device scheduling,
but also takes into account the practical device’s energy budget and dynamic
channel conditions. Conversely, [39, 11], and [23] do not study these
practical communication issues.

  * •

Given the number of communication rounds, problem (20) explicitly integrates
the target convergence accuracy requirement (i.e., constraint (20f)) into the
completion time minimization. In contrast, the formulated problems in [39, 11]
do not directly show the relationship between learning convergence accuracy
and the completion time.

Prior to solving problem (20), we should check its feasibility. According to
(18), when all devices are scheduled in every communication round, the
convergence bound reaches the minimum value. Therefore, if the minimum value
of the convergence bound is larger than the target convergence accuracy,
problem (20) is infeasible. Moreover, if $E_{k},\forall k$ is not big enough,
the constraints in (20f) may not be satisfied even though the scheduled
devices consume the lowest amount of energy. To sum up, the following
proposition is given to check the feasibility of problem (20).

######  Proposition 1.

Problem (20) is feasible if and only if

$\displaystyle
N\geq\lceil\frac{2(\mathcal{F}(\bm{w}_{0})-F^{\star})}{\epsilon\eta}\rceil\text{~{}and~{}}\sum_{k=1}^{K}E_{k}\geq|\mathcal{S}|\frac{\sigma^{2}sH^{2}\ln
2}{\beta_{0}B},$ (21)

where $|\mathcal{S}|$ denotes the required amount of scheduled devices during
training process, given by $|\mathcal{S}|=\lceil
KN-(\epsilon-\frac{2}{N\eta}(\mathcal{F}(\bm{w}_{0})-F^{\star}))\frac{ND^{2}}{4K\kappa\max_{k}D_{k}^{2}}\rceil.$

###### Proof.

Please refer to Appendix -B. ∎

We show the effect of the target convergence accuracy of FL on the completion
time.

######  Theorem 2.

For problem (20), the objective value is non-increasing with $\epsilon$.

###### Proof.

Please refer to Appendix -C. ∎

Theorem 2 sheds light on the tradeoff between the completion time of FL and
the target convergence accuracy of FL due to the limited energy budgets. This
is because imposing more stringent convergence accuracy requirements increases
the required amount of scheduled devices in the FL training process, which can
be observed from constraint (20f). From (20), we see that time used for the
update of the local models depends on the device scheduling matrix $\bm{A}$
and UAV trajectory $\bm{Q}$. Fortunately, by exploiting the UAV’s mobility,
UAV can dynamically establish favorable connections with scheduled devices in
each round to mitigate the communication straggler issue, thereby reducing the
completion time of the FL.

##  IV Device Scheduling and Time allocation along with Trajectory Design

In this section, we present the BCD-LD method to design the device scheduling,
time allocation, and UAV trajectory. Specifically, we first optimize the
device scheduling and time allocation for a given UAV trajectory. Given device
scheduling and time allocation solutions, we then optimize the UAV trajectory
$\bm{Q}$. To avoid the high computational complexity, we also use LD methods
to derive the optimal and closed-form solutions for each optimization
subproblem.

###  IV-A Joint Device Scheduling and Time Allocation

To eliminate the max function in constraints (20f), it is equivalently
converted into

$\displaystyle\sum_{k=1}^{K}\tau_{k}[n]+a_{k}[n]t_{k}^{\text{comp}}\leq\delta[n],\forall
k,\forall n\in\mathcal{N}.$ (22)

For constraints (20f), it can be rewritten as

$\displaystyle\sum_{n=0}^{N-1}\sum_{k=1}^{K}a_{k}[n+1]D_{k}^{2}\geq C.$ (23)

where
$C=N\sum_{k=1}^{K}D_{k}^{2}\\!-\\!(\epsilon\\!-\\!\frac{2}{N\eta}(\mathcal{F}(\bm{w}_{0})\\!-\\!F^{\star}))\frac{ND^{2}}{4K\kappa}$
is constant. Constraints (7) with given trajectory $\bm{Q}$ can be reduced to

$\displaystyle\delta[n]\geq\frac{\|\bm{q}[n]-\bm{q}[n-1]\|_{2}}{V_{\max}},\forall
n.$ (24)

By further relaxing the integer constraints, i.e., (20f), Problem (20) under
fixed UAV trajectory $\bm{Q}$ reduces to the following problem,

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathop{\text{minimize}}_{\bm{A},\bm{\delta},\bm{\tau}}$
$\displaystyle\sum_{n=1}^{N}\delta[n]$ subject to
$\displaystyle\sum_{n=1}^{N}\Big{(}\frac{\tau_{k}[n]\sigma^{2}}{h_{k}[n]}\Big{(}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}-1\Big{)}+a_{k}[n]E_{k}^{\text{comp}}[n]\Big{)}\leq{E}_{k},\forall
k\in\mathcal{K},$ $\displaystyle 0\leq a_{k}[n]\leq 1,\forall
k\in\mathcal{K},\forall n\in\mathcal{N},$
$\displaystyle\text{Constraints~{}}\eqref{Cons:T
slot-A},\eqref{Cons:accuracy-A},\text{and~{}}\eqref{Cons:Q speed-A}.$

Define
$\frac{\tau_{k}[n]\sigma^{2}}{h_{k}[n]}\Big{(}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}-1\Big{)}=0$
when $\tau_{k}[n]=0,\forall k,\forall n$, such that the left-hand-sides of
constraints (25) are continuous with respect to $\tau_{k}[n]$ with
$\tau_{k}[n]\geq 0$. Accordingly, since
$\frac{\sigma^{2}}{h_{k}[n]}\big{(}2^{\frac{a_{k}[n]s}{B}}-1\big{)}$ is convex
with respect to $a_{k}[n]$, its perspective function
$\frac{\tau_{k}[n]\sigma^{2}}{h_{k}[n]}\Big{(}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}-1\Big{)}$
with $\tau_{k}[n]\geq 0$ in constraints (25) is jointly convex with respect to
$a_{k}[n]$ and $\tau_{k}[n]$. Furthermore, all remaining constraints in
problem (25) are affine constraints. As such, it is concluded that problem
(25) is convex, which can be optimally solved by the Lagrange duality method.
The partial Lagrange function of problem (25) is given by

$\displaystyle\mathcal{L}(\bm{\delta},\bm{A},\bm{\tau},\bm{\lambda},\bm{\mu},\xi)$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{N}\delta[n]+\sum_{k=1}^{K}\lambda_{k}\Big{(}\sum_{n=1}^{N}\Big{(}\frac{\tau_{k}[n]\sigma^{2}}{h_{k}[n]}\Big{(}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}-1\Big{)}+a_{k}[n]E_{k}^{\text{comp}}[n]\Big{)}-{E}_{k}\\!\Big{)}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!+$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum_{n=1}^{N}\sum_{k=1}^{K}\mu_{k}[n]\Big{(}\sum_{k=1}^{K}\tau_{k}[n]+a_{k}[n]t_{k}^{\text{comp}}-\delta[n]\Big{)}+\xi(C-\sum_{n=0}^{N-1}\sum_{k=1}^{K}a_{k}[n+1]D_{k}^{2}),$

where $\bm{\lambda}=\\{\lambda_{k},\forall k\\}$,
$\bm{\mu}=\\{\mu_{k}[n],\forall k,\forall n\\}$, and $\xi$ are the non-
negative Lagrange multipliers associated with constraints (25), (22), and
(23), respectively. The other boundary constraints in problem (25) will be
absorbed into the optimal solution in the following. Accordingly, the dual
function is given by

$\displaystyle
g(\bm{\lambda},\bm{\mu},\xi)=\mathop{\text{minimize}}_{\bm{\delta},\bm{A},\bm{\tau},\xi}$
$\displaystyle\mathcal{L}(\bm{\delta},\bm{A},\bm{\tau},\bm{\lambda},\bm{\mu})$
subject to $\displaystyle\text{Constraints~{}}\eqref{Cons:binary-
relaxing}~{}\text{and}~{}\eqref{Cons:T slot-A}.$ (26)

To make $g(\bm{\lambda},\bm{\mu},\xi)$ lower-bounded (i.e.,
$g(\bm{\lambda},\bm{\mu},\xi)>-\infty$), the condition
$\sum_{k=1}^{K}\mu_{k}[n]\leq 1$ must hold. Therefore, the dual problem of
problem (25) is given by

$\displaystyle\mathop{\text{maximize}}_{\bm{\lambda},\bm{\mu},\xi}$
$\displaystyle g(\bm{\lambda},\bm{\mu},\xi)$ subject to
$\displaystyle\sum_{k=1}^{K}\mu_{k}[n]>1,\forall n,$ (27b)
$\displaystyle\bm{\lambda}\succeq 0,\bm{\mu}\succeq 0,\xi\geq 0.$

Since the strong duality holds, we can solve problem (25) by equivalently
solving its dual problem (27). In the following, we show how to obtain the
dual function $g(\bm{\lambda},\bm{\mu},\xi)$ by solving problem (IV-A) under
any given $\bm{\lambda},\bm{\mu},\xi$ that satisfy (27b) and (27b). By
ignoring the constant terms, problem (25) reduces to the following
formulation,

$\displaystyle\mathop{\text{minimize}}_{\bm{\delta},\bm{A},\bm{\tau}}$
$\displaystyle\sum_{n=1}^{N}\Big{(}1-\sum_{k=1}^{K}\mu_{k}[n]\Big{)}\delta[n]+\\!\sum_{k=1}^{K}\\!\lambda_{k}\\!\\!\sum_{n=1}^{N}\\!\\!\Big{(}\\!\frac{\tau_{k}[n]\sigma^{2}}{h_{k}[n]}\\!\Big{(}\\!2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}\\!-\\!1\Big{)}\\!+\\!a_{k}[n]E_{k}^{\text{comp}}[n]\\!\Big{)}$
$\displaystyle+\sum_{n=1}^{N}\sum_{k=1}^{K}\mu_{k}[n]\Big{(}\sum_{k=1}^{K}\tau_{k}[n]+a_{k}[n]t_{k}^{\text{comp}}\Big{)}-\xi\sum_{n=1}^{N}\sum_{k=1}^{K}a_{k}[n]D_{k}^{2}$
subject to $\displaystyle\text{Constraints~{}}\eqref{Cons:binary-
relaxing}~{}\text{and}~{}\eqref{Cons:T slot-A},$ (28a)

Note that problem (28) can be decomposed into two sets of subproblems, i.e.,
optimizing $\bm{\delta}$ and jointly optimizing $\bm{A}$ and $\bm{\tau}$. We
first consider the following optimization problem for optimizing $\bm{A}$ and
$\bm{\tau}$,

$\displaystyle\mathop{\text{minimize}}_{\bm{A},\bm{\tau}}$
$\displaystyle\sum_{n=1}^{N}\sum_{k=1}^{K}\mu_{k}[n]\Big{(}\sum_{k=1}^{K}\tau_{k}[n]+a_{k}[n]t_{k}^{\text{comp}}\Big{)}$
$\displaystyle+\sum_{k=1}^{K}\lambda_{k}\sum_{n=1}^{N}\Big{(}\frac{\tau_{k}[n]\sigma^{2}}{h_{k}[n]}\Big{(}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}-1\Big{)}+a_{k}[n]E_{k}^{\text{comp}}[n]\Big{)}-\xi\sum_{n=1}^{N}\sum_{k=1}^{K}a_{k}[n]D_{k}^{2}$
subject to $\displaystyle\text{Constraints~{}}\eqref{Cons:binary-relaxing},$
(29)

Problem (IV-A) is convex with respect to $\\{a_{k}[n]\\}$ and
$\\{\tau_{k}[n]\\}$, so the optimal solution is the one that satisfies the
Karush-Kuhn-Tucker (KKT) conditions. To obtain the optimal $\bm{\tau}$ in
problem (IV-A), we have the following theorem.

######  Theorem 3.

By setting the first derivative of the objective function of problem (IV-A)
with respect to $\tau_{k}[n]$ to zeros, the optimal time allocation can be
written as

$\displaystyle\tau_{k}^{\star}[n]=a_{k}[n]\Bigg{[}\frac{s\ln
2}{B(1+\mathcal{W}(\frac{h_{k}[n]\sum_{k=1}^{K}\mu_{k}[n]}{\lambda_{k}\sigma^{2}e}-\frac{1}{e})}\Bigg{]}^{+}\\!\\!\\!,\forall
k,\forall n,$ (30)

where $\mathcal{W}$ is the Lambert W function with
$\mathcal{W}(x)e^{\mathcal{W}(x)}=x$ and $[x]^{+}\triangleq\max\\{x,0\\}$.

###### Proof.

Please see Appendix -D. ∎

By substituting the obtained $\\{\tilde{\tau}_{k}[n]\\}$ into problem (IV-A),
we have

$\displaystyle\mathop{\text{minimize}}_{\bm{A}}$
$\displaystyle\sum_{k=1}^{K}\sum_{n=1}^{N}g(\tilde{\tau}_{k}[n])a_{k}[n]$
subject to $\displaystyle 0\leq a_{k}[n]\leq 1,\forall k\in\mathcal{K},\forall
n\in\mathcal{N},$ (31a)

where
$\tilde{\tau}_{k}[n]\\!=\\!\frac{\tau_{k}^{\star}[n]}{a_{k}[n]},g(\tilde{\tau}_{k}[n])\\!=\\!\lambda_{k}\Big{(}\frac{\tilde{\tau}_{k}[n]\sigma^{2}}{h_{k}[n]}\Big{(}2^{\frac{s}{B\tilde{\tau}_{k}[n]}}-1\Big{)}+E_{k}^{\text{comp}}[n]\Big{)}+\tilde{\tau}_{k}[n]\sum_{k=1}^{K}\mu_{k}[n]+\mu_{k}[n]t_{k}^{\text{comp}}-\xi
D_{k}^{2}.$ Problem (31) is a convex linear programming. It is evident that,
to minimize the objective function in (31), the $a_{k}[n]$ corresponding to
$g(\tilde{\tau}_{k}[n])\leq 0$ should be set to 1. Therefore, the optimal
solution for $\\{a_{k}[n]\\}$ are thus given by the following theorem.

######  Theorem 4.

For problem (31), the optimal device scheduling variables $\bm{A}$ can be
expressed as

$\displaystyle a^{\star}_{k}[n]=\left\\{\begin{aligned}
&1,\text{if~{}}g(\tilde{\tau}_{k}[n])\leq 0,\\\ &0,\
\text{otherwise}.\end{aligned}\right.$ (32)

######  Remark 2.

Theorem 4 shows that the dual method obtains the binary solution for device
scheduling variables, which guarantees both optimality and feasibility of the
original problem. It would also make sense to select a device with a large
data-set, a large channel gain, and a high computation capacity.

Next, we consider the other subproblem for optimizing $\bm{\delta}$, which is
given by

$\displaystyle\mathop{\text{minimize}}_{\bm{\delta}}$
$\displaystyle\sum_{n=1}^{N}\Big{(}1-\sum_{k=1}^{K}\mu_{k}[n]\Big{)}\delta[n]$
subject to
$\displaystyle\delta[n]\geq\frac{\|\bm{q}[n]-\bm{q}[n-1]\|_{2}}{V_{\max}},\forall
n.$ (33)

It is evident that problem (IV-A) is a linear programming. For problem (IV-A),
since $\sum_{k=1}^{K}\mu_{k}[n]\leq 1$ holds, the optimal time slot variables
are given by

$\displaystyle\delta^{\star}[n]=\left\\{\begin{aligned}
&\frac{\|\bm{q}[n]-\bm{q}[n-1]\|_{2}}{V_{\max}},\text{if
}\sum_{k=1}^{K}\mu_{k}[n]<1,\\\ &b,\ \text{if
}\sum_{k=1}^{K}\mu_{k}[n]=1,\end{aligned}\right.$ (34)

where $b$ can be any arbitrary real number which is not smaller than
$\frac{\|\bm{q}[n]-\bm{q}[n-1]\|_{2}}{V_{\max}}$ since the objective function
of problem (IV-A) is not affected in this case. For simplicity, we set
$b=\frac{\|\bm{q}[n]-\bm{q}[n-1]\|_{2}}{V_{\max}}$. In general, (34) cannot
provide the optimal primal solution for problem (25) even with optimal dual
variables. Nevertheless, with the above proposed solutions to problems (IV-A)
and (IV-A), the dual function $g(\bm{\lambda},\bm{\mu},\xi)$ is obtained.

The dual problem (27) can be solved after obtaining
$(\bm{\tau}^{\star},\bm{\delta}^{\star},\bm{A}^{\star})$. Despite the fact
that the dual function $g(\bm{\lambda},\bm{\mu},\xi)$ is always convex by
definition, it is generally non-differentiable. To address this challenge, a
common subgradient-based method, such as projected subgradient decent method,
can be applied to solving the (27). Specifically, dual variables are updated
in each iteration via

$\displaystyle\mu_{k}^{\frac{1}{2}}[n]=[\mu_{k}[n]+\phi\sum_{k=1}^{K}\tau_{k}[n]+a_{k}[n]t_{k}^{\text{comp}}-\delta[n]]^{+},\mu_{k}[n]=\frac{\mu_{k}^{\frac{1}{2}}[n]}{\max\\{1,\sum_{k=1}^{K}\mu_{k}^{\frac{1}{2}}[n]\\}},$
(35)
$\displaystyle\lambda_{k}=[\lambda_{k}+\phi\sum_{n=1}^{N}\Big{(}\frac{\tau_{k}[n]\sigma^{2}}{h_{k}[n]}\Big{(}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}-1\Big{)}+a_{k}[n]E_{k}^{\text{comp}}[n]\Big{)}-{E}_{k}]^{+},$
(36)
$\displaystyle\xi=[\xi+\phi(C-\sum_{n=0}^{N-1}\sum_{k=1}^{K}a_{k}[n+1]D_{k}^{2})]^{+},$
(37)

where $\phi$ is a dynamically chosen step-size. Based on
$\bm{\lambda}^{\star}$, $\bm{\mu}^{\star}$, and $\xi^{\star}$ have been
obtained, it is left to find the optimal primal solution
$\\{\bm{\delta}^{\star},\bm{\tau}^{\star},\bm{A}^{\star}\\}$ of problem (25).
For a convex optimization problem, a solution that minimizes the Lagrange
function is optimal only if it is unique and primal feasible. Unfortunately,
in this case, the solutions $\bm{\delta}$ that minimizes
$\mathcal{L}(\bm{\delta},\bm{A},\bm{\tau},\bm{\lambda},\bm{\mu},\xi)$ are not
unique when $\sum_{k=1}^{K}\mu_{k}[n]\leq 1$. To construct the optimal
solution, additional steps are needed. Specifically, given
$\bm{\lambda}^{\star}$, $\bm{\mu}^{\star}$, and $\xi^{\star}$, the optimal
time allocation (i.e., $\bm{\tau}^{\star}$) and device scheduling variable
(i.e., $\bm{A}^{\star}$) can be uniquely obtained by (30) and (32),
respectively. By substituting $\bm{\tau}^{\star}$ and $\bm{A}^{\star}$ into
the primal problem (25), we have

$\displaystyle\mathop{\text{minimize}}_{\bm{\delta}}$
$\displaystyle\sum_{n=1}^{N}\delta[n]$ subject to
$\displaystyle\sum_{k=1}^{K}\tau_{k}[n]+a_{k}[n]t_{k}^{\text{comp}}\leq\delta[n],\forall
k,\forall n\in\mathcal{N},$ (38b)
$\displaystyle\delta[n]\geq\frac{\|\bm{q}[n]-\bm{q}[n-1]\|_{2}}{V_{\max}},\forall
n.$

It is evident that problem (38) is a convex linear programming and can be
separated into $N$ independent problems. The optimal time slot variables are
given by

$\displaystyle\delta^{\star}[n]=\max\Big{\\{}\frac{\|\bm{q}[n]-\bm{q}[n-1]\|_{2}}{V_{\max}},\sum_{k=1}^{K}\tau_{k}[n]+\max_{k}a_{k}[n]t_{k}^{\text{comp}}\Big{\\}}.$
(39)

Algorithm 2 summarizes the details of obtaining the optimal solution to
problem (25). Algorithm 2 includes three parts, i.e., solving problems (IV-A)
and (IV-A), updating the dual variables, and solving problem (38). According
to (30) and (32), the complexity of solving problem (IV-A) is
$\mathcal{O}(KN)$. According to (34) and (39), the complexity of both solving
problem (IV-A) and problem (38) is $\mathcal{O}(N)$. In addition, according to
(36)-(35), the complexity of updating the dual variables is $\mathcal{O}(KN)$.
Denote by $l_{1}$ the number of iterations required for convergence.
Therefore, the total complexity of Algorithm 2 is given by
$\mathcal{O}(l_{1}KN)$.

1: Input: $K$, $N$, $\bm{Q}$.

2: Initialize dual variables $\\{\lambda_{k}=1\\}$, $\\{\mu_{k}[n]=1/K\\}$.

3: repeat

4: Update the primal variables $\bm{A}$, $\bm{\tau}$, and $\bm{\delta}$
according to (32), (30), and (34).

5: Update the dual variables $\bm{\lambda}$, $\bm{\mu}$, $\xi$ according to
(35)-(37).

6: until $\bm{\lambda}$ and $\bm{\mu}$ converge within a prescribed accuracy

7: Update $\bm{\delta}^{\star}$ according to (39).

8: Output: $\bm{A}^{\star}$, ${\bm{\tau}}^{\star}$, and $\bm{\delta}^{\star}$.

Algorithm 2 Dual Method for Problem (25)

###  IV-B Trajectory Design

Given device scheduling and time allocation
$\\{\bm{A},\bm{\delta},\bm{\tau}\\}$, the trajectory optimization subproblem
is reduced to the following feasibility checking problem

$\displaystyle\mathop{\text{find}}_{\bm{Q}}$ $\displaystyle\bm{Q}$ subject to
$\displaystyle\sum_{n=1}^{N}b_{k}[n]\|\bm{q}[n]-{{\bf
w}_{k}}\|_{2}^{2}\leq\bar{E}_{k},\forall k\in\mathcal{K},$ (40b)
$\displaystyle\text{Constraints}~{}\eqref{Cons:Q distance},\eqref{Cons:Q
position},$

where
$\bar{E}_{k}\triangleq{E}_{k}-\sum_{n=1}^{N}a_{k}[n]E_{k}^{\text{comp}}[n]-\sum_{n=1}^{N}\frac{\tau_{k}[n]\sigma^{2}H^{2}}{\beta_{0}}\big{(}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}-1\big{)}$
and
$b_{k}[n]\triangleq\frac{\tau_{k}[n]\sigma^{2}}{\beta_{0}}\big{(}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}-1\big{)}$.
According to (12), $\tau_{k}^{\star}[n]$ is a non-increasing function with
respect to channel gain $h_{k}[n]$. Hence, to further reduce the time
consumption while ensuring the feasibility of problem (40), we transform
problem (40) into the following problem with an explicit objective function

$\displaystyle\mathop{\text{minimize}}_{\bm{Q}}$
$\displaystyle\sum_{n=1}^{N}\sum_{k=1}^{K}b_{k}[n]\|\bm{q}[n]-{{\bf
w}_{k}}\|_{2}^{2}$ subject to $\displaystyle\text{Constraints}~{}\eqref{Cons:Q
distance},\eqref{Cons:Q position},\eqref{Cons:E budget-Q}.$ (41a)

Although the convex QCQP problem (41) can be solved using a general-purpose
solver through interior-point methods, to further reduce the computational
complexity, we exploit the specific structure of problem (41) and find its
optimal solution by using a Lagrange dual ascent method in the sequel. The
partial Lagrange function of problem (41) can be expressed as

$\displaystyle\mathcal{L}(\bm{Q},\bm{\gamma})=\sum_{n=1}^{N}\sum_{k=1}^{K}(a_{k}[n]+\gamma_{k}b_{k}[n])\|\bm{q}[n]-{{\bf
w}_{k}}\|_{2}^{2}-\sum_{k=1}^{K}\gamma_{k}\bar{E}_{k},$ (42)

where $\bm{\gamma}=\\{\gamma_{k},\forall k\\}$ are the non-negative Lagrange
multipliers associated with constraints (40b). Accordingly, the dual function
is given by

$\displaystyle g(\bm{\gamma})=\mathop{\text{minimize}}_{\bm{Q}}$
$\displaystyle\mathcal{L}(\bm{Q},\bm{\gamma})$ subject to
$\displaystyle\text{Constraints}~{}\eqref{Cons:Q distance},\eqref{Cons:Q
position}.$ (43)

The dual problem of problem (41) is given by

$\displaystyle\mathop{\text{maximize}}_{\bm{\gamma}\succeq 0}$ $\displaystyle
g(\bm{\gamma})$ (44)

As the strong duality holds, we can solve problem (41) by equivalently solving
its dual problem (44). In the following, we show how to obtain the dual
function $g(\bm{\gamma})$ by solving problem (IV-B) under any given
$\bm{\gamma}\succeq 0$. By ignoring the constant terms, problem (IV-B) reduces
to

$\displaystyle\mathop{\text{minimize}}_{\bm{Q}}$
$\displaystyle\sum_{n=1}^{N}\sum_{k=1}^{K}(b_{k}[n]+\gamma_{k}b_{k}[n])\|\bm{q}[n]-{{\bf
w}_{k}}\|_{2}^{2}$ subject to $\displaystyle\text{Constraints}~{}\eqref{Cons:Q
distance},\eqref{Cons:Q position}.$ (45)

Since problem (IV-B) is convex with respect to $\bm{Q}$, the solution that
satisfies KKT conditions is also optimal. To obtain the optimal solution
$\bm{Q}$ in problem (IV-B), we have the following theorem.

######  Theorem 5.

For problem (IV-B), the optimal UAV trajectory can be denoted as

$\displaystyle\bm{q}[n]$ $\displaystyle=$
$\displaystyle\left\\{\begin{aligned} &{\bf{q}_{I}},\text{if~{}}n=0,\\\
&\mathcal{P}_{\mathcal{C}}\Big{(}\frac{\sum_{k=1}^{K}(b_{k}[n]+\gamma_{k}b_{k}[n])({\bf{w}_{k}}-\bm{q}[n-1])}{\sum_{k=1}^{K}(b_{k}[n]+\gamma_{k}b_{k}[n])}\Big{)}+\bm{q}[n-1],&\text{otherwise},\end{aligned}\right.$
(46)

where
$\mathcal{P}_{\mathcal{C}}(\bm{x})\\!:=\\!\min\big{\\{}{\min\\{V_{\max}\delta[n],\Delta
q_{\max}\\}}\big{/}{\|\bm{x}\|},1\big{\\}}\bm{x}$ is the projector associated
with space $\mathcal{C}$.

After obtaining $\bm{Q}^{\star}$ for given $\bm{\gamma}$, we next solve the
dual problem (44) to find the optimal dual variables which maximize
$g(\bm{\gamma})$. Likewise in joint device scheduling and time allocation, the
dual variable is determined by the subgradient based method, the updates of
which in each iteration can be given by
$\gamma_{k}=\Big{[}\gamma_{k}+\varphi\Big{(}\sum_{n=1}^{N}b_{k}[n]\|\bm{q}[n]-{\bf
w_{k}}\|_{2}^{2}-\bar{E}_{k}\Big{)}\Big{]}^{+}$, where $\varphi$ is a
dynamically chosen step-size. The procedure for solving problem (41) is
similar to that of solving problem (25). The details are omitted due to space
limitations.

1: Input: $M$, $N$.

2: Initialize $\bm{Q}^{0}$. Let $r=1$.

3: repeat

4: Solve problem (25) by applying Algorithm 2 for given $\bm{Q}^{r-1}$, and
denote the optimal solution as
$\\{\bm{A}^{r},\bm{\tau}^{r},\bm{\delta}^{r}\\}$.

5: Solve problem (41) for given
$\\{\bm{A}^{r},\bm{\tau}^{r},\bm{\delta}^{r}\\}$, and denote the optimal
solution as $\bm{Q}^{r}$.

6: Update $r=r+1$.

7: until the fractional decrease of the objective value is below a threshod
$\varepsilon$.

8: Output: $\bm{A}$, $\bm{\tau}$, $\bm{\delta}$, and $\bm{Q}$.

Algorithm 3 BCD-LD for Problem (20)

###  IV-C Overall Algorithm Design

In this section, based on the results in previous two subsections, we present
an efficient iterative algorithm to solve problem (20) by using the BCD
technique [40], which is summarized in Algorithm 3. Note that the subproblem
for updating each block of variables is solved with optimality in each
iteration. The convergence of Algorithm 3 is shown in the following
proposition.

######  Proposition 2.

With Algorithm 3, the objective value of problem (20) decreases as the number
of iterations increases until convergence.

###### Proof.

Please refer to Appendix -E. ∎

##  V Numerical Results

In this section, we present extensive numerical results to demonstrate the
effectiveness of the proposed algorithm for FL via UAV. We consider the image
classification task on the widely-used CIFAR-10 datasets [41], which is
composed of 60, 000 $32\times 32$ RGB color images in 10 different classes. We
adopt the multi-nominal logistic regression model to classify the target
datasets with features $d=32\times 32\times 3\times 10$ and leaning rate
$\eta=0.01$. And the loss function is

$\displaystyle\mathcal{F}_{k}(\bm{w})=\frac{-1}{D_{k}}\sum_{i=1}^{D_{k}}\sum_{c=1}^{10}1_{\\{y_{i}=c\\}}\log\frac{\text{exp}(\bm{x}_{i}^{\sf
T}\bm{w}_{c})}{\sum_{j=1}^{10}\text{exp}(\bm{x}_{i}^{\sf T}\bm{w}_{j})}.$ (47)

Each parameter is assumed to be stored with $I=32$ bits, i.e., $s=I\times d$.
The effective capacitance coefficient of all devices’ computing chipset is
$\alpha_{1}=\ldots=\alpha_{k}=10^{-28}$. The local training data are uniformly
drawn from 50,000 images with $\\{D_{k}\\}$, and the test dataset contains the
remaining 10,000 images. Considering different numbers of training samples,
the values of $\\{D_{k}\\}$ are drawn uniformly. In the simulations, the
service area of the UAV is restricted to a square area with the size of [0,
400] m $\times$ [0, 400] m. The UAV is assumed to fly at a fixed altitude of
$H=100$ m, which complies with the practical rule, i.e., commercial UAVs
should not fly over 400 feet (122 m) [42]. And the UAV is placed at a
predetermined initial position, i.e., (200, 0, 100) m. The maximum speed of
the UAV is ${V}_{\max}=20$ m/s. In addition, considering channel
heterogeneity, $K$ devices are separated into two clusters allocated in two
circles, i.e., cluster $A$ with $\lfloor 0.3K\rfloor$ devices and cluster $B$
with $K-\lfloor 0.3K\rfloor$ devices. Specifically, the devices in cluster $A$
and cluster $B$ are randomly and uniformly distributed in circles centered at
(100, 100) m and (300, 300) m with a radius of 100 m, respectively. Other
parameters are summarized in Table I.

TABLE I: Parameter settings for simulations. Number of devices |  $K=40$ |  Noise power |  $-174$ dBm/Hz |  CPU frequency |  $f_{k}=5$ GHz
---|---|---|---|---|---
Channel gain at 1 meter |  $\beta_{0}=-50$ dB |  Uplink bandwidth |  10MHz |  Maximum distance |  $\Delta q_{\max}=10$ m
Communication rounds |  $N=4000$ |  CPU cycles |  $c_{k}=10$ |  Accuracy of Alg. 3 |  $\varepsilon=10^{-3}$

We compare the performance of the proposed joint design scheme with the
following schemes: 1) Static UAV: With this scheme, the UAV is placed at a
predetermined initial position, i.e., (200, 0, 100) m, and remains static
during the whole mission time. This scheme optimizes
$\\{\bm{A},\bm{\tau},\bm{\delta}\\}$ to minimize the completion time for FL by
solving problem (25), as presented in Algorithm 2. 2) Static UAV w/ HS: In
this scheme, the UAV is static and placed at a predetermined initial position.
With the static UAV, the channel conditions of devices are known and
invariant. According to the channel-aware criterion [12], the devices with
bigger channel gains are always scheduled to satisfy constraint (20f) with
equality. Therefore, in this scheme, $\bm{A}$ and $\bm{Q}$ are deterministic,
and we only need to optimize $\\{\bm{\tau},\bm{\delta}\\}$ to minimize the
completion time for FL. 3) Full Scheduling: This scheme schedules all devices
to upload in every communication round. And without model aggregation loss
resulting from device scheduling, this scheme achieves the minimum convergence
accuracy of FL, which serves as a performance bound for other schemes. By
substituting the given $\bm{A}$ into problem (20), this scheme optimizes
$\\{\bm{\tau},\bm{\delta},\bm{Q}\\}$ to minimize the completion time for FL.
We still adopt the BCD-based iterative algorithm to solve the resulting
problem, which is similar to Algorithm 3.

Figure 2: Convergence behaviors of Algorithm 3 for different energy budgets of
device.

Figure 3: UAV trajectories for different convergence accuracy of FL
constraints.

Figure 4: The corresponding UAV speed and the percentage of scheduled devices
over round when $\epsilon=0.2$.

###  V-A Optimized UAV Trajectory

Fig. 4 shows the convergence behaviors of the proposed BCD-based algorithm
(i.e., Algorithm 3) with different device energy budgets $E_{k}$, $\forall k$
when $\epsilon=0.2$. All devices have the same energy budgets. It is observed
that for both schemes, the completion time with Algorithm 3 decreases quickly
with the number of iterations, and the two algorithms converge within 5
iterations with prescribed accuracy $\varepsilon=10^{-3}$. Besides, the
proposed joint design achieves a smaller completion time under $E_{k}=30$ J
compared to $E_{k}=10$ J.

Fig. 4 illustrates the trajectories obtained by Algorithm 3 under different
convergence accuracy of FL $\epsilon$. Each trajectory is sampled every 5
rounds and the sampled points are marked with $\triangle$ by using the same
colors as their corresponding trajectories. The devices’ locations are marked
by a dark blue $\square$. The predetermined locations of the UAV are red
$\star$. We can observe that with different $\epsilon$, the optimized
trajectories have some similar behaviors. First, the UAV visits the devices in
both clusters as close as possible along an arc path, which means the UAV
proactively shortens the devices’ communication distance and thus schedules
different devices to participate in FL training. We also observe that the
densities of sampling points on the trajectory in different time slots are
different. As a result of varying channel coefficients, the selected devices
change during training.

To unveil the phenomena in trajectories obtained by these algorithms and the
reasons for such phenomena, we plot the corresponding UAV speed and the
percentage of scheduled devices over communication rounds, as shown in Fig. 4.
It can be observed that there are three stages for behaviors of scheduled
devices. Furthermore, the behaviors of the corresponding UAV speed are
consistent with that of the percentage of scheduled devices. In the following,
we elaborate on these three stages.

  * •

Stage I: As shown in Fig. 4, from round 1 to about 1300 rounds, the percentage
of participating devices per round is equal to 0, which means that no device
is involved in FL training during this time interval. This is because in this
interval when the UAV stays in the initial position, the communication
straggler issue is severe.

  * •

Stage II: From about 1300 to 1400 rounds, the percentage of participating
devices is dynamically changing, which means our proposed design outputs
different device selection decisions when the channels change.

  * •

Stage III: From about 1400 rounds to 4000 rounds, the percentage of
participating devices equals $100\%$ in each round, which means with the
synergy of trajectory and energy, the optimized device scheduling not only
satisfies the convergence accuracy but also maximizes data exploitation,
thereby reducing model aggregation loss and accelerating FL convergence.

Importantly note that the effective communication rounds of FL in the proposed
scheme only need about 2700 rounds to satisfy the convergence accuracy
condition, i.e., $\epsilon=0.2$.

###  V-B Performance Comparison for Completion Time

Figure 5: Completion time versus convergence accuracy of FL.

Figure 6: Completion time versus device energy budget.

Fig. 6 shows the effect of the convergence accuracy of FL on the completion
time when $E=10$ J. Since the full scheduling scheme does not result in the
model aggregation loss, its performance is invariant to the convergence
accuracy $\epsilon$. However, this scheme costs prohibitive completion time
without device scheduling. Note that this scheme may be forbidden in general
since UAVs usually have a limited endurance due to practical physical
constraints (e.g., 30 minutes for the typical rotary-wing UAV [30]). For the
other three schemes with device scheduling, the completion time decreases with
$\epsilon$, which is consistent with Theorem 2. In addition, the Static UAV
scheme has a shorter completion time than the Static UAV w/ HS scheme since
the former avoids the aggregation error explosion by excluding the weak
devices. However, in the case of strong straggler issues, the performance gain
brought by device scheduling optimization alone is very limited. Fortunately,
the proposed joint design scheme incorporated trajectory design with device
scheduling significantly reduce the completion time compared to all
benchmarks. This is because, the mobile UAV can shorten communication
distances between the scheduled devices and always achieve a high transmission
rate for local model uploading, thereby accelerating the model aggregation
process. These results demonstrate in UAV-enabled systems, joint trajectory
and device scheduling device is critical to mitigating the communication
stragglers’ effect.

Fig. 6 shows the total mission completion time versus the device energy budget
when $\epsilon=0.2$. It is observed that, for all schemes, the total
completion time decreases as $E$ increases. This is because, as $E$ increases,
the scheduled devices can afford more energy to upload local models with
higher transmission rates. We also find that the proposed joint design
achieves the smallest completion time compared to all benchmarks. This
observation further verifies the superiority of the proposed scheme to
mitigate the stragglers’ effect.

Figure 7: Training accuracy over communication rounds.

Figure 8: Test accuracy versus convergence accuracy of FL.

###  V-C Performance Comparison for FL

To demonstrate the performance of our proposed joint design for dealing with
FL tasks, we train image classifier models on the widely-used CIFAR-10
dataset. In the simulations, the full scheduling scheme allows all devices to
participate in the training process at each FL round that can achieve the most
optimal FL performance, which serves as the lower bound.

Fig. 8 shows training accuracy over communication rounds with different
schemes and different $\epsilon$. We can observe that the convergence accuracy
$\epsilon$ heavily affects the learning performance of the Static UAV w/ HS
since a larger value of $\epsilon$ implies that the data are less exploited in
this scheme due to the fact of device exclusion. In contrast, the proposed
joint design still achieves a training accuracy that is close to the ideal
benchmark even as $\epsilon$ increases. For example, we can see from Fig. 4
with $\epsilon=0.2$, the percentage of participating devices is $100\%$ from
about 1400 rounds to 4000 rounds. This is because the proposed joint design
scheme overcomes the straggler issue and maximizes data exploitation.
Specifically, the UAV’s trajectory tends to be close to the devices to
establish strong communication links, thus maximizing data exploitation. In
contrast, at some UAV locations (e.g., the initial position), where the
communication straggler issue is severe, the device schedule is optimized to
let no device be involved in FL training. This is the reason why the curve of
the proposed joint design scheme is invariant during the initial communication
rounds. On the other hand, by properly designing the trajectory of the UAV,
short-distance LoS links can be proactively and dynamically established for
any device, which ensures all devices have equal opportunity to participate in
FL training instead of device exclusion, thereby increasing the data
exploitation and training accuracy.

Fig. 8 shows the test accuracy versus convergence rate of FL constraints with
different schemes when $E=10$ J. It is observed that for all schemes except
for the full scheduling scheme, the test accuracy decreases as $\epsilon$
increases. Observed from Fig. 6 and Fig. 8, it shows that there exists a
fundamental trade-off between the mission completion time and the learning
performance of FL. However, by exploiting the mobility of the UAV and
flexibility of device scheduling, our proposed joint design significantly
improves the trade-off compared to the static UAV w/ HS scheme. For example,
when $\epsilon=0.2$, the completion time of FL achieved by our proposed joint
design, static UAV w/HS, and the full scheduling scheme are respectively $930$
s, and $1150$ s, $1500$ s. Meanwhile, when $\epsilon=0.2$, the test accuracy
achieved by our proposed joint design, static UAV w/HS, and the full
scheduling scheme are respectively $38.99\%$ s, and $32.52\%$ s, and
$39.74\%$. For static UAV w/HS, compared to the full scheduling scheme, the
completion time reduces $23.33\%$ while the test accuracy reduces $7.22\%$.
Fortunately, for our proposed joint design, compared to the full scheduling
scheme, the completion time reduces $38\%$ while the test accuracy only
reduces $0.71\%$.

##  VI Conclusion

In this paper, we studied the UAV-assisted FL system to effectively address
the straggler issue by exploiting the UAV’s high altitude and mobility when
the terrestrial PS was unavailable. Specifically, a mobile UAV was deployed as
a flying PS to exchange model parameters from distributed ground devices and
train a shared FL model. We focused on the joint consideration of device
scheduling, UAV trajectory, and time allocation to minimize the completion
time required for FL to converge to the desired accuracy level. Before
proceeding with problem formulation, we first theoretically analyzed the
effect of device scheduling on the convergence rate of FL without the
assumptions of convexity. We also provided a convergence bound for the average
norm of the global gradient. Based on such convergence results, we formulated
the completion time minimization problem, taking into account the practical
device’s energy budget, UAV’s mobility constraints, and convergence accuracy
constraint. Although the formulated problem was non-convex, we exploited its
structures to decompose it into two sub-problems, followed by deriving closed-
form solutions via the Lagrange dual ascent method. Simulation results
demonstrated that our proposed joint design can significantly reduce
completion time and enhance the tradeoff between completion time and
prediction accuracy compared to the existing benchmarks.

###  -A Proof of Theorem 1

Let
${\bm{g}}_{n}\triangleq\frac{\sum_{k=1}^{K}a_{k}[n+1]D_{k}\nabla\mathcal{F}_{k}(\bm{w}_{n})}{\sum_{k=1}^{K}a_{k}[n+1]D_{k}}$.
Combining the update rules at devices in (4) and the update rule at the server
in (5), the update of the global FL model at round $n+1$ is given by
$\bm{w}_{n+1}=\bm{w}_{n}-\eta\frac{\sum_{k=1}^{K}a_{k}[n+1]D_{k}\nabla\mathcal{F}_{k}(\bm{w}_{n})}{\sum_{k=1}^{K}a_{k}[n+1]D_{k}}=\bm{w}_{n}-\eta{\bm{g}}_{n}.$
From the assumption in (16), we have that

$\displaystyle\mathcal{F}(\bm{w}_{n+1})-\mathcal{F}(\bm{w}_{n})$
$\displaystyle\leq\langle\nabla\mathcal{F}(\bm{w}_{n}),\bm{w}_{n+1}-\bm{w}_{n}\rangle+(L/2)\|\bm{w}_{n+1}-\bm{w}_{n}\|_{2}^{2},$
(48)
$\displaystyle=\langle\nabla\mathcal{F}(\bm{w}_{n}),-\eta\bm{g}_{n}\rangle+(\eta^{2}L/2)\|{\bm{g}}_{n}\|_{2}^{2}.$

Using
$\bm{g}_{n}=\nabla\mathcal{F}(\bm{w}_{n})-(\nabla\mathcal{F}(\bm{w}_{n})-\bm{g}_{n})$,
we derive that

$\displaystyle\mathcal{F}(\bm{w}_{n+1})-\mathcal{F}(\bm{w}_{n})$
$\displaystyle\leq$ $\displaystyle(\eta
L/2-1)\eta\|\nabla\mathcal{F}(\bm{w}_{n})\|_{2}^{2}+(\eta^{2}L/2)\|\nabla\mathcal{F}(\bm{w}_{n})-\bm{g}_{n}\|_{2}^{2}$
(49) $\displaystyle+$ $\displaystyle(1-\eta
L)\eta\langle\nabla\mathcal{F}(\bm{w}_{n}),\nabla\mathcal{F}(\bm{w}_{n})-\bm{g}_{n}\rangle.$

The third term at the right-hand side in (49) can be upper bounded as

$\displaystyle\langle\nabla\mathcal{F}(\bm{w}_{n}),\nabla\mathcal{F}(\bm{w}_{n})-\bm{g}_{n}\rangle$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}(\|\nabla\mathcal{F}(\bm{w}_{n})\|_{2}^{2}+\|\nabla\mathcal{F}(\bm{w}_{n})-\bm{g}_{n}\|_{2}^{2}).$
(50)

Given $0<\eta\leq\frac{1}{L}$, we substitute (50) into (49) and rearrange the
result, yielding

$\displaystyle\|\nabla\mathcal{F}(\bm{w}_{n})\|_{2}^{2}\leq\frac{2}{\eta}(\mathcal{F}(\bm{w}_{n})-\mathcal{F}(\bm{w}_{n+1}))+\|\nabla\mathcal{F}(\bm{w}_{n})-\bm{g}_{n}\|_{2}^{2}.$
(51)

Therein, the second term , namely the global gradient deviation error in
expression (51) is can be rewritten as

$\displaystyle\\!\\!\\!\\!\\!\\!\|\nabla\mathcal{F}(\bm{w}_{n})-\bm{g}_{n}\|_{2}^{2}=\Big{\|}\frac{\sum_{k=1}^{K}a_{k}[n+1]D_{k}\nabla\mathcal{F}_{k}(\bm{w}_{n})}{\sum_{k=1}^{K}a_{k}[n+1]D_{k}}-\frac{1}{D}\sum_{k=1}^{K}D_{k}\nabla\mathcal{F}_{k}(\bm{w}_{n})\Big{\|}_{2}^{2}$
$\displaystyle\\!\\!\\!\\!=$
$\displaystyle\\!\\!\\!\\!\Big{(}\Big{\|}\frac{\sum_{k=1}^{K}\\!D_{k}(1\\!-\\!a_{k}[n\\!+\\!1])}{D\\!\sum_{k=1}^{K}\\!a_{k}[n\\!+\\!1]D_{k}}\sum_{k=1}^{K}a_{k}[n\\!+\\!1]D_{k}\nabla\mathcal{F}_{k}(\bm{w}_{n})\|\\!+\\!\|\frac{1}{D}\\!\sum_{k=1}^{K}(1-a_{k}[n+1])D_{k}\nabla\mathcal{F}_{k}(\bm{w}_{n})\Big{\|}\Big{)}^{2}.$

Thus, based on (-A) and triangle inequality, the global gradient deviation
error is bounded as

$\displaystyle\\!\\!\\!\\!\|\nabla\mathcal{F}(\bm{w}_{n})-\bm{g}_{n}\|_{2}^{2}$
$\displaystyle\leq\Big{(}\\!\frac{\sum_{k=1}^{K}\\!D_{k}(1\\!-\\!a_{k}[n\\!+\\!1])}{D\sum_{k=1}^{K}a_{k}[n\\!+\\!1]D_{k}}\\!\sum_{k=1}^{K}\\!a_{k}[n\\!+\\!1]\\!\sum_{i=1}^{D_{k}}\\!\|\nabla\\!f(\bm{w}_{n};\bm{x}_{ki},y_{ki})\|_{2}$
$\displaystyle+\frac{1}{D}\sum_{k=1}^{K}(1-a_{k}[n+1])\sum_{i=1}^{D_{k}}\|\nabla
f(\bm{w}_{n};\bm{x}_{ki},y_{ki})\|_{2}\Big{)}^{2}$ $\displaystyle\leq$
$\displaystyle\\!\\!\\!\\!\frac{4}{D^{2}}(\sum_{k=1}^{K}(1-a_{k}[n+1])D_{k})^{2}\kappa\leq\frac{4K\kappa}{D^{2}}\sum_{k=1}^{K}(1-a_{k}[n+1])D_{k}^{2}.$
(53)

Therefore, based on (51) and (-A), it follows that

$\displaystyle\frac{1}{N}\sum_{n=0}^{N-1}\|\nabla\mathcal{F}(\bm{w}_{n})\|^{2}\leq$
$\displaystyle\\!\\!\\!\\!\frac{2}{N\eta}(\mathcal{F}(\bm{w}_{0})-F(\bm{w}_{N}))+\frac{1}{N}\sum_{n=0}^{N-1}\|\nabla\mathcal{F}(\bm{w}_{n})-\bm{g}_{n}\|^{2}$
$\displaystyle\leq$
$\displaystyle\\!\\!\\!\\!\frac{2}{N\eta}(\mathcal{F}(\bm{w}_{0})-F^{\star})+\frac{1}{N}\sum_{n=0}^{N-1}\|\nabla\mathcal{F}(\bm{w}_{n})-\bm{g}_{n}\|^{2}$
$\displaystyle\overset{\eqref{Neq:error}}{\leq}$
$\displaystyle\\!\\!\\!\\!\frac{2}{N\eta}(\mathcal{F}(\bm{w}_{0})-F^{\star})+\frac{4K\kappa}{ND^{2}}\sum_{n=0}^{N-1}\sum_{k=1}^{K}(1-a_{k}[n+1])D_{k}^{2}.$
(54)

This completes the proof.

###  -B Proof of Proposition 1

Given an arbitrary convergence threshold $\epsilon$, to make constraint (20f)
in problem (20) feasible, if and only if the minimum communication rounds
satisfies
$N\geq\lceil\frac{2(\mathcal{F}(\bm{w}_{0})-F^{\star})}{\epsilon\eta}\rceil,$
where $a_{k}[n]=1,\forall k,\forall N$. In addition, we have that

$\displaystyle\frac{4K\kappa}{ND^{2}}\sum_{n=0}^{N-1}\sum_{k=1}^{K}(1-a_{k}[n+1])D_{k}^{2}\leq\\!\frac{4K\kappa}{ND^{2}}\max_{k}D_{k}^{2}\sum_{n=0}^{N-1}\sum_{k=1}^{K}(1\\!-\\!a_{k}[n\\!+\\!1]).$
(55)

By instituting the right term of inequality (55) into constraint (20f), if
(20f) is satisfied, then

$\displaystyle\sum_{n=0}^{N-1}\sum_{k=1}^{K}a_{k}[n+1]\geq|\mathcal{S}|,$ (56)

where $|\mathcal{S}|=\lceil
KN-(\epsilon-\frac{2}{N\eta}(\mathcal{F}(\bm{w}_{0})-F^{\star}))\frac{ND^{2}}{4K\kappa\max_{k}D_{k}^{2}}\rceil$.
For device $k$, the minimum energy consumption for local model uploading is
given by

$\displaystyle\\!\\!\\!\\!\\!\\!\lim_{\tau_{k}[n]\longrightarrow+\infty}E_{k}^{\text{comm}}[n]$
$\displaystyle=$
$\displaystyle\lim_{\tau_{k}[n]\longrightarrow+\infty}\frac{\tau_{k}[n]\sigma^{2}}{h_{k}[n]}\Big{(}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}-1\Big{)}=\frac{a_{k}[n]s\sigma^{2}\ln
2}{Bh_{k}[n]}\geq\frac{a_{k}[n]s\sigma^{2}H^{2}\ln 2}{B\beta_{0}}.$ (57)

Besides, if constraints (20f) are satisfied, we have that

$\displaystyle\frac{s\sigma^{2}H^{2}\ln
2}{B\beta_{0}}\sum_{k=1}^{K}\sum_{n=1}^{N}a_{k}[n]$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\sum_{n=1}^{N}\Big{(}E_{k}^{\text{comm}}[n]+E_{k}^{\text{comp}}[n]\Big{)}\leq\sum_{k=1}^{K}{E}_{k}.$
(58)

Combining (56) with (58), to make constraints (20f) and constraint (20f)
feasible, we have that

$\displaystyle\frac{s\sigma^{2}H^{2}\ln
2}{B\beta_{0}}|\mathcal{S}|\leq\sum_{k=1}^{K}{E}_{k},N\geq\lceil\frac{2(\mathcal{F}(\bm{w}_{0})-F^{\star})}{\epsilon\eta}\rceil.$
(59)

Thus, this completes the proof.

###  -C Proof of Theorem 2

Denote the optimal solutions of problem (20) with $\epsilon^{\star}$ and
$\hat{\epsilon}$ by with
$\mathcal{E}^{\star}=\\{\bm{A}^{\star},\bm{\Gamma}^{\star},\bm{Q}^{\star},\bm{\delta}^{\star}\\}$
and
$\hat{\mathcal{E}}=\\{\bm{\hat{A}},\bm{\hat{\Gamma}},\bm{\hat{Q}},\bm{\hat{\delta}}\\}$,
respectively. To prove Theorem 2, we only need to show that
$\sum\delta^{\star}[n]\geq\sum\hat{\delta}[n]$ holds when
$\epsilon^{\star}\leq\hat{\epsilon}$. Note that in problem (20), the
convergence threshold is only involved in constraint (20f). Thus, we have the
following inequalities

$\displaystyle\frac{2}{N\eta}(\mathcal{F}(\bm{w}_{0})-F^{\star})+\frac{4K\kappa}{ND^{2}}\sum_{n=0}^{N-1}\sum_{k=1}^{K}(1-a_{k}^{\star}[n+1])D_{k}^{2}\leq\epsilon^{\star}\leq\hat{\epsilon},$
(60)

which implies that $\mathcal{E}^{\star}$ is also a feasible solution of
problem (20) with $\hat{\epsilon}$. Since $\sum{\hat{\delta}}[n]$ is the
minimum objective value of problem (20) with $\hat{\epsilon}$, it follows that
$\sum\delta^{\star}[n]\geq\sum\hat{\delta}[n]$, which thus completes the proof
of Theorem 2.

###  -D Proof of Theorem 3

Let the first derivative of the objective function of problem (IV-A) w.r.t.
$\tau_{k}[n]$ be zeros, i.e.,

$\displaystyle\\!\\!\\!\\!\sum_{k=1}^{K}\\!\mu_{k}[n]\\!+\\!\lambda_{k}\frac{\sigma^{2}}{h_{k}[n]}\Big{(}\\!2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}\\!-\\!\frac{a_{k}[n]s\ln
2}{B\tau_{k}[n]}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}\\!-\\!1\\!\Big{)}\\!=\\!0.$
(61)

We can rewritten equation (61) as

$\displaystyle\Big{(}\frac{a_{k}[n]s\ln
2}{B\tau_{k}[n]}-1\Big{)}2^{\frac{a_{k}[n]s}{B\tau_{k}[n]}}=\frac{h_{k}[n]\sum_{k=1}^{K}\mu_{k}[n]}{\lambda_{k}\sigma^{2}}-1.$
(62)

By solving the above equation, one can have $\frac{a_{k}[n]s\ln
2}{B\tau_{k}[n]}-1=\mathcal{W}\Big{(}\frac{h_{k}[n]\sum_{k=1}^{K}\mu_{k}[n]}{e\lambda_{k}\sigma^{2}}-\frac{1}{e}\Big{)}.$
By simplifying the above equation, we can have that

$\displaystyle\tau_{k}[n]=\frac{a_{k}[n]s\ln
2}{B\Big{(}\mathcal{W}\Big{(}\frac{h_{k}[n]\sum_{k=1}^{K}\mu_{k}[n]}{e\lambda_{k}\sigma^{2}}-\frac{1}{e}\Big{)}+1\Big{)}}.$
(63)

Thus, this completes the proof.

###  -E Proof of Proposition 2

We denote
$T^{\star}(\bm{A}^{\star},\bm{\Gamma}^{\star},\bm{\delta}^{\star},\bm{Q}^{\star})=\sum_{n=1}^{N}\delta^{\star}[n]$
as the objective value of problem (20) with solution
$\\{\bm{A}^{\star},\bm{\Gamma}^{\star},\bm{\delta}^{\star},\bm{Q}^{\star}\\}$.
As shown in step 5 of Algorithm 3, a feasible solution of problem (40) (i.e.,
$\\{\bm{A}^{r},\bm{\Gamma}^{r},\bm{\delta}^{r},\bm{Q}^{r}\\}$) is also
feasible to problem (25). We denote
$\\{\bm{A}^{r},\bm{\Gamma}^{r},\bm{\delta}^{r},\bm{Q}^{r}\\}$ and
$\\{\bm{A}^{r+1},\bm{\Gamma}^{r+1},\bm{\delta}^{r+1},\bm{Q}^{r+1}\\}$ as a
feasible solution of problem (20) at the $r$-th and $(r+1)$-th iterations,
respectively.

Because, given $\bm{Q}^{r}$ as shown in step 4 of Algorithm 3,
$\\{\bm{A}^{r+1},\bm{\Gamma}^{r+1},\bm{\delta}^{r+1}\\}$ is the optimal
solution to problem (25), we have

$\displaystyle T(\bm{A}^{r},\bm{\Gamma}^{r},\bm{\delta}^{r},\bm{Q}^{r})\geq
T(\bm{A}^{r+1},\bm{\Gamma}^{r+1},\bm{\delta}^{r+1},\bm{Q}^{r}).$ (64)

Similarly, given $\bm{A}^{r+1},\bm{\Gamma}^{r+1},\bm{\delta}^{r+1}$ as shown
in step 5 of Algorithm 3, $\bm{Q}^{r+1}$ is the optimal solution to problem
(41), it follows that

$\displaystyle\\!\\!\\!\\!T(\bm{A}^{r+1},\bm{\Gamma}^{r+1},\bm{\delta}^{r+1},\bm{Q}^{r})\\!=\\!T(\bm{A}^{r+1},\bm{\Gamma}^{r+1},\bm{\delta}^{r+1},\bm{Q}^{r+1}).$
(65)

This holds because the original objective function $T$ is independent of
$\bm{Q}$ but depends on $\bm{\delta}$. Based on $\eqref{p1}$ and $\eqref{p3}$,
we further obtain

$\displaystyle
T(\bm{A}^{r+1},\bm{\Gamma}^{r+1},\bm{\delta}^{r+1},\bm{Q}^{r+1})\leq
T(\bm{A}^{r},\bm{\Gamma}^{r},\bm{\delta}^{r},\bm{Q}^{r}),$ (66)

which shows that the objective value of problem (20) is always decreasing over
iterations. Therefore, the proposed BCD-LD algorithm converges. This thus
completes the proof.

## References

  * [1] 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. Tutorials, vol. 22, no. 3, pp. 2031–2063, 2020.
  * [2] Y. Shi, K. Yang, T. Jiang, J. Zhang, and K. B. Letaief, “Communication-Efficient Edge AI: Algorithms and Systems,” IEEE Commun. Surv. Tutorials, vol. 22, no. 4, pp. 2167–2191, 2020.
  * [3] K. B. Letaief, Y. Shi, J. Lu, and J. Lu, “Edge artificial intelligence for 6G: Vision, enabling technologies, and applications,” IEEE J. Sel. Areas Commun., vol. 40, pp. 5–36, Jan. 2022.
  * [4] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” IEEE Signal Process. Mag., vol. 37, pp. 50–60, May 2020.
  * [5] Z. Zhou, X. Chen, E. Li, L. Zeng, K. Luo, and J. Zhang, “Edge intelligence: Paving the last mile of artificial intelligence with edge computing,” Proc. IEEE, vol. 107, pp. 1738–1762, Aug. 2019.
  * [6] K. Yang, T. Jiang, Y. Shi, and Z. Ding, “Federated learning via over-the-air computation,” IEEE Trans. Wireless Commun., vol. 19, pp. 2022–2035, Mar. 2020.
  * [7] S. Savazzi, M. Nicoli, M. Bennis, S. Kianoush, and L. Barbieri, “Opportunities of federated learning in connected, cooperative, and automated industrial systems,” IEEE Commun. Mag., vol. 59, pp. 16–21, Feb. 2021.
  * [8] L. Li, L. Yang, X. Guo, Y. Shi, H. Wang, W. Chen, and K. B. Letaief, “Delay analysis of wireless federated learning based on saddle point approximation and large deviation theory,” IEEE J. Select. Areas Commun., vol. 39, pp. 3772–3789, Dec. 2021.
  * [9] A. Imteaj, U. Thakker, S. Wang, J. Li, and M. H. Amini, “A survey on federated learning for resource-constrained IoT devices,” IEEE Internet Things J., vol. 9, pp. 1–24, Jan. 2022.
  * [10] G. Zhu, Y. Wang, and K. Huang, “Broadband analog aggregation for low-latency federated edge learning,” IEEE Trans. Wireless Commun., vol. 19, pp. 491–506, Jan. 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, pp. 2457–2471, Apr. 2021.
  * [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, pp. 7690–7703, Nov. 2020.
  * [13] M. M. Amiri, D. Gunduz, 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, pp. 3643–3658, Jun. 2021.
  * [14] Z. Lin, H. Liu, and Y.-J. A. Zhang, “Relay-assisted cooperative federated learning,” IEEE Trans. Wireless Commun., Jul. 2022, doi: 10.1109/TWC.2022.3155596.
  * [15] H. Liu, X. Yuan, and Y.-J. A. Zhang, “Reconfigurable intelligent surface enabled federated learning: A unified communication-learning design approach,” IEEE Trans. Wireless Commun., vol. 20, pp. 7595–7609, Nov. 2021\.
  * [16] Z. Wang, J. Qiu, Y. Zhou, Y. Shi, L. Fu, W. Chen, and K. B. Letaief, “Federated learning via intelligent reflecting surface,” IEEE Trans. Wireless Commun., vol. 21, pp. 808–822, Feb. 2022.
  * [17] Y. Yang, Y. Zhou, Y. Wu, and Y. Shi, “Differentially private federated learning via reconfigurable intelligent surface,” IEEE Internet of Things J., 2022, doi:10.1109/JIOT.2022.3168066.
  * [18] H. Chen, M. Xiao, and Z. Pang, “Satellite based computing networks with federated learning,” IEEE Wirel. Commun., vol. 29, no. Feb., pp. 78–84, 2022.
  * [19] Y. Zeng, Q. Wu, and R. Zhang, “Accessing from the sky: A tutorial on UAV communications for 5G and beyond,” Proc. IEEE, vol. 107, pp. 2327–2375, Mar. 2019.
  * [20] W. Y. B. Lim, S. Garg, Z. Xiong, Y. Zhang, D. Niyato, C. Leung, and C. Miao, “UAV-assisted communication efficient federated learning in the era of the artificial intelligence of things,” IEEE Netw., vol. 35, pp. 188–195, Sep. 2021.
  * [21] M. Fu, Y. Zhou, Y. Shi, W. Chen, and R. Zhang, “UAV aided over-the-air computation,” IEEE Trans. Wireless Commun., 2021, doi: 10.1109/TWC.2021.3134327.
  * [22] 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, pp. 398–409, Feb. 2021.
  * [23] Q. Ma, Y. Xu, H. Xu, Z. Jiang, L. Huang, and H. Huang, “Fedsa: A semi-asynchronous federated learning mechanism in heterogeneous edge computing,” IEEE J. Sel. Areas Commun., vol. 39, pp. 3654–3672, Dec. 2021\.
  * [24] C. Zhan and Y. Zeng, “Completion time minimization for multi-UAV-enabled data collection,” IEEE Trans. Wireless Commun., vol. 18, pp. 4859–4872, Oct. 2019.
  * [25] Y. Liu, J. Nie, X. Li, S. H. Ahmed, W. Y. B. Lim, and C. Miao, “Federated learning in the sky: Aerial-ground air quality sensing framework with UAV swarms,” IEEE Internet Things J., vol. 8, no. 12, pp. 9827–9837, 2021\.
  * [26] W. Y. B. Lim, J. Huang, Z. Xiong, J. Kang, D. Niyato, X.-S. Hua, C. Leung, and C. Miao, “Towards federated learning in UAV-enabled internet of vehicles: A multi-dimensional contract-matching approach,” IEEE Trans. Intell. Transp. Syst., vol. 22, pp. 5140–5154, Aug. 2021.
  * [27] J. S. Ng, W. Y. B. Lim, H.-N. Dai, Z. Xiong, J. Huang, D. Niyato, X.-S. Hua, C. Leung, and C. Miao, “Joint auction-coalition formation framework for communication-efficient federated learning in UAV-enabled internet of vehicles,” IEEE Trans. Intell. Transp. Syst., vol. 22, pp. 2326–2344, Apr. 2021.
  * [28] H. Yang, J. Zhao, Z. Xiong, K.-Y. Lam, S. Sun, and L. Xiao, “Privacy-preserving federated learning for UAV-enabled networks: Learning-based joint scheduling and resource management,” IEEE J. Sel. Areas Commun., vol. 39, pp. 3144–3159, Oct. 2021.
  * [29] 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, pp. 1935–1949, Mar. 2021.
  * [30] Q. Wu, Y. Zeng, and R. Zhang, “Joint trajectory and communication design for multi-UAV enabled wireless networks,” IEEE Trans. Wireless Commun., vol. 17, pp. 2109–2121, Mar. 2018.
  * [31] F. Zhou, Y. Wu, R. Q. Hu, and Y. Qian, “Computation rate maximization in UAV-enabled wireless-powered mobile-edge computing systems,” IEEE J. Sel. Areas Commun., vol. 36, pp. 1927–1941, Sept. 2018.
  * [32] L. Bottou, F. E. Curtis, and J. Nocedal, “Optimization methods for large-scale machine learning,” SIAM Rev., vol. 60, no. 2, pp. 223–311, 2018.
  * [33] S. Wang, T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan, “Adaptive federated learning in resource constrained edge computing systems,” IEEE J. Sel. Areas Commun., vol. 37, pp. 1205–1221, Jun. 2019\.
  * [34] Z. Allen-Zhu, “Natasha 2: Faster non-convex optimization than SGD,” in Proc. Adv. Neural Inf. Process. Syst. (NeurIPS), (Montreal, Canada), 2018.
  * [35] Q. Zeng, Y. Du, and K. Huang, “Wirelessly powered federated edge learning: Optimal tradeoffs between convergence and power transfer,” IEEE Trans. Wireless Commun., vol. 21, pp. 680–695, Jan. 2022.
  * [36] H. Yu, S. Yang, and S. Zhu, “Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning,” in Proc. AAAI Conf. Artif. Intell., (Honolulu, USA), 2019.
  * [37] D. Liu and O. Simeone, “Privacy for free: Wireless federated learning via uncoded transmission with adaptive power control,” IEEE J. Sel. Areas Commun., vol. 39, pp. 170–185, Jan. 2021.
  * [38] 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.
  * [39] W. Xia, T. Q. S. Quek, K. Guo, W. Wen, H. H. Yang, and H. Zhu, “Multi-armed bandit-based client scheduling for federated learning,” IEEE Trans. Wireless Commun., vol. 19, pp. 7108–7123, Nov. 2020.
  * [40] Y. Xu and W. Yin, “A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion,” SIAM J. Imag. Sci., vol. 6, no. 3, pp. 1758–1789, 2013.
  * [41] A. Krizhevsky, G. Hinton, et al., “Learning multiple layers of features from tiny images,” 2009.
  * [42] FAA, Summary of small unmanned aircraft rule.  Washington, DC: Federal Aviation Administration, 2016.