Speed Up Federated Learning in Heterogeneous Environment: A Dynamic Tiering Approach

Response 3. Regarding the reviewer's focus on the simulation environment used in our experiments, we acknowledge that the decision to simulate the experiments on both CPU/GPU was made deliberately. This decision aligns with the practical considerations of real-world federated learning scenarios, as demonstrated in previous studies such as [1] and [2].

In our simulation, we measured the training time of clients on CPU/GPU in each round, considering the inherent heterogeneity in devices commonly found in federated learning environments. The dynamic tier scheduler is designed to adapt to varying computation capabilities, making it essential to evaluate the system's performance across different hardware configurations.

Furthermore, to account for the communication aspect in federated learning, we simulate the network speed of clients based on their resource profiles. This ensures a comprehensive evaluation of the entire training process, incorporating both computation and communication aspects, which are critical factors in the effectiveness of the proposed DTFL. We believe that this approach enhances the realism of our simulation, providing valuable insights into the performance of DTFL in diverse and heterogeneous environments.

Response 4. We acknowledge the potential for delays in dynamic tier scheduling when relying on the total training time from previous communication rounds to estimate clients' computational status. The selection of the Exponential Moving Average (EMA) in our tier profiling algorithm was primarily driven by its simplicity and efficiency. EMA offers a straightforward and computationally efficient model-free method to smooth out fluctuations in client performance, providing a practical estimate of their current state and preventing any additional load or complexity in the system. EMA relies on past behavior to infer the current state, resembling a Markovian process. As we do not consider any further information about clients or the system or network, this model-free approach works well.

While more complex methods, such as the Kalman filter, particle filter, and RNN-based estimation methods, might offer marginal improvements in the accuracy of computational status, their increased computational overhead and complexity might not be justifiable in the context of real-time tier profiling. Additionally, using these methods would require more information, which is challenging in the federated learning setting. We have no assumptions about the network or clients' computational resources. This method can work well in practical applications where we do not have too many fluctuations. Furthermore, in our experiments, we considered other state estimation methods, and we found that EMA is a simple approach that can achieve good results in estimating clients' computational states. To further evaluate the impact of clients' state estimation method and its delays in accurately estimating clients' computational states, we conducted experiments where we deliberately introduced inaccuracies in clients' computational time estimation in 20% of training rounds for the CIFAR-10 IID case. We employed the same experimental settings as those described in the paper. In these cases, we observed an increase in training time from 2750 to 3190. We further extended the experiments to 40% of training rounds, resulting in a training time increase to 5063, which is still much less than the training time of other FL methods

Response 5. As the primary goal of the proposed method is to minimize training time, we focused on communication time as a proxy for communication cost. The communication cost, encompassing both intermediate data size and network speed of each client, is expressed in seconds, acknowledging the influence of these factors.

In Table 1, we present the communication time (cost) of the training process for different tiers. This table compares the cost of transmitting intermediate data from clients to the server in seconds, reflecting the impact of slower network speeds and larger intermediate data sizes on training time. Also, as discussed in Sec. 3.3, we investigated the influence of communication factors, including communication link speed and local dataset size, on training time.

[1] Chai, Zheng, et al. "Tifl: A tier-based federated learning system." Proceedings of the 29th international symposium on high-performance parallel and distributed computing. 2020.

[2] Tan, Alysa Ziying, et al. "Towards personalized federated learning." IEEE Transactions on Neural Networks and Learning Systems (2022).

We appreciate the committee and reviewer's valuable comments and suggestions. In the following, we address the reviewer's concerns.

Response 1. The experiments presented in our paper aim to support and validate the effectiveness of the proposed federated learning method in addressing the challenges posed by heterogeneous resource-constrained devices in distributed environments.

Our experimental design is motivated by the observed shortcomings in existing FL methodologies, especially in the context of training large models on devices with varying computation and communication capacities. We deliberately highlight the limitations of previous approaches, such as split learning, split federated learning, and tier-based FL, pointing out their inefficiencies in mitigating the straggler problem and reducing overall training time. To address these challenges, we introduce DTFL, a novel system that dynamically divides clients into tiers, offloading different portions of the global model to each client based on their capacities and training speeds. The dynamic tier scheduler utilizes tier profiling to estimate client-side training time, effectively minimizing overall training time. The proposed system incorporates benefits from both SFL and tier-based FL while addressing the straggler problem.

We not only theoretically prove the convergence of DTFL but also conduct extensive experiments, training large models on various datasets under both IID and non-IID settings. Our experimental results demonstrate that DTFL outperforms state-of-the-art FL methods, FedAvg, SplitFed, FedYogi, and FedGKT, in terms of reducing training time while maintaining model accuracy. By emphasizing the challenges in existing methodologies and showcasing the improvements brought by DTFL, we believe our experiments robustly support the arguments and contributions put forth in the paper.

Response 2. We acknowledge the reviewer's concerns about the potential unreliability of relying solely on communication and training time for profiling clients in tier scheduling. Training time can indeed be influenced by various factors such as device capabilities, network congestion, and background processes. While these factors can introduce variability in training time, we believe that using a combination of communication time and training time of client-side devices provides a practical and easy-to-implement approach for estimating a client's capabilities under typical operating conditions. Moreover, our approach does not require the server to collect additional information from clients, such as temperature, IO threads, or other potentially sensitive information. Our model-free approach allows the server to easily observe training time without requiring any further input from clients.

