Are We in (A)Sync?: Guidance for Efficient Federated Learning

We truly appreciate your thoughtful comments and valuable suggestions. Our responses are as follows:

Comment 1: Meaning of $f(T,c,i)$ and its relevance with respect to $k$

Thank you very much for your detailed question on our formulation. Your understanding is correct: if the client $i$ participated in asyncFL for $B_i$ time while the whole training process takes time $A$, then $f(T,c,i) = \frac{B_i}{A}$.

We would like to confirm that when $T = \{t_1, t_2\}$, $f(T,2,1) = f(T,2,2) = 1$ is correct, $f(T,2,1)$ and $f(T,2,2)$ indicates the portion of time which client 1 and client 2 each participated in asyncFL when concurrency value $c = 2$. As concurrency $= 2$ when the total number of clients $= 2$, client 1 and client 2 should continuously participate in asyncFL during the whole process to satisfy the concurrency parameter, which makes $f(T,2,1) = f(T,2,2) = 1$. We assume the time required for the server to aggregate updates and to sample new clients are zero for simplicity.

Moreover, $f(T,c,i)$ might depend on $k$ if a client is restricted to contributing more than once to the global model updates, a situation that occurs when $k$ client updates are buffered. However, our formulation is constructed without such restriction, making $k$ irrelevant to $f(T,c,i)$.

We will ensure to present the above in our revised manuscript, providing more details on the assumptions we made and clarifying the explanation of our formulation.

Comment 2: Inaccurate expression of terminologies

Thank you for pointing out this oversight. You are correct in noting that Eq. (4) does not precisely calculate the expected number of updates by other clients while client i is training and communicating. However, it offers a close approximation, as evidenced by our formulation based on Eq. (4), which closely predicts the actual time and resource usage observed in FL experiments. This is further supported by our delay prediction results directly derived from Eq. (4), as mentioned below in comment 4. We recognize the need to clarify this in our manuscript and either plan to revise Eq. (4) or explicitly state its approximate nature in the updated version.

Comment 3: Treating discrete variables as continuous variables

Thank you for bringing this to our attention. The number of updates and the delays (staleness) we mentioned in Section 3 are all expected values. We will ensure to update our inaccurate notations regarding the continuous or discrete nature of variables in our updated manuscript.

Comment 4 (Question): Comparison on formulated delay prediction and actual value

Thank you for your suggestion. We conducted a delay prediction based on the equation above Eq. (5), by comparing it with the actual delay values from the experiment on the FEMNIST dataset as follows:

The results indicate that our formulation aligns closely with the actual delay values observed in the FL experiment. However, we observed an increasing discrepancy at higher concurrency levels, likely stemming from the errors in Eq. (4) addressed in comment 2. We expect such an error to decrease as we suggest an accurate formulation for Eq. (4). In our revised manuscript, we plan to include results on delay prediction across all datasets used in our study.

We greatly appreciate your thoughtful comments and feedback. Our replies are as follows:

Comment 1: Formulation not considering training, loss functions, or data heterogeneity

Thank you for highlighting an important aspect to consider regarding our formulation. Incorporating model convergence, training specific, and data characteristics would yield more theoretically precise results. However, we instead approached formulating with an assumption that syncFL and asyncFL achieve the target accuracy after p global model updates. Our empirical results in Section 6 demonstrate that this simplified formulation also effectively predicts the actual values observed in FL runs across five datasets spanning vision and NLP domains that involve up to 21,876 clients. We plan to improve our theoretical formulation based on the elements you mentioned as a future work.

Comment 2: Experiments considering IID data distribution only

Thank you for emphasizing the importance of non-IID data distribution in federated learning. In our experiments, while we allocated IID data to clients within the CIFAR-10 dataset, the other four datasets (FEMNIST, CelebA, Shakespeare, Sent140) employed were distinctly non-IID. We utilized these four datasets in their original form, as provided by the LEAF federated learning framework [1], where they inherently exhibit non-IID characteristics with heterogeneous data quantity and class distributions.

In our revised manuscript, we will include details on non-IID characteristics of experimented datasets.

Comment 3: Meaning of proposed formulation compared to other algorithms

We interpreted your comment (item 3 under weaknesses) as about the experimental results shown in Figures 3c and 3d and have responded accordingly below. If your comment was about a different aspect, please inform us.

We built our formulation on the prevalent syncFL and asyncFL algorithms (FedAvg and FedBuff). In experiments on Figures 3c and 3d, we aimed to assess whether our formulation provides insight into the time and resource usage when other widely used FL optimization algorithms are applied, such as FedProx, FedYogi, and FedAdagrad. Our results indicate that employing our formulation with these algorithms may increase the prediction error. Still, the general trend in time and resource usage over different concurrency parameters remains consistent between the formulation and other FL algorithms.

