# FedCO: Communication-Efficient Federated Learning via Clustering Optimization +
## 3 Preliminaries and Definitions
### Problem Description  
In this work, we mainly concentrate on synchronous Federated Learning algorithms. A Federated Learning system consists of a global model \(\mathcal{M}\) and a set of workers \(W\). At each communication round \(t\), the server deploys the current model \(\mathcal{M}_{t}\) to a subset of workers \(W_{t}\subset W\) that dynamically participate in the global aggregation at round \(t\). Each worker \(w_{i}\in W_{t}\) locally keeps its personal data \(\mathcal{D}_{i}=\{x_{ij}\}_{j=1}^{n_{i}}\) (\(j=1,2,\dots,n_{i}\)), where \(x_{ij}\) is the \(j\)th training sample in \(\mathcal{D}_{i}\). The size of the local dataset \(\mathcal{D}_{i}\) varies with different real-world applications.  
In standard centralized Stochastic Gradient Descent (SGD), the local updates of each \(w_{i}\) are calculated according to Equation (1) to optimize \(\mathcal{M}_{t}^{i}\), where \(\eta\) is the learning rate and \(g_{t}^{i}\) refers to the gradients computed:  
\[\mathcal{M}_{t+1}^{i}=\mathcal{M}_{t}^{i}-\eta g_{t}^{i}. \tag{1}\]  
Then, each worker \(w_{i}\) sends the local model changes \(\mathcal{M}_{t+1}^{i}\) to the central server after the number of \(E\) local step, where \(p_{i}\) is the relative weight of worker \(w_{i}\), and the global model is computed by applying Equation (2):  
\[\mathcal{M}_{t+1}=\mathcal{M}_{t}+\frac{\sum_{w_{i}\in W_{t}}p_{i} \mathcal{M}_{t+1}^{i}}{\sum_{w_{i}\in W_{t}}p_{i}}. \tag{2}\]  
These are iterated until a certain stop criterion is met.  
The corresponding local loss function of \(\mathcal{M}^{i}\) of each worker \(w_{i}\) is defined as  
\[F_{i}(\mathcal{M}^{i})=\frac{1}{|\mathcal{D}_{i}|}\sum_{x_{ij}\in \mathcal{D}_{i}}f(\mathcal{M}^{i},x_{ij}), \tag{3}\]  
where \(f(\mathcal{M}^{i},x_{ij})\) is the loss function for data point \(x_{ij}\) using (1). Each worker \(w_{i}\) independently updates the model over its own data \(\mathcal{D}_{i}\) to optimize its local loss function \(F_{i}(\mathcal{M}^{i})\). The aim of improving the communication efficiency of Federated Learning is to minimize the cost of sending \(\mathcal{M}_{t}^{i}\) to a central server while learning from the data distributed over a large number of decentralized edge devices. Similarly, the global loss function on all the distributed datasets is defined as:  
\[F(\mathcal{M})=\frac{1}{|\ W|}\sum_{w_{i}\in W_{t}}F_{i}(\mathcal{M}^{i}), \tag{4}\]  
where \(\mathcal{M}\) is the aggregated global model, and the overall goal is to decrease the global loss function \(F(\mathcal{M})\), namely,  
\[\mathcal{M}^{*}=\arg\min F(\mathcal{M})\cdot \tag{5}\]Other issues related to Federated Learning problems, such as system heterogeneity or privacy, are beyond the scope of this paper. Specifically, the proposed FedCO algorithm does not account for heterogeneity, which for example could affect the selection of workers that have enough power to transmit the model parameters. In the worst case, heterogeneity could increase the convergence time or reduce the accuracy, if for example, workers that achieve a higher accuracy cannot be selected because they have short battery lifetimes.