Regarding the evaluation metrics, we recognize the use of target accuracy as a performance metric in previous studies, such as [1] and [2]. This metric offers a standardized approach to compare the training efficiency of various federated learning methods where the objective is to evaluate the training time performance of different methods. While total training time may not fully account for hardware and network variations, we believe it provides a straightforward and practical way to compare the overall training efficiency of different federated learning methods.

[1] Chai, Zheng, et al. "FedAT: A high-performance and communication-efficient federated learning system with asynchronous tiers." Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 2021.

[2] Karimireddy, Sai Praneeth, et al. "Scaffold: Stochastic controlled averaging for federated learning." International conference on machine learning. PMLR, 2020.

Response 4. The technical novelty of the proposed method lies in the introduction of tiering local-loss-based training and the development of dynamic tier scheduling, which significantly reduces the overall training time in heterogeneous environments. We would like to emphasize the challenge of the tier profiler design that involves considering multiple factors, such as communication link speed, client computation power, and local dataset size, and the challenge of solving dynamic tier scheduling, which is an integer programming problem with many unknown parameters.

Specifically, unlike traditional FL methods where client-side models remain static, DTFL introduces flexibility by adapting to the dynamic nature of client resources. It effectively combines the advantages of split learning and tier-based federated learning, overcoming the limitations of existing approaches. DTFL dynamically partitions clients into distinct tiers and optimally offloads portions of the global model based on their capacities, task sizes, and training speeds. The tier scheduler, incorporating tier profiling, offers a low-overhead solution for practical system implementation. Our theoretical analyses demonstrate the convergence of DTFL on both convex and nonconvex loss functions under standard federated learning assumptions. By employing DTFL, the training process accelerates by leveraging all the available resources in a heterogeneous environment while effectively adapting to dynamic changes.

Response 5. We recognize the use of target accuracy as a performance metric in previous studies, such as [2] and [3]. This metric offers a standardized approach to compare the training efficiency of various federated learning methods where the objective is to evaluate the training time performance of different methods. Figure 2 shows the convergence to the target accuracy, and we stopped the training process when we reached the target accuracy. In the experiments, we choose the target accuracy based on previous studies, which is higher than or equal to the accuracy used in previous studies such as [4]. In terms of the maximum accuracy, these methods can achieve similar accuracy in the end.

[1] Han et al., "Accelerating federated learning with split learning on locally generated losses." In ICML 2021 Workshop on Federated Learning for User Privacy and Data Confidentiality. ICML Board, 2021.

[2] Chai, Zheng, et al. "FedAT: A high-performance and communication-efficient federated learning system with asynchronous tiers." Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 2021.

[3] Karimireddy, Sai Praneeth, et al. "Scaffold: Stochastic controlled averaging for federated learning." International conference on machine learning. PMLR, 2020.

[4] He, Chaoyang, Murali Annavaram, and Salman Avestimehr. "Group knowledge transfer: Federated learning of large cnns at the edge." Advances in Neural Information Processing Systems 33 (2020): 14068-14080.

We appreciate the committee and reviewer's valuable comments and suggestions. In the following, we address the reviewer's concerns.

Response 1. In response to the reviewer's point regarding the dynamic nature of clients' resources would like to clarify that our experiments do consider the cases described in your comments, where the computational and communication resources of a portion of clients (30% in our experiments) change over time. Please refer to the first paragraph in Sec. 4.2.

Although our experiments, such as Table 1, demonstrate a scenario where 30% of clients' resources change every 50 rounds to simulate fluctuations in computation and communication resources, our method is designed to handle a broad spectrum of resource heterogeneity and dynamic changes. The tier profiler effectively captures both steady-state and dynamic resource changes, ensuring that clients are consistently assigned to appropriate tiers regardless of the proportion of clients experiencing resource variations.

The TierProfiler component of our method continuously monitors and captures the dynamics of clients' resources, including communication and computation capabilities. This allows the method to adapt to any changes of clients without compromising its effectiveness. In the case with only a subset of clients' resources change, TierProfiler will identify those clients and assign them to appropriate tiers accordingly, in order to minimize the overall training time.

Response 2. Regarding the reviewer's request for more concrete examples of practical applications where client resources change over time, here are a few examples:

• Edge Computing: Edge computing involves performing computations and data processing at the edge of the network, closer to the end devices. In edge computing scenarios, the resources of edge devices can vary due to factors such as workload fluctuations, hardware limitations, and power constraints. Our proposed methods can dynamically adapt to these resource changes, ensuring optimal performance and resource utilization in edge computing environments.
• Mobile Crowdsourcing: In mobile crowdsourcing applications, participants use their smartphones to contribute data or perform tasks. The resources of these devices can vary significantly depending on factors such as battery level, network connectivity, and CPU availability. DTFL can effectively handle these resource fluctuations, ensuring efficient and reliable crowdsourcing processes.
• Internet of Things (IoT): The IoT encompasses a vast network of interconnected devices, ranging from smart home appliances to industrial sensors. The resources of these devices can vary widely due to factors such as sensor data processing demands, network bandwidth limitations, and power availability. Our proposed methods can effectively manage heterogeneous resources and dynamic changes in IoT environments, enabling efficient and scalable IoT applications.

