# Robust Design of Federated Learning for Edge-Intelligent Networks

Qiao Qi and Xiaoming Chen Qiao Qi<EMAIL_ADDRESS>and Xiaoming Chen
<EMAIL_ADDRESS>are with the College of Information Science and
Electronic Engineering, Zhejiang University, Hangzhou 310027, China.

###### Abstract

Mass data traffics, low-latency wireless services and advanced artificial
intelligence (AI) technologies have driven the emergence of a new paradigm for
wireless networks, namely edge-intelligent networks, which are more efficient
and flexible than traditional cloud-intelligent networks. Considering users’
privacy, model sharing-based federated learning (FL) that migrates model
parameters but not private data from edge devices to a central cloud is
particularly attractive for edge-intelligent networks. Due to multiple rounds
of iterative updating of high-dimensional model parameters between base
station (BS) and edge devices, the communication reliability is a critical
issue of FL for edge-intelligent networks. We reveal the impacts of the errors
generated during model broadcast and model aggregation via wireless channels
caused by channel fading, interference and noise on the accuracy of FL,
especially when there exists channel uncertainty. To alleviate the impacts, we
propose a robust FL algorithm for edge-intelligent networks with channel
uncertainty, which is formulated as a worst-case optimization problem with
joint device selection and transceiver design. Finally, simulation results
validate the robustness and effectiveness of the proposed algorithm.

###### Index Terms:

Edge-intelligent networks, federated learning, resource allocation, robust
design

##  I Introduction

The sixth-generation (6G) wireless networks are desired to support a variety
of advanced wireless services, such as AR/VR, smart city, and video/audio
surveillance, which generate a vast amount of data at edge devices [1]-[3]. In
order to decrease transmission delay and communication burden, it is appealing
to process these data at the network edge, but not the cloud servers. Driven
by such a requirement, many researchers predict that 6G wireless networks will
be edge-intelligent networks powered by the integration of edge computing and
machine learning [4], [5].

Actually, edge intelligence has attracted considerable interests from both
academia and industry. Traditional data-sharing-based edge-intelligent
networks require to convey a large volume of data from edge devices to the
base station (BS) for training a global model [6], [7]. However, it not only
leads to network congestion due to mass data transmission, but also causes the
personal privacy leakage. With the rapid development of information technology
and chip technology, the federated edge learning (FEEL) framework has been
developed to address these issues, which implements distributed machine
learning at the network edge (e.g., intelligent devices and the BS) [8]. In
this context, model-sharing-based federated learning (FL) with the nature of
privacy protection has emerged as a new branch for edge-intelligent networks
[9]. Different from conventional edge intelligence supported by data sharing,
FL exploits the computation capabilities of multiple intelligent devices,
which are coordinated by an edge server, e.g., the BS, to cooperatively train
a global model in an iterative manner [10]. Specifically, in each iteration
(also called a communication round) of FL, the edge server first broadcasts
the global model parameters to the devices, such that all participating
devices can synchronize and initialize their local models. After that, each
participating device individually trains and updates the local model based on
its own dataset, and then sends the updated local model parameters to the edge
server for global model aggregation. Since the whole training process of the
global model only involves the transmission of model parameters rather than
real raw data, FL is very appealing to edge-intelligent networks for data
analysis and processing with better privacy.

###  I-A Related Works and Motivation

Since the exchange of model parameters between the server and the devices is a
key process of FL, the design of communication-efficient FL has received wide
attention in recent years. As a leading and widely used algorithm in FL,
federated averaging (FedAvg), also called model-average FL, runs stochastic
gradient descent (SGD) in parallel on a portion of the total devices and
obtains the global model by averaging the model parameters, which effectively
reduces the number of communication rounds for global model aggregation [11].
In particular, FedAvg has been shown to work in real-world settings by Google
with their GBoard in next-word-prediction [12] and emjoi-prediction [13].
Based on FedAvg, many excellent FL algorithms have emerged. For example, the
federated proximal (FedProx) algorithm was proposed by adding regularization
on each local loss function [14]. Additionally, Acar et. al. introduced the
federated learning with dynamic regularization (FedDyn) algorithm as a
solution to heterogenous dataset setting [15], which dynamically regularizes
each devices’ loss function such that the modified device losses converge to
the actual global loss.

In practice, edge devices are usually connected through long-distance wireless
access. Due to limited radio resources and iterative transmissions of high-
dimensional model parameters, especially when applying deep neural networks
(DNNs) into model training as DNNs nowadays often have millions of parameters
[16], the high communication burden is a main challenge of FL for edge-
intelligent networks. To this end, some prior works attempted to solve it in
various aspects. From the perspective of machine learning, it is usual to
reduce the communication load by decreasing the number of participating
devices or compressing the model parameters via quantization and
sparsification. For example, the authors in [17] proposed a joint learning and
communication framework for FL by resource allocation and device selection
with the goal of minimizing an FL loss function. In [18], an universal vector
quantization scheme for FL was put forward to effectively reduce the
communication-latency. These methods from the aspect of machine learning
regard wireless channels as a set of independent error-free bit-limited links
between the devices and the server. In fact, the transmission of model
parameters over wireless channels are inevitably affected by channel fading,
interference, and noise. As a result, the performance of FL is unsatisfactory.
Thus, it is necessary to develop novel transmission schemes to achieve
communication-efficient FL.

During the transmission of model parameters in FL, co-channel interference has
a great impact. To avoid the interference and achieve accurate model
aggregation, a common way is to adopt an orthogonal multiple access (OMA)
scheme, i.e., allocating an orthogonal resource block to each participating
device for uploading its local model parameters [19]-[21]. In [19], the
authors studied a probabilistic scheduling framework of FL based on orthogonal
frequency-division multiple access (OFDMA). Besides, energy-efficient radio
resource allocation algorithms for FL over wireless fading channels supported
by OMA schemes were proposed in [20] and [21]. Yet, such approaches
substantially restrict the number of accessible devices that participate in FL
under limited spectrum resources. In particular, it causes a high transmission
latency and a low spectrum efficiency when the number of participating devices
for FL is large, and thus is no longer applicable for edge-intelligent
networks with a massive number of devices. In this context, a promising
solution called _over-the-air computation_ (AirComp) has been proposed and
raised wide interests [22, 23], which exploits the superposition property of
wireless multiple access channels (MACs) to compute a class of _nomographic
functions_ of distributed data from devices via concurrent transmission [24].
Fortunately, the averaging method for global model aggregation in the FedAvg
algorithm falls into the category of nomographic functions. Hence, it is
possible to effectively enhance the learning performance by applying AirComp
into model-average FL for fast model aggregation and accurate learning
performance. For example, the authors in [25] developed a convergent over-the-
air FL algorithm by introducing a time-varying precoding and scaling scheme.
In [26], a novel digital over-the-air aggregation scheme was proposed to
alleviate the effects of wireless channel hostilities on the convergence rate
of FL.

To achieve accurate model aggregation based on AirComp over fading channels,
the devices need to have channel state information (CSI) to carry out channel
pre-equalization. Yet, inaccurate channel estimation and hardware impairment
at the devices may cause imperfect equalization, and thereby distort the
aggregated model. Some works have taken into consideration the aggregation
error via uplink and designed efficient schemes to improve the system
performance. For example, the authors in [27] derived the trade-off between
communication and learning, and proposed a broadband analog aggregation scheme
for FL to reduce the communication-latency. In [28], a resource allocation
scheme for AirComp-based on-device distributed FL system was proposed to
reduce the aggregation error and improve the learning performance when the
edge server was equipped with multiple antennas. In [29], the authors proposed
a novel AirComp-based FL system to achieve fast and reliable model aggregation
by utilizing the intelligent reflecting surface to compensate for the
magnitude reduction and misalignment of AirComp. However, most of exiting
works for Aircomp-based FL mainly focus on the effect of parameter
transmission via uplink while overlooking the impact of downlink parameters
transmission for model broadcast. In fact, due to imperfect channel
estimation, feedback quantization, or delay in signal acquisition on fading
channels, the received model parameters at the devices may not be perfectly
recovered. Such model distortion caused by unfavourable wireless transmission
leads to performance degradation in terms of convergence speed and prediction
accuracy. This key observation is also noted in a recent parallel work [30],
which assumed an error-free parameter aggregation over uplink and focused on
studying the impact of noisy downlink on the FL performance. Then, an analog
downlink transmission approach was proposed and the convergence of FL for the
proposed downlink approach was well studied. In order to compare related works
more clearly, we list a comparison table to highlight the contribution of our
work, cf. Table I. Besides, the number of participating devices at each
communication round is also a critical factor of the FL performance, which has
different impacts on learning and communication. On the one hand, selecting
more devices to participate in FL can collect more information from
distributed devices by model aggregation, which is benefit to the convergence
of global model. On the other hand, the error caused by AirComp-based model
aggregation via wireless transmission increases as the number of participating
devices for FL increases, which in turn results in the degradation of learning
performance. Thus, it is necessary to characterize the effects of the number
of participating devices and the distortion of transmitted model on the
performance of FL, and then design a corresponding transmission scheme for FL
in edge-intelligent networks.

TABLE I: The comparison of related works |  [30] |  [28] |  Our work
---|---|---|---
FL Model |  Gradient-average FL |  Model-average FL |  Model-average FL
Uplink Error |  No |  Yes |  Yes
Downlink Error |  Yes |  No |  Yes
CSI |  Perfect |  Perfect |  Imperfect
Transceiver |  Downlink: zero-forcing receiver at the device |  Uplink: receiver at the BS based on the optimization problem with a given zero-forcing transmitter at the device |  Uplink/Downlink: adaptive transceivers based on the optimization problem
Objective |  Analyzing the convergence of FL for the proposed downlink transmission approach |  Improving the FL performance by optimizing device selection and the receiver at the BS |  Improving the FL performance by optimizing device selection and transceiver design

###  I-B Contributions

In this paper, we consider a practical edge-intelligent network with imperfect
CSI, inevitably leading to errors of both model aggregation and model
broadcast in the training process of FL. To improve the performance of model-
average FL via AirComp, we provide a robust transmission scheme for FL in
edge-intelligent networks. The contributions of this paper are three-fold:

  1. 1.

We propose a communication-efficient FL framework for edge-intelligent
networks under practical but adverse conditions, where the BS as an edge sever
only has partial CSI due to imperfect channel estimation or feedback. To
realize fast model aggregation, AirComp technique is applied into model-
average FL for effectively improving the communication efficiency over limited
radio resources.

  2. 2.

We study the distortion in the received models at both the BS and the devices
caused by wireless transmission and reveal the impacts of the errors of model
parameter transmission and the number of participating devices on the
performance of FL. Specifically, the combination of the broadcast error over
the downlink and the aggregation error over the uplink may lead to a notable
degradation of learning performance, while the convergence of training can be
accelerated with more involved devices.

  3. 3.

We provide a robust transmission scheme with joint device selection and
transceiver design to improve the performance of FL. This design is formulated
as a computationally difficult combinatorial optimization problem, which
maximizes the number of selected devices while satisfying the MSE requirements
of model broadcast via downlink and model aggregation via uplink,
respectively. Then, an effective algorithm is proposed to solve such a
complicated nonconvex problem and obtain a feasible sub-optimal solution.

###  I-C Organization and Notations

The rest of this paper is organized as follows: Section II gives a concise
introduction of a practical FL framework for edge-intelligent networks.
Section III focuses on the robust design of a communication-efficient
transmission scheme for FL. Section IV presents extensive simulation results
to validate the effectiveness and robustness of the proposed scheme. Finally,
Section V summarizes the paper.

_Notations_ : We use bold upper (lower) letters to denote matrices (column
vectors), $(\cdot)^{H}$ to denote conjugate transpose, $\|\cdot\|_{0}$ to
denote the $\ell_{0}$-norm of a vector, $\|\cdot\|_{1}$ to denote the
$\ell_{1}$-norm of a vector, $\|\cdot\|$ to denote the $\ell_{2}$-norm of a
vector, $|\cdot|$ to denote the absolute value of a scalar or the size of a
set, $\mathrm{Re}\\{\cdot\\}$ to denote the real parts of matrices,
${{\mathbb{C}}^{M\times N}}$ to denote the set of $M$-by-$N$ dimensional
complex matrix, ${{\mathbb{R}}^{m\times n}}$ to denote the set of $m$-by-$n$
dimensional real matrix, $\mathbb{E}\\{\cdot\\}$ to denote expectation, and
$\mathcal{CN}(\mu,\sigma^{2})$ to denote the circularly symmetric complex
Gaussian (CSCG) distribution with mean $\mu$ and variance $\sigma^{2}$.

##  II System Model

Figure 1: A model of an edge-intelligent network.

Consider a single-cell edge-intelligent network operated in the time division
duplex (TDD) mode111The proposed scheme can be directly extended to the
multiple-cell scenario by taking into account inter-cell interference., cf.
Fig. 1, which consists of a BS equipped with $N$ antennas serving as an edge
server, and $K$ single-antenna intelligent devices. A computation model for
data analysis and processing at the BS is trained with the aid of intelligent
devices based on FL.

###  II-A FL Model

