Hierarchical Federated Learning with Multi-Timescale Gradient Correction

Authors: wenzhi  fang
dong-jun  han
evan  chen
shiqiang  wang
christopher g brinton
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 21:46:13

Abstract: While traditional federated learning (FL) typically focuses on a star topology where clients are directly connected to a central server, real-world distributed systems often exhibit hierarchical architectures. Hierarchical FL (HFL) has emerged as a promising solution to bridge this gap, leveraging aggregation points at multiple levels of the system. However, existing algorithms for HFL encounter challenges in dealing with multi-timescale model drift, i.e., model drift occurring across hierarchical levels of data heterogeneity. In this paper, we propose a multi-timescale gradient correction (MTGC) methodology to resolve this issue. Our key idea is to introduce distinct control variables to (i) correct the client gradient towards the group gradient, i.e., to reduce client model drift caused by local updates based on individual datasets, and (ii) correct the group gradient towards the global gradient, i.e., to reduce group model drift caused by FL over clients within the group. We analytically characterize the convergence behavior of MTGC under general non-convex settings, overcoming challenges associated with couplings between correction terms. We show that our convergence bound is immune to the extent of data heterogeneity, confirming the stability of the proposed algorithm against multi-level non-i.i.d. data. Through extensive experiments on various datasets and models, we validate the effectiveness of MTGC in diverse HFL settings. The code for this project is available at https://github.com/wenzhifang/MTGC.

Main paper: 
 introduction: 
 In the past several years, federated learning (FL) has emerged as a prevalent approach for distributed training [17, 22, 11, 52, 24] . Conventional FL has typically considered a star topology training architecture, where clients directly communicate with a central server for model synchronization [35, 26] . Scaling this architecture to large numbers of clients becomes problematic, however, given the heterogeneity in FL resource availability and dataset statistics manifesting over large geographies [14, 17, 10] . In practice, such communication networks are often comprised of a hierarchical architecture from clients to the main server, as observed in edge/fog computing [25, 38] and softwaredefined networks (SDN) [20] , where devices are supported by intermediate edge servers that are in turn connected to the cloud.To bridge this gap, researchers have proposed hierarchical federated learning (HFL) which integrates group aggregations into FL frameworks [30, 5, 47, 15] . In HFL (see Fig. 1 ), clients are segmented into multiple groups, and the training within each group is coordinated by a group aggregator node (e.g., an edge server coordinating a cell). Meanwhile, the central server orchestrates the training globally by periodically aggregating models across all client groups, facilitated by the group aggregators.Fundamental challenges. One of the key objectives in FL is to reduce communication overhead while maintaining model performance. Research in conventional FL has established how the global aggregation period, i.e., the number of local iterations during two consecutive communications between clients and the server, impacts FL performance according to the degree of non-i.i.d. (nonindependent or non-identically distributed) across client datasets: when local datasets are more heterogeneous, longer aggregation periods cause client models to drift further apart. In HFL, the situation becomes more complex, and is not yet well studied. There are multiple levels of aggregations within/across client groups, and the frequency of these aggregations diminishes further up the hierarchy (since the communication costs become progressively more expensive). As a result, model drift occurs across multiple levels of non-i.i.d., at different timescales. In the canonical two-level case from Fig. 1 , we have (i) intra-group non-i.i.d., similar to conventional FL, and (ii) inter-group non-i.i.d., arising from data heterogeneity across different groups. This introduces (i) client model drift caused by local updates on individual datasets, usually at a shorter timescale, as well as (ii) group model drift caused by FL over clients within the group, usually at a longer timescale.In conventional star-topology FL, algorithms like ProxSkip [36] , SCAFFOLD [18] , and FedDyn [1] have shown promise for correcting client model drift through local regularization and gradient tracking/correction. However, these approaches are not easily extendable to the HFL scenario due to its multi-timescale communication architecture. Specifically, when integrating these methods into HFL, control variables introduced to handle data heterogeneity, such as gradient tracking or dynamic regularization, need to be carefully injected at each level of the hierarchy, taking into account their coupled effects in taming non-i.i.d. Convergence analysis elucidating the impact of different updating frequencies for such control variables remains an unsolved challenge. Existing works on HFL have also not aimed to directly correct for multi-timescale model drift. This can be seen by the fact that the convergence bounds in existing HFL methods [30, 5, 47, 13] become worse as the extent of non-i.i.d. in the system increases (e.g., gradient divergence between hierarchy levels in [47] ). Some works have proposed adaptive control of the aggregation period in HFL [13, 31] , but they require frequent model aggregations to prevent excessive drift. We thus pose the following question:How can we tame multi-timescale model drift in non-i.i.d. hierarchical federated learning to provably enhance model convergence performance while not introducing frequent model aggregations? In this paper, we propose multi-timescale gradient correction (MTGC), a methodology which can effectively address multi-level model drift over the topology of HFL with a theoretical guarantee. As depicted in Fig. 1 , our key idea is to introduce coupled gradient correction terms -client-group correction and group-global correction -to (i) correct the client gradient towards the group gradient, i.e., to reduce client model drift caused by local updates based on their individual datasets, and (ii) correct the group gradient towards the global gradient, i.e., to reduce group model drift caused by FL across clients within the group, respectively. MTGC thus assists each client model to evolve towards improvements in global performance during HFL. We propose a strategy for updating these gradient correction terms after every group aggregation and global aggregation, respectively, and analyze the convergence behavior of MTGC. Due to the coupling of correction terms and their updates being performed at different timescales, additional challenges arise for theoretical analysis compared to prior work. We thoroughly investigate this problem and make the following contributions:• We develop the multi-timescale gradient correction (MTGC) algorithm for taming leveled model drift in HFL. MTGC incorporates coupled control variables for correcting client gradients and group gradients, effectively tackling model biases arising from various levels of non-i.i.d. data at different timescales. The estimation and update procedures for these control variables rely solely on the model updates, ensuring that no significant additional communication overhead is introduced. • We characterize the convergence rate for MTGC under the non-convex setup. This rate is immune to the extent of intra and inter-group data heterogeneity, confirming the stability of our approach against multi-level non-i.i.d. statistics. Our theoretical result also demonstrates that MTGC achieves linear speedup in the number of local iterations, group aggregations, and clients. Also, we show that the convergence rate of MTGC recovers that of SCAFFOLD, i.e., the non-hierarchical case, when the number of groups and group aggregation period reduces to one. • We conduct extensive experiments using various datasets and models across different parameter settings, which demonstrate the superiority of MTGC in diverse non-i.i.d. HFL environments.Algorithms for conventional FL. The seminal work [35] developed the FedAvg algorithm, incorporating multiple local updates into distributed SGD [58] to relieve communication bottlenecks within conventional star-topology FL. However, FedAvg convergence analysis makes assumptions such as bounded gradients [28, 56, 41] or bounded gradient dissimilarity [45, 12] , showing it is not resistant to non-i.i.d. data. To tackle this issue, numerous techniques have been proposed in the literature, including incorporating static/dynamic regularizers [27, 1, 57, 16] , adaptive control variables [29, 8, 51, 50] , and/or gradient tracking methods [18, 32] . Despite these efforts, existing FL algorithms are not easily extendable to HFL due to the timescale mismatch of multi-level model aggregations induced by the hierarchical system topology. Optimizing these algorithms and ensuring their theoretical convergence in the presence of hierarchical model drift remains unsolved. Our paper addresses these issues through a principled multi-timescale gradient correction method.Hierarchical FL. The authors of [5, 30, 13, 49, 55, 47] explored a new FL branch, HFL, tailored for hierarchical systems consisting of a central server, group aggregators, and clients. To tackle the issue of limited communication resources, the authors of [5] developed a FedAvg-like algorithm called hierarchical FedAvg tailored to HFL, and analyzed its convergence behavior. However, their algorithm is built upon an assumption of i.i.d. data. Another work [47] investigated the convergence behavior of hierarchical FedAvg under the non-i.i.d. setup. However, the convergence bound becomes worse as the extent of data heterogeneity increases, making the algorithm vulnerable to non-i.i.d. data characteristics. In [34] , ProxSkip-HUB is introduced, but requires clients to compute full batch gradients and upload them to group aggregators after every iteration, which is impractical especially when training large-scale models. Overall, there is still a lack of an algorithm that fully addresses the unique challenge of HFL, i.e., the multi-timescale model drift problem, with theoretical guarantees. We fill this gap by introducing multi-timescale gradient correction and providing theoretical insights.Gradient tracking/correction. Both gradient tracking and gradient correction aim to fix the local updating directions of clients to mitigate the impact of model drift caused by data heterogeneity. The gradient tracking concept was originally proposed and analyzed in [9] and then extended to consider various factors like time-vary graphs and asynchronous updates [37, 40, 42, 54] . Subsequently, SCAFFOLD [18] applied gradient tracking in FL to mitigate the impact of data heterogeneity across clients, ensuring convergence and stability in non-i.i.d. settings. More recently, in [32, 2] , the authors demonstrate the effectiveness of gradient tracking in fully decentralized FL, where clients conduct model aggregations through local client-to-client communications. In [6, 43] , gradient tracking is further studied in a semi-decentralized FL setup. Compared to all prior research, our work is the earliest attempt to design an algorithm specifically tailored to multi-timescale model drift in HFL and its training process with periodic local/global aggregations. This presents new challenges in our algorithm design and convergence analysis due to the coupling of our correction terms through their updates at different timescales. In Section 5, we empirically validate the effectiveness of our approach over the prior gradient correction method.2 Background and MotivationQuestion: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The abstract and introduction clearly state the claims made, including the contributions made in the paper. Additionally, the claims made in the abstract and introduction are supported by the theoretical analysis (see Sec. 4) and experiments (see Sec. 5). 