These examples illustrate the growing importance of addressing the problem of resource fluctuations in distributed machine-learning applications. Our method provides a robust and adaptable solution for handling these resource dynamics, enabling efficient, scalable, and reliable distributed machine learning in real-world scenarios.

Response 3. Regarding the reviewer's request for ablation studies, it is essential to note that local-loss-based training without tiers is equivalent to static tiered methods, where the tier is fixed throughout the entire training process. Thus comparing the proposed dynamic tiered method with static tiered methods is the same as comparing it with local-loss-based SFL. In Table 1, we do provide these fixed-tier experimental results, which show that the overall training times under different tiers (fixed throughout the entire training process) are different, and finding the optimal tier is a nontrivial problem. This motivates us to develop dynamic tier scheduling.

In response to the reviewer's suggestion to evaluate the effectiveness of EMA by comparing the results of tier profiling with and without EMA, we conducted this comparison using ResNet-56 and the same configuration as described in the paper. The results consistently show that employing EMA in tier profiling reduces training time across all datasets. The average reduction in training time across all tiers is 7.6%. For instance, for CIFAR-10 IID, removing EMA increases training time from 2750 to 3018. This demonstrates the effectiveness of EMA in smoothing out temporary fluctuations in client performance and providing more accurate tier assignments, ultimately leading to reduced training time. Due to the space limitation, we did not include these results in the paper.

We appreciate the committee and reviewer's valuable comments and suggestions. In the following, we address the reviewer's concerns.

Response 1. In response to the reviewer's inquiry about the proposed method's motivation and advantages in the context of existing federated learning (FL) approaches the DTFL method aims to speed up FL training for resource-constrained devices with heterogeneous computation and communication capabilities, which are prevalent in real-world FL settings. Existing FL methods often struggle to adapt to fluctuating resource availability and varying computational capabilities of clients, leading to inefficient training and suboptimal performance, which can be observed from our experiments in Table 3.

DTFL offers several compelling advantages over existing FL methods:

• Reduced Training Time: By offloading portions of the global model to the server and employing local-loss-based training, DTFL significantly reduces training time compared to traditional FL methods. This is particularly beneficial for training large models in heterogeneous environments.
• Dynamic Resource Adaptation: DTFL effectively adapts to dynamic resource changes among clients through its dynamic tier scheduler. This scheduler continuously monitors client performance and assigns clients to appropriate tiers based on their current resource availability, ensuring efficient utilization of resources.

For the privacy concerns due to the model update at the server side, we evaluate the model accuracy and privacy trade-offs of DTFL when integrating distance correlation and patch shuffling techniques in Table 5:

• Distance Correlation Minimization: We employ distance correlation techniques to reduce the mutual information between hidden feature maps and raw data, making it more difficult for attackers to reconstruct raw data from intermediate representations.
• Patch Shuffling: We implement patch shuffling to further protect privacy by scrambling data patches and preventing attackers from directly accessing raw data.
• Compatibility with Privacy-Preserving FL Methods: DTFL is compatible with existing privacy-preserving FL methods, allowing for easy integration of additional privacy measures.

Response 2. Regarding the feedback about the convergence rate of DTFL, it is important to note that while the convergence rate of DTFL may appear suboptimal compared to certain classical FL settings in terms of training rounds, it is important to note that the training time of DTFL in each round is much less than existing FL methods, which would lead to much less overall training time using DTFL. As demonstrated in Table 3, DTFL significantly reduces the overall training time compared to other FL methods. The convergence analysis provided in Theorem 1 demonstrates that DTFL converges effectively after a certain number of rounds. The deliberate design choice to prioritize training time efficiency over convergence round reflects the method's suitability for real-world applications that demand faster training.

Response 3. In Table 3, we do provide the results in non-IID settings. The non-IID convergence curve shows a similar pattern in terms of training time, and due to the space limit of the paper we only show the IID case. In Figure 2, we follow related studies, such as [1] and [2], by using the training time to achieve the target accuracy as a performance metric. This metric offers a standardized approach to compare the training efficiency of various FL methods. Figure 2 shows the convergence to the target accuracy, and we stopped the training process when we reached the target accuracy. In the experiments, the chosen target accuracy is higher than or equal to the accuracy used in previous studies such as [3].

[1] Chai, Zheng, et al. "FedAT: A high-performance and communication-efficient federated learning system with asynchronous tiers." Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 2021.

[2] Karimireddy, Sai Praneeth, et al. "Scaffold: Stochastic controlled averaging for federated learning." International conference on machine learning. PMLR, 2020.

[3] He, Chaoyang, Murali Annavaram, and Salman Avestimehr. "Group knowledge transfer: Federated learning of large cnns at the edge." Advances in Neural Information Processing Systems 33 (2020): 14068-14080.