For FL, a shared learning process with a global model $\mathbf{q}$ is trained
cooperatively by multiple selected intelligent devices. Each selected device
$k\in\mathcal{K}=\\{1,2,\ldots,K\\}$ has its own local dataset
$\mathcal{D}_{k}$ with labeled data samples
$\left\\{\left(\mathbf{g}_{j},l_{j}\right)\right\\}\in\mathcal{D}_{k}$, where
$\left(\mathbf{g}_{i},l_{i}\right)$ denotes the input-output data pair
consisting of training vector sample $\mathbf{g}_{i}$ and its ground-truth
label $l_{i}$. The sample-wise loss function is defined as
$f_{i}(\mathbf{q};\mathbf{g}_{i},l_{i})$ for sample $i$. Then, the global loss
function on all distributed datasets can be expressed as

$\mathcal{F}\left(\mathbf{q}\right)=\frac{1}{\left|{{D}_{\text{total}}}\right|}\sum\limits_{j\in{{D}_{\text{total}}}}{f_{j}\left(\mathbf{q};{{\mathbf{g}}_{j}},{{l}_{j}}\right)},$
(1)

where
${{D}_{\text{total}}}=\left\\{{{D}_{1}},{{D}_{2}},\cdots,{{D}_{K}}\right\\}$,
and $\left|{{D}_{\text{total}}}\right|$ is the size of dataset
${{D}_{\text{total}}}$. The learning target is to optimize the model
$\mathbf{q}$ by minimizing the global loss function $\mathcal{F}(\mathbf{q})$,
i.e.,

$\mathbf{q}^{*}=\arg\min\mathcal{F}(\mathbf{q}).$ (2)

The model-averaging FL algorithm is commonly employed to find the optimal
model $\mathbf{q}^{*}$ in an iterative manner, which obtains the global model
$\mathbf{q}$ by averaging the local models $\mathbf{q}_{k}$ without the need
of sharing datasets among the intelligent devices. Due to the transmission of
model parameters between the BS and the devices via wireless links, received
model parameters may be distorted. For example, imperfect channel estimation,
feedback quantization, or delay in signal acquisition on fading channels may
lead to imperfect recovery of model parameters at the BS and at the devices.
In general, the distortion of the received model at the devices and the BS in
the $t$-th iteration can be modeled as

Devices:
$\displaystyle\mathbf{q}_{i}^{[t]}=\mathbf{q}^{[t-1]}+\Delta\mathbf{q}_{i}^{[t]},i\in{\mathcal{S}_{t}},$
(3a) BS:
$\displaystyle\mathbf{q}^{[t]}=\frac{1}{\sum\limits_{i\in\mathcal{S}_{t}}{\left|{{D}_{i}}\right|}}\sum\limits_{i\in\mathcal{S}_{t}}{{\left|{{D}_{i}}\right|}\mathbf{q}_{i}^{[t]}}+\Delta\mathbf{q}^{[t]},$
(3b)

where $\mathcal{S}_{t}$ is the selected device set in the $t$-th iteration,
$\Delta\mathbf{q}_{i}^{[t]}$ and $\Delta\mathbf{q}^{[t]}$ are the broadcast
error at the $i$-th device and the aggregation error at the BS in the $t$-th
iteration, respectively. In summary, the model-average FL algorithm is
described as Algorithm 1. Note that for step 4 of Algorithm 1, a single-step
SGD method updates the local model, which is given by

$\mathbf{q}_{i}^{[t]}=\mathbf{{q}}_{i}^{[t-1]}-\eta_{i}\nabla{\mathcal{F}_{i}}\left(\mathbf{{q}}_{i}^{[t-1]}\right),$
(4)

where $\eta_{i}$ is the learning step size and
$\nabla{\mathcal{F}_{i}}\left(\mathbf{{q}}_{i}^{[t-1]}\right)$ is the gradient
of ${\mathcal{F}_{i}}\left(\mathbf{{q}}_{i}^{[t-1]}\right)$ at the point
$\mathbf{{q}}_{i}^{[t-1]}$. Then, the updated local model
$\mathbf{q}_{i}^{[t]}$ can be obtained until convergence by $\tau$-step
($\tau\geq 1$) SGD repeating the updating rule in (4).

Algorithm 1 : Model-average FL algorithm for edge-intelligent networks.

1: Initialize global model $\mathbf{q}^{[0]}$, communication round index
$t=1$;

2: repeat

3: The BS determines the participating devices set
$\mathcal{S}_{t}\in\mathcal{K}$;

4: The BS broadcasts the current global model $\mathbf{q}^{[t-1]}$ to the
participating devices via downlink.

5: Based on the received model
$\mathbf{q}_{i}^{[t]}=\mathbf{q}^{[t-1]}+\Delta\mathbf{q}_{i}^{[t]}$, each
device $i\in\mathcal{S}_{t}$ performs a SGD algorithm to update the local
model with its own dataset $D_{i}$.

6: Participating devices upload their updated local models
$\mathbf{q}_{i}^{[t]}$ to the BS via uplink;

7: The BS updates the global model as
$\mathbf{q}^{[t]}=\frac{1}{\sum\limits_{i\in\mathcal{S}_{t}}{\left|{{D}_{i}}\right|}}\sum\limits_{i\in\mathcal{S}_{t}}{{\left|{{D}_{i}}\right|}\mathbf{q}_{i}^{[t]}}+\Delta\mathbf{q}^{[t]}$;

8: $t=t+1$;

9: until Global model convergence

In the following, we train a convolutional neural network (CNN) on the
commonly used MNIST dataset with the model-average FL to show the impacts of
the number of selected devices, model aggregation error, and model broadcast
error on the prediction accuracy. The detailed experiment setup is presented
in Section IV. To simulate the model distortion caused by model aggregation
and broadcast errors, we add Gaussian noise to the received models at the BS
and the devices, respectively. It is seen from Fig. 2 that the performance gap
between Benchmark (ideal situation without aggregation error and broadcast
error) and the case without aggregation error is negligible. This is because
broadcast error is applied to the initial local model, but the device can
adjust its neural network to achieve a good training performance. However, if
aggregation error exists, the effect of broadcast error aggravates the
performance deterioration. Thus, it is necessary to consider both aggregation
error and broadcast error in the design of FL. Moreover, it is found that the
number of selected devices is also a critical factor on the prediction
accuracy of FL [9], [10], [17]. Note that the errors are mainly caused by
channel fading and additive noise during model aggregation and broadcast over
wireless channels. Motivated by these observations, we propose to jointly
conduct device selection and transceiver design to enhance the FL performance
by maximizing the number of devices participating in FL while guaranteeing
aggregation error and broadcast error to be within a certain range.

Figure 2: The test accuracy of FL versus communication rounds under different
error situation with all devices, where $\gamma_{D}$ and $\gamma_{B}$ are the
MSE at the devices and at the BS.

###  II-B Transmission Model

As mentioned above, model broadcast and model aggregation are both implemented
by parameter transmission over wireless channels. Referring to prior works on
resource allocation for wireless FL, we apply the similar assumptions to
facilitate analysis. First, we assume Rayleigh block flat-fading channels,
where the channel coefficients remain constant within a communication block,
but independently fade over successive blocks. Due to limited data storage and
computing capability of intelligent devices, the dimension of model parameters
$d$ is set to ensure that the entire model parameters can be transmitted
within a communication block. Moreover, it is assumed that the transmitted
model parameters $\mathbf{q}\in\mathbb{R}^{d\times 1}$ and
$\mathbf{q}_{i}\in\mathbb{R}^{d\times 1},i\in\mathcal{K}$ are independent and
normalized to have zero mean and unit variance [28, 29], i.e.,
$\mathbb{E}\left[\mathbf{q}\mathbf{q}^{\mathrm{H}}\right]=\mathbf{I}_{d}$ and
$\mathbb{E}\left[\mathbf{q}_{i}\mathbf{q}_{i}^{\mathrm{H}}\right]=\mathbf{I}_{d}$.
To simplify the notation, we will drop the communication round index $t$ and
discuss a typical entry of the transmitted vector signal, which is denoted by
$q$ at the BS for downlink and ${q}_{i}$ at the $i$-th device for uplink in
the following.

####  II-B1 Model broadcast via downlink

In the stage of model broadcast, the BS broadcasts the transmit signal
$\mathbf{x}_{BS}$ constructed based on the global model parameters over the
downlink channels as follows

$\mathbf{x}_{BS}=\mathbf{w}q,$ (5)

where $\mathbf{w}$ is an $N$-dimensional transmit beam. Then, the received
signal at the $k$-th device can be expressed as

${{y}_{k}}=\mathbf{h}_{k}^{H}\mathbf{x}_{BS}+{{n}_{k}},$ (6)

where $\mathbf{h}_{k}$ denotes the channel vector from the $k$-th device to
the BS, and ${{n}_{k}}$ is additive white Gaussian noise (AWGN) with variance
$\sigma_{0}^{2}$. Therefore, the mean-square error (MSE) measuring the model
distortion at the $k$-th device is given by

$\displaystyle\\!\\!\\!\\!\text{MSE}_{k}^{\text{Device}}$ $\displaystyle=$
$\displaystyle\mathbb{E}\left\\{\left({{v}_{k}}{{y}_{k}}-q\right){{\left({{v}_{k}}{{y}_{k}}-q\right)}^{H}}\right\\}$
$\displaystyle=$
$\displaystyle{{\left|{{v}_{k}}\mathbf{h}_{k}^{H}\mathbf{w}-1\right|}^{2}}+\sigma_{0}^{2}{{\left|{{v}_{k}}\right|}^{2}},$

where ${{v}_{k}}$ denotes the receiver scalar at the $k$-th device.

####  II-B2 Model aggregation via uplink

Since the average sum for model aggregation (1) belongs to the category of
nomographic functions [24], AirComp as a feasible solution is utilized to
improve the communication efficiency for model aggregation from distributed
devices. Based on the global loss function in (1), let $\phi_{i}(x)=|D_{i}|x$
and
$\varphi(x)=\frac{1}{\sum\limits_{i\in\mathcal{S}}{\left|{{D}_{i}}\right|}}x$
denote the pre-processing function at the $i$-th device and the post-
processing function at the BS, c.f., Fig. 3, respectively. Thus, the target of
aggregating local models at the BS is given by

$\tilde{q}=\frac{1}{\sum\limits_{i\in\mathcal{S}}{\left|{{D}_{i}}\right|}}\sum\limits_{i\in\mathcal{S}}{{\left|{{D}_{i}}\right|}q_{i}},$
(8)

where $\mathcal{S}$ is the selected device set. To simplify the analysis and
without loss of generality, we assume that all local datasets have a uniform
size in the following, i.e., $|D_{k}|=D,\forall k\in\mathcal{K}$. In this
context, the target of model aggregation in (8) can be reduced as

$\tilde{q}=\frac{1}{\left|\mathcal{S}\right|}\sum\limits_{i\in\mathcal{S}}{{{q}_{i}}}.$
(9)

To minimize the distortion of the targeted function signal caused by channel
fading and noise, it is desired to perform receive beamforming at the BS.
Thus, the received signal at the BS is given by

$\hat{q}={{\mathbf{z}}^{H}}\sum\limits_{i\in\mathcal{S}}{{{\mathbf{h}}_{i}}{{b}_{i}}{{q}_{i}}}+{{\mathbf{z}}^{H}}\mathbf{n},$
(10)

where $\mathbf{z}$ denotes the $N$-dimensional receive beam at the BS, $b_{i}$
is the transmit scalar at the $i$-th device, and $\mathbf{n}$ is the AWGN
vector with the distribution
$\mathcal{C}\mathcal{N}\left(\mathbf{0},\sigma_{1}^{2}\mathbf{I}\right)$.
Mathematically, the accuracy of model aggregation at the BS can be measured by
the MSE between $\sum\limits_{i\in\mathcal{S}}{{{q}_{i}}}$ and $\hat{q}$,
which is given by

$\displaystyle\text{MSE}_{\text{BS}}$ $\displaystyle=$
$\displaystyle\mathbb{E}\left\\{\left(\hat{q}-\sum\limits_{i\in
S}{{{q}_{i}}}\right){{\left(\hat{q}-\sum\limits_{i\in
S}{{{q}_{i}}}\right)}^{H}}\right\\}$ $\displaystyle=$
$\displaystyle\sum\limits_{i\in
S}{{{\left|{{\mathbf{z}}^{H}}{{\mathbf{h}}_{i}}{{b}_{i}}-1\right|}^{2}}}+\sigma_{1}^{2}{{\left\|\mathbf{z}\right\|}^{2}},$

Figure 3: The AirComp block diagram for the model aggregation.

Checking (II-B1) and (II-B2), the broadcast error and aggregation error are
jointly affected by the number of devices participating in FL, and the
transceivers at the BS and the devices, and thus determine the FL performance.
Hence, it makes sense to jointly perform device selection and transceiver
design according to instantaneous CSI. In edge-intelligent networks, it is
only able to obtain partial CSI due to imperfect channel estimation or
feedback. Thus, it is necessary to take channel uncertainty into consideration
for joint device selection and transceiver design, namely robust transmission
scheme design. To characterize the channel uncertainty, we adopt a commonly-
used deterministic CSI model [32, 33]. In particular, the real CSI
$\mathbf{h}_{i}$ related to the $i$-th device can be modeled as

$\mathcal{H}_{i}\triangleq\left\\{\mathbf{h}_{i}=\hat{\mathbf{h}}_{i}+\mathbf{e}_{i}\mid\left\|\mathbf{e}_{i}\right\|\leq\varepsilon_{i}\right\\},$
(12)

