When Do Curricula Work in Federated Learning?

In this section, we investigate five scoring functions. As discussed earlier, in standard centralized training, samples are scored using the loss value of an expert pre-trained model. Given a pre-trained model $f_{\theta}:\mathcal{X}\to\mathcal{Y}$, the score is defined as $s_{i}(x_{i})=\frac{r_{i}}{\sum_{i}r_{i}}$, where $r_{i}=\frac{1}{{\mathcal{L}}(y_{i},f_{\theta}(x_{i}))}$, with ${\mathcal{L}}$ being the inference loss. In this setup, a higher score corresponds to an easier sample.

In FL [mcmahan2017communication, Vahidian-federated-2021], a trusted server broadcasts a single initial global model, $\theta_{g}$, to a random subset of selected clients in each round. The model is optimized in a decentralized fashion by multiple clients who perform some steps of SGD updates $(\theta_{k}=\theta_{g}-\eta\nabla\mathcal{L}_{k})$. The resulting model is then sent back to the server, ultimately converging to a joint representative model. With that in mind, in our setting, the scores can be obtained by clients either via the global model that they receive from the server, which we name as $s_{G}$ or by their own updated local model, named as $s_{L}$ or the score can be determined based on the average of the local and global model loss, named as $s_{LG}$¹¹1Since it produces very similar results to $s_{G}$, we skipped it..

We further consider another family of scoring that is based on ground truth class prediction. In particular, in each round, clients receive the global model from the server and get the prediction using the received global model and the current local model as $\hat{y}_{G}$ and $\hat{y}_{L}$, respectively. For those samples whose $\hat{y}_{L}$ and $\hat{y}_{G}$ do not match, the client tags them as hard samples and otherwise as easy ones. This scoring method is called $s_{LG}^{pred}$. Further, ground truth class prediction and scoring can be solely done by the global model or the client’s local model, which end up with two other different scoring methods, namely  $s_{G}^{pred}$, and $s_{L}^{pred}$ respectively. This procedure is described in Algorithm 1.

Fig. 1 demonstrates what the impact of using these various scoring methods is on the global accuracy when curriculum, anti-curriculum, or random ordering is exploited by the clients in the order in which their CIFAR-10 examples are learned with FedAvg under IID and Non-IID (2) data partitions. The results are obtained by averaging over three randomly initialized trials and calculating the standard deviation (std).

The results reveal that first, the scoring functions are producing broadly consistent results except for $s_{L}^{pred}$ for both IID and Non-IID and $s_{L}$ for Non-IID settings. $s_{G}$ provides the most accurate scores, thereby improving the accuracy by a noticeable margin compared to its peers. This is quite expected, as the global model is more mature compared to the client model, second, the curriculum learning improves the accuracy results consistently across different scoring functions, third, curriculum learning is more effective when the clients underlying data distributions are Non-IID. To ensure that the latter does not occur by chance, we will delve into this point in detail in subsection 3.3. Due to the superiority of $s_{G}$ relative to others, we set the scoring function to be $s_{G}$ henceforth. We will further elaborate on the precision of $s_{G}$ compared to an expert model in Section LABEL:expert-G-compare.

In order to study the effect of different families of pacing functions along with the hyperparameters $\lambda=(a,b)$, we test the exponential, step, linear, quadratic, and root function families. We further first fix $b$ to $0.2$ and let $a\in\{0.1,0.5,0.8\}$²²2Note that $b\in[0,1]$. Also, $a=0$ or $b=1$ is equivalent to no ordered training, i.e., standard training.. The accuracy results are presented in Fig. 2. It is noteworthy that the complement of this figure for Non-IID is presented in Fig. LABEL:pacing-a-cifar10-iid-ordering in the SM. As is evident, for all pacing function families, the trends between the curriculum and the other orderings, i.e., (anti, random)-curriculum are markedly opposite in how they improve/degrade by sweeping $a$ from small values to large ones. The pattern for Non-IID which presented in the SM is almost similar to that of IID. Values of $a\in[0.5,0.8]$ produce the best results. As can be seen from Fig. 2, the best accuracy achieved by curriculum learning outperforms the best accuracy obtained by other orderings by a large margin. For example, in the “linear” pacing function, the best accuracy achieved for curriculum learning when $a=0.8$ is $56.60\pm 0.91$ which improved the vanilla results by $4\%$ while that of random when $a=0.1$ is $52.73\pm 0.81$ and improved vanilla by $0.5\%$. Henceforth, we set $a=0.8$ and the pacing function to linear. After selecting the pacing function and $a$ the final step is to fix these two and see the impact of $b$. Now we let all curricula use the linear pacing functions with a = 0.8 and only sweep $b\in\{0.0025,0.1,0.2,0.5,0.8\}$ and report the results in Fig. 3. Perhaps most striking is that curriculum learning tends to have smaller values of $b$ to improve accuracy, which is in contrast with (random-/anti) orderings. The performance of anti-curriculum shows a significant dependence on the value of $b$. Further, curriculum learning provides a robust benefit for different values of $b$ and it beats the vanilla FedAvg by $4-7\%$ depending upon the distribution of the data. Henceforth, we fix $b$ to $0.2$.