problem setup: hierarchical fl: 
 We consider the hierarchical system depicted in Fig. 1 . The central server is connected to N group aggregators, each linked to the clients within its region, defined as a group. Each group j ∈ {1, 2, . . . , N } consists of a set of n j non-overlapping clients, denoted C j , resulting in a total of N j=1 n j clients within the system. Each client i has its own local data distribution D i . The goal of HFL is to construct an optimal global model x * considering the data distributions of all clients in the system. The role of each group aggregator j involves coordinating the training for the n j clients within its region, while the central server orchestrates the training across all N groups through interaction with the group aggregators. We can formally state the HFL learning objective as follows:min x f (x) := 1 N N j=1 f j (x), where f j (x) := 1 nj i∈Cj F i (x) and F i (x) := E ξi∼Di [F i (x, ξ i )] . (1)Here, f : R d → R denotes the global loss function, f j : R d → R is the loss specific to group j, and F i : R d → R represents the local loss for client i. In addition, ξ i is the data point sampled from distribution D i . Note that our analysis can be easily extended to a weighted average form of (1) by incorporating positive coefficients for each f j (x) or F i (x). For simplicity, these coefficients are assumed to be included in F i (x) as in previous works [18, 48] .In HFL algorithms, group aggregations are conducted after every H local client updates, while global aggregations are performed after every E group aggregations, introducing different timescales. Moreover, different forms of data heterogeneity exist in HFL: (i) intra-group non-i.i.d., due to data heterogeneity across different clients i ∈ C j , and (ii) inter-group non-i.i.d., arising from data heterogeneity across different groups C 1 , ..., C N . These lead to client model drift and group model drift, respectively. The model drifts induced by multi-level data heterogeneity at different timescales hinder hierarchical FedAvg from converging. In Fig. 2 (a), we see that during local training, each local model gradually converges towards the optimal point of its respective client's objective function. Hence, to guarantee theoretical convergence, existing HFL works either assume an i.i.d. setup [5] or rely on a bounded gradient dissimilarity assumption similar to the following [47, 15] :EQUATIONThe first inequality is employed to limit the group drift, i.e., the deviation of group gradients from the global gradient, while the second one bounds the client drift, i.e., the divergence of client gradients from their group gradient. As a result, the convergence bounds of algorithms in these works become worse as data heterogeneity increases (i.e., as δ 1 or δ 2 increase) [19] . Our approach, developed next, does not require these assumptions and remains stable regardless of the extent of data heterogeneity.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The limitation are included in Sec. 6.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
intuition: gradient correction in hierarchical fl: 
 When relying on multiple local SGD iterations as in hierarchical FedAvg, the model update process is not stable even when the model has reached the optimal x * satisfying ∇f (x * ) = 0. Specifically, with γ as the learning rate, we have x * ̸ = x * -γ∇Fi(x * ), as the global optimum x * may not necessarily be optimal for each client's local loss due to data heterogeneity, i.e., ∇Fi(x * ) ̸ = 0 [39] . Correcting the client gradient ∇Fi(x * ) to the global gradient ∇f (x * ) is thus necessary to stabilize the process.1 Motivation and idea. In HFL, however, due to multi-level aggregations occurring at different timescales, it is infeasible to directly correct the client gradient to the global gradient. In particular, EQUATIONClient-group correction initialization: z t,0 i = -∇Fi(x t,0 i,0 , ξ t,0 i,0 )+ 1 n j i∈C j ∇Fi(x t,0 i,0 ,ξ t,0 i,0 ), ∀i ∈ Cj,∀j clients are not able to communicate with the central server directly, and there are multiple group aggregation steps before the group aggregators communicate with the main server. Our idea is thus to inject two gradient correction terms: client-group correction and group-global correction. Specifically, the desired iteration to obtain the updated model x new at the optimal point x * can be written asEQUATIONwhere ∇fj(x * ) -∇Fi(x * ) and ∇f (x * ) -∇fj(x * ) represent client-group and group-global correction terms, respectively. Since ∇f (x * ) = 0, the two correction terms will enable the model to remain at the optimal point. Given this intuition, the ideal local iteration at client i ∈ C j can be written asx t,e i,h+1 = x t,e i,h -γ ∇F i (x 1 n j i∈C j x t,ei,h is the averaged model across the system. Based on (4), we expect to bring each client model closer to the global optima during local updates, as illustrated in Fig. 2(c ).Challenge encountered in HFL. However, it is important to note that the update process in (4) still cannot be directly used in HFL. This is because client-group communication and group-global communication do not occur at every iteration of HFL training; instead, they happen at different timescales, and clients are not able to obtain the current group information ∇fj( xt,e i,h ) and global information ∇f ( xt,e i,h ) at every local iteration. We next propose a strategy that mimics the gradient correction described above while ensuring theoretical convergence.Tackling multi-timescale model drifts. To approximate (4) during HFL training, we introduce two control variables z and y that track/approximate ∇f j -∇F i and ∇f -∇f j , respectively. The variables z and y are then employed to correct the local gradients to prevent model drifts. The challenge here is to keep updating z and y appropriately in the multi-timescale communication scenario, given that communications between the clients and group aggregator, and between the group aggregators and global aggregator, are not always feasible. We propose a strategy to update z after every H local iterations, i.e., whenever each client is able to communicate with the group aggregator, allowing the group information to be updated and shared among the clients within the same group. Similarly, we propose a strategy to update y after every E group aggregations, i.e., whenever the group aggregators are able to communicate with the global aggregator, enabling the global information to be refreshed and shared across all clients in the system. We name our strategy multi-timescale gradient correction (MTGC) due to the updates of z and y occurring in different timescales, to tackle the issue of multi-level model drift coupled across the hierarchy in HFL.In Fig. 2 (c), we illustrate MTGC during client-side model updates. In particular, at each local iteration h of group round e of global round t, each client i ∈ C j updates its local model as follows:x t,e i,h+1 = x t,e i,h -γ ∇F i (x t,e i,h , ξ t,e i,h ) + z t,e i + y t j .(EQUATION(i) Client-group correction term. In (5), z t,e i is responsible for correcting the gradient of client i ∈ C j towards the gradient of group j at the e-th group aggregation of global round t. After every group aggregation e at global round t, this term is updated at each client i as follows:EQUATION(ii) Group-global correction term. y t j in (5) aims to correct the gradient of group j towards the global gradient. At the end of global round t, this term is updated at group aggregator j as follows:EQUATION)Key remarks. The updating policies for z t,e i and y t j follow similar patterns to the ideal corrections outlined in (4) . Here, we observe that i∈C j z t,e i = 0, ∀j and N j=1 y t j = 0, indicating that the correction terms do not have an impact on the per-iteration model averages. Instead, the introduction of z t,e i and y t j eliminates model drifts of clients and groups, respectively, during local iterations. Intuitively, as the iteration approaches the global optimal point, we expect z t,e i → ∇fj(x * ) -∇Fi(x * ) and y t j → ∇f (x * ) -∇fj(x * ) so that the update in (5) stabilizes at the global optimal point. We also see that z t,e i and y t j are coupled (5), i.e., the update of one of the terms affects x which in turn affects the other one, raising challenges for theoretical analysis. In Section 4, we will guarantee convergence of MTGC in general non-convex settings without relying on bounded data heterogeneity assumptions.MTGC algorithm. The overall procedure of our training strategy is summarized in Algorithm 1, where we rewrite the updates of z t,e i and y t j in a different but equivalent manner to facilitate practical implementation of MTGC. Compared to hierarchical FedAvg, which does not consider any correction terms, we see that no additional communication is required for MTGC within each group round e. Additional communication is introduced only after E group aggregations for initializing z t,0 i (Line 4)2 and broadcasting y t+1 j (obtained in Line 14) to the clients in C j . We will see in Section 5 that these marginal additional costs lead to significant performance enhancements for HFL settings.Generalization to arbitrary number of levels. The proposed MTGC algorithm can be extended to an HFL system architecture with an arbitrary number of levels. Further discussions and experimental results for a three-level case are provided in Appendix E.When the number of groups reduces to N = 1 with E = 1, we have y t j = 0 (no group-global correction), and thus MTGC reduces to SCAFFOLD [18] . In SCAFFOLD, at each round t, clients perform local updates according tox t i,h+1 = x t i,h -γ ∇Fi(x t i,h , ξ t i,h ) -c t i + c t , h = 0, 1, . . . , H -1,wherec t+1 i = c t i -c t + 1 Hγ xt -x ti,H , and the server aggregates local models and controlling variables asxt+1 = 1 N N i=1 x t i,H and c t+1 = 1 N N i=1 c t+1 i .We can show that c t i -c t in SCAFFOLD plays the same role as z t,e i in MTGC. However, the additional term y t j introduced in MTGC for the multi-level setting makes the convergence guarantee more challenging, as y t j is coupled with z t,e i and both are updated at different time scales. These aspects will be thoroughly examined next.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: We provide the information of the computer resources used for this work including the GPU type and memory information.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
