# Intensity Prediction of Tropical Cyclones using Long Short-Term Memory
Network

Koushik Biswas
Department of Computer Science, IIIT Delhi
New Delhi, India, 110020.
<EMAIL_ADDRESS>
& Sandeep Kumar
Department of Computer Science, IIIT Delhi
&
Department of Mathematics,
Shaheed Bhagat Singh College, University of Delhi
New Delhi, India, 110020.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Ashish Kumar Pandey
Department of Mathematics, IIIT Delhi
New Delhi, India, 110020.
<EMAIL_ADDRESS>

###### Abstract

Tropical cyclones can be of varied intensity and cause a huge loss of lives
and property if the intensity is high enough. Therefore, the prediction of the
intensity of tropical cyclones advance in time is of utmost importance. We
propose a novel stacked bidirectional long short-term memory network (BiLSTM)
based model architecture to predict the intensity of a tropical cyclone in
terms of Maximum surface sustained wind speed (MSWS). The proposed model can
predict MSWS well advance in time (up to 72 h) with very high accuracy. We
have applied the model on tropical cyclones in the North Indian Ocean from
1982 to 2018 and checked its performance on two recent tropical cyclones,
namely, Fani and Vayu. The model predicts MSWS (in knots) for the next 3, 12,
24, 36, 48, 60, and 72 hours with a mean absolute error of 1.52, 3.66, 5.88,
7.42, 8.96, 10.15, and 11.92, respectively.

_Keywords_ Deep Learning $\cdot$ LSTM $\cdot$ Tropical Cyclone $\cdot$ Cyclone
intensity

##  1 Introduction

The weather-related forecast is one of the difficult problems to solve due to
the complex interplay between various cause factors. Accurate tropical cyclone
intensity prediction is one such problem that has huge importance due to its
vast social and economic impact. Cyclones are one of the devastating natural
phenomena that frequently occur in tropical regions. Being a tropical region,
Indian coastal regions are frequently affected by tropical cyclones [1] that
originate into the Arabian Sea (AS) and Bay of Bengal (BOB), which are parts
of the North Indian Ocean (NIO). With the increasing frequency of cyclones in
NIO [2], it becomes more crucial to develop a model that can forecast the
intensity of a cyclone for a longer period of time by observing the cyclone
only for a small period of time. Various statistical and numerical methods
have been developed to predict the intensity of cyclones [3, 4, 5, 6, 7] but
all these methods lack effectiveness in terms of accuracy and computation
time.

India Meteorological Department (IMD) keep track of tropical cyclones which
originates in the North Indian Ocean between $100^{\circ}$E and $45^{\circ}$E.
Typically, the intensity of the tropical cyclone is stated in terms of
"Grade", which is directly derived from different ranges of the Maximum
Sustained Surface Wind Speed (MSWS), see Table 1 [8]. Therefore, MSWS being a
continuous variable is a better choice for the intensity prediction [9], which
we adopt for this work. We have used latitude, longitude, MSWS, estimated
central pressure, distance, direction, and sea surface temperature as input
features.

Table 1: The classification of the low pressure systems by IMD. Grade | Low pressure system | MSWS (in knots)
---|---|---
0 | Low Pressure Area (LP) |  $<$17
1 | Depression (D) | 17-27
2 | Deep Depression (DD) | 28-33
3 | Cyclonic Storm (CS) | 34-47
4 | Severe Cyclonic Storm (SCS) | 48-63
5 | Very Severe Cyclonic Storm (VSCS) | 64-89
6 | Extremely Severe Cyclonic Storm (ESCS) | 90-119
7 | Super Cyclonic Storm (SS) |  $\geq$120

Recently, Artificial neural Networks (ANNs) have been successful in capturing
the complex non-linear relationship between input and output variables [10,
11, 12]. ANNs are also explored recently to predict the cyclone intensity [13,
9, 14, 15]. These studies use the various recordings of weather conditions for
a particular time point and predict the intensity of cyclones at a particular
future time point. However, this does not allow us to fully utilise the time
series data available. Instead, we use the Long Term Short Memory (LSTM)
network to forecast the intensity of tropical cyclones in NIO. By using LSTM,
we are able to use the different weather characteristics for a certain number
of continuous-time points to forecast the cyclone intensity for an immediately
succeeding a certain number of time points.

In related works [13, 9, 15] for tropical cyclones in NIO, the MSWS has been
predicted for a particular future time point. Although it is important to know
the intensity at a particular time point, the change in intensity as the
tropical cyclone progresses is equally important to know. As mentioned
earlier, using ANNs, this continuous variation can not be captured
effectively. Our work is unique in the sense that we have used an LSTM based
model for the first time to predict the cyclone intensity for multiple
successive future time points and report the combined accuracy for these time
points. The reported combined accuracy outperforms the accuracy reported at a
single point in other works. Our model works consistently well, even for a
large number of future time points, and increases gradually with the number of
future time points. In Section II, we present a brief description of our
model, and in Section III, the used dataset is described. Section IV presents
results and their analysis, and Section V includes the conclusion and future
directions.

##  2 METHODOLOGY

###  2.1 Artificial Neural Networks

An artificial neural network (ANN) is a connected network inspired by the
human brain’s biological neurons. ANN has an input layer, an output layer, and
multiple hidden layers. Each hidden layer contains several artificial neurons
at which incoming information is first linearly combined using weights and
bias and then acted upon by an activation function. Mathematically, for input
matrix $X$, the $i$th neuron in the $j$th layer can be written as

$\displaystyle h_{j}^{i}=\sigma(W_{j}^{i}X+b_{j}^{i})$ (1)

where $W_{j}^{i}$ and $b_{j}^{i}$ are weight matrix and bias vector of the
corresponding neuron, respectively, and $\sigma$ is the activation function.
The weights and bias at each neuron are updated using the gradient descent
algorithm to make the final loss as small as possible. An example of a fully
connected ANN with two hidden layers is given in the Figure 1. A type of ANN
that can handle time series or sequential data is Recurrent Neural Network,
which we will discuss next.

Figure 1: Fully Connected ANN

###  2.2 Recurrent Neural Network

Recurrent Neural Networks (RNNs) can take a sequence of inputs and produce a
sequence of outputs and the outputs are influenced not just by weights applied
on inputs like a regular ANN, but also by a hidden state vector representing
the learned information based on prior inputs and outputs [16, 17, 18, 19].
RNN can be represented by a chain-like structure, see Figure 2, where the
lower, middle, and upper chains represent the sequence of inputs, hidden state
vector, and sequence of outputs, respectively. Mathematically, a simple RNN
can be written as

$\displaystyle h_{t}=$ $\displaystyle\sigma(W_{h}x_{t}+U_{h}h_{t-1}+b_{h})$
(2) $\displaystyle y_{t}=$ $\displaystyle\sigma(W_{y}h_{t}+b_{y})$ (3)

where $\sigma$ is the activation function, $x_{t}$ is the input vector at
timestamp $t$, $h_{t}$ is the hidden state vector at timestamp $t$, $y_{t}$ is
the output vector at timestamp $t$, $h_{t-1}$ is the output vector at
timestamp ${(t-1)}$, $W_{h},W_{y}$ and $U_{h}$ are weight matrices, and
$b_{h},b_{y}$ are the biases. The gradient vector of RNN can increase or
decrease exponentially during the training period, which leads to exploding or
vanishing gradient problems because of which an RNN cannot retain a very long
term history from the past. This problem is solved by Long Short Term Memory
Networks.