where $\hat{\mathbf{h}}_{i}$ is the obtained CSI and $\mathbf{e}_{i}$ is the
CSI error, whose norm is within a given radius $\varepsilon_{i}$. In what
follows, we make an effort to enhance the performance of FL from the
perspective of efficient communication.

##  III Robust Design of Transmission Scheme for FL

In this section, we aim to design a robust transmission scheme for
communication-efficient FL in edge-intelligent networks.

###  III-A Problem Formulation

Inspired by the key observations that the combination of the broadcast error
over the downlink and the aggregation errors over the uplink may lead to a
notable degradation of learning performance, while the convergence of training
can be accelerated with more involved devices, we propose to simultaneously
minimize the model distortion and maximize the number of involved devices
[28]. In particular, we propose to maximize the number of selected devices
while satisfying the MSE requirements of model broadcast via downlink and
model aggregation via uplink, respectively. According to the characteristic of
channel uncertainty in (12), we attempt to design a worst-case robust
transmission scheme, which is equivalent to the following optimization
problem:

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\underset{\mathcal{S},{{v}_{i}},{{b}_{i}},\mathbf{w},\mathbf{z}}{\mathop{\max}}\,\\!\\!\\!\\!\\!\\!$
$\displaystyle\\!\\!\\!\\!\left|\mathcal{S}\right|$ (13a) s.t.
$\displaystyle\\!\\!\\!\\!\\!\\!\underset{{{\mathbf{h}}_{i}}\in{\mathcal{H}_{i}}}{\mathop{\max}}\,\sum\limits_{i\in\mathcal{S}}{{{\left|{{\mathbf{z}}^{H}}{{\mathbf{h}}_{i}}{{b}_{i}}-1\right|}^{2}}}+\sigma_{1}^{2}{{\left\|\mathbf{z}\right\|}^{2}}\leq\gamma_{B},$
(13e)
$\displaystyle\\!\\!\\!\\!\underset{{{\mathbf{h}}_{i}}\in{\mathcal{H}_{i}}}{\mathop{\max}}\,{{\left|{{v}_{i}}\mathbf{h}_{i}^{H}\mathbf{w}-1\right|}^{2}}+\sigma_{0}^{2}{{\left|{{v}_{i}}\right|}^{2}}\leq{{\gamma}_{D,i}},i\in\mathcal{S},$
$\displaystyle\\!\\!\\!\\!{{b}_{i}}\leq\sqrt{{{P}_{i}}},i\in\mathcal{S},$
$\displaystyle\\!\\!\\!\\!{{\left\|\mathbf{w}\right\|}^{2}}\leq{{P}_{\max}},$

where $\left|\mathcal{S}\right|$ in the objective function (13a) is the number
of selected devices. $\gamma_{B}$ and ${{\gamma}_{D,i}}$ are the MSE
requirements of model aggregation at the BS and model broadcast at the $i$-th
device, respectively. (13e) and (13e) are the transmit power constraints at
the $i$-th device with a power budget $P_{i}$ and at the BS with a power
budget $P_{\max}$, respectively. It is intuitive that the mixed optimization
problem (13) is highly intractable due to the combinatorial objective function
$\left|\mathcal{S}\right|$. To solve this challenge, we introduce an auxiliary
variable $\bm{\chi}=[\chi_{1},\chi_{2},\ldots,\chi_{K}]^{T}$ to indicate the
priority of being selected for devices, which characterizes the gap between
the required MSE and the achievable MSE for the $k$-th device. In other words,
the smaller the value of $\chi_{k}$, the higher priority the $k$-th device to
be selected. By adding $\chi_{k}$ to the right hand side of the corresponding
MSE constraints, the objective function of maximizing the number of selected
devices is equivalent to minimizing the number of non-zero $\chi_{k}$ ([36],
section 11.4), where $\chi_{k}=0$ represents the $k$-th device being selected
to participate in FL. Thus, problem (13) can be reformulated as the following
sparsity minimization problem:

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\underset{{{v}_{k}},{{b}_{k}},\mathbf{w},\mathbf{z},\bm{\chi},\rho_{k},\vartheta_{k}}{\mathop{\min}}\,\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\\!\\!\\!\\!\|\bm{\chi}\|_{0}$ (14a) s.t.
$\displaystyle\\!\\!\\!\\!\underset{\|\mathbf{e}\|\leq\varepsilon_{k}}{\mathop{\max}}\,{{{\left|{{\mathbf{z}}^{H}}{\left({{{\mathbf{\hat{h}}}}_{k}}+{{\mathbf{e}}_{k}}\right)}{{b}_{k}}-1\right|}^{2}}}\\!\\!\leq\\!\\!\rho_{k}+\chi_{k},$
(14j)
$\displaystyle\\!\\!\\!\\!\sum\limits_{k\in\mathcal{K}}{\rho_{k}}+\sigma_{1}^{2}{{\left\|\mathbf{z}\right\|}^{2}}\\!\\!\leq\\!\\!\gamma_{B},$
$\displaystyle\\!\\!\\!\\!\underset{\|\mathbf{e}\|\leq\varepsilon_{k}}{\mathop{\max}}\,{{\left|{{v}_{k}}{\left({{{\mathbf{\hat{h}}}}_{k}}+{{\mathbf{e}}_{k}}\right)}^{H}\mathbf{w}-1\right|}^{2}}\leq\vartheta_{k},$
$\displaystyle\\!\\!\\!\\!\vartheta_{k}+\sigma_{0}^{2}{{\left|{{v}_{k}}\right|}^{2}}\leq{{\gamma}_{D,k}}+\chi_{k},$
$\displaystyle\\!\\!\\!\\!{{\left\|\mathbf{w}\right\|}^{2}}\leq{{P}_{\max}},$
$\displaystyle\\!\\!\\!\\!{{b}_{k}}\leq\sqrt{{{P}_{k}}},$
$\displaystyle\\!\\!\\!\\!\rho_{k}\geq 0,$
$\displaystyle\\!\\!\\!\\!\vartheta_{k}\geq 0,$
$\displaystyle\\!\\!\\!\\!\chi_{k}\geq 0,$

where $\rho_{k}$ and $\vartheta_{k}$ are auxiliary variables for splitting the
original MSE constraints in order to further deal with the non-convexity
caused by channel uncertainty. However, the sparsity minimization problem (14)
is still nonconvex due to the nonconvex sparse objective function (14a) and
nonconvex constraints (14j) and (14j) caused by channel uncertainty and
coupled variables, i.e., transmitter $\mathbf{w},b_{i}$ and receiver
$\mathbf{z},v_{i}$. To address these issues, we shall utilize the alternating
optimization (AO) method [35] to decouple the problem and resort to some
approximation means to solve the nonconvexity.

###  III-B Problem Solution

In this section, we propose a two-step algorithm framework to solve problem
(14) for joint device selection and transceiver design, including sparsity
inducing for determining the order of priority for devices and feasible
detection for finding the maximum number of selected devices while ensuring
the MSE requirements.

####  III-B1 Sparsity Inducing

For the untractable and non-convex sparse objective function in the form of
$\ell_{0}$-norm , we utilize a commonly used $\ell_{1}$-relaxation in the form
of $\ell_{1}$-norm [28], which is based on minimizing the sum of the
infeasibilities [36]. Thus, problem (14) can be rewritten as

$\displaystyle\underset{{{v}_{k}},{{b}_{k}},\mathbf{w},\mathbf{z},\bm{\chi},\rho_{k},\vartheta_{k}}{\mathop{\min}}\,$
$\displaystyle\\!\\!\\!\\!\|\bm{\chi}\|_{1}$ (15) s.t.
$\displaystyle\\!\\!\\!\\!(\ref{OP2st1})-(\ref{OP2st9}),$

Further, to address the non-convex constraint (14j) and (14j) involving the
channel uncertainty, we have to introduce the following lemmas.

_Lemma 1_ : (Schurs’s complement, [36]) Let $\mathbf{D}$ be a Hermitian matrix
defined as
$\mathbf{D}\text{=}\left[\begin{matrix}\mathbf{A}&{{\mathbf{B}}^{H}}\\\
\mathbf{B}&\mathbf{C}\\\ \end{matrix}\right]$, where $\mathbf{D}$ is positive
semi-definite if and only if
$\mathbf{A}-{{\mathbf{B}}^{H}}{{\mathbf{C}}^{\text{-1}}}\mathbf{B}\succeq\mathbf{0}$
with the invertible matrix $\mathbf{C}$ or
$\mathbf{C}-{{\mathbf{B}}^{H}}{{\mathbf{A}}^{\text{-1}}}\mathbf{B}\succeq\mathbf{0}$
with the invertible matrix $\mathbf{A}$.

_Lemma 2_ : Let us define a matrix function
$\mathbf{F}\left(\mathbf{x}\right)=\mathbf{A}-{{\mathbf{B}}^{{H}}}\mathbf{x}{{\mathbf{c}}^{{H}}}-\mathbf{c}{{\mathbf{x}}^{{H}}}\mathbf{B}$,
where variable vector $\mathbf{x}\in\mathbb{C}^{m\times 1}$, constant matrix
$\mathbf{B}\in\mathbb{C}^{m\times n}$, constant vector
$\mathbf{c}\in\mathbb{C}^{n\times n}$, and constant Hermitian matrix
$\mathbf{A}\in\mathbb{C}^{n\times n}$. Then,

$\mathbf{F}\left(\mathbf{x}\right)\geq\mathbf{0},\forall\mathbf{x}:\left\|\mathbf{x}\right\|\leq\varpi,$

holds true if and only if there exits $\lambda\geq 0$, such that

$\left[\begin{matrix}\mathbf{A}-\lambda\mathbf{c}{{\mathbf{c}}^{H}}&-\varpi{{\mathbf{B}}^{H}}\\\
-\varpi\mathbf{B}&\lambda{{\mathbf{I}}_{n}}\\\
\end{matrix}\right]\succeq\mathbf{0}.$

###### Proof:

Please refer to Appendix A. ∎

Now, we first deal with the constraint (14j), i.e.,

$\displaystyle{{{\left|{{\mathbf{z}}^{H}}{\left({{{\mathbf{\hat{h}}}}_{k}}+{{\mathbf{e}}_{k}}\right)}{{b}_{k}}-1\right|}^{2}}}$
(16) $\displaystyle=$
$\displaystyle{{\left|\left({{\mathbf{z}}^{H}}{{{\mathbf{\hat{h}}}}_{k}}{{b}_{k}}-1\right)+{{\mathbf{z}}^{H}}{{\mathbf{e}}_{k}}{{b}_{k}}\right|}^{2}}$
$\displaystyle\leq$ $\displaystyle\rho_{k}+\chi_{k}.$

Based on Lemma 1, (16) can be transformed as

$\displaystyle\left[\begin{matrix}{{\rho}_{k}}+{{\chi}_{k}}&b_{k}^{H}\mathbf{\hat{h}}_{k}^{H}\mathbf{z}-1+b_{k}^{H}\mathbf{ze}_{k}^{H}\\\
{{b}_{k}}{{\mathbf{z}}^{H}}{{{\mathbf{\hat{h}}}}_{k}}-1+{{b}_{k}}{{\mathbf{z}}^{H}}{{\mathbf{e}}_{k}}&1\\\
\end{matrix}\right]\succeq\mathbf{0},$
$\displaystyle\forall{{\mathbf{e}}_{k}}:\left\|{{\mathbf{e}}_{k}}\right\|\leq{{\varepsilon}_{k}}.$
(17)

Then, we let
${{\mathbf{A}}_{k}}\triangleq\left[\begin{matrix}{{\rho}_{k}}+{{\chi}_{k}}&{{b}_{k}^{H}}{{{\mathbf{\hat{h}}}}_{k}^{H}}{{\mathbf{z}}}-1\\\
{{b}_{k}}{{\mathbf{z}}^{H}}{{{\mathbf{\hat{h}}}}_{k}}-1&1\\\
\end{matrix}\right],{{\mathbf{B}}_{k}}\triangleq\left[\begin{matrix}\mathbf{0}&-b_{k}^{H}\mathbf{z}\\\
\end{matrix}\right],\mathbf{c}\triangleq{{\left[\begin{matrix}1&0\\\
\end{matrix}\right]}^{T}}.$ Combine with (III-B1), we have

${{\mathbf{F}}_{k}}({{\mathbf{e}}_{k}})={{\mathbf{A}}_{k}}-\mathbf{B}_{k}^{H}{{\mathbf{e}}_{k}}{{\mathbf{c}}^{H}}-\mathbf{ce}_{k}^{H}{{\mathbf{B}}_{k}}\succeq\mathbf{0},\forall{{\mathbf{e}}_{k}}:\left\|{{\mathbf{e}}_{k}}\right\|\leq{{\varepsilon}_{k}}.$
(18)

According to Lemma 2, the constraint (14j) can be reformulated as

$\left[\begin{matrix}{{\rho}_{k}}+{{\chi}_{k}}-{{\alpha}_{k}}&b_{k}^{H}\mathbf{\hat{h}}_{k}^{H}\mathbf{z}-1&\mathbf{0}\\\
{{b}_{k}}{{\mathbf{z}}^{H}}{{{\mathbf{\hat{h}}}}_{k}}-1&1&{{\varepsilon}_{k}}{{b}_{k}}{{\mathbf{z}}^{H}}\\\
\mathbf{0}&{{\varepsilon}_{k}}b_{k}^{H}\mathbf{z}&{{\alpha}_{k}}{{\mathbf{I}}_{N}}\\\
\end{matrix}\right]\succeq\mathbf{0},\exists{{\alpha}_{k}}\geq 0.$ (19)