convergence analysis: 
 In this section, we establish a convergence guarantee for the proposed MTGC algorithm. Our theoretical analysis relies on the following standard assumptions commonly used in the literature on stochastic optimization and FL under non-convex settings [18, 44, 4] . EQUATION)whereÑ = 1 N 2 N j=1 1 nj -1, and f * is the lower bound of f (x), i.e., f (x) ≥ f * .There are two key steps in our proof. The first is the characterization of the evolution of z t,e i +∇Fi xt,e j -∇fj xt,e j 2 and y t j +∇fj xt,e -∇f xt,e 2 . By bounding these values that capture the error between each control variable and the ideal correction, we are able to establish a connection between the local updating direction and the global gradient without relying on the bounded gradient dissimilarity assumption, laying the foundation for the whole proof. The second is that we extracted a recursive relationship for the accumulation of group-level and client-level model drifts, and designed a novel Lyapunov function to mitigate the interplay impact between these drifts. Further details are provided in the appendix.Applying an appropriate learning rate γ to Algorithm 1 yields the following corollary: Corollary 4.1. Under the assumptions of Theorem 4.1, let F 0 = f ( x0 )-f * . Then there exists a learning rate γ ≤ 1 40EHL such that the iterates { xt,e } satisfyEQUATIONDiscussions. Corollary 4.1 provides the convergence upper bound of the MTGC algorithm. It shows that the error approaches zero as T → ∞. If σ ̸ = 0, the upper bound is dominated by the first term in the right-hand side of ( 9), which characterizes the speed of convergence of MTGC to a stationary point in the stochastic case. This reveals MTGC achieves linear speedup in the number of group aggregations E and local updates H. In other words, we can attain the same level of performance with less global communication rounds, i.e., a smaller value of T , by increasing the number of local iterations, i.e., H, and group aggregations, i.e., E. When considering the special casen j ′ = n, ∀j ′ ∈ {1, 2, . . . , N } with uniform client numbers, the rate becomes O( √ F0Lσ 2 / √ N nT EH).This implies that MTGC attains linear speedup in the number of clients as well.Moreover, we also see that our convergence rate recovers the results of SCAFFOLD when the number of groups reduces to N = 1 and the number of group aggregations reduces to E = 1 (see Appendix G for more discussions). We also highlight that, different from prior works on HFL where the convergence bound becomes worse as the extent of data heterogeneity increases, our bound is stable against multi-level non-i.i.d. data due to the multi-timescale gradient correction approach. 
setup: 
 Dataset, model, hyperparameters, and compute setting. In our experiments, we consider four widely used datasets: EMNIST-Letters (EMNIST-L) [7] , Fashion-MNIST [53] , CIFAR-10 [23] , and Experiments are conducted over 3 random trials. We see that MTGC obtains the best testing accuracy in each case, validating our multi-level approach for correcting multi-timescale model drifts. considered. We see that the local correction method is effective for handling client non-i.i.d. within each group (top row), while the group correction method is effective for handling non-i.i.d. across groups (middle row). MTGC obtains the most stable performance (all rows) by combining multiple correction levels.CIFAR-100 [23] . The former two are processed through a multi-layer perceptron (MLP) model, featuring two hidden layers, each comprising 200 neurons, and ending with a softmax layer. For the CIFAR-10 classification task, we employ a convolutional neural network (CNN) following the architecture outlined in seminal work [35] . For CIFAR-100, we adopt a ResNet-18 model with batch normalization layers substituted by group normalization layers. Across all algorithms considered, we maintain a consistent learning rate η = 0.1 and batch size 50. We conduct the experiments based on a cluster of 3 NVIDIA A100 GPUs with 40 GB memory. Our code is based on the framework of [1] .FL data distribution. We set the total number of clients as 100, evenly distributed over N = 10 groups. We also study the effect of N in Appendix B. We consider three different data distribution settings: (i) group i.i. Second, in the group non-i.i.d. & client i.i.d. case, the dataset is first segmented into N partitions for the groups using a Dirichlet distribution, followed by a uniform random distribution of each segment to 100/N clients. Finally, when both groups and clients are non-i.i.d., the dataset is split into N segments for the groups using a Dirichlet distribution, and then, each group's segment is distributed among 100/N clients through a Dirichlet distribution. The Dirichlet parameter is set to 0.1. Comparison with conventional FL algorithms. For comparison, we first apply the well-known FL methods, FedProx [27] , SCAFFOLD [18] , and FedDyn [1], to HFL, by running their training algorithms within each group of the hierarchical system. We also consider HFedAvg [47] as a baseline. Fig. 3 compares MTGC with these baselines in the group non-i.i.d. & client non-i.i.d. case. We observe that MTGC outperforms all the considered conventional algorithms, achieving the highest testing accuracy, especially for the complicated CIFAR-100 dataset. FedDyn achieves the lowest performance, demonstrating significant variance and instability. The significant performance gap between MTGC and FedDyn, in particular, can be attributed to the hierarchical setup disrupting the special structure of FedDyn. This result reveals that some algorithms designed for the conventional star-topology FL may be non-trivial to be extended to hierarchical setups. The overall results confirm the effectiveness of our approach that effectively tackles the multi-timescale drift problem in HFL.Comparison with gradient correction baselines. In Fig. 4 , we compare MTGC with the gradient correction baselines. Specifically, we apply local correction (z t,e i ) to HFedAvg, and group correction (y t j ) to HFedAvg. These baselines can be viewed as schemes applying SCAFFOLD [18] within each group and across groups, respectively. We also report the results of the original HFedAvg to see the effects of gradient correction clearly. We make the following key observations. First, the testing accuracy achieved by HFedAvg decreases as the extent of data heterogeneity increases, e.g., from the first or second row to the third row in Fig. 4 . This shows that data heterogeneity hinders the convergence of HFedAvg. Second, with the assistance of local or group correction, the algorithm attains a higher accuracy. In the case of group i.i.d. & client non-i.i.d., HFedAvg augmented with client local correction performs better than the variant with group correction. Conversely, in the scenario where groups are non-i.i.d. and clients are i.i.d., the opposite holds. This can be explained by the dominance of data heterogeneity in each case. In the former scenario, because the heterogeneity is primarily at the client-level, local client correction becomes more beneficial. On the other hand, in the latter scenario, where the heterogeneity shifts to the group level, group correction becomes more advantageous. Finally, we see that MTGC consistently outperforms baselines under all settings, where the performance gains brought by the multi-timescale gradient correction become more significant when it comes to the group non-i.i.d.& client non-i.i.d. case.Speedup in H and E. In Table 5 .1, we investigate the effects H and E, which determine the periods of group aggregation and global aggregation in HFL. We report the number of global rounds required to attain the desired testing accuracy of 80% for CIFAR-10 under different settings. We have the following observations: As E or H increases, the required number of global rounds of MTGC for achieving the desired accuracy decreases. This demonstrates the speedup of the proposed algorithm in the number of local iterations and group aggregations, which fits well with our theory discussed in Section 4. In addition, the speedup achieved by MTGC compared to HFedAvg gets more significant as E or H increases. For instance, in the group i.i.d. & client non-i.i.d. case, MTGC attains 3.3× speedup when E = 10 , H = 20, which increases to 4.7× when E = 10 , H = 40. This reveals that MTGC utilizes local iterations better compared with the baselines.Impact of data heterogeneity. Consistent with the results in Fig. 4 , we see from Table 5 .1 that the required number of global rounds of HFedAvg increases as data heterogeneity increases, while MTGC is more stable against non-i.i.d. data. The gain of MTGC over HFedAvg becomes evident as data heterogeneity increases, confirming the effectiveness of our multi-timescale gradient correction approach for addressing the unique challenges of HFL.Further experiments. Additional experimental results including the impacts of hierarchical system parameters and the performance in 3-level HFL are provided in Appendices B and E. 