Figure 2: Recurrent Neural Network

###  2.3 Long Short Term Memory Networks

Long Short Term Memory Network (LSTM) was first introduced in 1997 by
Hochreiter and Schmidhuber[20] and further few improved version of LSTM was
proposed later [21, 22, 23]. LSTM was defined in such a way so that it can
remember long term dependencies from past and overcome the issue of vanishing
and gradient problem of RNN. An LSTM network works on the philosophy of
selectively forget, selectively read, and selectively write. LSTM can add or
delete information to the cell state. This states are called gates. LSTM has
three gates which are usually known as Input, Forget and Output gate. The
equations for the three LSTM gates are

$\displaystyle f_{t}=$ $\displaystyle\sigma(w_{f}.x_{t}+u_{f}.h_{t-1}+b_{f})$
(4) $\displaystyle i_{t}=$
$\displaystyle\sigma(w_{i}.x_{t}+u_{i}.h_{t-1}+b_{i})$ (5) $\displaystyle
o_{t}=$ $\displaystyle\sigma(w_{o}.x_{t}+u_{o}.h_{t-1}+b_{o})$ (6)

and the equations for the cell state, candidate cell state and output are

$\displaystyle\tilde{c_{t}}=$
$\displaystyle\sigma(w_{c}.x_{t}+u_{c}.h_{t-1}+b_{c})$ (7) $\displaystyle
c_{t}=$ $\displaystyle f_{t}.c_{t-1}+i_{t}.c_{t}$ (8) $\displaystyle h_{t}=$
$\displaystyle o_{t}.\sigma(c_{t})$ (8)

where $i_{t}$ represents input gate, $f_{t}$ represents forget gate, $o_{t}$
represents output gate, $h_{t-1}$ is output from previous LSTM block at
$(t-1)$ timestamp, $x_{t}$ is input at current timestamp, $c_{t}$ represents
cell state at timestamp $t$, $\tilde{c_{t}}$ is candidate for cell state at
timestamp $t$, and $w_{f},w_{i},w_{c},w_{o},u_{f},u_{i},u_{c},u_{o}$ are
weight matrices, $b_{f},b_{i},b_{c},b_{o}$ are bias vectors and $\sigma$ is
the activation function, see figure 3.

###  2.4 Stacked LSTM

Stacked LSTM is an extended version of the LSTM model. In this model, there
are multiple hidden layers where the next layer is stacked on top of the
previous layer, and each layer contains multiple LSTM cells. Stacking layers
make the model more deeper and help to learn patterns in sequence-learning and
time-series problems more accurately.

###  2.5 Bidirectional LSTM

A more modified and classic version of LSTM is Bidirectional LSTM (BiLSTM)
[24]. LSTM is trained to learn in one direction; on the other hand, BiLSTM
learns in two directions, one from past to future and another from future to
past. BiLSTM has two separate LSTM layers in opposite directions of each
other. The input sequence is fed into one layer in the forward direction and
another layer in the backward direction. Both of the layers are connected to
the same output layer, and it collects information from the past and future
simultaneously.

Figure 3: Example of an LSTM Cell

###  2.6 Dropout

A model will learn complex and dynamical behaviour more accurately if hidden
units are independent of each other while learning features. It has been
observed that in neural network models, some of the neurons become highly
correlated and dependent on each other while the rest are independent. They
can significantly affect model performance, which may lead to overfitting.
This is called co-adaptation, and it’s a major issue in large networks. This
problem is solved using the dropout method [25]. Dropout is a regularisation
technique used in neural network models to prevent the model from overfitting.
It randomly ignores neurons with probability $1-p$ and keeps neurons with
probability $p$ during training time. It helps the model to learn more
powerful features and patterns from data.

##  3 Data

Various organisations around the world keep a record of all tropical cyclones
in that region; such records are generally known as Best Track Datasets
(BTDs). In this study, we have used the BTD of tropical cyclones in the North
Indian ocean provided by the Regional Specialized Meteorological Centre, New
Delhi
111http://www.rsmcnewdelhi.imd.gov.in/index.php?option=com_content&view=article&id=48&Itemid=194&lang=en.

The dataset contains three hourly records of 341 tropical cyclones from 1982
to 2018 in the NIO. There are a total of 7662 recordings, and each recording
contains information about the cyclone’s basin of origin (AS or BOB), name (if
any), date and time of occurrence, latitude, longitude, estimated central
pressure (ECP), and MSWS, pressure drop (PD), T.No., and grade. The
trajectories (with MSWS) of all the cyclones in NIO along with the trajectory
(with MSWS) of two recent devastating cyclones Vayu and Fani are shown in the
Figures 4(a), 4(b), 4(c) respectively.

After processing the dataset for possible errors, we obtained a dataset of 341
cyclones with an average number of 27 recordings. The largest cyclone has 90
such recordings. The dataset has lots of missing data, and it is handled using
imputing techniques. We have used pandas linear interpolation techniques to
fill the missing values.

We have used latitude, longitude, ECP, and MSWS from the BTD. The sea surface
temperature (SST) is an important factor for cyclone generation and governs
its intensity. SST is obtained from the NOAA dataset provided at
222http://apdrc.soest.hawaii.edu/erddap/griddap/hawaii_soest_afc8_9785_907e.html.
We have generated two new features, distance and direction from latitudes and
longitudes 333https://www.movable-type.co.uk/scripts/latlong.html. The
features latitude, longitude, MSWS, ECP, distance, direction, and SST are used
in our model as input variables.

It has been observed that RNN learns from its inputs equally with the scaled
data. We have kept MSWS in original scale and re-scaled latitude, longitude,
ECP, SST, distance and direction to [-1,1] range. We have utilized Scikit
learn for features re-scaling using MinMaxScaler transformation [26].
MinMaxScaler transformation will map the interval $[\min,\max]$ one-to-one to
the interval $[a,b]$, defined as follows

$\displaystyle f(x)=a+\left(\frac{b-a}{\max-\min}\right)(x-\min)$ (9)

with the assumption that $\min\neq\max$ and $f(\min)=a$ and $f(\max)=b$, and
$f$ is the transformation.

(a)

(b)

(c)

Figure 4: North Indian ocean cyclone’s trajectory with MSWS

##  4 Training and Proposed Model implementation

###  4.1 Model training

Model weights and biases have been trained and updated via back-propagation
algorithm. We consider Mean Square Error (MSE) as the loss function and
evaluate the model performance using Root Mean Square Error (RMSE) and Mean
Absolute Error (MAE). The definitions are given as follow

$\displaystyle\operatorname{MSE}=\frac{1}{n}\sum_{i=1}^{n}(y_{i}-\bar{y_{i}})^{2}$
(10)
$\displaystyle\operatorname{RMSE}=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(y_{i}-\bar{y_{i}})^{2}}$
(11)
$\displaystyle\operatorname{MAE}=\frac{1}{n}\sum_{i=1}^{n}\left|y_{i}-\bar{y_{i}}\right|$
(12)

where $y_{i}$ is the actual value and $\bar{y_{i}}$ is the model predicted
value.

###  4.2 Model Implementation