Similarly, if there exists $\beta_{k}\geq 0$, the constraint (14j) can be
reformulated as

$\left[\begin{matrix}{{\vartheta}_{k}}-{{\beta}_{k}}&{{v}_{k}}\mathbf{\hat{h}}_{k}^{H}\mathbf{w}-1&\mathbf{0}\\\
{{\mathbf{w}}^{H}}{{{\mathbf{\hat{h}}}}_{k}}v_{k}^{H}-1&1&\varepsilon_{k}\mathbf{w}{{v}_{k}}\\\
\mathbf{0}&{{\varepsilon}_{k}}v_{k}^{H}{{\mathbf{w}}^{H}}&{{\beta}_{k}}\mathbf{I}_{N}\\\
\end{matrix}\right]\succeq\mathbf{0},\exists{{\beta}_{k}}\geq 0.$ (20)

Note that constraints (19) and (20) are still non-convex due to the coupled
variables. To this end, we develop an AO method to decouple problem (15).
Specifically, problem (15) can be divided into two subproblems, one for BS
transceiver design and another for device transceiver design. The AO method
will stop until the value of the objective function of the original problem
approaches a stationary point in the iterations. In this context, the first
subproblem of optimizing the device transceiver $\\{v_{k},b_{k}\\}$ by given
the BS transceiver $\\{\mathbf{w,z}\\}$ is equivalent to

$\displaystyle\\!\\!\\!\\!\\!\\!\underset{{{v}_{k}},{{b}_{k}},\bm{\chi},\rho_{k},\vartheta_{k},\alpha_{k},\beta_{k}}{\mathop{\min}}\,$
$\displaystyle\\!\\!\\!\\!\|\bm{\chi}\|_{1}$ (21a) s.t.
$\displaystyle\\!\\!\\!\\!(\ref{OP2st2}),(\ref{OP2st4}),(\ref{OP2st6})-(\ref{OP2st9}),(\ref{eq18}),(\ref{eq19}),$
(21c) $\displaystyle\\!\\!\\!\\!\alpha_{k}\geq 0,$
$\displaystyle\\!\\!\\!\\!\beta_{k}\geq 0.$

It is seen that problem (21) is a joint convex problem, and thus it can be
solved by some off-the-shelf optimization toolboxes, e.g., CVX [37]. Then, the
second subproblem of optimizing the BS transceiver $\\{\mathbf{w,z}\\}$ with
the obtained solution for device transceiver $\\{v_{k},b_{k}\\}$ from problem
(21) can be expressed as

$\displaystyle\underset{\mathbf{w,z},\bm{\chi},\rho_{k},\vartheta_{k},\alpha_{k},\beta_{k}}{\mathop{\min}}\,$
$\displaystyle\\!\\!\\!\\!\|\bm{\chi}\|_{1}$ (22) s.t.
$\displaystyle\\!\\!\\!\\!(\ref{OP2st2}),(\ref{OP2st4}),(\ref{OP2st5}),(\ref{OP2st7})-(\ref{OP2st9}),$
$\displaystyle\\!\\!\\!\\!(\ref{eq18}),(\ref{eq19}),(\ref{OP4st1}),(\ref{OP4st2}).$

It is observed that subproblem (22) is also a joint convex problem, which can
be solved by CVX directly. By iteratively solving the two subproblems, we can
obtain the sparse vector $\bm{\chi}^{*}$. Next, we will conduct feasibility
detection in the second step to find the feasible subset of devices
$\mathcal{S}$ based on the obtained sparse vector.

####  III-B2 Feasibility Detection

With the obtained sparse vector $\bm{\chi}$ from the above step, we first sort
the elements $\chi_{k},\forall k$ in an ascending order, i.e.,
${{\chi}_{\pi\left(1\right)}}\leq{{\chi}_{\pi\left(2\right)}}\leq\cdots\leq{{\chi}_{\pi\left(K\right)}}$,
where ${{\chi}_{\pi\left(i\right)}}$ represents the $i$-th smallest element in
$\\{\chi_{1},\cdots,\chi_{K}\\}$. Then, we aim to find the maximum $m\in[1,K]$
that enables all devices in the selected devices set
$\mathcal{S}^{[m]}=\\{{\pi\left(1\right)},{\pi\left(2\right)},\cdots,{\pi\left(m\right)}\\}$
to be feasible, i.e., satisfying the MSE requirements. Specifically, for a
given device set $\mathcal{S}^{[m]}$, we check the feasibility via comparing
the required MSE and the obtained MSE value based on the following problem:

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\underset{\mathbf{w},\mathbf{z},{{b}_{i}},{{v}_{i}}}{\mathop{\min}}\\!\\!\\!\\!\,\\!\\!\\!\\!$
$\displaystyle\\!\\!\\!\\!\underset{\left\|{{\mathbf{e}}_{i}}\right\|\leq{{\varepsilon}_{i}}}{\mathop{\max}}\,\\!\\!\\!\\!\sum\limits_{i\in{\mathcal{S}^{[m]}}}{{{\left|{{\mathbf{z}}^{H}}\left({{{\mathbf{\hat{h}}}}_{i}}+{{\mathbf{e}}_{i}}\right){{b}_{i}}-1\right|}^{2}}}+\sigma_{1}^{2}{{\left\|\mathbf{z}\right\|}^{2}}$
(23a) s.t.
$\displaystyle\\!\\!\\!\\!\underset{\left\|{{\mathbf{e}}_{i}}\right\|\leq{{\varepsilon}_{i}}}{\mathop{\max}}\,{{\left|{{v}_{k}}{\left({{{\mathbf{\hat{h}}}}_{k}}+{{\mathbf{e}}_{k}}\right)}^{H}\mathbf{w}-1\right|}^{2}}+\sigma_{0}^{2}{{\left|{{v}_{i}}\right|}^{2}}\leq{{\gamma}_{D,i}},$
(23d)
$\displaystyle\\!\\!\\!\\!{{\left\|\mathbf{w}\right\|}^{2}}\leq{{P}_{\max}},$
$\displaystyle\\!\\!\\!\\!{{b}_{i}}\leq\sqrt{{{P}_{i}}},\forall
i\in{\mathcal{S}^{[m]}}.$

Since the structure of nonconvex problem (23) is similar to problem (15),
i.e., nonconvexity due to coupled variables and channel uncertainty, we just
give the transformed convex subproblems directly. Specifically, the first
subproblem of optimizing the device transceiver $\\{v_{i},b_{i}\\}$ with the
fixed BS transceiver $\\{\mathbf{w,z}\\}$ is given by

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\underset{v_{i},b_{i},\rho_{i},\vartheta_{i},\alpha_{i},\beta_{i}}{\mathop{\min}}\\!\\!\\!\\!\\!\\!\\!\\!\,\\!\\!\\!\\!$
$\displaystyle\\!\\!\\!\\!\sum\limits_{i\in{{S}^{[m]}}}{{{\rho}_{i}}}+\sigma_{1}^{2}{{\left\|\mathbf{z}\right\|}^{2}},$
(24a) s.t.
$\displaystyle\\!\\!\\!\\!(\ref{OP2st7}),(\ref{OP2st8}),(\ref{OP4st1}),(\ref{OP4st2}),(\ref{OP6st3}),$
(24d)
$\displaystyle\\!\\!\\!\\!\left[\begin{matrix}{{\rho}_{i}}-{{\alpha}_{i}}&b_{i}^{H}\mathbf{\hat{h}}_{i}^{H}\mathbf{z}-1&\mathbf{0}\\\
{{b}_{i}}{{\mathbf{z}}^{H}}{{{\mathbf{\hat{h}}}}_{i}}-1&1&{{\varepsilon}_{i}}{{b}_{i}}{{\mathbf{z}}^{H}}\\\
\mathbf{0}&{{\varepsilon}_{i}}b_{i}^{H}\mathbf{z}&{{\alpha}_{i}}{{\mathbf{I}}_{N}}\\\
\end{matrix}\right]\succeq\mathbf{0},$
$\displaystyle\\!\\!\\!\\!\left[\begin{matrix}{{\vartheta}_{i}}-{{\beta}_{i}}\\!\\!&\\!\\!{{v}_{i}}\mathbf{\hat{h}}_{i}^{H}\mathbf{w}-1\\!\\!&\\!\\!\mathbf{0}\\\
{{\mathbf{w}}^{H}}{{{\mathbf{\hat{h}}}}_{i}}v_{i}^{H}-1&1&\varepsilon_{i}\mathbf{w}{{v}_{i}}\\\
\mathbf{0}&{{\varepsilon}_{i}}v_{i}^{H}{{\mathbf{w}}^{H}}&{{\beta}_{i}}\mathbf{I}_{N}\\\
\end{matrix}\right]\succeq\mathbf{0},$
$\displaystyle\\!\\!\\!\\!\sum\limits_{i\in{{S}^{[m]}}}{{{\vartheta}_{i}}}+\sigma_{0}^{2}{{\left|{{v}_{i}}\right|}^{2}}\leq{{\gamma}_{D,i}}.$

Then, the second subproblem of optimizing the BS transceiver
$\\{\mathbf{w,z}\\}$ with the obtained device transceiver $\\{v_{i},b_{i}\\}$
from (24) can be expressed as

$\displaystyle\\!\\!\underset{\mathbf{w,z},\rho_{i},\vartheta_{i},\alpha_{i},\beta_{i}}{\mathop{\min}}\\!\\!\\!\\!\,$
$\displaystyle\\!\\!\\!\\!\sum\limits_{i\in{{S}^{[k]}}}{{{\rho}_{i}}}+\sigma_{1}^{2}{{\left\|\mathbf{z}\right\|}^{2}},$
(25) s.t.
$\displaystyle\\!\\!\\!\\!(\ref{OP2st7}),(\ref{OP2st8}),(\ref{OP4st1}),(\ref{OP4st2}),(\ref{OP6st2}),(\ref{OP7st1})-(\ref{OP7st3}).$

By alternatively solving these two subproblems, we can obtain a sub-optimal
solution of problem (23). If the obtained objective value is less than or
equal to the required MSE $\gamma_{B}$ at the BS, then the set
${\mathcal{S}^{[m]}}$ can be chosen as a feasible set and corresponding
aggregation error and broadcast error can be computed by designed
transceivers. Otherwise, reset the selected devices set by letting $m=m-1$. In
summary, a robust design of transmission scheme for FL in edge-intelligent
networks can be described as Algorithm 2.

Algorithm 2 : Robust design of transmission scheme for FL in edge-intelligent
networks.

Input:
$N,K,\sigma_{0}^{2},\sigma_{1}^{2},P_{\max}$,$\gamma,P_{k},\varepsilon_{k},\delta_{k}$
Output: $\mathcal{S}$, $\text{MSE}_{\text{BS}}$,
$\text{MSE}_{i}^{\text{Device}}$

1: Initialize $\mathbf{z}^{[0]},\mathbf{w}^{[0]}$, convergence accuracy
$\nu_{1}$ and iteration index $t=1$;

2: repeat

3: obtain $\\{v_{k}^{[t]},b^{[t]}_{k}\\}$ by solving problem (21) with fixed
$\\{\mathbf{w}^{[t-1]},\mathbf{z}^{[t-1]}\\}$;

4: obtain $\\{\mathbf{w}^{[t]},\mathbf{z}^{[t]},\bm{\chi}^{[t]}\\}$ by solving
problem (22) with fixed $\\{v_{k}^{[t]},b^{[t]}_{k}\\}$;

5: Compute $\triangle_{1}=|\|\bm{\chi}\|_{1}^{[t]}-\|\bm{\chi}\|_{1}^{[t-1]}|$

6: $t=t+1$;

7: until convergence: $\triangle_{1}<\nu_{1}$

8: obtain $\bm{\chi}^{*}=\bm{\chi}^{[t]}$, and sort the elements by an
ascending order, i.e.,
${{\chi}_{\pi\left(1\right)}}\leq{{\chi}_{\pi\left(2\right)}}\leq\cdots\leq{{\chi}_{\pi\left(K\right)}}$;

9: Initialize the maximum number of selected devices $m=K$, convergence
accuracy $\nu_{2}$;

10: while $m\geq 0$ do

11: Set the selected devices set
$\mathcal{S}^{[m]}=\\{{\pi\left(1\right)},{\pi\left(2\right)},\cdots,{\pi\left(m\right)}\\}$;

12: repeat

13: Initialize $\mathbf{z}^{[0]},\mathbf{w}^{[0]}$, iteration index $t=1$

14: Obtain $\\{v_{k}^{[t]},b^{[t]}_{k}\\}$ by solving problem (24) with fixed
$\\{\mathbf{w}^{[t-1]},\mathbf{z}^{[t-1]}\\}$;

15: Obtain $\\{\mathbf{w}^{[t]},\mathbf{z}^{[t]}\\}$ by solving problem (25)
with fixed $\\{v_{k}^{[t]},b^{[t]}_{k}\\}$;

16: Compute
$\triangle_{2}=|\text{MSE}_{\text{BS}}^{[t]}-\text{MSE}_{\text{BS}}^{[t-1]}|$

17: $t=t+1$;