conclusion and limitation: 
 We have proposed MTGC, a multi-timescale gradient correction approach for HFL. Embedded with control variables updated in different timescales, MTGC effectively corrects gradient biases and alleviates both client model drift and group model drift in hierarchical setups. We established the convergence bound of MTGC in the non-convex setup and showed its stability against multi-level data heterogeneity. Finally, we confirmed the advantage of our MTGC through extensive experiments in different non-i.i.d. HFL settings. A limitation of our work is that despite providing experiments for HFL systems with more than two levels (in Appendix E), our convergence analysis focused on the two-level case, which provides an interesting future direction of investigation.  
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We credit the framework that our work is based on in Sec. 5.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: Our paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: Our paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: Our paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Our work focuses on HFL, employing a multi-layered structure consisting of local nodes, local aggregators, and a central server. Both clustered FL and HFL aim to improve FL learning efficiency by leveraging structured client groupings. The difference between them lies in the grouping criteria. HFL focuses on collaborative training over a given network topology, where clients are generally grouped based on their geographical location or network connection status, and aims to build a single global model under this setting. CFL groups clients to optimize model training, with different global models constructed depending on the group. [33] demonstrates how dynamic clustering based on data distributions can enhance model performance. [3] explores alleviating negative transfer from collaboration by clustering clients into non-overlapping coalitions based on their distribution distances and data quantities. The impact of system parameters. Fig. 5 shows how the performance of MTGC changes with different numbers of groups and clients in each group. From this figure, we observe that as the number of clients in each group, i.e., n j increases, client correction becomes more important. On the other hand, as the number of groups increases, the algorithm with group correction performs better than that with client correction. The results are shown in Fig. 7a . The results demonstrate that MTGC achieves higher testing accuracy for a given communication cost, highlighting the efficiency and effectiveness of our approach.Running time comparison. We compared the computation time of our MTGC algorithm with the baselines. Using NVIDIA A100 GPUs with 40 GB memory, we conducted experiments on the CIFAR-10 dataset with E = 30 and H = 20 under both client and group non-i.i.d. setup. The model and other parameters are the same as in the original manuscript. We report the required time for attaining a preset accuracy of 75% and for running 100 global rounds in Fig. 7b of the attached pdf.The speedup in the convergence makes up for the introduced computation cost per iteration due to the extra operation induced by the correction variables. Actually, the computation cost incurred by the correction variable is relatively small compared to computing gradients in a neural network using backpropagation. To further show the robustness, we studied the performance of MTGC under another two different non-i.i.d. scenarios: label shift and feature shift, as referenced in [3, 33] . These experiments were performed using the Fashion-MNIST dataset.For label shift [3, 33] , we randomly assign 3 classes out of 10 classes to each group with a relatively balanced number of instances per class, and then assign 2 classes to each client. As discussed in [3] , label shift adds more heterogeneity to this system. According to the results shown in Fig. 8a , it is clear that the proposed algorithm is more robust against data heterogeneity. Specifically, there is less oscillation in MTGC compared with HFedAvg and the attained accuracy of MTGC in the given communication round is higher than all baselines. Concretely, for the clients at the i-th group, the angle is -50 + 10 × i. Note that this rotation is only applied to the training set. The feature shift increases the diversity between the training set and the testing set, which thus adds difficulty to this classification task. In Fig. 8b , we see that MTGC attains the best performance among these baselines.We conducted additional experiments on the larger Shakespeare and CINIC-10 datasets. For the Shakespeare dataset, we randomly pick 100 characters (people) in Shakespeare's plays. We let each client have 1,500 samples, where each sample is a sequence of 80 characters (words). Considering that there are 100 clients in the system, there are 150,000 train samples in total. This means that the number of samples is 3 times that of CIFAR-10 (or CIFAR-100), which has 50,000 train samples. The performance comparison is presented in Fig. 9a , where we use the LSTM model, the same as [1], and set the learning rate 0.5, H = 75, and E = 30. It is seen that MTGC consistently outperforms the baseline methods in larger datasets.The CINIC-10 dataset contains 90,000 training images, 90,000 validation images, and 90,000 test images, significantly larger than CIFAR-10 and CIFAR-100 with 60,000 images. It includes images from both CIFAR-10 and ImageNet, enhancing diversity. We believe that the larger size and diversity of CINIC-10 further confirm the validity of our experiments. The model and hyperparameters used for the CINIC-10 dataset are the same as those of the CIFAR-10 task shown in the original manuscript. As illustrated in Fig. 9b , MTGC maintains its superior performance on the CINIC-10 dataset, consistent with its performance on other tasks.We extend MTGC for the HFL system with M levels in this subsection. For presentation ease, we adopt different notations than those used in the main text. Specifically, we denote the number of total iterations at clients as r. The aggregation periods for level m are denoted as P m . This means that the m-th level aggregator aggregates the model from the clients within its coverage after every P m local iterations. The global server is treated as the first level aggregator. Note that P m > P m+1 and P m+1 | P m , ∀m = 1, . . . , M -1. We denote the model maintained at the nodes connected to the m-th level aggregator (k 1 , k 2 , . . . , k m-1 ) as x r k1,...,km , where k m ∈ {1, . . . , N m }. The gradient correction term between nodes (k 1 , k 2 , . . . , k m-1 ) and (k 1 , k 2 , . . . , k m ) is denoted as ν r k1,k2,...,km . The overall procedures are summarized in Algorithm 2.Input: γ, {Pi : i ∈ {1, 2, . . . , M }} 1 Initialize: ν r k 1 , ν r k 1 ,k 2 , . . . , ν r k 1 ,k 2 ,...,k M , ∀k1, k2, . . . , kM 2 r = 0, 1, . . . , R -1 do 3 each client (k1, . . . , kM ) ∈ V in parallel do 4 Compute stochastic gradient: g r k 1 ,...,k M 5 x r+1 k 1 ,...,k M = x r k 1 ,...,k M -γ g r k 1 ,...,k M +ν r k 1 +ν r k 1 ,k 2 +. . .+ν r k 1 ,k 2 ,...,k M 6 level i = M, . . . , 1 do 7 if Pi | r + 1 then 8i-th level model aggregate:EQUATIONi-th level correction term update:EQUATION1 st layer aggregator 2 nd layer aggregator 3 rd layer aggregator We numerically validate the performance of MTGC by conducting experiments in the three-level case as shown in Fig. 10 . The results are shown in Fig. 11 . The total number of clients is set to be 100 while N 1 = 4, N 2 = 5, N 3 = 5. Additionally, the aggregation periods are set to be P 1 = 500, P 2 = 100, P 3 = 10. The data is non-i.i.d. distributed across each level.EQUATIONBefore proceeding to the proof of the main theorem. We introduce some basic inequalities in this subsection that will be frequently used in our proof.Lemma F.1.1. For any set ofK vectors {p k } K k=1 , 1 K K k=1 p k 2 ≤ 1 K K k=1 ∥p k ∥ 2 , K k=1 p k 2 ≤ K K k=1 ∥p k ∥ 2 ,and1 K K k=1 p k - 1 K K k=1 p k 2 = 1 K K k=1 ∥p k ∥ 2 - 1 K K k=1 p k 2 .Lemma F.1.2. For any two vectors p, q ∈ R d , ∥p+ q∥ 2 ≤ (1 + α) ∥p∥ 2 + 1 + 1 α ∥q∥ 2 . Lemma F.1.3. Suppose a sequence of random vectors {p k } K k=1 satisfy E[p k ] = 0, ∀k. Then, E 1 K K k=1 p k 2 = 1 K 2 K k=1 E ∥p k ∥ 2 . Lemma F.1.4. [46, Lemma 2] Suppose a sequence of random vectors {p k } K k=1 satisfy E[p k | p k-1 ,p k-2 ,. . . ,p 1 ] = 0, ∀k. Then, E   K k=1 p k 2   = K k=1 E ∥p k ∥ 2 .Lemma F.1.5. [21, Lemma 17] For anyEQUATIONF.2 Proofs of Theorem 4.1 and Corollary 4.1For the convenience of presentation, we introduce the following notations To prove the convergence of MTGC, we start with characterizing the evolution of the global loss, i.e., f (x) through the following lemma.EQUATIONEQUATIONLemma F.2.1. Suppose that Assumptions 1 and 2 hold and γ ≤ 1 2HL , then the iterates generated by Algorithm 1 satisfyEQUATIONLemma (F.2.1) implies that we need further to study the evolution of Q t and D t . In particular, we establish upper bounds for Q t and D t in Lemmas F.2.2 and F.2.3, respectively. Lemma F.2.2. Suppose that Assumptions 1 and 2 hold and γ ≤ 1 8HL , then the client model drift Q t , defined in (11) , can be bounded asEQUATION)Lemma F.2.3. Suppose that Assumptions 1 and 2 hold and γ ≤ 1 10EHL . Then the group model drift D t , defined in (11) , can be bounded asEQUATION)The results shown in Lemmas F.2.2 and F.2.3 suggest that Z t,e j and Y t,e j are crucial for understanding the dynamics of MTGC. Hence, we derive upper bounds for Z t,e j and Y t,e j , which are presented in Lemmas F.2.4 and F.2.5, respectively. Lemma F.2.4. Suppose that Assumptions 1 and 2 hold. Then the bias between client-group correction term z t,e i and ∇F i xt,e j -∇f j xt,e j , i.e., Z t,e j can be bounded asEQUATION)Lemma F.2.5. Suppose that Assumptions 1 and 2 hold. Then the bias between group-global correction term y t j and ∇f j ( xt,e )-∇f ( xt,e ), i.e., Y t,e j defined in (11) , t ≥ 1, can be bounded asEQUATIONAdditionally, when t = 0, Y 0,e j can be bounded asEQUATION)In addition, the upper bound of Θ t,e j is presented in the following lemma. Lemma F.2.6. Suppose that Assumptions 1 and 2 hold. Then the group model progress at the (t, e)-th round, i.e., Θ t,e j , defined in (11) , can be bounded asEQUATION)Recalling Lemma (F. Γ t = Q t + D t satisfies Γt ≤ 1 2 Γt-1 + 1152γ 4 H 4 L 2 +72γ 2 E 2 H 2 E-1 τ =0 E ∇f ( xt-1,τ ) 2 +E ∇f ( xt,τ ) 2 + 294γ 2 E 3 Hσ 2 , Γ0 ≤ 648γ 4 H 4 L 2 +42γ 2 E 2 H 2 E-1 e=0 E ∇f x0,e 2 +146γ 2 E 3 H 2 σ 2 .The proofs of Lemmas F. EQUATIONEQUATIONwhere Γ t = Q t + D t . Adding 2γL 2 HΓ t on both sides of the above inequality and utilizing Lemma F.2.7, we haveEf ( xt+1 ) + γL 2 HΓt ≤ Ef ( xt ) + γL 2 HΓt-1 - γH 2 E-1 e=0 E ∇f ( xt,e ) 2 +γ 2 LEH 1 N 2 N j=1 1 nj σ 2 +2γL 2 H × 294γ 2 E 3 Hσ 2 + 2304γ 5 H 5 L 4 +144γ 3 E 2 H 3 L 2 E-1 τ =0 E ∇f ( xt-1,τ ) 2 +E ∇f ( xt,τ ) 2 .For notation ease, we denote Φ t+1 = Ef ( xt+1 ) -f * + γL 2 HΓ t , Φ t ≥ 0, ∀t ≥ 0. As long as γ ≤ E 8HL in Theorem 4.1, 2304γ 5 H 5 L 4 ≤ 36γ 3 E 2 H 3 L 2 , we thus haveEQUATION) When γ ≤ 1 40EHL , we have γH 2 -360γ 3 E 2 H 3 L 2 ≥ γH 4 .Telescoping the above inequality from t = 1 to T -1, we haveEQUATION)According to Lemma F.2.1, when t = 0,EQUATION)it follows thatEQUATION)Combining ( 23) with ( 21) and plugging the upper bound of Γ 0 , established in Lemma F.2.7, into the inequality, we haveEQUATIONT -1 t=1 E-1 e=0 E ∇f ( xt,e ) 2 .The setup of γ presented in Theorem 4.1 is enough to guarantee γH2 -180γ 3 E 2 H 3 L 2 -2γL 2 H × 648γ 4 H 4 L 2 +42γ 2 E 2 H 2 ≥ γH 4 .Therefore, combining the last terms and taking some basic algebra operation, we have1 T E T -1 t=0 E-1 e=0 E ∇f ( xt,e ) 2 ≤4 Ef ( x0 )-f * γT EH +4γL 1 N 2 N j=1 1 nj σ 2 + 1168 T γ 2 L 2 E 2 H 2 σ 2 +2352γ 2 L 2 E 2 Hσ 2 .The above bound can be further simplified toEQUATION)This completes the proof of Theorem 4.1.Rewriting the bound in 24 asEQUATION)and recalling Lemma F.1.5, one can claim that there exists a learning rate (γEH) ≤ 1 d such thatEQUATIONGiven that we need γ ≤ 1 40EHL for Theorem 4.1, we can set d = 40L. We thus can find a step size in the range of (γEH)EQUATION)This completes the proof of Corollary 4.1.F. With Assumption 1, we haveEQUATION)Plugging ( 28) into ( 29), we haveEQUATIONEQUATION)UtilizingE 1 N N j=1 1 n j i∈C j H-1 h=0 ∇Fi x t,e i,h , ξ t,e i,h -1 N N j=1 1 n j i∈C j H-1 h=0 ∇Fi(x t,ei,h ) = 0, we rewrite T 1 as followsEQUATION- γH 2 E ∇f ( xt,e ) 2 - γH 2 E 1 N N j=1 1 nj i∈C j 1 H H-1 h=0 ∇Fi(x t,e i,h )On the other hand, we can bound T 2 as followsT2 ≤E 1 N N j=1 1 nj i∈C j H-1 h=0 ∇Fi x t,e i,h ,ξ t,e i,h -∇Fi(x t,e i,h ) 2 +E 1 N N j=1 1 nj i∈C j H-1 h=0 ∇Fi(x t,e i,h ) 2 ≤ 1 N 2 N j=1 1 n 2 j i∈C j E H-1 h=0 g t,e i,h - H-1 h=0 ∇Fi(x t,e i,h ) 2 + E 1 N N j=1 1 nj i∈C j H-1 h=0 ∇Fi(x t,e i,h ) 2 ≤ Hσ 2 N 2 N j=1 1 nj + E 1 N N j=1 1 nj i∈C j H-1 h=0 ∇Fi(x t,e i,h ) 2 ,where second inequality comes from Lemma F.1.3 and the last inequality follows Assumption 2 and Lemma F.1.4.Plugging the derived upper bounds of T 1 and T 2 into 30 and utilized γ ≤ 1 2HL , we obtainEQUATION+ γHL 2 1 N N j=1 E xt,e -xt,e j 2 .Telescoping the above inequality from e = 0 to H -1 gives rise to Lemma F. where the first inequality comes from Lemma F.1.2 and Assumption 2 and the second inequality follows Lemma F.1.1. Letρ 1 = 1 + 1 H-1 + 4γ 2 HL 2 . As γ ≤ 1 8HL , we have ρ h 1 ≤ ρ H-1 1 ≤ 1 + 1 H-1 + 1 16(H-1) H-1 ≤ e 17 160 < 3 and where the last inequality follows Assumption 1.H-1 h=0 ρ h 1 ≤ 3H,Plugging the derived upper bound of n j q t,e j,h+1 into .Q t = E-1 e=0 1 N N j=1 1 H H-1 h=0 q t,Next, we establish an upper bound for Θ t,e j as follows EQUATIONEQUATION≤2γ 2 H H-1 h=0 E 1 nj i∈C j ∇Fi x tEQUATION,where we utilize 1 N N j=1 y t j = 0 and 1EQUATIONEQUATION,where the first inequality comes from Lemma F.1.2. We thus haveEQUATIONEQUATIONEQUATIONwhere the first equality comes from Lemmas F.1.1 and the second inequality follows Lemmas F.1.3 and F.1.4. Additionally, we bound T 3 asT3 = 1 H H-1 h=0 1 N N j=1 E y t j ∓ ∇fj xt,e ∓ ∇f xt,e + 1 nj i∈C j ∇Fi x t,e i,h - 1 N N j=1 1 nj i∈C j ∇Fi x t,e i,h 2 ≤2 1 N N j=1 E y t j + ∇fj xt,e -∇f xt,e 2 + 2 1 H H-1 h=0 1 N N j=1 E 1 nj i∈C j ∇Fi x t,e i,h -∇fj xt,e -   1 N N j=1 1 nj i∈C j ∇Fi x t,e i,h -∇f xt,e   2 ≤2 1 N N j=1 E y t j +∇fj xt,e -∇f xt,e 2 +2 1 H H-1 h=0 1 N N j=1 E 1 nj i∈C j ∇Fi x t,e i,h -∇fj xt,e 2 ≤4L 2 1 N N j=1 1 nj i∈C j 1 H H-1 h=0 E x t,e i,h -xt,e j 2 + 4L 2 1 N N j=1 E xt,e j -xt,e 2 + 2 1 N N j=1 E y t j + ∇fj xt,e -∇f xt,e 2 ,where the second inequality follows Lemma F.1.1 and the last inequality follows Assumption 1.Plugging the derived upper bound of T 3 into (31) gives rise toEQUATIONLetρ 2 = 1 + 1 E-1 + 8γ 2 EH 2 L 2 . As γ ≤ 1 10EHL , we have ρ 2 ≤ ρ E-1 2 ≤ 1 + 1 E-1 + 1 12(E-1) E-1 ≤ e 13 120 < 3, where e 0 denotes Euler's number. Therefore, we haveEQUATIONHence, forD t = E-1 e=0 1 N N j=1 E e txt,e j -xt,e 2 , we haveEQUATIONThis completes the proof of Lemma F.2.3.For e = 0, z t,0 i = -∇F i x t,0 i,0 , ξ t,0 i,0 + 1 nj i∈Cj ∇F i x t,0 i,0 , ξ t,0 i,0 where x t,0 i,0 = xt,0 j , we haveEQUATIONwhere the first inequality follows Lemma F.1.1 and the second inequality holds due to Assumption 2.In addition, when e ≥ 0, z t,e i obeys the following iteration As i∈Cj z t,e i = 0, we thus havez t,e+1 i =z t,e i + 1 Hγ   x t,e i,H -x t,e i,0 - 1 nj i∈C j x t,e i,H -x t,e i,0   =z t,e i - 1 H H-1 h=0   ∇Fi x tz t,e+1 i = 1 H H-1 h=0   1 nj i∈C j ∇Fi x t,e i,h , ξ t,e i,h -∇Fi x t,e i,h , ξ t,e i,h   .To establish an upper bound forE-1 e=0 1 N N j=1 Z t,e+1 j, we start with bounding Z t,e j as followsEQUATIONEQUATIONEQUATIONwhere the first inequality comes from Lemma F.1.1, the third inequality follows Lemma F.1.4 and Assumption 2, and the fourth inequality follows Assumption 1. Combining this bound with (34), we thus obtain Lemma F.2.4, i.e.,EQUATIONF.3.5 Proof of Lemma F.2.5Part I (t ≥ 1): As i∈Cj z t,e i = 0, the updating rule of y t+1 j can be simplified asEQUATIONWe next bound Y t+1,e j as followsEQUATIONwhere the first inequality holds due to Lemma F.1.1, the second inequality follows Lemmas F.1.1 and F.1.3, the third inequality follows Lemmas F.1.1 and F.1.4 and Assumption 2, the fourth inequality follows Lemma F.1.1, and the final one comes from Assumption 1.Given the above inequality, it follows thatEQUATIONAdditionally, .E x t,τ i,h -xt+1,e 2 ≤E x t,τ i,h ∓ xt,τ j ∓ xt,τ ∓ xt+1 -xt+1,e 2 ≤4E x t,τ i,h -xt,τ j 2 + 4E xt,τ j -xt,τ 2 + 4E xt,τ -xt+1 2 + 4E xt+1 -xt+1,e 2 ,For E xt+1 -xt+1,e 2 , we haveEQUATIONwhere the second equality holds due to Lemma F.1.3, the second inequality follows Lemma F.1.4 and Assumption 2, the third inequality comes from Lemma F.1.1, the last inequality follows Lemma F.1.1 and Assumption 1.Similarly, we can bound E xt,τ -xt+1 2 asEQUATIONGiven ( 41) and ( 42), it follows thatEQUATIONCombining ( 39) and ( 40), we can obtainEQUATIONEQUATIONPlugging ( 43) into (44), we haveE-1 e=0 1 N N j=1 Y t+1,e j ≤ 8L 2 Qt + 8L 2 Dt + 32γ 2 L 2 E 2 H 1 N 2 N j=1 1 nj σ 2 + 2 H 1 N N j=1 1 nj σ 2 + 48γ 2 L 4 E 2 H 2 Qt + 48γ 2 L 4 E 2 H 2 Dt + 48γ 2 L 2 E 2 H 2 E-1 τ =0 E ∇f ( xt,τ ) 2 +48γ 2 L 4 E 2 H 2 Qt+1 +48γ 2 L 4 E 2 H 2 Dt+1 +48γ 2 L 2 E 2 H 2 E-1 τ =0 E ∇f ( xt+1,τ ) 2 .Part II (t = 0): On the other hand, when t = 0, we haveE-1 e=0 1 N N j=1 Y 0,e j = E-1 e=0 1 N N j=1 E - 1 nj i∈C j ∇Fi( x0 , ξ 0,0 i,0 )+ 1 N N j=1 1 nj i∈C j ∇Fi( x0 , ξ t,0 i,0 ) + ∇fj x0,e -∇f x0,e 2 ≤ E-1 e=0 1 N N j=1 E - 1 nj i∈C j ∇Fi( x0 , ξ 0,0 i,0 ) + ∇fj x0 + 1 N N j=1 1 nj i∈C j ∇Fi( x0 , ξ t,0 i,0 ) -∇f x0 2 + E-1 e=0 1 N N j=1 E ∇fj x0,e -∇fj x0 -∇f x0,e + ∇f x0 2 ≤E 1 N N j=1 1 nj σ 2 + L 2 E-1 e=0 E x0,e -x0 2 .Similar to (41) , we haveE-1 e=0 E x0,e -x0 2 ≤6γ 2 L 2 E 2 H E-1 τ =0 H-1 h=0 1 N N j=1 1 nj i∈C j E x 0,τ i,h -x0,τ j 2 +6γ 2 L 2 E 2 H 2 E-1 τ =0 1 N N j=1 E x0,τ j -x0,τ 2 + 6γ 2 E 2 H 2 E-1 τ =0 E ∇f ( x0,τ ) 2 + 2γ 2 E 2 H N 2 N j=1 1 nj σ 2 .Combining the above two inequalities gives rise toE-1 e=0 1 N N j=1 Y 0,e j ≤E 1 N N j=1 1 nj σ 2 + 6γ 2 L 4 E 2 H 2 (Q0 + D0) + 6γ 2 L 2 E 2 H 2 E-1 e=0 E ∇f ( x0,e ) 2 + 2γ 2 L 2 E 2 H N 2 N j=1 1 nj σ 2 .To this end, we complete the proof of Lemma F.2.5.F.3.6 Proof of Lemma F.2.7Part I (t ≥ 1): (15) with an upper bound established in Lemma F.2.6 (i.e., (18) ), and then plugging it into (13), we haveReplacing E-1 e=0 1 N N j=1 Θ t,e j inEQUATIONSumming (45) with the inequality established in Lemma F.2.3 and utilizing the upper bound ofE-1 e=0 1 N N j=1 Y t,e jestablished in Lemma F.2.5, we haveQt +Dt ≤ 48γ 2 H 2 L 2 +384γ 4 H 4 L 4 +24γ 2 E 2 H 2 L 2 Qt + 24γ 2 H 2 L 2 +384γ 4 H 4 L 4 Dt + 384γ 4 H 4 L 2 +24γ 2 H 2 E-1 e=0 E ∇f xt,e 2 + 384γ 4 H 4 L 2 +12γ 2 H 2 +12γ 2 E 2 H 2 8L 2 +48γ 2 L 4 E 2 H 2 (Qt-1 + Dt-1) +48γ 2 L 4 E 2 H 2 (Qt +Dt)+48γ 2 L 2 E 2 H 2 E-1 τ =0 E ∇f ( xt-1,τ ) 2 +E ∇f ( xt,τ ) 2 +32γ 2 L 2 E 2 H 1 N 2 N j=1 1 nj σ 2 + 2 H 1 N N j=1 1 nj σ 2 +96γ 4 EH 3 L 2 1 N N j=1 1 nj σ 2 +27γ 2 EHσ 2 +12γ 2 H 2 σ 2 +3γ 2 E 3 H N -1 N 2 N j=1 1 nj σ 2 .Qt +Dt≤ 48γ 2 H 2 L 2 +384γ 4 H 4 L 4 +24γ 2 E 2 H 2 L 2 + 384γ 4 H 4 L 2 +12γ 2 H 2 +12γ 2 E 2 H 2 ×48γ 2 L 4 E 2 H 2 × (Qt +Dt) + 384γ 4 H 4 L 2 +12γ 2 H 2 +12γ 2 E 2 H 2 8L 2 +48γ 2 L 4 E 2 H 2 (Qt-1 + Dt-1) + 384γ 4 H 4 L 2 +24γ 2 H 2 + 384γ 4 H 4 L 2 +12γ 2 H 2 +12γ 2 E 2 H 2 ×48γ 2 L 2 E 2 H 2 × E-1 τ =0 E ∇f ( xt-1,τ ) 2 +E ∇f ( xt,τ ) 2 + 384γ 4 H 4 L 2 +12γ 2 H 2 +12γ 2 E 2 H 2 32γ 2 L 2 E 2 H 1 N 2 N j=1 1 nj σ 2 + 2 H 1 N N j=1 1 nj σ 2 +96γ 4 EH 3 L 2 1 N N j=1 1 nj σ 2 +27γ 2 EHσ 2 +12γ 2 H 2 σ 2 +3γ 2 E 3 H N -1 N 2 N j=1 1 nj σ 2 .When γ ≤ 1 7EHL , we have 48γ 2 L 2 E 2 H 2 ≤ 1 andEQUATIONAsγ ≤ 1 33EHL , we have 1 -60γ 2 H 2 L 2 +768γ 4 H 4 L 4 +36γ 2 E 2 H 2 L 2 ≥ 2 3 and 3840γ 4 H 4 L 4 + 120γ 2 H 2 L 2 +120γ 2 E 2 H 2 L 2 ≤ 1 3 .Hence, (46) can be simplified asQt +Dt ≤ 1 2 (Qt-1 + Dt-1)+ 1152γ 4 H 4 L 2 +72γ 2 E 2 H 2 × E-1 τ =0 E ∇f ( xt-1,τ ) 2 +E ∇f ( xt,τ ) 2 + ϕ(γ, σ 2 ), where ϕ(γ, σ 2 ) = 1728γ 4 H 4 L 2 +216γ 2 E 2 H 2 1 H 1 N N j=1 1 nj σ 2 +144γ 4 EH 3 L 2 1 N N j=1 1 nj σ 2 +42γ 2 EHσ 2 +18γ 2 H 2 σ 2 +5γ 2 E 3 H 1 N N j=1 1 nj σ 2 .Further, we establish an upper bound for ϕ(γ, σ 2 ) as follows,ϕ(γ, σ 2 ) =1728γ 4 H 3 L 2 1 n σ 2 +144γ 4 1 n EH 3 L 2 σ 2 +γ 2 σ 2 216 E 2 H n +42EH +18H 2 +5 E 3 H n ≤1728γ 4 EH 3 L 2 1 n σ 2 +144γ 4 1 n EH 3 L 2 σ 2 +281γ 2 E 3 Hσ 2 ≤294γ 2 E 3 Hσ 2 ,where the last inequality holds due to1 n = 1 N N j=1 1 nj ≤ 1 and γ ≤ √ nE 12HL ≤ 1 33EHL .Part II (t = 0): Summing (45) with the inequality established in Lemma F.2.3 and utilizing the upper bound ofE-1 e=0 1 N N j=1 Y t,e j established in Lemma F.2.5, we have Γ0 ≤ 48γ 2 H 2 L 2 +384γ 4 H 4 L 4 +24γ 2 E 2 H 2 L 2 Γ0 + 384γ 4 H 4 L 2 +24γ 2 H 2 E-1 e=0 E ∇f x0,e 2 + 384γ 4 H 4 L 2 +12γ 2 H 2 +12γ 2 E 2 H 2 E 1 N N j=1 1 nj σ 2 + 6γ 2 L 4 E 2 H 2 Γ1 +6γ 2 L 2 E 2 H 2 E-1 e=0 E ∇f ( x0,e ) 2 + 2γ 2 L 2 E 2 H N 2 N j=1 1 nj σ 2 +96γ 4 EH 3 L 2 1 N N j=1 1 nj σ 2 +27γ 2 EHσ 2 +12γ 2 H 2 σ 2 +3γ 2 E 3 H N -1 N 2 N j=1 1 nj σ 2 .Reorganizing the above inequality gives rise toΓ0 ≤ 50γ 2 H 2 L 2 +432γ 4 H 4 L 4 +26γ 2 E 2 H 2 L 2 Γ0 + 26γ 2 H 2 +432γ 4 H 4 L 2 +2γ 2 E 2 H 2 E-1 e=0 E ∇f x0,e 2 + 384γ 4 H 4 L 2 +12γ 2 H 2 +12γ 2 E 2 H 2 E 1 N N j=1 1 nj σ 2 + 2γ 2 L 2 E 2 H N 2 N j=1 1 nj σ 2 +96γ 4 EH 3 L 2 1 N N j=1 1 nj σ 2 +27γ 2 EHσ 2 +12γ 2 H 2 σ 2 +3γ 2 E 3 H 1 N N j=1 1 nj σ 2 .Following the same derivation as in Part I, we obtainΓ0 ≤ 648γ 4 H 4 L 2 +42γ 2 E 2 H 2 E-1 e=0 E ∇f x0,e 2 + ψ(γ, σ 2 ).whereψ(γ, σ 2 ) = 1044γ 4 H 4 L 2 +72γ 2 E 2 H 2 E 1 N N j=1 1 nj σ 2 +144γ 4 EH 3 L 2 1 N N j=1 1 nj σ 2 +42γ 2 EHσ 2 +18γ 2 H 2 σ 2 +5γ 2 E 3 H 1 N N j=1 1 nj σ 2 .Utilizing1 n = 1 N N j=1 1 nj ≤ 1 and γ ≤ √ nE 12HL ≤ 1 33EHL , we can further bound ψ(γ, σ 2 ) as ψ(γ, σ 2 ) = 1044γ 4 H 4 L 2 +72γ 2 E 2 H 2 E 1 N N j=1 1 nj σ 2 +144γ 4 EH 3 L 2 1 N N j=1 1 nj σ 2 +42γ 2 EHσ 2 +18γ 2 H 2 σ 2 +5γ 2 E 3 H 1 N N j=1 1 nj σ 2 =1044γ 4 EH 4 L 2 1 n σ 2 +144γ 4 L 2 EH 3 1 n σ 2 +γ 2 σ 2 72 E 3 H 2 n +42EH +18H 2 +5 E 3 H n ≤146γ 2 E 3 H 2 σ 2 .To this end, we complete the proof of Lemma F.2.7.By comparing the communication complexity T required to achieve a ϵ-stationary solution, we can see that our result recovers that of SCAFFOLD when N = 1 and E = 1. Specifically, for our MTGC algorithm, to achieve an ϵ error bound, according to Corollary 4.1, we can find a T to satisfyEQUATION, and T ≥ LF0 ϵ . In other words, the MTGC algorithm will have an expected error smaller than ϵ if T satisfiesT = O Lσ 2 F 0 Ñ EHϵ 2 + LσF 0 (ϵ) 3 2 + LF 0 ϵ .According to Theorem II of [18] , to achieve the ϵ error bound, the number of global communication rounds SCAFFOLD needs to take can be expressed asT = O Lσ 2 F 0 n j Hϵ 2 + LF 0 ϵ ,where we have converted the notation from [18] to our notation.We see that the dominating term of the MTGC, O Lσ 2 F0 Ñ EHϵ 2 , recovers that of SCAFFOLD when N = 1 (i.e., Ñ = n j ) and E = 1, which corresponds to the case of a single group with a single (global) aggregator.• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Justification: Our work adheres to the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Justification: There is no societal impact of the work performed.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).We motivate our approach here using full batch gradients, though our subsequent algorithm and analysis will support stochastic gradients.This is only required for theoretical analysis. In the experiments, we initialize z t,0 i = 0, ∀i., where the last inequality comes from Assumption 1. 