We have considered a total of four stacked BiLSTM layers (one input, one
output, and two hidden layers) for our proposed model architecture. Latitude,
longitude, distance, direction, SST, ECP, and MSWS used as data tuples in the
input layer. We have implemented our proposed model using Keras API [27].
Keras is an API which runs on top of low-level language TensorFlow [28],
developed by Google. We use a learning rate 0.01, which is useful to update
weights at each layer of BiLSTM and is improved using Adaptive moment
estimation (Adam) [29] and it helps to minimise the loss function. We have set
dropout value equals to 0.02 in internal layers. Our proposed model is shown
in Figure 5. It has been generated using Keras API.

Figure 5: Our Proposed BiLSTM model for $T_{1}=4$ and $T_{2}=12$

.

Table 2: Our Proposed BiLSTM Model performance on Indian ocean cyclone data.  Data Used | Mean Absolute Error | Root Mean Square Error
---|---|---
Training Points $T_{1}$ (hours) |  Predict Points $T_{2}$ (hours) |  Training data size (no of cyclones) |  5-fold MAE on Validation Data |  Test on Cyclone Vayu |  Test on Cyclone Fani |  5-fold RMSE on Validation Data |  Test on Cyclone Vayu |  Test on Cyclone Fani
4 (12) |  1 (3) |  7211 (320) |  1.54 |  3.95 |  3.20 |  3.12 |  4.47 |  4.51
4 (12) |  6263 (306) |  3.66 |  9.81 |  7.12 |  6.72 |  11.52 |  9.17
8 (24) |  5109 (266) |  5.88 |  11.31 |  13.52 |  9.95 |  13.98 |  18.48
12 (36) |  4110 (228) |  7.42 |  17.52 |  20.04 |  12.64 |  21.03 |  26.05
16 (48) |  3244 (195) |  8.96 |  15.50 |  21.32 |  14.82 |  18.22 |  27.12
20 (60) |  2512 (165) |  10.15 |  16.98 |  22.72 |  16.07 |  21.34 |  28.87
24 (72) |  1888 (138) |  11.92 |  15.01 |  22.97 |  17.87 |  20.83 |  28.14
6 (18) |  1 (3) |  6574 (311) |  1.55 |  2.98 |  2.32 |  3.20 |  3.31 |  3.56
4 (12) |  5657 (277) |  3.72 |  8.01 |  7.03 |  6.37 |  10.36 |  9.42
8 (24) |  4588 (243) |  6.19 |  13.24 |  12.53 |  10.62 |  15.84 |  16.23
12 (36) |  3657 (211) |  7.92 |  17.32 |  20.54 |  13.23 |  20.01 |  26.12
16 (48) |  2864 (179) |  9.31 |  10.82 |  27.74 |  15.35 |  13.05 |  27.52
20 (60) |  2185 (151) |  10.22 |  11.82 |  22.56 |  16.42 |  15.01 |  28.52
24 (72) |  1627 (117) |  11.52 |  16.34 |  19.82 |  17.85 |  28.98 |  35.86
8 (24) |  1 (3) |  5957 (300) |  1.52 |  2.32 |  2.52 |  3.32 |  2.98 |  3.56
4 (12) |  5109 (266) |  3.82 |  7.08 |  6.82 |  6.88 |  9.01 |  9.02
8 (24) |  4110 (228) |  5.98 |  9.92 |  13.46 |  10.82 |  12.32 |  18.57
12 (36) |  3244 (195) |  8.12 |  10.66 |  21.62 |  13.18 |  13.03 |  30.05
16 (48) |  2512 (165) |  9.91 |  10.02 |  25.11 |  15.82 |  11.82 |  30.98
20 (60) |  1888 (138) |  11.52 |  14.02 |  27.12 |  17.56 |  16.52 |  33.26
24 (72) |  1399 (104) |  12.01 |  18.82 |  32.52 |  18.52 |  21.98 |  39.80
12 (36) |  1 (3) |  4843 (255) |  1.72 |  2.22 |  3.45 |  3.44 |  2.52 |  5.41
4 (12) |  4110 (228) |  3.96 |  4.52 |  5.37 |  7.52 |  6.01 |  8.12
8 (24) |  3244 (195) |  6.52 |  8.37 |  17.85 |  11.32 |  9.75 |  20.33
12 (36) |  2512 (165) |  8.62 |  8.01 |  21.10 |  14.31 |  10.51 |  27.33
16 (48) |  1888 (138) |  10.32 |  8.51 |  29.31 |  16.57 |  10.85 |  27.82
20 (60) |  1399 (104) |  10.98 |  14.02 |  21.27 |  17.63 |  17.07 |  28.02
24 (72) |  1016 (80) |  12.01 |  15.55 |  34.34 |  18.57 |  19.52 |  39.37

(a)

(b)

(c)

(d)

Figure 6: Actual and Model predicted MSWS for Testing Data- Cyclone Vayu and
Fani.

##  5 Result and Analysis

In this study, we are interested in predicting a cyclone’s intensity in the
form of MSWS for $T_{2}$ number of time points at a regular interval, using
the cyclone information for $T_{1}$ number of time points, again given at
regular time interval. For example, if our $T_{1}$ is 4 and $T_{2}$ is 6, then
we want to train a model that uses a cyclone data of 4 regular time points and
predict the intensity of the cyclone immediately succeeding 6 regular time
points. We report the results for different combinations of $T_{1}$ and
$T_{2}$. To compare our results with the existing related works, the model
performance is reported in terms of RMSE and MAE. We have reported our model’s
performance for two recent cyclones Vayu and Fani, along with 5-fold cross-
validation scores in Table 2. These two named cyclones are not part of the
training data.

The predicted intensity of cyclones Vayu and Fani for different combinations
of $T_{1}$ and $T_{2}$ is shown in Figures 6(a), 6(b), 6(c), and 6(d) along
with the actual intensity for $T_{1}+T_{2}$ number of time points. These
figures show that our model effectively captures the future evolution of
cyclone intensity from the given training data. The graphs for Fani cyclones
in Figures 6(c), and 6(d), show that though the intensity of cyclone remains
almost constant during training time, still our model predicts the intensity
quite accurately for future $T_{2}$ number of time points. This demonstrates
that our model is effectively learning from its input features latitude,
longitude, direction, distance, ECP, and SST. A similar but reverse behaviour
can be observed from the graph of the Fani cyclone in Figure 6(a), where
though the intensity is continuously increasing during training time, still,
our model accurately captures the almost constant intensity for future $T_{2}$
number of time points. Thus, we can conclude that our model is learning the
complex non-linear relationship of input features with the output effectively
and successfully predicts sudden changes in the intensity of cyclones. Graphs,
as reported in Figure 6 for any future cyclone, can be used for preventives
measures well in time.

From Table 2, it is clear that our model is able to learn MSWS with good
accuracy in terms of MAE and RMSE for different combinations of $T_{1}$ and
$T_{2}$. If we fix $T_{1}$, from the Table 2, we can see that as $T_{2}$
increases, error increases as well. This is expected because we are predicting
MSWS for a longer duration as $T_{2}$ increases from the same set of training
points. Moreover, as $T_{1}$ increases, there is no significant difference
between errors. For example, if $T_{1}=4$ and $T_{2}=1$, MAE is 1.54 and if
$T_{1}=8$ and $T_{2}=1$, MAE is 1.52. Similar trend can be observed for other
combinations of $T_{1}$ and $T_{2}$. So, even though we increased the number
of training points two-fold, the change in MAE is not significant. This
indicates that the model is learning most from the initial few data points.
For practical purposes, this is very important as it reduces both the waiting
and computational time.