Equipped with the ingredients explained in the preceding section, we are now in a position to investigate the significant benefits of employing curriculum learning in FL when the data distribution environment is more heterogeneous. To ensure a reliable finding, we investigate the impact of heterogeneity in four baselines through extensive experiments on benchmark datasets, i.e., CIFAR-10, CIFAR-100, and FMNIST. In particular, we distribute the data between clients according to Non-IID Dir$(\beta)$ defined in [li2021federated]. In Dir$(\beta)$, heterogeneity can be controlled by the parameter $\beta$ of the Dirichlet distribution. Specifically, when $\beta\to\infty$ the clients’ data partitions become IID, and when $\beta\to 0$ they become extremely Non-IID.

To understand the relationship between the ordering-based learning and the level of statistical data heterogeneity, we ran all baselines for different Dirichlet distribution $\beta$ values $\beta\in\{0.05,0.2,0.9\}$.  The accuracy results of different baselines on CIFAR-10 while employing (anti-) curriculum, or random learning with linear pacing functions $(0.8,0.2)$ and using $s_{G}$ are presented in Tables 1, 2, 3, and 4. For the comprehensiveness of the study, we will present results for CIFAR-100 respectively in Section LABEL:cifar-100-effect-of-level-hetero of the SM.

The results are surprising: The benefits of ordered learning are more prominent with increased data heterogeneity. The greater the distribution discrepancy between clients, the greater the benefit to curriculum learning.

If we consider client heterogeneity as distributional skew[zhu2021federated], then this is logical: easier data samples are those with overall lower variance, both unbiased and skew from the mean, and thus the total collection of CL-easier data samples in a dataset is more IID than the alternative. Thus, in the crucial early phases of training, the training behaves closer to FedAvg/FedProx/SCAFFOLD/FedNova under IID distributions. Therefore, CL can alleviate the drastic accuracy drop when clients’ decentralized data are statistically heterogeneous, which comes from stable training from IID samples to Non-IID ones, fundamentally improving the accuracy. This is formalized with quantitative convergence rates in the Section LABEL:analysis-main-paper of the main paper and in Section LABEL:sec:analysis of the SM.

In the real world, the distributed dataset used in FL is often generated in-situ by clients, and the data is measured/generated using a particular sensor belonging to the client. For example, consider the case of a distributed image dataset generated by smartphone users using the onboard camera or a distributed medical imaging dataset generated by hospitals with their in-house imaging systems. In such scenarios, as there is a huge variety in the make and quality of the imaging sensors, the data generated by the clients is uniquely biased by the idiosyncrasies of the sensor, such as the noise, distortions, quality, etc. This introduces variability in the quality of the data at clients, in addition to the Non-IID nature of the data. However, it is interesting to note that these effects apply consistently across all the data at the specific client.

From a curriculum point of view, as the data points are scored and ordered by difficulty, which is just a function of the loss value of that data point, these idiosyncratic distortions uniformly affect the loss/difficulty value of all the data at that particular client. Also, it is possible that the difficulty among the data points at the particular client is fairly consistent as the level of noise, quality of the sensor, etc. are the same across the data points. This bias in difficulty varies between clients but is often constant within the same client. Naturally, this introduces a heterogeneity in the clients participating in the federation. In general, this can be thought of as some clients being ”easy” and some being ”difficult”. We can quantify this notion of consistency in difficulty by the standard deviation in the score of the data points at the client.