18: until convergence: $\triangle_{2}<\nu_{2}$

19: if $\text{MSE}_{\text{BS}}^{[t]}\leq\gamma$ then

20:
$\mathbf{z}^{*}=\mathbf{z}^{[t]},\mathbf{w}^{*}=\mathbf{w}^{[t]},v_{i}^{*}=v_{i}^{[t]},b_{i}^{*}=b_{i}^{[t]},\forall
i\in\mathcal{S}^{[m]}$

21: break;

22: end if

23: $m=m-1$;

24: end while

25: Obtain $\mathcal{S}^{[m]}$, and compute $\text{MSE}_{\text{BS}}$ and
$\text{MSE}_{i}^{\text{Device}}$ according to the
$\mathbf{z}^{*},\mathbf{w}^{*},v_{i}^{*},b_{i}^{*},\forall
i\in\mathcal{S}^{[m]}$ .

_Optimality Analysis:_ It is observed that Algorithm 2 is divided into two
main stages, one for sparse inducing (from step 1 to step 8) and another for
feasibility detection (from step 9 to step 25). To overcome the non-convexity,
we adopt well-known $\ell_{1}$-relaxation to approximate $\ell_{0}$-norm at
the first stage and utilize the AO method to decouple the sub-problems in the
overall process. As a result, the obtained solution might be not optimal. But
the approximations will not shrink the feasible region too much over the
original problem and the AO method will approach a local optimal point in the
iterations.

_Convergence Analysis:_ According to [35] and [38], the convergence of the AO
algorithm is guaranteed when the solution of each subproblem in the iterations
is its global optimum. As for the sparsity inducing problem (14), we define
its objective function at the $t$-iteration as
$F_{1}(v_{k}^{[t]},b_{k}^{[t]},\mathbf{x}^{[t]},\mathbf{w}^{[t]},\mathbf{z}^{[t]})$.
In the step 3 of Algorithm 2, since the transceivers at the devices can be
optimally obtained for a given transceiver at the BS by solving the convex
subproblem (21), we have

$F_{1}(v_{k}^{[t]},b_{k}^{[t]},\mathbf{x}^{[t]},\mathbf{w}^{[t]},\mathbf{z}^{[t]})\geq
F_{1}(v_{k}^{[t+1]},b_{k}^{[t+1]},\mathbf{x}^{[t]},\mathbf{w}^{[t]},\mathbf{z}^{[t]}).$
(26)

Then, in step 4 of Algorithm 2, the transceiver at the BS and the priority of
being selected for devices can be optimally obtained for given transceivers at
the devices by solving the convex subproblem (22), we have

$\displaystyle
F_{1}(v_{k}^{[t+1]},b_{k}^{[t+1]},\mathbf{x}^{[t]},\mathbf{w}^{[t]},\mathbf{z}^{[t]})\geq$
$\displaystyle
F_{1}(v_{k}^{[t+1]},b_{k}^{[t+1]},\mathbf{x}^{[t+1]},\mathbf{w}^{[t+1]},\mathbf{z}^{[t+1]})$
(27)

Based on (26) and (III-B2), we can obtain

$\displaystyle
F_{1}(v_{k}^{[t]},b_{k}^{[t]},\mathbf{x}^{[t]},\mathbf{w}^{[t]},\mathbf{z}^{[t]})\geq$
$\displaystyle
F_{1}(v_{k}^{[t+1]},b_{k}^{[t+1]},\mathbf{x}^{[t+1]},\mathbf{w}^{[t+1]},\mathbf{z}^{[t+1]}).$
(28)

It is shown that the value of the objective function $F_{1}$ after each
iteration of Algorithm 2 (step 1-8) is non-increasing. At the same time, the
objective function value of problem (15) has a lower bound, so the convergence
of Algorithm 2 is guaranteed. As for the feasibility detection problem (23),
we define its objective function at the $t$-iteration as
$F_{2}(v_{i}^{[t]},b_{i}^{[t]},\mathbf{w}^{[t]},\mathbf{z}^{[t]})$ for a given
device set. Similarly, since the subproblems (24) and (25) are both convex, we
can obtain
$F_{2}(v_{k}^{[t]},b_{k}^{[t]},\mathbf{w}^{[t]},\mathbf{z}^{[t]})\geq
F_{2}(v_{k}^{[t+1]},b_{k}^{[t+1]},\mathbf{w}^{[t+1]},\mathbf{z}^{[t+1]})$.
Thus, the proposed AO algorithm for solving the feasibility detection problem
is also convergent. Moreover, based on the convergence rate analysis of AO
algorithm in [35] and [39], it is known that the convergence rates of the
proposed algorithms both show a two-stage behavior. Specifically, at first,
the error decreases q-linearly until sufficiently small. After that, the sub-
linear convergence is initiated. Besides, we show the required number of
iterations under various MSE requirements by simulations in Fig. 4. It is seen
that Algorithm 2 has a fast convergence speed under different conditions,
which also verifies the convergence property of Algorithm 2.

_Complexity Analysis:_ As mentioned above, the proposed robust algorithm is
split into two main stages, which have the similar structure in an iterative
manner. Thus, we only discuss the per-iteration complexity in detail. It is
seen that the main computational complexity of sparse inducing comes from the
step 4, i.e., obtaining ${\\{\mathbf{w,z},\bm{\chi}\\}}$ by optimizing problem
(22) through a standard interior-point method (IPM) [40]. Specifically, it has
$2K$ linear matrix inequality (LMI) constraints of size $N+2$, $6K$ LMI
constraints of size 1, and $2$ second-order cone (SOC) constraints of size
$N$. Thus, for a given precision $\Theta>0$ of solution, the per-iteration
complexities of solving problem (22) by IPM is
$\ln\frac{1}{\Theta}\sqrt{10K+2KN+4}\cdot
n\cdot\left[6K+2K{{\left(N+2\right)}^{3}}+2{{N}^{2}}+n\left(n+6K+2K{{(N+2)}^{2}}\right)\right]$.
Similarly, the main computational complexity of solving the feasibility
detection problem comes from the step 9, which has $2K$ LMI constraints of
size $N+2$, $5K$ LMI constraints of size 1, and $1$ SOC constraints of size
$N$. Thus, the per-iteration complexities of solving problem (24) by IPM is
$\ln\frac{1}{\Theta}\sqrt{9K+2KN+2}\cdot
n\cdot\left[5K+2K{{\left(N+2\right)}^{3}}+{{N}^{2}}+n\left(n+5K+2K{{(N+2)}^{2}}\right)\right]$,
where the decision variable $n$ is on the order of $\mathcal{O}(KN^{2})$.

##  IV Simulation Results

In this section, we provide extensive simulation results to validate the
effectiveness and robustness of the proposed algorithm for FL in edge-
intelligent networks.

###  IV-A Performance on Parameter Transmission

TABLE II: Simulation Parameters  Parameters | Values
---|---
Number of BS antennas |  $N=48$ [41]
Number of devices | $K=20$
CSI uncertainty |  $\varepsilon_{k}=\varepsilon=0.1$ [32]
Maximum transmit SNR at the BS |  $\text{SNR}_{B}=10$ dB
Maximum transmit SNR at the devices |  $\text{SNR}_{D,k}=\text{SNR}_{D}=10$ dB
MSE requirement at the BS |  $\gamma_{B}=5$ dB
MSE requirements at the devices |  $\gamma_{D,k}=\gamma_{D}=5$ dB

Without loss of generality, it is assumed that all devices are randomly
distributed within a range of $100$ m from the BS. To be close to the reality,
the pass loss is modeled as $\mathrm{PL}_{\mathrm{dB}}=128.1+37.6\log_{10}(l)$
[42], where $l$ (km) is the distance between the BS and the device. For ease
of analysis, we assume all devices have the same transmit power budget
$P_{k}=P_{0}$ and the same MSE requirement $\gamma_{D,k}=\gamma_{D}$.
Moreover, we use $\text{SNR}_{B}=10\log_{10}(P_{\max}/\sigma_{0}^{2})$ to
denote the transmit signal-to-noise ratio (SNR) (in dB) at the BS,
$\text{SNR}_{D}=10\log_{10}(P_{0}/\sigma_{1}^{2})$ to denote the transmit SNR
(in dB) at the device,
$\gamma_{B}=10\log_{10}[\text{MSE}_{BS}/(\sigma_{1}^{2}/{P_{0}})]$ to denote
the MSE requirement (in dB) at the BS, and
$\gamma_{D,k}=10\log_{10}[\text{MSE}_{k}^{Device}/(\sigma_{0}^{2}/{P_{\max}})]$
to denote the MSE requirement (in dB) at the $k$-th device. The results
averaged over 50 channel realizations. Unless specified, the simulation
parameters are set as in Table II following relevant standards [32], [41]. It
is worth pointing out that the proposed algorithm is applicable to various
practical edge-intelligent networks by setting proper system parameters.

Figure 4: Convergence behavior for sparse inducing of the proposed robust
algorithm.

First, we present the convergence behavior of the proposed robust algorithm
for solving sparse inducing problem using the AO method. As seen in Fig. 4,
the objective value $\|\bm{\chi}\|_{1}$ decreases monotonically as expected,
and converges to a stationary value within 10 iterations on average under
different MSE requirements $\gamma_{B}$ at the BS, which verifies the proposed
robust algorithm has a quick convergence speed. Moreover, it is seen that the
smaller the value of $\gamma_{B}$, the faster the convergence, and the bigger
the objective value. This is because that a small $\gamma_{B}$ represents a
strict MSE requirement, leading to less sparsity and easy to find a minimum
objective value.

Figure 5: Average number of selected devices versus the required MSE
$\gamma_{B}$ at the BS for different MSE requirements $\gamma_{D}$ at the
devices.

Then, we show the impacts of the MSE requirements $\gamma_{B}$ for the BS and
$\gamma_{D}$ for the devices on the performance of device selection for the
proposed robust algorithm in Fig. 5. It is found that the average number of
selected devices increases with the increment of the MSE requirements
$\gamma_{B}$ for the BS. This is because that relaxing the condition of
aggregation error at the BS can make more devices to be selected to
participate in FL. Moreover, it is also found that the average number of
selected devices can be increased by relaxing the MSE requirements at the
devices. However, as mentioned above, the loose restrictions of MSE at the BS
and at the devices mean the improvement of the distortion, leading to the
performance degradation of the FL. Thus, it is desired to choose an
appropriate number of devices under the suitable MSE requirements.

Figure 6: Average number of selected devices versus the required MSE
$\gamma_{D}$ at the devices for different device selection algorithms.

Next, we compare the performance of different device selection algorithms.
Note that the difference-of-convex (DC) nonrobust algorithm is designed based
on the combination of [30] and [28]. Specifically, for a given zero-forcing
receiver $v_{i}$ at the device for downlink transmission [30] and a zero-
forcing transmitter $b_{i}$ at the device for uplink transmission [28], the
device selection and the transceiver at the BS are obtained based on the DC
approach [28]. The AO nonrobust algorithm is the same as the proposed robust
algorithm, i.e., adopting the AO method to design adaptive transceivers
according to the system requirements, except that it does not take into
account of channel uncertainty. It is seen that, for a given MSE requirement
at the BS, the average number of selected devices increases as the required
MSE at the device increases, but the improvement is finite. Moreover, for the
two nonrobust algorithms, there seems to be no regularity in their trend. This
is because they design the transceivers without considering the CSI
uncertainty, sometimes selecting a few devices or even no device to ensure the
MSE constraints. In particular, the proposed robust algorithm has the most
stable performance, while the DC nonrobust algorithm has the worst
performance. That quite confirms the effectiveness and robustness of the
proposed robust algorithm.

Figure 7: Average number of selected devices versus the bound of the channel
error $\varepsilon_{0}$ for different numbers of BS antennas.

Fig. 7 investigates the effect of channel error bound $\varepsilon_{0}$ and
the number of BS antennas $N$ on the performance of the proposed robust
algorithm. Note that $\varepsilon_{0}=0$ represents the case of perfect CSI.
It is found that the average number of selected devices decreases as the bound
of channel error increases. This is because a large channel error bound
requires more resource to combat the channel uncertainty and guarantee the MSE
in the worse case, and accordingly less resource contributes to improving the
overall performance. Moreover, it is seen that the proposed robust algorithm
with more BS antennas can select more devices to participate in FL due to more
array gains for improving the performance. Especially, in the case of the
number BS antennas $N=64$, the proposed robust algorithm selects all devices
while ensuring MSE requirements. Thus, it is able to enhance the performance
for the proposed robust algorithm by adding BS antennas.

###  IV-B Performance on FL

Figure 8: Architecture of 6-layer CNN for training model used in experiments.
Figure 9: FL Performance comparisons of different algorithms for parameter
transmission with IID MNIST dataset. Figure 10: FL Performance comparisons of
different algorithms for parameter transmission with Non-IID MNIST dataset.