The model can predict MSWS up to 24 h well within 6 knots. From Table 1, range
of MSWS for higher Grades ($\geq 3$) is at least 15. It means with a high
probability, the model will predict the grades greater than equal to 3
accurately up to 24 h.

##  6 Conclusion

The authors presented a BiLSTM model to predict the intensity of tropical
cyclones in NIO for continuous long-duration future time points with high
accuracy. The BiLSTM model is used for the first time for the intensity
forecast. As we are able to achieve high accuracy for longer period intensity
forecast, this means that our model is successfully able to capture the
complex relationship between various cause factors behind cyclone formation
that governs the evolution of cyclone intensity.

The most crucial time point to predict the cyclone intensity would be at
landfall. In future, one can try to predict the time of landfall and then
train a model that accurately predicts the intensity at that instance. This
will make the forecast more practical and effective as the government agencies
can take more precise preventive steps both in terms of the region to focus
and level of preparedness.

## Acknowledgment

The authors would like to thank the India Meteorological Department (IMD), New
Delhi, for providing BTD for this study. The authors acknowledge NOAA for
providing the SST data.

## References

  * [1] Sutapa Chaudhuri, Anirban Middey, Sayantika Goswami, and Soumita Banerjee.  Appraisal of the prevalence of severe tropical storms over indian ocean by screening the features of tropical depressions.  Natural hazards, 61(2):745–756, 2012.
  * [2] William M Frank and Elizabeth A Ritchie.  Effects of environmental flow upon tropical cyclone structure.  Monthly weather review, 127(9):2044–2061, 1999.
  * [3] Brian R Jarvinen and Charles J Neumann.  Statistical forecasts of tropical cyclone intensity for the north atlantic basin.  1979\.
  * [4] Mark DeMaria and John Kaplan.  An updated statistical hurricane intensity prediction scheme (ships) for the atlantic and eastern north pacific basins.  Weather and Forecasting, 14(3):326–337, 1999.
  * [5] Jong-Jin Baik and Hong-Sub Hwang.  Tropical cyclone intensity prediction using regression method and neural network.  Journal of the Meteorological Society of Japan. ser. ii, 76(5):711–717, 1998.
  * [6] Sutapa Chaudhuri and Anindita De Sarkar.  Severity of tropical cyclones atypical during el nino–a statistical elucidation.  Asian Journal of Water, Environment and Pollution, 6(4):79–85, 2009\.
  * [7] Vernon F Dvorak.  Tropical cyclone intensity analysis using satellite data, volume 11.  US Department of Commerce, National Oceanic and Atmospheric Administration …, 1984.
  * [8] India Meteorological Department(IMD).  Frequently asked questions on tropical cyclones.  Available at http://www.rsmcnewdelhi.imd.gov.in/images/pdf/cyclone-awareness/terminology/faq.pdf.
  * [9] S Chaudhuri, D Basu, D Das, S Goswami, and S Varshney.  Swarm intelligence and neural nets in forecasting the maximum sustained wind speed along the track of tropical cyclones over bay of bengal.  Natural Hazards, 87(3):1413–1433, 2017.
  * [10] MM Ali, P. Jagadeesh, I-I Lin, and Je-Yuan Hsu.  A neural network approach to estimate tropical cyclone heat potential in the indian ocean.  IEEE Geoscience and Remote Sensing Letters, 9:1114–1117, 11 2012\.
  * [11] Kumar Abhishek, M.P. Singh, Saswata Ghosh, and Abhishek Anand.  Weather forecasting model using artificial neural network.  Procedia Technology, 4:311 – 318, 2012.  2nd International Conference on Computer, Communication, Control and Information Technology( C3IT-2012) on February 25 - 26, 2012.
  * [12] Rita Kovordányi and Chandan Roy.  Cyclone track forecasting based on satellite images using artificial neural networks.  ISPRS Journal of Photogrammetry and Remote Sensing, 64:513–521, 11 2009.
  * [13] Sutapa Chaudhuri, Debashree Dutta, Sayantika Goswami, and Anirban Middey.  Track and intensity forecast of tropical cyclones over the north indian ocean with multilayer feed forward neural nets.  Meteorological Applications, 22(3):563–575, 2015.
  * [14] Chandan Roy and Rita Kovordányi.  Tropical cyclone track forecasting techniques—a review.  Atmospheric research, 104:40–69, 2012.
  * [15] M Mohapatra, BK Bandyopadhyay, and DP Nayak.  Evaluation of operational tropical cyclone intensity forecasts over north indian ocean issued by india meteorological department.  Natural Hazards, 68(2):433–451, 2013.
  * [16] Michael I. Jordan.  Attractor Dynamics and Parallelism in a Connectionist Sequential Machine, page 112–127.  IEEE Press, 1990.
  * [17] D. E. Rumelhart and J. L. McClelland.  Learning Internal Representations by Error Propagation, pages 318–362.  1987\.
  * [18] Axel Cleeremans, David Servan-Schreiber, and James L. McClelland.  Finite state automata and simple recurrent networks.  Neural Comput., 1(3):372–381, September 1989.
  * [19] Pearlmutter.  Learning state space trajectories in recurrent neural networks.  In International 1989 Joint Conference on Neural Networks, pages 365–372 vol.2, 1989.
  * [20] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural Comput., 9(8):1735–1780, November 1997.
  * [21] F. A. Gers, J. Schmidhuber, and F. Cummins.  Learning to forget: continual prediction with lstm.  In 1999 Ninth International Conference on Artificial Neural Networks ICANN 99. (Conf. Publ. No. 470), volume 2, pages 850–855 vol.2, 1999\.
  * [22] Felix A. Gers, Nicol N. Schraudolph, and Jürgen Schmidhuber.  Learning precise timing with lstm recurrent networks.  J. Mach. Learn. Res., 3(null):115–143, March 2003.
  * [23] F. A. Gers and E. Schmidhuber.  Lstm recurrent networks learn simple context-free and context-sensitive languages.  IEEE Transactions on Neural Networks, 12(6):1333–1340, 2001.
  * [24] M. Schuster and K. K. Paliwal.  Bidirectional recurrent neural networks.  IEEE Transactions on Signal Processing, 45(11):2673–2681, 1997\.
  * [25] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: A simple way to prevent neural networks from overfitting.  J. Mach. Learn. Res., 15(1):1929–1958, January 2014.
  * [26] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [27] François Chollet.  Keras.  https://github.com/fchollet/keras, 2015.
  * [28] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  Software available from tensorflow.org.
  * [29] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.


# A Contribution-based Device Selection Scheme in Federated Learning

