# Rebirth of Distributed AI--A Review of eHealth Research
## 5 Federated Learning Tutorial
### Federated Averaging (FedAvg)  
The traditional objective of training a dataset in machine learning is to minimize the loss function of predicting an input. Let say for a dataset containing n samples (\(x_{i},y_{i}\), \(1\leq i\leq n\)). Given sample input \(x_{i}\), the model should predict \(y_{i}\) using a set of parameters \(w\). While \(y_{i}\) is an estimated value, \(f_{i}(w)\) measures how far this estimated value is from its true value. The less \(f_{i}(w)\) is, the more confident the model is. For the whole dataset, the loss function \(f(w)\) for a model is the average of error prediction for each input. The objective is to minimize the error, hence the loss function is as presented below:  
\[\min_{w}f(w)\quad\text{ where }\quad f(w)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(w)\]  
Stochastic Gradient Descent (SGD) is widely used to optimize this objective. Through random mini batches of the dataset for a client \(k\), and iteratively, SGD keeps optimizing the objective by updating the value of \(w\) in small steps, as presented below:  
\[w_{t+1}\gets w_{t}-\eta\
abla f(w_{t};x_{k},y_{k})\]  
The new set of \(w\) at iteration t+1 should bring us closer to the targeted minimum value of the loss function, than what it was at iteration t. While \(\
abla f(w_{t};x_{k},y_{k})\) is the amount of movement or change at each iteration, \(\eta\) is the learning rate which is a tuning parameter that determines the step size at each iteration while moving toward a minimum of a loss function. The distributed (federated) variant of SGD is called FedSGD. In FedSGD, the data is distributed across different clients, and each performs one and only one round of local computation before sending the result to the server. FedSDG is the baseline of the FedAvg. FedAvg is the standard vanilla-flavor algorithm used in the federated learning process. FedAvg differs from FedSGD in some points. First, in FedSGD a single batch gradient calculation (on a randomly selected client) is performed per round of communication, while in FedAvg clients can perform multiple gradient calculations (epochs) before sending the results to the server. Moreover, the FedSGD approach is computationally efficient but requires very large numbers of rounds of training to produce acceptable models. On the other hand, convergence in FedAvg is not guaranteed. This is because the FedAvg client does not send gradients, as is the case in FedSGD, but rather an updated model. The averaging of gradients guarantees convergence, while the averaging of the model cannot. In terms of communication, gradient averaging is a heavier consumer due to the single round per gradient Algorithm 1 presents the Federated Averaging algorithm. ```
1:Initialization: global model \(w_{0}\). 2:for each global epoch \(t\in{1,\dots,epoch}\)do
3:# Determine the number of participants. 4:\(m\gets max(C\cdot N,1)\)
5:# Randomly choose participants. 6:\(S_{p}=RandomChoice(S,m)\)
7:for all each client \(k\in S_{p}\)doin parallel
8:# Get clients updated model. 9:\(w_{t+1}^{k}\gets OnClientUpdate(k,w_{t})\)
10:endfor
11:# Update global model. 12:\(w_{t+1}\leftarrow\sum_{k=0}^{N}p_{k}w_{t+1}^{k}\)
13:endfor OnClientUpdate\((k,w_{0})\) :
14:for each client epoch do
15:# Do local model training on local dataset. 16:\(w_{e+1}\gets w_{e}-\eta\
abla F(w_{e})\)
17:endfor
18:return\(w_{e+1}\)
```  
**Algorithm 1** Federated Averaging. In the cluster there are \(N\) clients in total, each with a learning rate of \(\eta\). The set containing all clients is denoted as \(S\), the communication interval is denoted as \(E\), and the fraction of clients is denoted as \(C\)  
Notice the following:  
* FedAvg gives more weight \(p_{k}\) to devices with larger datasets
* Each client is required to do the same number of local epochs. Compared to existing distributed learning schemes, FL is distinguished by several key aspects, explained in [6] as follows:  
* Data are heterogeneous and must be assumed to be non-identical, independent (non-i.i.d).