We empirically showed our formulation’s applicability in predicting time and resource usage trends over different concurrency parameters. This could potentially assist FL practitioners in choosing the most suitable approach (asyncFL / syncFL) or parameter for different FL algorithms.

[1] Caldas, Sebastian, et al. "Leaf: A benchmark for federated settings." arXiv preprint arXiv:1812.01097 (2018).

Thanks for your respones, I decide to keep my scores based on following comments:

1. The analysis considering training, loss functions, or data heterogeneity is important.
2. I checked the revision, the details of the dataset partition are not provided.

Thank you very much again for your valuable feedback.

We fully acknowledge the importance of considering training, loss functions, and data heterogeneity in our research. While we regret not including these in the current discussion due to time constraints, we would like to stress that our simplified formulation accurately predicts the actual values observed in FL executions.

In the paper, we added an explanation that four out of five used datasets were non-IID as originally provided by LEAF. We opted not to include extensive details of the dataset in our paper, as the datasets we used are well-established in the field and the details are covered in prior literature.

We are deeply grateful for your thoughtful comments and feedback. In our revised manuscript, we intend to address these points as follows:

Comment 1: Lack of comparison with state-of-the-art approaches

We appreciate your question regarding the comparison with state-of-the-art approaches. To our knowledge, no existing literature proposes to predict the relative time or resource usage between syncFL and asyncFL. Thus, we could only compare with a basic baseline, “Updates-$N$,” which predicts after observing the metrics for $N$ rounds. In our revised manuscript, we plan to introduce an additional baseline that predicts based on the observed metrics from initial FL runs reaching a low target accuracy (e.g., 10%). Please note that these baseline methods require sample FL runs for each configuration to make predictions, whereas our formulation uniquely predicts the metrics without requiring any FL runs.

Comment 2: Resource usage in FL is over-simplified

Thank you for questioning our abstraction of resource usage as the cumulative time for on-device training and model weight communication. We acknowledge the variety of resources in real-world FL systems and the value of examining each type separately. Although capable of presenting our resource usage formulation for each type, we opted for a time-based abstraction to simplify our prediction experiments on actual values. The time units metric is proportional to various resource types such as energy consumption [1]. It allows us to avoid fine-grained measurements (e.g., power measurements), which are challenging to accurately simulate at scale. Our choice of a time-based abstraction is based on Abdelmoniem et al. [2], who explored the resource efficiency of federated learning systems.

We will ensure to explain our choice of resource usage abstraction in our revised manuscript.

Comment 3: Assumption in time and resource usage formulations

We acknowledge that our formulation was built on an assumption that syncFL and asyncFL achieve the target accuracy after p global model updates. However, we would like to note that in actual FL runs, the number of required global model updates observed in both approaches is similar while having different time and resource usage, as shown below:

The numbers of asyncFL global model updates in the table are adjusted with the staleness penalty as proposed in Section 3. We observed that the required global model updates for asyncFL are generally comparable to those needed for syncFL. This suggests that our formulation could be leveraged to predict time and resource usage of actual FL runs, as we evidenced in our experiments in Section 6.

Addressing your question on client times varying over time, we conducted an additional experiment to compare the prediction errors in scenarios where client times are either changing or remaining constant. To simulate dynamically changing client times, we employed a methodology from a previous study [3] that simulated client training and communication times based on real-world user traces from 136,000 smartphones. In this method, each client is assigned a mean and standard deviation for its time, with the client's time being sampled from a normal distribution each time it is selected. For experiments where client times are constant, the mean value was always used. Our experiments on the FEMNIST dataset, using the same hyperparameters as in Section 6, generated the following results:

These results show that the prediction accuracy is remarkably similar in both scenarios. We surmise that the minimal difference arises as the variations in client times in the dynamic case tend to average out over numerous global model updates in FL. This finding implies that our formulation would be effective in real-world conditions. We intend to incorporate these findings on dynamic client times in our revised manuscript, extending the experiment across all datasets used in our study.

[1] Li, Li, et al. "SmartPC: Hierarchical pace control in real-time federated learning system." IEEE Real-Time Systems Symposium, 2019.

[2] Abdelmoniem, Ahmed M., et al. "REFL: Resource-Efficient Federated Learning." The Eighteenth European Conference on Computer Systems, 2023.

[3] Yang, Chengxu, et al. "Characterizing impacts of heterogeneity in federated learning upon large-scale smartphone data." The Web Conference, 2021.