Shashi Raj Pandey, IEEE Member, Lam D. Nguyen, IEEE Member, and Petar
Popovski, IEEE Fellow Shashi Raj Pandey, Lam D. Nguyen, and Petar Popovski are
with Connectivity Section, Department of Electronic Systems, Aalborg
University, Denmark. Email: {srp, ndl<EMAIL_ADDRESS>
###### Abstract

In a Federated Learning (FL) setup, a number of devices contribute to the
training of a common model. We present a method for selecting the devices that
provide updates in order to achieve improved generalization, fast convergence,
and better device-level performance. We formulate a min-max optimization
problem and decompose it into a primal-dual setup, where the duality gap is
used to quantify the device-level performance. Our strategy combines
_exploration_ of data freshness through a random device selection with
_exploitation_ through simplified estimates of device contributions. This
improves the performance of the trained model both in terms of generalization
and personalization. A modified Truncated Monte-Carlo (TMC) method is applied
during the exploitation phase to estimate the device’s contribution and lower
the communication overhead. The experimental results show that the proposed
approach has a competitive performance, with lower communication overhead and
competitive personalization performance against the baseline schemes.

###### Index Terms:

federated learning, device selection, exploration, exploitation,
personalization, generalization

##  I Introduction

Federated Learning (FL), as introduced by McMahan et. al. [1], discusses
unbalanced and non-i.i.d. (independent and identical distribution) data
partitioning across a massive number of unreliable devices, coordinating with
a central server, to distributively train learning models without sharing the
actual data. In practice, the data samples are generated through device’s
usage, such as interactions with applications, results to such statistical
heterogeneity. Towards that, related works primarily focus on improving the
model performance by tackling data properties, i.e., statistical challenges in
the FL [1, 2]. Noticeably, in the initial work [1], the authors show that
their proposed Federated Averaging (FedAvg) algorithm empirically works well
with non-i.i.d. data. However, the accuracy of FedAvg varies differently for
different datasets, as observed in the existing methods [2, 3], and how client
selection is made [3, 4, 5]. For instance, the authors in [3, 4] discussed the
impact of having heterogeneous clients, given time requirements for per round
training execution, during the decentralized model training over unreliable
wireless networks. In doing so, more devices are packed within a training
round to improve model accuracy; however, this lead to consumption of
excessive communication resources and larger communication rounds to attain a
level of global model accuracy. Also, all received local updates are given
equal priority during model aggregation; thus, fairly ignoring their
contributions and rationale behind selecting them. In line with that, the
authors in [1, 2, 3] revealed adding local computations can dramatically
increase communication efficiency and improve the trained model performance.
However, this additional computational load may be prohibitive for some
devices.

In principle, aforementioned issues appear primarily as a result of selecting
ill-conditioned devices in the training procedure without evaluating their
marginal contribution in improving the model performance. In fact, in FL
literature [2, 3, 4], device selection problem over wireless networks has
remained an overarching challenge, particularly, due to two reasons: _first_ ,
owing to the consequences of statistical and system-level heterogeneity,
uniformly random selection of device may lead to slower convergence and poor
model performance across devices; _second_ , devices with trivial
contributions may get scheduled in model training process which only adds
larger communication overhead. Moreover, device’s contribution are unknown a
priori, and its estimation is not straightforward. Some recent works [5, 6]
introduced quality-aware device selection strategy with multi-arm bandits
(MAB) method in the absence of estimates on available computation-
communication resources with fixed dataset; however, they focus on
minimization of the convergence time, leaving aside the impact of device
selection on the trained model performance, particularly on unseen data, as
well as the device-level performance.

Figure 1: An illustration of device selection strategy with a mix of
exploration and exploitation.

In this work, we are interested in, and provide a solution to, the problem of
device selection and its impact on model performance defined in terms of
_generalization_ , i.e., how the trained model work on unseen/new data
samples, and _personalization_ , i.e., the device-level performance. Different
from the related literature, our approach considers the impact of device
selection procedure in the decentralized training framework of FL with
fairness guarantees in the model performance. The term _fairness_ captures the
discrepancies in device-level model performance, i.e., personalization
performance, appeared as a direct consequence of statistical heterogeneity and
device selection approach. Referring to Fig. 1, we start by random device
selection in FL during the exploration phase at each global iteration.
Subsequently, in the exploitation phase, the focus is on contribution-based
model aggregation for refining the global model. As the contributions of
devices in enhancing the global model performance is unknown a priori, we
develop a mechanism that first provides an estimation of device’s
contribution, which is followed by model aggregation. This way, we bring
balance in improving both generalization and personalization performance of
the trained model. The summary of our contributions are as follows.

  * •

We develop a cost-efficient, simplified device selection mechanism in the FL
setting that captures the notion of fairness in terms of personalized
performance. It lowers the communication overhead while enhancing the
generalization performance of the trained model. Therein, as an initial step,
the problem is revealed as a min-max optimization problem that specifically
captures the aforementioned joint objectives.

  * •

To solve the problem of device selection, we propose a strategic mix of
exploration and exploitation during each global iteration. This is in contrast
to periodic exploration that particularly leads to poor model performance. In
particular, we unleash a mechanism that both assess and incorporates the value
of contribution of each randomly selected device during model training.

  * •

We propose a contribution-based device selection (CDS) technique for model
aggregation with the modified Truncated Monte-Carlo (TMC) [7] method during
exploitation phase within random device selection rounds, i.e., the
exploration phase. We show this technique eliminates the need of adding local
computations to lower communication overhead and improve model convergence.

  * •

The simulation results show that the proposed method, while offering a $4$X
decrease in the communication rounds, still brings a small performance
improvement in terms of personalization.

Overall, the chief contribution of this work is that it incorporates a
contribution-based device selection strategy for model aggregation in FL. This
improves device-level performance in several aspects simultaneously:
generalization, low communication overhead, and fast convergence.

##  II Problem Setting

We consider a supervised learning problem in a FL setting where each available
device (client) $m\in\mathcal{M}$ in the training process has a local data set
$\mathcal{D}_{m}$ of size $D_{m}$ such that the overall training data size
$D=\sum_{m=1}^{M}D_{m}$. The devices communicate with the central aggregator
(e.g., a multi-access edge computing (MEC) server) via orthogonal frequency
division multiple access (OFDMA). For simplicity, downlink is treated as
error-free. The data samples are defined as a collection set of input-output
pairs $\\{x_{i},y_{i}\\}_{i=1}^{D_{m}}$, where, respectively,
$x_{i}\in\mathcal{X}$ characterizes the feature space of data sample with
corresponding labels $y_{i}\in\mathcal{Y}$,
$\mathcal{X}\subseteq\mathbb{R}^{d}$ and $\mathcal{Y}\subseteq\mathbb{R}$. The
goal of the central aggregator orchestrating the distributed training process
is to learn a predictor $F(w):\mathcal{X}\rightarrow\mathcal{Y}\in\mathbb{R}$.
The predictor performance is associated with learning of a model parameter
$w\in\mathbb{R}^{d}$ that captures the empirical risk on all distributed data
samples as the finite-sum objective of the form

$\underset{w\in\mathbb{R}^{d}}{\text{min}}J(w)+\lambda g(w)\ \ \text{where}\ \
J(w):=\sum\nolimits_{m=1}^{M}\frac{D_{m}}{D}\cdot J_{m}(w),$ (1)

$J_{m}(w):=\frac{1}{D_{m}}\sum\nolimits_{i=1}^{D_{m}}f_{i}(w)$, $f_{i}(w)$ is
the loss function that depends upon the choice of learning algorithms [1, 8];
$\lambda$ is a regularizer and $g(w)$ is a regularization function (e.g., a
L2-norm). We assume $f_{i}$ is $(1/\gamma)$-smooth and 1-strongly convex of
$g$ and continuous differentiable to ensure convergence.

Solving FL problem with FedAvg [1]: The learning problem in (1) is solved
following a two-step approach in an iterative manner. Step 1: In the
$t^{\textrm{th}}$ update of the global iteration, a fraction of selected
devices $m$ iterates over its on-device training data $\mathcal{D}_{m}$ to
solve the local problem

$w^{(t)}_{m}=\underset{w_{m}\in\mathbb{R}^{d}}{\mathrm{arg\,min}}\
J_{m}(w_{m}|w^{(t-1)}),$ (2)

and communicates the parameters $w^{(t)}_{m}$ to MEC. Step 2:At the MEC, the
collected local parameters are simply aggregated as

$\displaystyle w^{(t+1)}=\sum\nolimits_{m=1}^{M}\frac{D_{m}}{D}\cdot
w^{(t)}_{m},$ (3)

and broadcast back to the fraction of participating devices for the next
global iteration. This process continues until a desired level of model
accuracy is achieved. We observe the MEC does not access the local data,
instead, it aggregates all of the received local model parameters, i.e.,
$w_{m},\forall m,$ to obtain the global model parameters (i.e., $w$) required
for the selected devices to solve the local problem in the next global
iteration. This approach of model aggregation imposes an equal value of
contribution to the selected local model parameters without considering its
consequences on the model performance; e.g. a deterioration due to poor local
updates. This eventually exerts larger communication rounds to converge to a
high-quality global model while alongside inducing irregularities in the
device-level performances.

###  II-A Device Selection in FL with Fairness Guarantees

We note that a plain FL [1] ignores the device-level performance, particularly
caused due to small data, limited computational capabilities and available
communication channels to share parameters with the server, or having devices
with poor local updates. Hence, the random device selection procedure may
incur costs in terms of overhead. While it is also significant to maintain
device-level performance, the cost overhead due to uncertainty in random
device selection should be minimized. Therein, we first develop a natural
extension to plain FL which captures the risk associated with the local
accuracy loss using model $w$ in each device $m$ as

$R^{(t)}_{m}(F)=\underset{\\{X^{m},Y^{m}\\}\sim\mathcal{P}_{m}}{\mathbb{E}}\Bigg{[}J(F(X^{m};w),Y^{m})\Bigg{]},$
(4)

where $\mathcal{P}_{m}$ is the underlying distribution of local data samples.
Here, we look forward to characterize a predictor $F$ that works well with
dataset in all associated devices. Basically, in a risk-averse FL setting, we
aim to minimize the maximum risk across all participating devices, ensuring
improved personalization and generalization performance of the trained model.
Subsequently, we formulate a min-max optimization problem: it jointly selects
the devices contributing the most in improving the model performance and
minimize the maximal risk to ensure fairness amongst these associated devices:

$\displaystyle{\textbf{P:}}\min_{w}\quad$
$\displaystyle\Bigg{[}\max_{\tilde{\mathcal{M}}:=\\{m\\}}\sum\nolimits_{m\in\tilde{\mathcal{M}}}\
R^{(t)}_{m}(F)\Bigg{]},$ (5) s.t. $\displaystyle
w\in\arg\min_{w\in\mathbb{R}^{d}}R_{m}^{(t)}(F_{m}),\quad\forall
m\in\tilde{\mathcal{M}},$ (6) $\displaystyle\quad
R_{m}^{(t)}(F_{m})\leq\theta_{m}^{\textrm{th}},\forall
m\in\tilde{\mathcal{M}},$ (7)
$\displaystyle\quad\tilde{\mathcal{M}}\subseteq\mathcal{M}.$ (8)

where $\tilde{\mathcal{M}}$ is a subset of devices selected based on their
local contribution to the global model and satisfying fairness constraint (7)
imposed as $\theta_{m}^{\textrm{th}}$, defined with details in Section III-A.
To solve P, we need to efficiently derive $\tilde{\mathcal{M}}$ in prior,
which is not straightforward. For that purpose, we use the primal-dual
decomposition method and capture the contribution of devices in terms of the
quality of obtained dual solution, that is defined in details in the following
Section III-A.

Next, we define and discuss the incurred time costs from the perspective of
random device selection procedure.

###  II-B Time cost

In each global iteration, the time cost for device $m$ has two components: (i)
local computation time: $t_{m}^{\textrm{comp}}=c_{m}D_{m}/f_{m}$, where
$c_{m}$ is CPU-cycles requirement to compute per bit data; $f_{m}$ is CPU-
cycle frequency; and (ii) communication time:
$t_{m}^{\textrm{comm}}=s_{m}/(r_{m}B_{m})$, where $s_{m}$ is the size of
transmitted data in bits; $r_{m}=\log_{2}(1+\frac{p_{m}h_{m}}{N_{0}B_{m}})$ is
the rate; $p_{m}$ is the transmission power; $h_{m}$ is the channel gain;
$N_{0}$ is the noise power spectral density and $B_{m}$ is the corresponding
bandwidth. Then, the corresponding execution time cost $t^{\textrm{exec}}$ per
global iteration due to random device scheduling is proportional to
$t^{\textrm{cost}}:=\underset{m}{\max}\\{t_{m}^{\textrm{comp}}+t_{m}^{\textrm{comm}}\\},\forall
m\in\mathcal{M}.$ This captures the fact that minimization of
$t_{\tau}^{\textrm{cost}}$ while ensuring fairness of the collaborative
training in solving P, there is a need for careful device selection
$\tilde{\mathcal{M}}$ and subsequent model aggregation.

In the following, we first review the risk minimization problem in P for a
known set of selected devices in a primal-dual setting. Then, we propose a
cost-efficient contribution-based device selection approach with fairness
guarantees by exploiting the modified TMC [7, 9] method to solve the
formulated problem in subsequent global iterations.

Algorithm 1 CDS: Contribution-based Device Selection

1: Input: $M$ is the number of devices in set $\mathcal{M}$; $C\in(0,1]$ is
fraction of random devices selected; $B$ is the local minibatch size; $E$ is
the number of epochs, and $\eta$ is the learning rate.

2: Initialize: $\phi^{1},C,B,E,\Delta t,\epsilon$ and $\eta$.//Exploration://

3: for all global iteration $t\in\\{1,2,\ldots,\tau\\}$ do

4: Set $\mathcal{S}_{t}\subseteq\mathcal{M}$ with $\max(1,C\times M)$ devices;

5: for all $m\in\mathcal{S}_{t}$ do

6: Execute DeviceUpdate($m,\phi^{t}$);

7: end for//Exploitation://

8: Start exploitation timer $t^{\prime}=0$;

9: while $t^{\prime}<\Delta t$ do

10: Define $\pi^{t^{\prime}}$ as random permutation of the selected devices;

11: Set $v^{t^{\prime}}_{0}=V(\emptyset)$;

12: for all $m\in\mathcal{S}_{t^{\prime}}$ do

13: if $|V(\phi^{t^{\prime}})-v^{t^{\prime}}_{m-1}|<\epsilon$ then

14: $v^{t^{\prime}}_{m}=v^{t^{\prime}}_{m-1}$;

15: else

16: Set $v^{t^{\prime}}_{m}\leftarrow
V(\\{\pi^{t^{\prime}}[1],\ldots,\pi^{t^{\prime}}[m]\\});$

17: end if

18:
$\beta_{\pi^{t^{\prime}}[m]}\leftarrow\frac{{t^{\prime}}-1}{{t^{\prime}}}\beta_{\pi^{{t^{\prime}}-1}[m]}+\frac{1}{{t^{\prime}}}(v^{t^{\prime}}_{m}-v^{t^{\prime}}_{m-1})$;

19: end for

20: Update $t^{\prime}=t^{\prime}+1$;

21: end while

22: Sort $\beta_{\pi^{t^{\prime}}[m]}$ in descending order;

23: Obtain $\tilde{\mathcal{M}}$ as per contributions
$\beta_{\pi^{t^{\prime}}[m]}$ and update global variable $\phi^{t}$ (13);

24: end forDeviceUpdate($m,\phi^{t}$):

25: Solve the local sub-problem (10);

26: Update dual variables using (12);

27: Return $\Delta\phi^{t}_{[m]},\forall m\in\mathcal{M};$

##  III Contribution-based Device Scheduling Algorithm

###  III-A Device’s local contribution in a distributed setting

We revisit the global problem (1) in its dual optimization form [10] with $M$
devices to evaluate their local contribution in solving the learning problem.
The corresponding dual optimization problem of (1) for a convex loss function
$f$ is

$\underset{\alpha\in\mathbb{R}^{D}}{\text{max}}\bm{\mathcal{R}}(\alpha):=\frac{1}{D}\sum\nolimits_{i=1}^{D}-f_{i}^{*}(-\alpha_{i})-\lambda
g^{*}(\phi(\alpha)),$ (9)

where $f_{i}^{*}$ and $g^{*}$ are the convex conjugates of $f_{i}$ and $g$,
respectively [10]; $\alpha\in\mathbb{R}^{D}$ is the dual variable mapping to
the primal candidate vector; and $\phi(\alpha)=\frac{1}{\lambda D}X\alpha$.
Here, we define $X\in\mathbb{R}^{d\times D_{m}}$ as a matrix with columns
having data points for $i\in\mathcal{D}_{m},\forall m$. Then, having the
optimal value of dual variable $\alpha^{*}$ in (9), we obtain the optimal
solution111Finding the optimal solution follows an iterative process to attain
a global accuracy $0\leq\epsilon\leq 1$ (i.e.,
$\mathbb{E}\left[\bm{\mathcal{R}}(\alpha)-\bm{\mathcal{R}}(\alpha^{*})\right]<\epsilon$).
of (1) as $w(\alpha^{*})=\nabla g^{*}(\phi(\alpha^{*}))$ [4]. Hereafter, we
use $\phi\in\mathbb{R}^{d}$ for $\phi{(\alpha)}$ for simplicity, and define a
weight vector $\varrho_{[m]}\in\mathbb{R}^{D}$ at the local sub-problem $m$
with its elements zero for the unavailable data points. As the consequence of
the properties of $f_{i}$ and $g$, we obtain the approximate solution to the
local sub-problem:

$\underset{\varrho_{[m]}\in\mathbb{R}^{D}}{\text{max}}\bm{\mathcal{R}}_{m}(\varrho_{[m]};\phi,\alpha_{[m]}),$
(10)

defined by the dual variables $\alpha_{[m]}$, $\varrho_{[m]}$. Here, we have
$\bm{\mathcal{R}}_{m}(\varrho_{[m]};\phi,\alpha_{[m]})=-\frac{1}{M}-\langle\nabla(\lambda
g^{*}(\phi(\alpha))),\varrho_{[m]}\rangle-\frac{\lambda}{2}\|\frac{1}{\lambda
D}X_{[m]}\varrho_{[m]}\|^{2}$ with $X_{[m]}$ as a matrix with columns having
data points for $i\in\mathcal{D}_{m}$, and zero padded otherwise. Each
selected device $m\in\mathcal{M}$ iterates over its computational resources
using any arbitrary solver to solve its local problem (10) for a defined local
relative $\theta_{m}^{\textrm{th}}$ accuracy, i.e., the maximal risk in P in
terms of fairness, that characterizes the quality of the local solution and
produces a random output $\varrho_{[m]}$ satisfying

$\mathbb{E}\left[\bm{\mathcal{R}}_{m}(\varrho^{*}_{[m]})-\bm{\mathcal{R}}_{m}(\varrho_{[m]})\right]\leq\theta_{m}^{\textrm{th}}\left[\bm{\mathcal{R}}_{m}(\varrho^{*}_{[m]})-\bm{\mathcal{R}}_{m}(0)\right].$
(11)

Then, the local dual variable is updated as follows:

$\alpha^{t+1}_{[m]}:=\alpha^{t}_{[m]}+\varrho^{t}_{[m]},\forall
m\in\mathcal{M}.$ (12)

The selected devices then broadcast the local parameter defined as
$\Delta\phi^{t}_{[m]}:=\frac{1}{\lambda D}X_{[m]}\varrho^{t}_{[m]}$ to the MEC
server along with its local relative accuracy, which completes the exploration
phase. Next, considering all selected devices contribute equally, which is the
usual case of FedAvg, the MEC server can simply aggregate the local parameters
as

$\phi^{t+1}:=\phi^{t}+\frac{1}{M}\sum\nolimits_{m=1}^{M}\Delta\phi^{t}_{[m]}.$
(13)

and share $\phi^{t+1}$ back to the randomly selected devices to again solve
(10). However, instantiating random device selection in each exploration phase
with the global model using FedAvg demerits local model performance,
particularly poor personalization and large variance in model accuracy across
devices. This is because the technique does not specifically consider the
actual contribution of each device in the model training, and tune parameters
accordingly to minimize the empirical risk at worse performing devices; this
leads to the increase of the number of communication rounds for convergence.
Therefore, we depart from the naive approach of model aggregation and
introduce an additional exploitation phase, where the contributions made by
selected devices are taken into consideration.

In the following, we present our proposed approach that utilizes the
contribution of each device within the exploration phase in improving the
model performance and lowering the long-term communication overhead.

###  III-B Contribution-based device selection with modified TMC

Within each round of global iteration that executes random device scheduling,
we first eliminate the frequency of transmitting the local dual variables
through an estimation of TMC at the MEC, leading to an efficient parameter
aggregation scheme. Specifically, following the value of contribution of each
selected device, we operate $\Delta t$ rounds of model averaging before
proceeding to the next global iteration with random device selection strategy.
We use the estimation of the contribution of each selected device
$m\in\mathcal{S}_{t}$ in round $t$ as

$\beta_{m}=\frac{1}{|\mathcal{S}_{t}|!}\sum\nolimits_{\pi\in\Pi(\Delta\phi^{t}_{[m]})}[V(P^{\pi}_{m}\cup\\{m\\})-V(P_{m}^{\pi})],$
(14)

where $V(\cdot)$ is the standard valuation of local parameter defined as its
performance score while contributing to improve the model accuracy.
$\pi\in\Pi(\Delta\phi^{t}_{[m]})$ characterizes the permutation of devices and
$P^{\pi}_{m}$ is the preceding devices selected for model aggregation. The
details are described in in Algorithm 1. Once the exploration phase is
executed, the MEC proceeds to exploitation phase (lines 8–21), where the
estimates of the contributions of each selected device in improving the model
performance is evaluated (lines 12–20). The devices are sorted based on their
contributions, after which the final model is obtained (line 23) to execute
the next round of exploration.

(a) Testing accuracy.

(b) Training loss.

(c) Device-level performance.

(d) Effect of $\Delta t$.

Figure 2: Comparative performance analysis with different sampling strategies
on: (a) testing accuracy, (b) training loss, (c) personalization, i.e., the
device-level performance, and (d) the impact of $\Delta t$ against adding more
local computations during local training.

##  IV Performance Evaluation

We have simulated the MEC environment with network parameters defined in [3]
and conducted extensive experiments with popular large-scale MNIST datasets
[11]. We have taken into account the statistical heterogeneity involving the
non-i.i.d. characteristics and unbalanced dataset, and setup devices data
accordingly [8]. We have considered $M=100$ devices on a single server with 26
core Intel Xeon 2.6 GHz, 256 GB RAM, 4 TB, Nvidia V100 GPU, Ubuntu OS.
Accordingly, we have normalized the time cost per global iteration and also
assumed that the devices and server are synchronized. We have then evaluated
the model performance by considering the impact of device selection strategy
during the model aggregation. For training, each device uses $E=10$ epochs,
the batch size $B=10$, and the learning rate $\eta=0.01$ as a default.
Further, in all of our evaluations, unless specified, we set the value of
$C=0.1$, which exhibits a good balance between computational efficiency and
convergence rate, as demonstrated experimentally in [1]. The default value of
$\Delta t$ is set to 1. We compare CDS against (a) two intuitive baselines: 1)
Random Sampling method which choose devices randomly, 2) Greedy Algorithm
[12], in which the server collects the local gradients of all devices and
chooses a subset of devices providing the greatest marginal gain, and (b) a
more competitive approach, namely FedFomo[13], customized for personalized
federated updates of each device.