Decision: This paper consider a setting of FL where the clients have hierarchical architectures. Then they proposed a simple but effective algorithm for handling multi-timescale model drift based on multi-timescale gradient correction (MTGC) techniques. This paper is closely relevant to practices and fills the gap in existing literature on hierarchical FL. The theoretical results are strong and without any assumptions data heterogeneity. Also a linear speedup with the number of local iterations is obtained in theory.

Reviews: review: paper_summary: paper_summary: This paper introduces the usage of the gradient correction scheme to hierarchical federated learning. Specifically, the authors propose and analyze the multi-timescale gradient correction MTGC algorithm which is a direct generalization of SCAFFOLD to the framework where local clients aggregate their models on group server and group servers aggregate their models to a global server. The authors introduce control variables that correct i) client model drift and ii) group model drift that arises due to data heterogeneity. Theoretical convergence results are presented in the non-convex regime and experimental results showcase the ability of MTGC to address data heterogeneity both from clients and from group-servers.
strength_weakness: strength_weakness: - The main weakness of this work is its lack of novelty and technical contribution. The proposed MTGC is a straightforward extension of the well-known SCAFFOLD algorithm to a two-level hierarchical FL. Although the authors mention that the coupling of the two error correction variables is introducing new challenges I fail to see how this is the case. Indeed, the analysis of the correction variables appears to be largely the same as in SCAFFOLD and the authors to not make clear in the main body of their work what specific new challenges they faced and how they were circumvented. To summarize, although the paper is well written I do not see enough contribution to justify its acceptance to a top tier conference.

