# Advanced Optimization Techniques for Federated Learning on Non-IID Data
## 2 Background
### FedAvg Algorithm  
In Federated Learning (FL), a key component is the aggregation of model parameters from the clients into a unified, centrally managed model. The aggregation process must ensure that the combined parameters do not negatively impact the model's accuracy. The Federated Averaging (FedAvg) algorithm is perhaps the most widely known aggregation algorithm, which computes the weighted average of local model updates based on the sizes of the clients' datasets [2]. Federated Stochastic Gradient Descent (FedSGD) is the fundamental approach to model training in FL, which aims to minimize a loss function across data distributed across multiple clients without the need for centralized data collection. Let the loss function \(L(w;x,y)\) represent the loss over data \((x,y)\) with parameters \(w\in R^{d}\). The goal of training is to find the optimal parameters \(w^{*}\) that minimize the global objective:  
\[w^{*}=\arg min_{w}\frac{1}{N}\sum_{i=1}^{N}L(w;x_{i},y_{i})\]  
where \(N\) is the total number of clients. During a training round, a predetermined number of clients \(m\) update their local models using distributed global parameters. These local updates are then sent back to the central server, which computes the average of the gradient updates to update the global model as follows:  
\[w_{t}\gets w_{t-1}-\alpha\frac{1}{m}\sum_{i=1}^{m}\
abla L(w_{t-1};x_{i},y_{i})\]where \(\alpha\) is the learning rate. In FedSGD, only one local update is performed per round, which can limit communication overhead but also affects training performance depending on the heterogeneity and quality of local data [27]. Federated Averaging (FedAvg) builds on FedSGD by optimizing model performance through progressively improving accuracy and reducing communication costs while keeping the data secure and private on each local device. FedAvg allows for multiple computations per client in each round, as clients perform several iterations (epochs) on their local data before aggregation. The main parameters of FedAvg include the fraction of clients \(C\) participating in each round, the number of local passes over the data (epochs) \(E\) performed by each client in each round, and the local mini-batch size \(B\) used for client updates. Additionally, the learning rate \(\eta\) and, in some cases, a learning rate decay term \(\lambda\) may be introduced [28]. The FedAvg algorithm proceeds as follows: The global model is initialized randomly. In each communication round, the server randomly selects a subset of clients \(S_{t}\), where \(|S_{t}|=C\times K\geq 1\), to participate in training and distributes the current global model \(w_{t}\) to all clients in \(S_{t}\). Each client partitions its local data into batches of size \(B\) and performs \(E\) local epochs of training, applying gradient descent on the current model using its local data. The clients send their trained local models \(w_{t+1}^{k}\) back to the server, which then creates a new global model \(w_{t+1}\) by computing a weighted sum of all the received local models:  
\[w_{t+1}\leftarrow\sum_{k=1}^{K}\frac{n_{k}}{n}w_{t+1}^{k}\]  
where \(n_{k}\) is the number of local data points on client \(k\) and \(n\) is the total number of data points across all clients. This process continues iteratively until convergence. The detailed steps that the Federated Averaging (FedAvg) method follows, are given in Algorithm 1.