Fig. 2(a) shows that that our proposed contribution-based device selection
approach achieves a high accuracy, approximately 97%, while using
substantially fewer communication rounds compared to the Greedy and Random
Sampling algorithms. This is due to the fact that we are strategically
selecting device updates based on their contribution in improving the model
performance during model aggregation. This is further supported by Table I,
where we present a comparative analysis on the execution time cost
$t^{\textrm{exec}}$ in achieving around $80\%$ of the target model accuracy
and the required number of communication rounds. In all cases, we see CDS
demonstrates better and stable performance than these baselines, and a
competitive model accuracy as compared with FedFomo. Similar observations
pertain to the training loss of different sampling strategies, as shown in
Fig. 2(b). In Fig. 2(c), we evaluate and compare the average device-level
performance, i.e., personalization of the trained model. Interestingly, we see
that CDS provides improvement in the device-level performance: $6.54\%$ and
$4.78\%$ higher than Greedy method and Random sampling, respectively, as well
as $2.54\%$ compared to FedFomo. This is due to the appropriateness of the
local updates that are aggregate in the model following the contributions of
the selected devices. Furthermore, Random Sampling shows better performance in
terms of personalization compared to the Greedy. This is reasonable as it
explores the available devices to improve personalization, while the Greedy
approach focuses only on improving the performance of the global model.