- Minor typo: on line 110 in "However, their is" should be "However, their algorithm is".
questions: questions: See weaknesses section.
limitations: limitations: The authors adequately addressed the limitations  of their work.
paper_summary: paper_summary: This paper presents a method to address multi-timescale model drift in hierarchical federated learning. Specifically, it introduces two control variables to correct intra-group client drift and group model drift. The paper establishes the convergence bound in a non-convex setup and demonstrates its stability against multi-level data heterogeneity. Overall, the paper is well-written and easy to follow.
strength_weakness: strength_weakness: 1. It would be beneficial to include comparisons of additional computational and communication costs of MTGC in the experimental section.
questions: questions: 1. In Algorithm 1, consider using different color blocks to mark $x$, $z$, and $y$. This could help in better understanding the algorithm's process.

2. How about the runtime of the algorithm? Would it be possible to include comparisons of runtime with the baseline in the experiments?

3. In the experiments, does Eq.5 require the addition of regularization coefficients for correction terms $z$ and $y$?

4. Could you include some measurements of the additional communication costs in the experiments?
limitations: limitations: N.A.
paper_summary: paper_summary: This paper proposes a novel algorithm called Multi-Timescale Gradient Correction (MTGC) for Hierarchical Federated Learning (HFL). The authors address the challenge of multi-timescale model drift in HFL systems, where data heterogeneity exists both within client groups and across groups. MTGC introduces coupled gradient correction terms to mitigate client model drift and group model drift. The authors provide theoretical convergence analysis for non-convex settings and demonstrate MTGC's effectiveness through experiments on various datasets and models.
strength_weakness: strength_weakness: - There is a lack of comparisons and discussions on clustered federated learning [1,2], which share similar context to some extent and could provide valuable background for the readers.