In order to testify the performance of the proposed algorithm in practical FL
applications, we consider a commonly used FL task of handwritten-digit
recognition using the well-known MNIST dataset that consists of 10 categories
ranging from digit “0” to “9” and a total of 70,000 labeled training data
samples (60,000 for training and 10,000 for testing). To simulate the
distributed mobile data, we consider two types of data partitions, i.e., the
independent andidentically distributed (IID) setting and non-IID one. For the
former setting, we randomly partition the training samples into 20 equal
shards, each of which is assigned to one particular device. While for the
latter setting, we first sort the data by digit label, divide it into 40
shards of 1,500 images, and randomly assign 2 shards to each device. As
illustrated in Fig. 8, the training model is implemented using a 6-layer CNN
that consists of two 5$\times$5 convolution layers with ReLu activation (the
first with 32 channels, the second with 64 channels), each followed with
2$\times$2 max pooling layer, a fully connected layer with 512 units and ReLu
activation, and a fully connected layer with Softmax classifier as the output
layer (1,663,370 total parameters) [11]. Each device updates its local model
using the SGD algorithm with a learning rate being 0.01. The cross-entropy is
used as the loss function, batchsize is 64, and epoch is 1. Note that
different learning tasks, datasets, and training methods will have different
prediction results. In particular, our adopted benchmark FL algorithm trained
by such a 6-layer CNN on MNIST dataset for image classification presents over
95% test accuracy in the ideal situation without aggregation error and
broadcast error, cf. Fig. 2. Thus, it is fair and illustrates the performance
of our proposed algorithm.

TABLE III: Some examples of handwritten-digit identification on IID MNIST dataset Data image |  |  |  |  |  |  |
---|---|---|---|---|---|---|---
Proposed Algorithm | 0 | 5 | 9 | 0 | 2 | 1 | 7
AO Algorithm | 0 | 6($\times$) | 9 | 0 | 2 | 1 | 7
DC Algorithm | 0 | 4($\times$) | 4($\times$) | 0 | 4($\times$) | 4($\times$) | 4($\times$)
Data image |  |  |  |  |  |  |
Proposed Algorithm | 3 | 6 | 2 | 8 | 4 | 3 | 1
AO Algorithm | 3 | 6 | 2 | 8 | 4 | 3 | 7($\times$)
DC Algorithm | 4($\times$) | 5($\times$) | 4($\times$) | 4($\times$) | 4 | 4($\times$) | 4($\times$)

As shown in Fig. 9 and 10, given $\text{SNR}_{B}=\text{SNR}_{D}=10$ dB and
$\gamma_{D}=\gamma_{B}=5$ dB, we compare the performance on the training loss
and the test accuracy for the above three algorithms with the IID MNIST
dataset and the Non-IID MNIST dataset, respectively. For the IID setting, it
is seen that the proposed robust algorithm and the AO nonrobust algorithm both
perform better than the DC nonrobust algorithm, and the proposed robust
algorithm has a most stable and best performance on the training loss
decreasing and the test accuracy increasing. For the Non-IID setting, it is
found that the three algorithms all have the oscillatory waves on the
performance. This is because some devices have not been selected to
participate in FL due to the MSE constraints, resulting in some data samples
not being trained. For example, the $k$-th device is assigned two shards “0”
and “9”. If the $k$-th device is rarely selected in multiple communication
rounds, then digit sample “0” and “9” are seldom trained, leading to a low
prediction accuracy for digit sample ”0” and ”9”. Even so, the proposed robust
algorithm performs best and achieves a high test accuracy. For vivid
illustration, we present some examples of handwritten-digit identification in
Table III. These phenomenons confirm the effectiveness and robustness of the
proposed robust algorithm for enhancing the performance of FL in edge-
intelligent networks.

##  V Conclusion

In this paper, we have investigated the factors affecting the accuracy of FL
in edge-intelligent networks. For enhancing the performance of FL, we have
proposed a robust parameter transmission scheme for both model broadcast and
model aggregation, which has been formulated as an optimization problem by
maximizing the number of selected devices participating in FL while ensuring
the required MSE constraints on model broadcast and aggregation. To solve this
problem, we have resorts to some approximation methods on convex
transformation and proposed an AO-based robust algorithm including sparse
inducing and feasibility detection. Numerical results have verified the
effectiveness of the proposed algorithm for edge-intelligent networks.
Moreover, it is found that whether or not the dataset is iid, the proposed
robust algorithm can achieve a lower training loss and higher test accuracy
compared with the nonrobust baselines.

##  Appendix A The Proof of Lemma 2

Prior to the proof, we provide a useful lemma in the following.

_Lemma 3:_ (S-procedure, [36]) Let us consider a function
${{\mathbf{f}}_{m}}\left(\mathbf{x}\right)$ as

${{\mathbf{f}}_{m}}\left(\mathbf{x}\right)={{\mathbf{x}}^{H}}{{\mathbf{A}}_{m}}\mathbf{x}+2\operatorname{Re}\left\\{\mathbf{b}_{m}^{H}\mathbf{x}\right\\}+{{\mathbf{c}}_{m}},m\in\left\\{1,2\right\\},\mathbf{x}\in{{\mathbb{C}}^{N\times
1}},$ (29)

where ${{\mathbf{A}}_{m}}\in{{\mathbb{C}}^{N\times
N}},{{\mathbf{b}}_{m}}\in{{\mathbb{C}}^{N\times 1}}$ and
${{\mathbf{c}}_{m}}\in{{\mathbb{C}}^{N\times 1}}$. The derivation
${{\mathbf{f}}_{1}}\left(\mathbf{x}\right)\leq
0\Rightarrow{{\mathbf{f}}_{2}}\left(\mathbf{x}\right)\leq 0$ holds true if and
only if there exists $\tau\geq 0$, such that

$\displaystyle\tau\left[\begin{matrix}{{\mathbf{A}}_{1}}&{{\mathbf{b}}_{1}}\\\
\mathbf{b}_{1}^{H}&{{\mathbf{c}}_{1}}\\\
\end{matrix}\right]-\left[\begin{matrix}{{\mathbf{A}}_{2}}&{{\mathbf{b}}_{2}}\\\
\mathbf{b}_{2}^{H}&{{\mathbf{c}}_{2}}\\\
\end{matrix}\right]\succeq\mathbf{0}.$ (30)

_Proof:_ According to the definition of semi-positive matrix, if for
$\forall\mathbf{d}\neq\mathbf{0}$, we have

${{\mathbf{d}}^{H}}\mathbf{Ad}-{{\mathbf{d}}^{H}}\left({{\mathbf{B}}^{H}}\mathbf{x}\mathbf{c}^{H}+{{\mathbf{c}}}{{\mathbf{x}}^{H}}\mathbf{B}\right)\mathbf{d}\geq
0.$ (31)

That confirms that $\mathbf{F}\left(\mathbf{x}\right)\succeq\mathbf{0},\text{
}\forall\mathbf{x}:\left\|\mathbf{x}\right\|\leq\varpi$ holds true. Based on
Lemma 1, (31) is equivalent to

$\displaystyle{{\mathbf{d}}^{H}}\mathbf{Ad}$ $\displaystyle\geq$
$\displaystyle\underset{{{\left\|\mathbf{x}\right\|}}\leq\varpi}{\mathop{\max}}\,{{\mathbf{d}}^{H}}\left({{\mathbf{B}}^{H}}\mathbf{xc}^{H}+{{\mathbf{c}}}{{\mathbf{x}}^{H}}\mathbf{B}\right)\mathbf{d}$
(32) $\displaystyle=$ $\displaystyle
2\varpi|\mathbf{c}^{H}\mathbf{d}|\left\|\mathbf{Bd}\right\|.$

By utilizing the _Cauchy-Schwarz inequality_ [43], (32) can be further
transformed as

${{\mathbf{d}}^{H}}\mathbf{Ad}-2\varpi\xi\mathbf{c}^{H}\mathbf{d}\geq
0,\forall\xi:|\xi|\leq\left\|\mathbf{Bd}\right\|.$ (33)

Then, by exploiting Lemma 3 with
$\varpi^{2}-{{\mathbf{d}}^{H}}{{\mathbf{B}}^{H}}\mathbf{Bd}\leq 0$, (33) is
satisfied if and only if there exists a $\lambda\geq 0$ such that

$\left[\begin{matrix}\mathbf{A}-\lambda{{\mathbf{c}}}\mathbf{c}^{H}&-\varpi{{\mathbf{B}}^{H}}\\\
-\varpi\mathbf{B}&\lambda{{\mathbf{I}_{n}}}\\\
\end{matrix}\right]\succeq\mathbf{0}.$

The proof is completed.

## References

  * [1] P. Yang, Y. Xiao, M. Xiao, and S. Li, “6G wireless communications: Vision and potential techniques,” _IEEE Netw._ , vol. 33, no. 4, pp. 70-75, Jul. 2019.
  * [2] W. Saad, M. Bennis, and M. Chen, “A vision of 6G wireless systems: Applications, trends, technologies, and open research problems,” _IEEE Netw._ , vol. 34, no. 3, pp. 134-142, May 2020.
  * [3] Y. Chen, P. Zhu, G. He, X. Yan, H. Baligh, and J. Wu, “From connected people, connected things, to connected intelligence,” in _Proc. 2020 6G SUMMIT_ , Levi, Finland, 2020, pp. 1-7.
  * [4] H. Yang, A. Alphones, Z. Xiong, D. Niyato, J. Zhao, and K. Wu, “Artificial-intelligence-enabled intelligent 6G networks,” _IEEE Netw._ , vol. 34, no. 6, pp. 272-280, Nov. 2020.
  * [5] S. Deng, H. Zhao, W. Fang, J. Yin, S. Dustdar, and A. Y. Zomaya, “Edge intelligence: The confluence of edge computing and artificial intelligence,” _IEEE Internet of Things J._ , vol. 7, no. 8, pp. 7457-7469, Aug. 2020.
  * [6] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: Vision and challenges,” _IEEE Internet Things J._ , vol. 3, no. 5, pp. 637-646, Oct. 2016.
  * [7] H. Lee, S. H. Lee, T. Q. S. Quek, and I. Lee, “Deep learning framework for wireless systems: Applications to optical wireless communications,” _IEEE Commun. Mag._ , vol. 57, no. 3, pp. 35-41, Mar. 2019.
  * [8] G. Zhu, D. Liu, Y. Du, C. You, J. Zhang, and K. Huang, “Towards an intelligent edge: Wireless communication meets machine learning,” _IEEE Commun. Mag._ , vol. 58, no. 1, pp. 19-25, Jan. 2020.
  * [9] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Y. Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Proc. Artif. Intell. Statist._ , 2017, pp. 1273-1282.
  * [10] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” _IEEE Signal Process. Mag._ , vol. 37, no. 3, pp. 50-60, May 2020.
  * [11] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Y. Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Proc. Int. Conf. Artif. Intell. Stat. (AISTATS)_ , 2017, pp. 1273-1282.
  * [12] A. Hard, K. Rao, R. Mathews, S. Ramaswamy et al, “Federated Learning for Mobile Keyboard Prediction,” [Online]. Available: https://arxiv.org/abs/1811.03604, 2018.
  * [13] S.Ramaswamy, R. Mathews, K. Rao, and F. Beaufays, “Federated learning for emoji prediction in a mobile keyboard,” [Online]. Available: https://arxiv.org/abs/1906.04329, 2019.
  * [14] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” in _Proc. Machine Learning and Systems_ , 2020, pp. 429-450.
  * [15] D. A. E. Acar, Y. Zhao, Navarro, R. M. Mattina, P. N. Whatmough, and V. Saligrama,“Federated learning based on dynamic regularization,” [Online]. Available: https://arxiv.org/abs/2111.04263, 2021.
  * [16] F. Sattler, S. Wiedemann, K.-R. Müler, and W. Samek, “Sparse binary compression: Towards distributed deep learning with minimal communication,” in _Proc. IEEE Int. Joint Conf. Neural Netw. (IJCNN)_ , 2019, pp. 1-8.
  * [17] 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, Jan. 2021.
  * [18] N. Shlezinger, M. Chen, Y. C. Eldar, H. V. Poor, and S. Cui, “UVeQFed: Universal vector quantization for federated learning,” _IEEE Trans. Signal Process._ , vol. 69, pp. 500-514, 2021.
  * [19] 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.
  * [20] Q. Zeng, Y. Du, K. Huang, and K. K. Leung, “Energy-efficient radio resource allocation for federated edge learning,” in _Proc. 2020 ICC Workshops_ , Dublin, Ireland, 2020, pp. 1-6.
  * [21] 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, Mar. 2021.
  * [22] O. Abari, H. Rahul, and D. Katabi, “Over-the-air function computation in sensor networks,” [Online]. Available: http://arxiv.org/abs/1612.02307, 2016.
  * [23] X. Chen and Q. Qi, _Convergence of Energy, Computation and Communication in B5G Cellular Internet of Things_ , Germany: Springer, 2020.
  * [24] M. Goldenbaum, H. Boche, and S. Staczak, “Nomographic functions: Efficient computation in clustered gaussian sensor networks,” _IEEE Trans. Wireless Commun._ , vol. 14, no. 4, pp. 2093-2105, Apr. 2015.
  * [25] T. Sery, N. Shlezinger, K. Cohen, and Y. C. Eldar, “Over-the-air federated learning from heterogeneous data,” _IEEE Trans. Signal Process._ , vol. 69, pp. 3796-3811, Jun. 2021.
  * [26] G. Zhu, Y. Du, D. Gunduz, and K. Huang, “One-bit over-the-air aggregation for communication-efficient federated edge learning: Design and convergence analysis,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 3, pp. 2120-2135, Mar. 2021.
  * [27] G. Zhu, Y. Wang, and K. Huang, “Broadband analog aggregation for low-latency federated edge learning,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 1, pp. 491-506, Jan. 2020.
  * [28] K. Yang, T. Jiang, Y. Shi, and Z. Ding, “Federated learning via over-the-air computation,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 3, pp. 2022-2035, Mar. 2020.
  * [29] 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, no. 2, pp. 808-822, Feb. 2022.
  * [30] M. M. Amiri, D. Guduz, S. R. Kulkarni, and H. Vincent Poor, “Convergence of federated learning over a noisy downlink,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 3, pp. 1422-1437, Mar. 2022.
  * [31] X. Cao, G. Zhu, J. Xu, and K. Huang, “Optimized power control for over-the-air computation in fading channels,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 11, pp. 7498-7513, Nov. 2020.
  * [32] H. Sun, F. Zhou, R. Q. Hu, and L. Hanzo, “Robust beamforming design in a NOMA cognitive radio network relying on SWIPT,” _IEEE J. Sel. Areas Commun._ , vol. 37, no. 1, pp. 142-155, Jan. 2019.
  * [33] Q. Qi, X. Chen, and D. W. K. Ng, “Robust beamforming for NOMA-based cellular massive IoT with SWIPT,” _IEEE Trans. Signal Process._ , vol. 68, pp. 211-224, Dec. 2020.
  * [34] M. M. Amiri and D. Gunduz, “Federated learning over wireless fading channels,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 5, pp. 3546-3557, May 2020.
  * [35] J. C. Bezdek and R. J. Hathaway, “Convergence of alternating optimization,” _Neural, Parallel & Scientific Computations_, vol. 11, no. 4, pp. 351-368, Dec. 2003.
  * [36] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge, U.K.: Cambridge Univ. Press, 2004.
  * [37] M. Grant and S. Boyd, _CVX: Matlab Software for Disciplined Convex Programming._ [Online]. Available: http://cvxr.com/cvx.
  * [38] M. Razaviyayn, M. Hong, and Z. Q. Luo, “A unified convergence analysis of block successive minimization methods for nonsmooth optimization,” _SIAM J. Optim._ , vol. 23, no. 2, pp. 1126-1153, Jun. 2013.
  * [39] J. W. Both, “On the rate of convergence of alternating minimization for non-smooth non-strongly convex optimization in Banach spaces,” [Online]. Available: https://arxiv.org/abs/1911.00404, Nov. 2019.
  * [40] A. Ben-Tal and A. Nemirovski, “Lectures on modern convex optimization: Analysis, algorithms, and engineering applications,” _MPS-SIAMSeries on Optimization_. Philadelphia, PA, USA: SIAM, 2001.
  * [41] X. Chen, _Massive Access for Cellular Internet of Things: Theory and Technique_ , Germany: Springer Press, 2019.
  * [42] _Coordinated Multi-Point Operation for LTE Physical Layer Aspects (Rel. 11)_ , document TR 36.819, 3GPP, Feb. 2011.
  * [43] G. H. Hardy, J. E. Littlewood, and G. Polya, _Inequalities_. Cambridge, U.K.: Cambridge Univ. Press, 1952.