Finally, in Fig. 2(d), we analyze the significance of $\Delta t$ on
eliminating the time cost required for the model convergence to a target
accuracy. The insight is that, instead of adding more computation per device
to lower the communication overhead [1], we perform contribution-based model
aggregation that compensates the increase in local computation costs and the
resulting higher $t^{\textrm{cost}}$ for achieving better convergence.
Specifically, relaxing $\Delta t$ allows more rounds of random permutation to
explore the contribution of local model updates. In return, having broader
exposure of the contributing devices results in better device selection
strategy for model aggregation and a better model performance as shown in Fig.
2(d), while saving local computations (epoch) at the devices. We also observe
the impact of relaxing $\Delta t$ as a reference to evaluate and compare model
performance against adding more local computations. For example, when $E=40$,
we see no significant improvement in the model performance even though we
increase $\Delta t$ by more than $3$ rounds, which is due to the optimized
device selection strategy.

TABLE I: Comparison of execution time cost $t^{\textrm{exec}}$ (in $sec$). Algorithms |  | Average time to achieve accuracy of
---
80%, and number rounds to achieve
Average $t^{\textrm{exec}}$ | Number of rounds
Random Sampling [1] | 0.521664 | 5$\pm$1
Greedy-based solution[12] | 1.768358 | 9$\pm$1
FedFomo[13] | 0.338333 | 2$\pm$1
CDS - Our proposed | 0.335492 | 2$\pm$1