- The experiments primarily focus on image classification tasks. Including other types of tasks (e.g., natural language processing) could strengthen the generalizability of the results. There is a lack of experiments on various types of distribution shifts such as domain shift, label shift etc. Exploring different non-i.i.d. scenarios could provide more insights into the algorithm's robustness.

- While the paper analyzes model drift theoretically, there is a lack of empirical and theoretical analysis on how model drift affects generalization performance, especially in relation to the number of hierarchical communication levels. The study also does not clearly demonstrate in which scenarios and to what extent increasing the number of hierarchical communication levels benefits federated learning performance.

- The paper could also be strengthened by providing more insights into the practical implications of the theoretical results.

[1] An Efficient Framework for Clustered Federated Learning. NeurIPS 2020.

[2] Optimizing the Collaboration Structure in Cross-Silo Federated Learning. ICML 2023
questions: questions: Please refer to the weaknesses mentioned above.
limitations: limitations: The limitations of the study are discussed, and no potential negative societal impacts of the work have been identified.
paper_summary: paper_summary: This paper proposes a multi-timescale gradient correction (MTGC) methodology to deal with multi-timescale model drift. It introduces a distinct control variables to correct the client gradient towards the group gradient, and correct the group gradient towards the global gradient. Then, the stability of the proposed algorithm against multi-level non-i.i.d. data is shown empirically.
strength_weakness: strength_weakness: The model is tested on small datasets.
questions: questions: 1. What are the practical applications of HFL?
2. Are there any techniques implemented for preserving the privacy of the model?
3. The model has been tested on small datasets; how does it perform on larger datasets?
4. The ablation study is missing. How does the model perform when only one of the corrections is used?
5. How about the stability of the proposed method?
limitations: limitations: Yes