When the standard deviation of the intra-client data is low, i.e., when the difficulty of the data within a client is consistent, we find that the curriculum on FL behaves very differently in these kinds of scenarios. We observe the advantage of curriculum diminishes significantly and has similar efficacy as that of random curricula as shown in Fig 4. The advantage of curriculum can be defined as $A_{o}=accuracy(o)-accuracy(vanilla)$, where $o\in\{curr,anti,rand\}$.

We propose to extend the ideas of curriculum onto the set of clients, in an attempt to leverage the heterogeneity in the clients. To the best of our knowledge, our paper is the first attempt to introduce the idea of curriculum on clients in an FL setting. Many curricula ideas can be neatly extended to apply to the set of clients. In order to define a curriculum over the clients, we need to define a scoring function, a pacing function, and an ordering over the scores. We define the client loss as the mean loss of the local data points at the client (Eq. 1), and the client score can be thought of as inversely proportional to the loss. The ordering is defined over the client scores.

The pacing function, as in the case of data curricula, is used to pace the number of clients participating in the federation. Starting from a small value, the pacing function gradually increases the number of clients participating in the federation. The action of the pacing function amounts to scaling the participation rate of the clients.

The clients are scored and rank-ordered based on the choice of ordering, then a subset of size $K^{(t)}$ of the $K$ clients is chosen in a rank-ordered fashion. The value $K^{(t)}$ is prescribed by the pacing function. The $K^{(t)}$ clients are randomly batched into mini-batches of clients. These mini-batches of clients subsequently participate in the federation process. Thereby, we have two sets of curricula, one that acts locally on the client data and the other that acts on the set of clients. Henceforth we will refer to these as the data curriculum and the client curriculum, respectively. We study the interplay of these curricula in Section LABEL:sec:ablation_study.

Fig. 5 confirms that the benefits of the algorithm severely depend on the data of the client having a diverse set of difficulties. As is evident from Fig. 5, we are able to realize an $A_{curr}$ of $5.67-7.19$% for the different values of Non-IIDness using our proposed client curriculum algorithm in the scenario with high consistency in the client data where the data curriculum has reduced/no benefits. This illustrates that the client curriculum is able to effectively overcome the limiting constraint of local variability in data and is able to leverage the heterogeneity in the set of clients to its benefit.

For the experiments in this section, we require client datasets ($\mathbb{D}_{m}$) of varying difficulty at the desired level of Non-IIDness. In order to construct partitions of varying difficulty, we need to address two key challenges: one, we need a way to accurately assess the difficulty of each of the data points, and two, we need to be able to work with different levels of Non-IIDness. To address the first challenge, we rank the data points in order of difficulty using an a priori trained expert model $\theta_{\mathcal{E}}$ that was trained on the entire baseline dataset and has the same network topology as the global model. As the expert model has the same topology as the model that we intend to train and as it is trained on the entire dataset, it is an accurate judge of the difficulty of the data points. Interestingly, this idea can be extended to be used as a scoring method for curriculum as well. We call this scoring method the expert scoring $s_{E}$. We look at this in greater detail in Section LABEL:expert-G-compare.

To address the second challenge, a possible solution is to first partition the standard dataset into the desired Non-IID partitions using well-known techniques such as the Dirichlet distribution, followed by adding different levels of noise to the samples of the different data partitions. This would partition with varying difficulty; however, doing so would alter the standard baseline dataset, and we would lose the ability to compare the results to known baseline values and between different settings. We would like to be able to compare our performance results with standard baselines, so we require a method that does not alter the data or resort to data augmentation techniques, and we devise a technique that does just that.

Starting with the baseline dataset, we first divide it into the desired Non-IID partitions the same as before, but then instead of adding noise to the dataset, we attempt to reshuffle the data among partitions in such a way that we create ”easy” partitions and ”hard” partitions. This can be achieved by ordering the data in increasing order of difficulty and distributing the data among the partitions starting from the ”easy” data points, all the while honoring the Non-IID class counts of each of the partitions as determined by the Non-IID distribution. The outline is detailed in Algorithm 2. It is noteworthy that, although we are able to generate partitions of varying difficulty, we do not have direct control over the ”difficulty” of each of the partitions and hence cannot generate partitions with an arbitrary distribution of difficulty as can be done by adding noise.