# Rigid Real Closed Fields

David Marker
University of Illinois Chicago  Charles Steinhorn
Vassar College Partially supported by Simons Foundation Mathematics and
Physical Sciences Collaboration Grant for Mathematicians 524012.

###### Abstract

We construct a non-Archimedean real closed field of transcendence degree two
with no nontrivial automorphisms. This is the first construction of a
countable rigid non-Archimedean real closed field,

We say that a structure is rigid if its automorphism group is trivial. In real
closed fields, the positive elements are the nonzero squares. Thus every
automorphism of a real closed field preserves the ordering as well as the
field structure. If $K$ is an Archimedean real closed field, the field of
rational numbers is dense in $K$ and fixed pointwise by all automorphisms;
hence $K$ is rigid.

Are there non-Archimedean rigid real closed fields? In [5], Shelah proved that
it is consistent with ZFC that there are. More specifically, he showed,
assuming Jensen’s combinatorial principle $\diamondsuit_{\kappa^{+}}$, that
there are rigid non-Archimedean real closed fields of cardinality
$\kappa^{+}$. In later work, Mekler and Shelah [3] revisited Shelah’s results
and showed that the existence of arbitrarily large rigid non-Archimedean real
closed fields could be proved in ZFC without extra set-theoretic assumptions.
We are grateful to Biran Falk Dotan for calling our attention to the
Mekler–Shelah paper.

In 2018 Ali Enayat asked on MathOverflow if there are countable rigid non-
Archimedean real closed fields. Our main result, Theorem 2.2, is that there
are rigid non-Archimedean real closed fields of transcendence degree two. This
gives the first positive answer to Enayat’s question.

##  1 Preliminaries

Let $k$ be the field of real algebraic numbers. We work in a sufficiently
saturated real closed field ${\cal R}\supset{\mathbb{R}}$. All the fields we
construct are subfields of $\cal R$. For a real closed field $K$, let
$K\langle a_{1},\dots a_{n}\rangle$ denote the real closure of the ordered
field $K(a_{1},\dots,a_{n})$. The rigid field we construct in Theorem 2.2 has
the form $k\langle a,b\rangle$, where $a$ is an infinite element and $b$ is
transcendental over $k\langle a\rangle$.

If $K\subset{\cal R}$ is real closed and $a_{1},\dots,a_{n}\in{\cal R}$, we
let ${\rm tp}(a_{1},\dots,a_{n}/K)$, the type of $a_{1},\dots,a_{n}$ over $K$,
be the set of all first order formulas $\phi(v_{1},\dots,v_{n})$ in the
language of ordered rings with free variable from $v_{1},\dots,v_{n}$ and
parameters from $K$ such that ${{\cal R}}\models\phi(a_{1},\dots,a_{n})$. By
Tarski’s quantifier elimination, ${\rm tp}(a_{1},\dots,a_{n}/K)$ is completely
determined by knowing

$\\{p\in K[X_{1},\dots,X_{n}]:p(a_{1},\dots,a_{n})\geq 0\\}.$

When $n=1$ this simplifies further, and ${\rm tp}(a/K)$ is completely
determined by

$\\{v\leq m:m\in K,a\leq m\\}\cup\\{v\geq m:m\in K,a\geq m\\},$

i.e., the position of $a$ with respect to the ordering of $K$.

We use several basic facts about definable sets and functions in real closed
fields that hold in every o-minimal expansion of a real closed field (see [4]
and [1] for details):

  * •

(o-minimality) If $K\subset{\cal R}$ is a real closed, every $K$-definable
subset of ${\cal R}$ is a finite union of points and intervals with endpoints
in $K\cup\\{\pm\infty\\}$.

  * •

(monotonicity) If $I\subset{\cal R}$ is an interval, and $f:I\rightarrow{\cal
R}$ is definable in ${\cal R}$, we can partition $I=J_{1}\cup\dots\cup
J_{m}\cup X$, such that $X$ is finite and each $J_{i}$, for $i\leq m$, is an
(open) interval with endpoints in ${\cal R}\cup\\{\pm\infty\\}$ on which
$f\restriction J_{i}$ is continuous and strictly monotonic.

  * •

(exchange) If $K\subset{\cal R}$ is real closed, $a,b\in\cal R$ and $b\in
K\langle a\rangle$, then $b\in K$ or $a\in K\langle b\rangle$.

  * •

(algebraic closure = definable closure) If $K\subset{\cal R}$ is real closed,
$A\subset{\cal R}$, and $b\in K\langle A\rangle$, then there is a
$K$-definable function $F:{\cal R}^{n}\rightarrow{\cal R}$ and
$a_{1},\dots,a_{n}\in A$ such that $b=F(a_{1},\dots,a_{n})$.

  * •

(cell decomposition) For $K\subset{\cal R}$ real closed, we say that
$C\subseteq{\cal R}^{2}$ is a cell defined over $K$ if either:

    * –

$C$ is a point in $K^{2}$;

    * –

$C=\\{a\\}\times I$ where $a\in K$ and $I$ is a $K$-definable interval;

    * –

there is an interval $I$ and a $K$-definable continuous $f:I\rightarrow{\cal
R}$ such that $C$ is the graph of $f$;

    * –

there is an interval $I$ and $K$-definable functions
$g_{0},g_{1}:I\rightarrow{\cal R}$ such that $g_{0}(x)<g_{1}(x)$ for all $x\in
I$ and

$C=\\{(x,y):x\in I,g_{0}(x)<y<g_{1}(x)\\}.$

The Cell Decomposition Theorem asserts that every $K$-definable subset of
${\cal R}^{2}$ is a finite union of cells defined over $K$.

##  2 Construction of a rigid non-Archimedean real closed field

We begin by noting that we cannot improve our main result to transcendence
degree one. Recall that $k$ is the field of real algebraic numbers.

###### Proposition 2.1

If $K$ is a non-Archimedean real closed field of transcendence degree one,
then $K$ has a nontrivial automorphism. Indeed, $|{\rm Aut}(K)|=\aleph_{0}$.

Proof  Let $a\in K$ with $a$ infinite. By exchange, $K=k\langle a\rangle$. Let
$b\in k\langle a\rangle$ be any other infinite element. For example, $b=a^{m}$
for some $m>1$. Since $a$ and $b$ realize the same cut over $k$, we have ${\rm
tp}(a/k)={\rm tp}(b/k)$. Thus there is an ordered field isomorphism $\sigma$
between $k(a)$ and $k(b)$ where $\sigma|k$ is the identity and $\sigma(a)=b$.
By the uniqueness of real closures, $\sigma$ extends to an isomorphism from
$K$ onto $k\langle b\rangle$. By exchange, $K=k\langle b\rangle$ and there is
an automorphism of $K$ sending $a$ to $b$.

Moreover, if $\sigma\in{\rm Aut}(K)$, then, because definable closure and
algebraic closure agree, $\sigma$ is completely determined by knowing
$\sigma(a)$. Thus $|{\rm Aut}(K)|=\aleph_{0}$. $\Box$

###### Theorem 2.2

There is a rigid non-Archimedean real closed field of transcendence degree
two.

The field we construct has the form $K=k\langle a,b\rangle$ where $a$ is
infinite and $b$ is transcendental over $k\langle a\rangle$. We first argue
that to make $K$ rigid it is both necessary and sufficient to show that
$(a,b)$ is the unique realization of ${\rm tp}(a,b/k)$ in $K$.

To see necessity, let $u,v\in k\langle a,b\rangle$ and ${\rm
tp}(a,b/k)=tp(u,v/k)$. Then, arguing as in the proof of Proposition 2.1, the
ordered fields $k(a,b)$ and $k(u,v)$ are isomorphic and this isomorphism
extends to their real closures $K$ and $k\langle u,v\rangle$, respectively. By
exchange $k\langle u,v\rangle=K$ and there is a nontrivial automorphism of
$K$. For sufficiency, note that if $k\langle a,b\rangle$ is not rigid, it must
have an automorphism $\sigma$ such that $\sigma(a,b)=(u,v)\not=(a,b)$.

Thus, to build a rigid $K$ we need to ensure that $(a,b)$ is the only
realization of ${\rm tp}(a,b/k)$ in $K$. Observe that because algebraic
closure agrees with definable closure, we must construct ${\rm tp}(a,b/k)$
such that if $F:{\cal R}^{2}\rightarrow{\cal R}^{2}$ is definable over $k$ and
$F(a,b)\neq(a,b)$, then ${\rm tp}(F(a,b)/k)\neq{\rm tp}(ab/k)$. As we want
$a>k$ and $b$ transcendental over $k\langle a\rangle$, there are restrictions
on the $k$-definable cells $C$ where $(a,b)\in C$.

Definition 2.3 We say that $C\subset{\cal R}^{2}$ is an end-cell if there is
$\alpha\in k$ and $k$-definable and continuous
$h_{0},h_{1}:(\alpha,+\infty)\rightarrow{\cal R}$ such that
$h_{0}(x)<h_{1}(x)$ for all $x>\alpha$ and

$C=\\{(x,y):x>\alpha,h_{0}(x)<y<h_{1}(x)\\}.$

Observe that if $C$ is an end-cell and $X\subseteq C$ is $k$-definable, then,
from a cell decomposition of $X$, we see that there is an end-cell
$C^{\prime}\subseteq C$ such that either $C^{\prime}\subseteq X$ or
$C^{\prime}\cap X=\emptyset$.

We claim that ${\rm tp}(a,b/k)$ is determined by the end-cells that contain
$(a,b)$. Indeed, suppose $C\subseteq{\cal R}^{2}$ is a cell defined over $k$
and $(a,b)\in C$. As we want $a>k$, the $x$-coordinates of $C$ cannot be
bounded. Also, $C$ must have dimension 2, as otherwise $b$ would be algebraic
over $k(a)$. Moreover, were $|b|>k\langle a\rangle$, as in the proof of
Proposition 2.1, we could build non-trivial automorphisms of $K$ fixing
$k\langle a\rangle$. Thus we can find $\alpha\in k$ and continuous,
$k$-definable $h_{0},h_{1}:(\alpha,+\infty)\rightarrow{\cal R}$ with
$h_{0}(x)<h_{1}(x)$ for all $x>\alpha$ such that

$(a,b)\in\\{(x,y):x>\alpha,h_{0}(x)<y<h_{1}(x)\\}\subseteq C.$

The principal ingredient needed for the proof of Theorem 2.2 is

###### Lemma 2.4