Comments: title: Post Rebuttal
Hierarchical Federated Learning with Multi-Timescale Gradient Correction
comment: Dear Reviewer r1S6,

Could you please respond with how you think about the authors' response? Please at least indicate that you have read their responses.

Thank you,
Area chair
Dear Reviewer fhg9,

Could you please respond with how you think about the authors' response? Please at least indicate that you have read their responses.

Thank you,
Area chair
Thanks for your feedback. We appreciate your time for the discussion. We agree with the reviewer that preserving privacy of clients is crucial in FL. Here, we would like to emphasize that implementing additional privacy-preserving techniques on top of each scheme would degrade not only the accuracy of our approach, but also that of the baselines (they also were not integrated with privacy-preserving techniques in their original work).

To demonstrate this, we have conducted an experiment to compare the performance of our algorithm with HFedAvg under the same $(\epsilon, \delta)$-differential privacy (DP) guarantees. We apply DP to the gradient to ensure sample-level privacy.
To implement DP, we employ gradient clipping followed by the addition of Gaussian noise, a standard practice in the literature [R1, R2]. This approach is applied to both our algorithm and the baseline.

Specifically, to guarantee DP, we replace step 7 of Algorithm 1 in the manuscript with the following procedures:

+ Compute stochastic gradient: $g_{i,m}^{t,e,h}, m=1,\ldots B_s$, $\forall i $ 

+ Gradient clipping: $\hat{g}\_{i,m}^{t,e,h} = g_{i,m}^{t,e,h} \cdot \min\left(1, \frac{c}{||g_{i,m}^{t,e,h}||}\right), m=1,\ldots B_s$, $\forall i $ 

+ Applying Gaussian noise to the gradient: $G_i^{t,e,h} = \frac{1}{B_s} (\sum_{m=1}^{B_s} \hat{g}_i^{t,e,h} + \mathcal{N}(0,\sigma_g^2))$, $\forall i $  

+ Local model update: $ \boldsymbol x_{i,h+1}^{t,e}= \boldsymbol x_{i,h}^{t,e} - \gamma( G_i^{t,e,h} +  \boldsymbol z_i^{t,e}  +  \boldsymbol y\_j^t), \forall i  \in   \mathcal{C}\_j,\forall j$

To achieve $(\epsilon, \delta)$ privacy, the noise should be set at the following scale [R1, R2]:
$$
n \sim \mathcal{N}(0,\sigma_{g}^2) ~~ \text{while} ~~
\sigma\_{g}^2 = \frac{c^2 \log (1 / \delta) THE}{(|\mathcal{D}\_i|/B_s)^2 \epsilon^2},
$$
where $B_s$ denotes the batch size.

The table below shows the results using the Shakespeare and CIFAR-100 datasets. For the Shakespeare task, we set $T=30, E=30, H=35$, $c=1$, $\delta = 10^{-3}$, $|\mathcal{D}\_i| = 1500$, and $B\_s = 200$. We compare their performance under a privacy budget of $\epsilon = 15$. 
The standard deviation of the Gaussian noise is thus $\sigma_{g} = 1.37$. For CIFAR-100, we set $T=50, E=20, H=20$, $c=10$, $\delta = 10^{-3}$, $|\mathcal{D}\_i| = 500$, and $B\_s = 50$. Under the privacy budget of $\epsilon = 15$, the standard deviation of the Gaussian noise is $\sigma\_{g} = 1.63$.


| Dataset  | MTGC  (w/o DP) | MTGC-DP | HFedAvg  (w/o DP) | HFedAvg-DP |
|-------------------|-------|---------|---------|------------|
| Shakespeare    | 46.42 | 45.50   | 43.16   | 42.95      |
| CIFAR-100       | 53.53 | 50.72   | 41.69   | 39.70      |

We see that, as expected, the noise injection process for guaranteeing DP slightly decreases the accuracy of both schemes. Importantly, MTGC performs better than HFedAvg with and without DP. We will include these new results in the revised version of our manuscript.

[R1] Abadi, Martin, et al. Deep learning with differential privacy. ACM SIGSAC, 2016.

[R2] Li, Bo, et al. An improved analysis of per-sample and per-update clipping in federated learning. ICLR, 2024
We really appreciate your reply and score update. We will include these discussions in the main body of the revised manuscript. Thanks again for the helpful suggestion.
I appreciate the efforts of the authors to address my concerns in their rebuttal.

After carefully reading the comments from the rest of the reviewers as well as the responses of the authors I have decided to increase my score. Specifically, the extensive description of the challenges and the techniques used to overcome these challenges (found in the rebuttal) are of crucial importance, helping the reader to better understand the technical contribution of this work. I believe that including this discussion in the main body of the paper will further improve its quality and presentation. 

That being said, I still consider the main weaknesses of this work to be its - somewhat limited - novelty and impact. Overall, I find this paper to be very close to the acceptance threshold leaning slightly towards acceptance (indicated by my updated score 5).
I thank the authors for their detailed rebuttal.

I appreciate the discussion on privacy-preserving methods. Although the primary focus of this study is to tackle the data heterogeneity issue, it is essential to recognize that this is a federated learning model, and the privacy of the data must be preserved. I assume that applying the methods mentioned by the authors could potentially degrade the model's performance.

I've read the comments and feedback from the other reviewers and look forward to the discussions following the rebuttal. I will keep my score for now.