##  V Conclusion

We have presented a simplified solution of the device selection problem in
Federated Learning (FL), aiming to jointly improve model performance and lower
the communication costs. In doing so, we have first formulated a min-max
optimization problem. to solve it, we have developed a strategy that
constitutes a mixture of exploration phase, where random selection of devices
is made, similar to the plain FL approach but under a primal-dual setting of
the learning problem, and an additional exploitation scheme that quantifies
the contribution of selected devices in improving the model performance via
efficient model aggregation. Extensive simulations on real-world dataset have
demonstrated the efficacy of the proposed approach against the baselines in
improving model performance, i.e., better generalization and personalization,
lowering communication costs, and achieving fast convergence rate.

## Acknowledgment

This paper was supported in part by the Villum Investigator Grant ”WATER” from
the Velux Foundations, Denmark.

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in International Conference on Artificial Intelligence and Statistics (AISTATS), Fort Lauderdale, FL, USA, April 2017.
  * [2] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al., “Advances and open problems in federated learning,” Foundations and Trends in Machine Learning, vol. 14, no. 1–2, pp. 1–210, 2021.
  * [3] T. Nishio and R. Yonetani, “Client selection for federated learning with heterogeneous resources in mobile edge,” in IEEE International Conference on Communications (ICC), Shanghai, China, May 2019.
  * [4] S. R. Pandey, N. H. Tran, M. Bennis, Y. K. Tun, A. Manzoor, and C. S. Hong, “A crowdsourcing framework for on-device federated learning,” IEEE Transactions on Wireless Communications, vol. 19, no. 5, pp. 3241–3256, Feb. 2020.
  * [5] N. Yoshida, T. Nishio, M. Morikura, and K. Yamamoto, “Mab-based client selection for federated learning with uncertain resources in mobile networks,” in IEEE Globecom Workshops (GC Wkshps), Taipei, Taiwan, Dec. 2020.
  * [6] W. Xia, T. Q. Quek, K. Guo, W. Wen, H. H. Yang, and H. Zhu, “Multi-armed bandit-based client scheduling for federated learning,” IEEE Transactions on Wireless Communications, vol. 19, no. 11, pp. 7108–7123, July 2020.
  * [7] R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos, “Towards efficient data valuation based on the shapley value,” in International Conference on Artificial Intelligence and Statistics (AISTATS), Naha, Okinawa, Japan, April 2019.
  * [8] S. R. Pandey, M. N. Nguyen, T. N. Dang, N. H. Tran, K. Thar, Z. Han, and C. S. Hong, “Edge-assisted democratized learning toward federated analytics,” IEEE Internet of Things Journal, vol. 9, no. 1, pp. 572–588, June 2021\.
  * [9] L. D. Nguyen, S. R. Pandey, B. Soret, A. Broering, and P. Popovski, “A marketplace for trading ai models based on blockchain and incentives for iot data,” arXiv preprint arXiv:2112.02870, 2021.
  * [10] S. Boyd, S. P. Boyd, and L. Vandenberghe, Convex optimization.  Cambridge university press, March 2004.
  * [11] “Mnist handwritten digit database, yann lecun, corinna cortes and chris burges.” http://yann.lecun.com/exdb/mnist/.  (Accessed on 03/02/2022).
  * [12] R. Balakrishnan, T. Li, T. Zhou, N. Himayat, V. Smith, and J. Bilmes, “Diverse client selection for federated learning: Submodularity and convergence analysis,” in International Conference on Machine Learning Society (ICML), July 2021.
  * [13] M. Zhang, K. Sapra, S. Fidler, S. Yeung, and J. M. Alvarez, “Personalized federated learning with first order model optimization,” in International Conference on Learning Representations (ICLR), Vienna, Austria, May 2021.