Suppose $C$ is an end-cell and $F:C\rightarrow{\cal R}^{2}$ is $k$-definable.
Then there is an end-cell $C^{\prime}\subseteq C$ such that either
$F\restriction C^{\prime}$ is the identity function or ${\rm img\
}(F\restriction C^{\prime})\cap C^{\prime}=\emptyset.$

Proof of Theorem 2.4 from Lemma 2.4

Let $F_{0},F_{1},\dots,F_{n},\dots$ enumerate all $k$-definable functions
$F:{\cal R}^{2}\rightarrow{\cal R}^{2}$ and let
$\phi_{0}(v_{1},v_{2}),\phi_{1}(v_{1},v_{2}),\dots$ enumerate all formulas in
the language of ordered rings with parameters from $k$ allowing only $v_{1}$
and $v_{2}$ as free variables.

Let $C_{0}=(0,+\infty)\times{\cal R}$. We build a sequence of $k$-definable
end-cells

$C_{0}\supset C_{1}\supset\dots\supset C_{n}\supset\dots.$

Applying Lemma 2.4 we find an end-cell $\widehat{C}_{n+1}\subset C_{n}$ such
that either $F\restriction\widehat{C}_{n+1}$ is the identity function or ${\rm
img\ }(F_{n}\restriction\widehat{C}_{n+1})\cap\widehat{C}_{n+1}=\emptyset$. We
then can find an end-cell $C_{n+1}\subseteq\widehat{C}_{n+1}$ such that
$C_{n+1}\subseteq(n,+\infty)\times{\cal R}$ and either $\phi_{n}(x,y)$ for all
$(x,y)\in C_{n+1}$ or $\neg\phi(x,y)$ for all $(x,y)\in C_{n+1}$.

We see that $\bigcap C_{n}$ determines a unique 2-type $p$ over $k$. If
$(a,b)$ realizes $p$, then $a>k$ and if $F:{\cal R}^{2}\rightarrow{\cal
R}^{2}$ is $k$-definable and $F(a,b)\neq(a,b)$, then $F(a,b)$ does not realize
$p$. Thus $k\langle a,b\rangle$ is non-Archimedean and has no nontrivial
automorphisms. $\Box$

We have a great deal of freedom in our construction. It easily could be
modified to build $2^{\aleph_{0}}$ non-isomorphic rigid non-Archimedean real
closed fields of transcendence degree two.

For the proof of Lemma 2.4, we need one refinement of cell decomposition; see
§7.3 of [1] for details.

###### Fact 2.5

If $C\subseteq{\cal R}^{2}$ is an end-cell and $F:C\rightarrow{\cal R}^{2}$ is
$k$-definable, we can find a $k$-definable end-cell $C^{\prime}\subset C$ such
that either $F~{}\restriction C^{\prime}$ is a homeomorphism or ${\rm img\
}(F\restriction C^{\prime})$ has dimension at most 1.

Proof of Lemma 2.4

Let $C$ be the end-cell $C:=\\{(x,y):x>\alpha,h_{0}(x)<y<h_{1}(x)\\}$. There
are several cases to consider.

Case 1 There is an end-cell $C_{0}\subseteq C$ such that ${\rm img\
}(F\restriction C_{0})$ has dimension at most one.

In this case we can find $C^{\prime}\subseteq C_{0}$ such that ${\rm img\
}(F\restriction C^{\prime})\cap C^{\prime}=\emptyset$, yielding the conclusion
of the lemma.

If we are not in Case 1, then, by Fact 2.5, without loss of generality we may
assume that $F\restriction C$ is a homeomorphism.

Case 2 There is an end cell $C^{\prime}\subseteq C$ such that $F\restriction
C^{\prime}$ is the identity function.

In this case the conclusion of the lemma certainly holds.

If we are not in Case 2, then, by cell decomposition we may assume without
loss of generality that $F(x,y)\neq(x,y)$ for all $(x,y)\in C$. We introduce
some notation for the next case. Let $f:(\alpha,+\infty)\rightarrow{\cal R}$
be $k$-definable such that $h_{0}(x)<f(x)<h_{1}(x)$ for all $x>\alpha$. We
define $\mu_{f},\nu_{f}:(\alpha,+\infty)\rightarrow{\cal R}$ by
$F(x,f(x))=(\mu_{f}(x),\nu_{f}(x)).$

Case 3 $\displaystyle\lim_{x\to\infty}\mu_{f}(x)\neq+\infty$ for some such
function $f$.

By monotonicity, there are $\alpha^{\prime}>\alpha$ and $\beta$ such that
$\mu_{f}(x)<\beta$ for all $x>\alpha^{\prime}$ and $\alpha^{\prime}>\beta$.
Applying cell decomposition we can find $k$-definable $g_{0}$ and $g_{1}$ such
that $h_{0}(x)<g_{0}(x)<f(x)<g_{1}(x)<h_{1}(x)$ and, with $\pi$ denoting
projection onto the first coordinate, $\pi(F(x,y))<\beta$ for all

$(x,y)\in C^{\prime}:=\\{(x,y):x>\alpha^{\prime},g_{0}(x)<y<g_{1}(x)\\}.$

Then ${\rm img\ }(F\restriction C^{\prime})\cap C^{\prime}=\emptyset$ and thus
the conclusion of the lemma holds.

Assuming we are not in Case 3, for every such function $f$ as above,
$\displaystyle\lim_{x\to\infty}\mu_{f}(x)=+\infty$. By monotonicity, shrinking
$C$ if needed, we may assume that $\mu_{f}$ is increasing. Thus, for
sufficiently large $x$, we can define

$f^{*}(x)=\nu_{f}(\mu^{-1}_{f}(x)).$

The graph of $f^{*}$ is a of the image for sufficiently large $x$ of the graph
of $f$ under $F$.

Case 4 There is some function $f$ such that $f(x)\neq f^{*}(x)$ for
sufficiently large $x$.

Shrinking the cell $C$ if necessary we can assume that either $f^{*}(x)>f(x)$
for all sufficiently large $x$ or $f^{*}(x)<f(x)$ for all sufficiently large
$x$. The cases are similar and we consider only the alternative in which
$f^{*}(x)>f(x)$ for sufficiently large $x$.

We claim we can find disjoint tubular neighborhoods of the graphs of $f$ and
$f^{*}$ such that the neighborhood of the graph of $f$ is mapped by $F$ into
the neighborhood of the graph of $f^{*}$. More precisely, we assert that we
can find $k$-definable functions $g_{0},g_{1},\phi_{0},\phi_{1}$ with domain
$(\gamma,+\infty)$ such that

$h_{0}(x)<g_{0}(x)<f(x)<g_{1}(x)<h_{1}(x)\hbox{ and
}g_{1}(x)<\phi_{0}(x)<f^{*}(x)<\phi_{1}(x)$

for all $x\in(\gamma,+\infty)$ and if we put

$C^{\prime}:=\\{(x,y):x>\gamma,g_{0}(x)<y<g_{1}(x)\\}$

then

${\rm img\ }(F\restriction
C^{\prime})\subseteq\\{(x,y):x>\gamma,\phi_{0}(x)<y<\phi_{1}(x)\\}.$

In this case ${\rm img\ }(F\restriction C^{\prime})\cap C^{\prime}=\emptyset$
and we have satisfied the conclusion of the lemma.

To see this, first choose continuous $k$-definable $\phi_{0}$ and $\phi_{1}$
and $\beta$ such that

$f(x)<\phi_{0}(x)<f^{*}(x)<\phi_{1}(x)$

for all $x>\beta$. By continuity of $F$ and cell decomposition, we can find
$k$-definable $g_{0}$ and $\widehat{g}$ such that
$g_{0}(x)<f(x)<\widehat{g}(x)$ for all $x>\beta$ and $\\{(x,y):x>\beta\hbox{
and }g_{0}(x)<y<\widehat{g}(x)\\}$ is contained in
$F^{-1}(\\{(x,y):x>\beta\hbox{ and }\phi_{0}(x)<y<\phi_{1}(x)\\}$. Now define

$g_{1}(x)=f(x)+{\min(\widehat{g}(x),\phi_{0}(x),h_{1}(x))-f(x)\over 2}$

and if necessary choose $\gamma\geq\beta$ so that $g_{0}$ and $g_{1}$ are
continuous for $x>\gamma$.

To complete the proof of the lemma, we now assume that none of Cases 1-4 holds
and derive a contradiction.

For each $r\in[0,1]$ let

$f_{r}(x)=h_{0}(x)+r(h_{1}(x)-h_{0}(x)).$

We may assume that for each $r$ there is a value $m_{r}$ such that
$f_{r}(x)=f_{r}^{*}(x)$ for all $x>m_{r}$. We further may assume that
$r\mapsto m_{r}$ is a definable continuous and monotonic function. Thus we can
find an interval $[a,b]$ and $m\in k$ such that if $r\in[a,b]$, then
$f_{r}(x)=f_{r}^{*}(x)$ for $x>\max(m,\alpha)$. Replacing $h_{0}$ by $f_{a}$,
$h_{1}$ by $f_{b}$, and $\alpha$ by $\max(\alpha,m)$, without loss of
generality we may assume that $F$ fixes the graph $f_{r}$ for all $r$.

Let $\psi:(\alpha,+\infty)\rightarrow(0,1)$ be an increasing $k$-definable
continuous bijection. Define

$f(x)=f_{\psi(x)}(x)\hbox{ for }x>\alpha.$

Observe that for each $r$ the graph of $f_{r}$ intersects the graph of $f$ at
a unique point $x_{r}$. Hence, for sufficiently large $x$, we have
$f_{\psi(x)}(x)=f(x)$. Since for all $r$ we have $f_{r}(x)=f_{r}^{*}(x)$ for
$x>\max(m,\alpha)$, it follows that $F(x,f(x))=(x,f(x))$. But we have assumed
that the hypothesis for Case 2 does not hold, that is, $F(x,y)\neq(x,y)$ for
all $(x,y)\in C$, and thus we reach a contradiction. $\Box$.

##  3 Remarks and Questions

  1. 1.

Using quantifier elimination for real closed fields and the decidability of
the real algebraic numbers, our construction could be done effectively,
producing a computable rigid non-Archimedean real closed field.

  2. 2.

Let $T$ be the theory of an o-minimal expansion of a real closed field. Our
construction works in this setting to build a rigid non-Archimedean ${\cal
M}\models T$ of o-minimal dimension two.

  3. 3.

Presumably our method can be extended to produce rigid real closed fields of
any finite transcendence degree greater than one. Can one produce a rigid
countable non-Archimedean real closed field of infinite transcendence degree?
It does not seem to be useful in the infinite transcendence degree case as we
can no longer easily diagonalize over all possible automorphisms.

  4. 4.

One might be tempted to try producing larger rigid real closed fields using
the following idea. Let $K$ be a countable real closed subfield of
${\mathbb{R}}$ of positive transcendence degree. The arguments above allow us
to construct $K\langle x,y\rangle$ with no non-trivial automorphism fixing
$K$. But, while $K$ is itself rigid, automorphisms of $K\langle x,y\rangle$
need not fix $K$.

To illustrate, let $B$ be a transcendence base for $K$, $b\in B$ and
$B_{0}=B\setminus\\{b\\}$. Let $K_{0}$ be the real closure of
${\mathbb{Q}}(B_{0})$. Note that $b$ is the unique realization of ${\rm
tp}(b/K_{0})$ in $K$. Let $L_{0}=K_{0}\langle x\rangle$ and $L=L_{0}\langle
y\rangle.$

For a real closed field $F$, we say that $a\in{\cal R}\setminus F$ realizes a
non-cut over $F$ if $F<|a|$ or there is $b\in F$ with $|a-b|<\epsilon$ for all
$\epsilon\in F$ with $\epsilon>0$. Otherwise, we say $a$ realizes a cut over
$F$.

Since ${\rm tp}(x/K_{0})$ is a non-cut and ${\rm tp}(b/K_{0})$ is a cut, by
[2] 3.3, ${\rm tp}(b/K_{0})$ is not realized in $L_{0}$. By construction,
${\rm tp}(y/L_{0})$ has a unique realization in $L$, but $b+{1\over x}$ is a
second realization of ${\rm tp}(b/L_{0})$ in $L_{0}\langle b\rangle$. Thus, by
[2] 3.6, ${\rm tp}(b/L_{0})$ is not realized in $L$. It follows that $b$ and
$b+{1\over x}$ realize the same type over $L$. Thus there is an automorphism
of $K\langle x,y\rangle=L\langle b\rangle$ fixing $L$ and sending $b$ to
$b+{1\over x}$.

## References

  * [1] van den Dries, Lou,  Tame topology and o-minimal structures. London Math. Soc. Lecture Note Ser., 248 Cambridge University Press, Cambridge, 1998.
  * [2] Marker, David, Omitting types in O-minimal theories, J. Symbolic Logic 51 (1986), no.1, 63–74.
  * [3] Mekler, Alan H, Shelah, Saharon, Some compact logics—results in ZFC, Ann. of Math. (2)137(1993), no.2, 221–248.
  * [4] Pillay, Anand and Steinhorn, Charles, Definable sets in ordered structures I, Trans. Amer. Math. Soc. 295 (1986), no.2, 565–592.
  * [5] Shelah, Saharon, Models with second order properties IV: A general method and eliminating diamonds, Ann. Pure Appl. Logic 25 (1983), no.2, 183–212.