Hierarchical Federated Learning with Multi-Timescale Gradient Correction
Authors: Wenzhi Fang
Dong-Jun Han
Evan Chen
Shiqiang Wang
Christopher Brinton
Venue: NeurIPS 2024 poster (2024)
Keywords: Federated learning
gradient correction
hierarchical
Primary area: other

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.

Hierarchical Federated Learning with Multi-Tiimescae Gradient Correction
Wenzhi Fang Purdue University f Fang3750purdue edu
Dong-Jun Han Yonsei University ajh@yonsei. ac kr
Evan Chen
Shiqiang Wang
Christopher G. Brinton Purdue University cgb@purdue,co edu
Purdue University chen4388@purdue..e edu
IBM Research
wangshiq@us: .inssiibm ibm. com
Abstract
While traditional federated learning (FL) typically focuses 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 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 hierarchical levels of data heterogeneity. this paper, we propose multi-timesalee gradient correction (MTGC) methodology to resolve this issue. Our key idea is 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//ggiibbb.cm///evv/raaaagat
model drift, i.e., model drift occurring across
Introduction
In the past several years, federated learning (FL. has emerged as a prevalent approach for distributed training [7 22
52 24 Conventional FL has typically considered a star topology training architecture, where clients directly communicate with a central server for model synchronization
355 26). Scaling this architecture to large numbers of clients becomes problematic, however, given heterogeneity FL resource availability and dataset statistics manifesting over large geographies In practice, such communication networks are often comprised of hierarchical architecture from clients
14 17 [0].
main server, as observed in edge/fog computing 25 38) and software-
defined 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 33 47] [5]. HFL (see Fig. [ 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.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 FI. performance according to the degree of non-i.id. (non- independent 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 result, model drift occurs across multiple levels of non-i.i.d. at different timescales. In the canonical two-level case from Fig. [ we have (i) intra- group non-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 individual datasets, usually 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 [8] and FedDyn I have shown promise for correcting client model drift through local regularization and gradient tracking/correction. However, these approaches are not easily extendable to the IIL scenario due to its multi- timescale communication architecture. Specifically, when integrating these methods into HFL, control variables introduced to handle data heterogeneity, such gradient tracking dynamic regularization, need to be carefully injected at each level of the hierarchy, taking into account their coupled effects in taming non-ii.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 (3 [ 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 [3 31. but they require frequent model aggregations to prevent excessive drift. We thus pose the following question:
How can we tame multi-fimescale model drift in non-i.idd hierarchical federated learning to prov- ably enhance model convergence performance while not introducing frequent model aggregations?
1.1 Contributions
Global asaropation perforted afler evens E group zaurogation Gooup eppreastion perficmne oftes every if local Reeuiioss
In this paper, we propose correction (MTGC), a methodology which can ef- fectively address multi-level model drift over the topology of HFL with a theoretical guarantee. As depicted in Fig. [] our key idea is to introduce coupled gradient correction terms - client-group correction and group-global correction - to (i) cor- rect 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 gra- dient, 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 HFI. We propose a strategy for updating these gradient correction terms after every group aggregation and global aggregation, respectively, and analyze the convergence hehavior of MTGG. Due to the coupling of correction terms and their updates being performed different timescales, additional challenges arise for theoretical analysis compared to prior work. We thoroughly investigate this problem and make the following contributions:
gradient
Central aggregtorr
Group alobal commetion
model datt.
Croup sugeceation
drit
Clist-groop
Cliest model drit
Clees
Cliest
11.
Labe's each clane
(4,5)
16, 71
labels: 3,
6,
Figure 1: Illustration of multi-timescale gradient cor- rection (MTGC) for multi-level non-i.i.d. in HFL.
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 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 thcoretical 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.
1.2 Related Works
Algorithms for conventional FL. The seminal work [35 developed the FodAvg algorithm, incor- porating 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 445 12], showing it is
not resistant to non-i.i.d. data. To tackle this issue, numerous techniques have been proposed in
57 16], adaptive control variables [29] 8 [1 [5], and/or gradient tracking methods 18 32). Despite these efforts, existing
the literature, including incorporating static/dynamic regularizers [27
1
FL algorithms are not easily extendable 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 hicrarchical model drift remains unsolved. Our paper addresses these issues through a principled multi-timescale gradient correction method.
FL branch, HFL, tailored for hierarchical systems consisting of central server, group aggregators, and clients. To tackle the issue of limited communication resources, the authors of (5) developed 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-HUU 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 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 culti--tmeecale gradient correction and providing theoretical insights.
Hierarchical FL. The authors of [ 30 B
49
55 47 explored
Gradient tracking/corrretton. 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 consider various factors like time-vary graphs and asynchronous updates [37 40 42 54]. Subsequently, SCAFFOLD [8] applied gradient tracking FL to mitigate the impact of data heterogeneity across clients, ensuring convergence and stability in non-i.i.d, settings. More recently, in [32 22. the authors demonstrate the effectiveness of gradient tracking in fully decentralized FL. where clients conduct model aggregations through local client-to-clien 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 Motivation
2.1 Problem Setup: Hierarchical FI.
We consider the hierarchical system depicted in Fig. [ The central server is connected to N group aggregators, each linked to the clients within its region, defined group. Each group j jE (1,2...... N} consists of a set of n, non-overlapping clients, denoted C,. resulting in a total of ΣS ny clients within the system. Each client has its own local data distribution D.. The goal of HFL is to construct an optimal global model xx considering the data distributions of all clients in the system. The role of each group aggregator j involves coordinating the training for the n, clients within its region, while the central server orchestrates the training across all N groups through
3

---

Local gradient each client #:Optimal point of each client
conecction
Cliant correction
Corrected gradient group
global coreecion
Corrected gradient group
Corrocted gridiett
Client
Cllentgrouup correction
Group uplimum
Group-plohal correction
Client 2
25
Clurrt
Global uptimurn
Client
Inital model
Inilial
Group
Inmail model
W2
Client 4
model
optimuum
2
2
(a) No gradient correction
(b) Only client-group gradiens correction
(c) Multi-timescale gradient correction (Ours)
Figure 2: Visualization of the local update process using multi-timescale gradient correction (MTGC) with 4 clients and 2 groups. (a) Without any gradient correction (e.g., hierarchical FedAvg), each client model moves towards its respective optimal point, denoted by æ;. (b) When only client- gieup correction term is applied, the model of client E Cj moves towards the group optimum æj. (c) In MTGC, the gradient client E C2 adjusted by both the client-group correction term 2; and the group-glohal correction variable yy, assisting each client model to converge towards the global optimum x. during local iterations.
interaction with the group aggregators. We can formally state the HFL learning objective as follows:
ming f(x) = N Σmn fz)), where f,()) == 1 n, Eiec, F((x)) and F((x) == EEND. Fz E.). (I)
Here, f Rdd RR denotes the global loss function, fn f Rd -> R is the loss specific to group j, and F; : IR + R represents the local loss for client i. In addition, &, is the data point sampled from distribution D. Note that our analysis can be easily extended to a weighted average form of (I) by incorporating positive coefficients for each (ax) or (x()). For simplicity, these coefficients are assumed to be included in Fi (a( as in previous works 18 48
2.2 Limitation of Existing Works
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 E Cj. and (ii) inter-group non-i.i.d., arising from data heterogeneity across different groups C..... CN. These lead to client model drift and group model drift, respectively. The model drifts induced by multi-level data heterogeneity 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]:
N E (x) f(())] < 67, Vo and ny Eiec, [[) (f)(1)) < 82 Ya, Vj. (2)
The first inequality is employed to limit the group drift, i.c., the deviation of group gradients from the global gradient, while the second one bounds the client drift, i.c., the divergence of client gradients from their group gradient. As result, the convergence bounds of algorithms in these works become worse as data heterogeneity increases (i.e., as 82 or 82 increase) [9. Our approach, developed next, does not require these assumptions and remains stable regardless of the extent of data heterogeneity.
3 Algorithm
3.1 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 æ satisfying V Vf(")) = O. Specifically, with as the learning rate, we have x * x <V F. (x"), as the global optimum x may not necessarily be optimal for each client's 's local loss due data heterogeneity. i.c. V ") # the client gradient V F.("")) to the global gradient vf(=") is thus necessary to stabilize the process
39
Correcting
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,
'We motivate our approach here using full batch gradients, though our subsequent algorithm and analysis will support stochastic gradients.

---

Algorithm 1: HFL with Maulti-Timescale Gradient Correction (MTGC)
Input: Initial model æ², glohal aggregation period E., group aggregation period H, learning rate 7; and LD 20,0
proup-global correction y ny Liec, VF (0 St,0
2=j=1 ny Liec, F (2 ( 5, Vjj
each global round 0, 1................
Group model initialization: z; 4.0 = Vj
3
Client-group correction initialization:
x -V $2,0++ n, Σiec, VFi 20.0) VEC,
each group communication round = 0, I...., Local model initialization: 2 =x); Vi,j
each local iteration h = O,I,.......
2// +y.) ViEC,, x 1 3 -7 (V [,))),)))))))))))00)))0).. +2,
Clients do parallel
Group aggregation: क..0
nj Liec, 2
Client-group corr. update: 2, zi,ttl
=2 Hy ( - = -,t C Vj Clients do in parallel
10
Global aggregation: a=* N 2===1 2..
Group-global corr. update: w,th U HBT 2) -x kj
Group aggregators in parallel
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-giobal correction. Specifically, desired iteration to obtain the updated model Unew at the optimal point x can written as
Feww x - o / Fzx(x)) + (=) VF (2
(V((=))VV((("
client-group correction
group-global correction
where (z)(x)) (x") and ff(=") (x") represent client-group and group-globe correction terms, respectively. Since V f((")) = O, the two correction terms will enable the model to remain at the optimal point. Given this intuition, the ideal local iteration client i Cj be written
3 7 (V.(
-V (V
}. (4)
L
where 1, e, and h represent global communication rounds, group communication rounds, and client local iterations, respectively, 3 = - E,Ece, T!; is the averaged model within group j. and my Σiec, te 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. (c).
a Σx=
Challenge encountered in HFL. However, it is important to note that the update process in still cannot be directly used in HFL. This 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 obtaín the current group information V V (= and global
information V ( at every local iteration. We next propose a strategy that mimics the gradient correction described above while ensuring theoretical convergence.
3.2 Multi- Times-ee Gradient Correction (MTGC)
model drifts. To approximate 4 during HFL training, we introduce two control variables and y that track//pproximate Vf, VF; and Vf fz. respectively. The variables z and y are then employed to correct the local gradients to prevent model drifts. The challenge here is keep updating 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 strategy to update 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 strategy to update y after every E group aggregations, i.c.,
Tackling
5

---

whenever the group aggregators are able to communicate with the global aggregator, enabling the global information be refreshed and shared across all clients in the system. We name our strategy multi-timescale gradient correction (MTGC) due to the updates of and occurring in different timescales, to tackle the issue of multi-level model drift coupled across the hierarchy HFL.
In Fig. c), we illustrate MTGC during client-side model updates. In particular, at each local iteration h of group round of global round t, each client i Cj updates its local model as follows:
i,++1 = 2ihh FV (a <1,
2/-- 93)
(5)
(i) Client-group correction term. In (5) x is responsible for correcting the gradient of client i C towards the gradient of group at the e-th group aggregation of global round l. After every group aggregation e at global round I, this term is updated at each client as follows:
E (,
VF <.))
V F. be 1,1 (1,h)
(6)
(ii) Group-global correction term. y in ( aims to correct the gradient of group towards the global gradient. At the end of global round i, this term updated at group aggregator j as follows:
E En
(*
1 ny Eise, (. <)
1 my Eiee, VF 4.)
Key remarks. The updating policies for z:ee and y follow similar patterns to the ideal corrections outlined in (4). Here, we observe that Exec, z/ = 0, Vj and Σ5 v = O. indicating that the correction terms do not have an impact on the per-iteration model averages. Instead, the introduction of the and y eliminates model drifts of clients and groups, respectively, during local iterations. Intuitively, as the iteration approaches the global optimal point, we expect 2 [=("=) Fi(("=) ) so that the update in (5) stabilizes at the global optimal point. We also see that 2, and y are coupled (5), i.e., the update of one of the terms affects æ which in turn affects the other one, raising challenges for theoretical analysis. In Section 4 will guarantee convergence of MTGC in general non-convex settings without relying on bounded data heterogeneity assumptions.
and y + [====) (fz("")
MTGC algorithm. The overall procedure of our training strategy is summarized in Algorithm [ where we rewrite the updates of 2 and y in different but equivalent manner to facilitate practical implementation 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;-" (Line and broadcasting y .+1 (obtained in Line 14) to the clients in Cj. 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
3.3 Connection with SCAFFOLD
When the number of groups reduces N 1 with E we have y 0 (no group-global correction), and thus MTGC reduces to SCAFFOLD I8] In SCAFFOLD, at each round t, clients perform local updates according to 2H = a/ - (wi - of + c²) h = 0, 1,..., H-1, where e. ct c' My (a' =(,H), and the server aggregates local models and controlling variables as #H y Em æ and cl t ΣN ett We can show that ci ct in SCAFFOLD plays the same role as 2 in MTGC. However, the additional term y introduced in MTGC for the multi-level setting makes the convergence guarantee more challenging, as J is coupled with z! and both are updated at different time scales. These aspects will be thoroughly examined next.
Convergence Analysis
In this section, we establish a convergence guarantee for the proposed MTGC algorithm. Our theoretical analysis relies on the following standard ussumptions commonly used in the literature on stochastic optimization and FL under non-convex settings [8
Thii is only required for theoretical analysis. In the experiments, we initialize z.-0 = 0, vi.

---

Assumption 1. Each local loss function F; is differentiable and L-smooth, i.e., there exists a positive constant such that for any x and y. [[VF;(z) VFlly)] - Liy x||,
The stochastic gradient F,, Ei) is an unbiased estimate of the true gradient, i.e. E,, [. E.] (x), Vx and the variance of the stochastic gradient V FF( E.) is uniformly bounded as VV Ei) (=))l I o0, Vx.
Assumption 2.
Note that (i) global aggregation, (ii) the update of upper-level correction variable y and local aggregation, and (iii) the update of lower-level correction variable are performed at different timescales in MTGC. we directly consider [Vf(=')} } as in SCAFFOLD, it is difficult to capture Moreover, it is hard to establish te
the effects of group aggregation and correction variable
fie tight connection between f((" and Like Vi, h, since there is large lag between 2i and 0 To tackle this, we introduce a new metric, which is the gradient ( at virtual sequence { N Σソー Aee, ) to characterize the convergence of MTGC.
We next state our main theoretical results. All the proofs are provided in Appendix F
Theorem 4.1. Suppose Assumptions and 2 hold and the learning rate satisfies S 40EH1. Then the iterates { obtained by the MTGC algorithm satisfy
1-
(f(*)) 7TEH
)12
11==0 =0
( "N"
2L0² (o2++PE21P
(8)
TE
where Ñ
N 25= and f is the lower bound of [xx), i.e. f(x)
There are two key steps in our proof. The first the characterization of the evolution of || +VF (+)")) (1]"")| and V/g (#*=0) -Vf (=*==)11. 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 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 I yields the following corollary:
Corollary 4.1. Under the assumptions of Theorem 4. let Fo = f( - Then there exists
learning rate 7 S WOEHL such that the iterates { (a. satisfy
T-1E-1
FoLa² NTEE + ( (Fotor
I.Fo
+
(9)
TE 10 0=0
T
T
Discussions. Corollary |.1 provides the convergence upper bound of the MTGC algorithm. It shows that the error approaches zero as T oc. a & O, 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 the stochastic case. This reveals MTGC achieves linear speedup in the number of group aggregations E and local updates H. In other words, with less global communication rounds, i.c., 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 case n2 Vj e 21,2.... 2....... N} with uniform client numbers, the rate becomes O Lo /FoLo//VNNi //NT//NTTEE) This implies that MTGC attains linear speedup in the number of clients as well.
attain the same level of performance
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 E (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 stable against multi-level non-i.i.d. data due to the multi-timescale gradient correction approach.
5
Experimental Results
5.1 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
7

---

PAININTA
Mackke
13PAR-18 E2PAK-31
Twetng (N
13
-3
99-
Figure 3: Comparison with FL baselines. In this experiment, popular FL algorithms are extended to the HFL setup for comparison with MTGC. We consider four datasets in the group non-ii.d. & client non-i.idd setting. Experiments are conducted over 3 random trials. We see that MTGC obtains the best testing accuracy in cach casc, validating our multi-level approach for correcting malti-timescale model drifts.
Locd Deovecos
Girap Corvettioo
CIPAR-1I
CITAB-100
Tooing Aecuee 190
Thitke Aeteery
10:
30-
Global Toazsds
Glibed Rocreds
Globel Bearsl
Glibel Reardd
Sortng Antien (M)
02-
Twitee Anmenay 196)
15
55
66
30-
Sootigg Arcuss 190
Teaite Anveaa 186)
16
5
23
100
100
Boaads
Global
Global Boazdds
Rlcaads
Figure 4: Comparison with gradient correction baselines. Three different data distribution scenarios are 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 ohtains the most stable performance (all rows) by combining multiple correction levels.
CIFAR- 100 (23] The former two are processed through 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 convolutional neural network (CNN) following the architecture outlined in seminal work [35]. For CIFAR- 100, we adopt ResNet-18 18 model with batch normalization layers substituted by group normalization layers. Across all algorithms considered, we maintain a consistent learning rate 7 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.d. & client non-i.i.d., (ii) group non-i.i.d. & client i.i.d., and (iii) group non-i...d & client non-i.i.d. scenarios. First, in the group i.i.d. & client non-i.i.d. case, the training dataset is initially divided uniformly and randomly into N segments corresponding to N groups Subsequently, each segment further divided into 100/N partitions for the clients using a Dirichlet distribution M. 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 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 Dirichlet distribution, and then, each group's 's segment is distributed among 100/N clients through Dirichlet distribution. The Dirichlet parameter is set to 0.1.
8

---

Table 5.1: The number of global rounds required by different algorithms to attain the testing accuracy of 80% for CIFAR-10 under different settings. Taking HFedAAg as the benchmark, we show the speedup achieved by MTGC and other baselines as we vary aggregation periods E and H. MTGC consistently outperforms basclines, and the speedup gets more significant as E and H increase. Standard deviation is based on 3 random trials.
Data distribution
Params (E, I/)
HFedAvg
Local Correction
Group Correction
MTGC
(10, 20)
144.3+3.441 (1x)
57.0+008 (2.5%)
72.0+ 1, (2.0x)
45.7+009 (3.2x)
(10, 30)
169.042.4 (1x)
(3.32)
81.3:1.2
37.3:19 (4.x))
Group iid client non-i.id.
(10, 40)
211.045,9 (1x)
15.3#1.2 (4.7x)
8. (25x)
32.0=0.8 (6.7x)
(10, 20)
144.3:3.44 (1x)
57.0=0.8 (2.5%)
72.0+16 (2.0%)
45.7=00.9 (3.2%)
(20, 20)
105.0= (Lx)
3100 (3.0x)
53.0 (2.0%)
22.3:00.9 (4.7x)
(30, 20)
82.71:2.1 (1x)
25.7: (3.2x)
44.7::0.5 (1.8x)
16.3= (5.1x)
(10, 20)
246.0=3.7 (Lx)
92.31177 (2.7x)
03.7111 (4.6%)
37.7 (6.5x)
(10, 30)
302.7+4.99 (1x)
88.0=1.6 (3.4%)
1.341.26669)
27.2112
Group nou-i..d. &
(10, 40)
320.0=2.4 (Lx)
91.7+12 (3.5x)
13.0#1660..x
21 (15.4x
client i.i.d.
(10, 20)
246.0+3.7 (Lx)
92.3+1.7 (2.7x)
37.7=0.. (6.5%)
(20, 20)
308.7+3.3 (1X)
74.31 (4.2%)
31.0=0.8 (10.0x)
18.7+17 (16.5x)
(30, 20)
344.7=4.6 (Lx)
85.7 (4.0%)
1.7=117(1344))
13.0+ (26.5x)
(10, 20)
363.0+ (1x)
11.7429.2..6
1..7412.(4.%)
5..7+ (6.7%)
(10,
>500 (1x)
127.7=2.9 (53.9x)
79.7 (56.3x)
78.7 (>129x)
Group non-i.i.d. &
(10, 40)
>500 (1xx
169.7=5.2 (>29x)
106.3+ (x4.7x)
31.7= (=15.8)
client non-i.id.
(10, 20)
363.0 (1X)
141.7+29 (2.6%)
83.7
52.7
(20, 20)
>500 (1x)
113.3=3.4 (54.4x)
45.3411.
25.0+1.6 (x20000
(30, 20)
>500 (1x)
86.7+2.44 (55.8x)
50.7+22 (59.9))
19.6 (x25.5%)
5.2 Results and Discussion
Comparison with conventional FL algorithms. For comparison, we first apply the well-known FL. methods, FedProx (27). SCAFFOLD (18), and FedDyn M. to HFI, by running their training algorithms within each group of the hierarchical system. We also consider HFedAvg [47] as baseline. Fig. 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- -IFAR-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) (z) to HFedAvg, and group correction (y²) to HFedAvg. These baselines can be viewed as schemes applying SCAFFOLD [8 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 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 higher accuracy. In the case of group i.i.d. & client non-i.i.d., HFeeAAg 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 advantagcous. Finally, we see that MTGC consistently outperforms basclines under all settings, where the performance gains brought by the mulli-timescale gradient correction become more significant when it comes to the group non-i.i.d.& & client non-i.i.d. case.
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 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 In addition, the speedup achieved by MTGC compared to HFedAvg gets more significant
Speedup in H and E. In Table 5.1

---

as E or H increases. For instance, in the group i..d. & client non-i..d case, MTGC attains 3.3 speedup when 10, H 20, which increases to 4.7x when E 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 the required number of global rounds of HvedAvg increases as data heterogencity increases, while MTGC 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.
from Table 5.1 that
Further experiments. Additional experimental results including the impacts hierarchical system parameters and the performance in 3-level HFL provided in Appendices Bnnd E
Conclusion and Limitation
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 stability against multi-level data heterogeneity. Finally, we confirmed the advantage of our MTGC through extensive experiments different non-i.i.d. HFL. settings. A limitation of our work 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.
We have proposed MTGC, a
Acknowledgments
This work was supported by the National Science Foundation (NSF) under grants ENS-2116111 and CPS-2313109, and by the Air Force Office of Scientific Research (AFOSR) under grant FA9550-24- 1-0083.
References
[1] Acar, D.A.E., Zhao, Y., Matas, R., Mattina, M., Whatmough, P., Saligrama, Federated learn- ing based on dynamic regularization. In: International Conference on Learning Representations (2020)
[2] Alghunaim, S.A.: Local exact-diffusion for decentralized optimization and learning. IEEE
Transactions on Automatic Control (2024)
[3] Bao, W., Wang, H., Wu, J., He, J.: Optimizing the collaboration structure in cross-silo federated learning. In: International Conference Machine Learning. pp. 1718-1736. PMLR (2023)
[4] Bottou, L., Curtis, F.E., Nocedal, J.: Optimization methods for large-scale machine learning (2018)
[5] Castiglia, T., Das, A., Patterson, S.: Multi-level local SGD: Distributed SGD for heterogeneous
hierarchical networks. In: International Conference on Learning Representations (2020)
[6] Chen, E., Wang. S., Brinton, C.G.: Taming subnet-drift in D2D-enabled fog learning: A hierarchical gradient tracking approach. arXiv preprint arXiv:2312.04728 (2023)
[7] Cohen, G., Afshar, S., Tapson, van Schaik, A.: EMNIST: extension of mnist handwritten letters (2017)
[8] Condat, L., Agarský, I., Malinovsky, G., Richtárik, P:: TAMUNA: Doubly accelerated fed- erated learning with local training, compression, and partial participation. arXiv preprint arXiv:2302.09832 (2023)
[9] Di Lorenzo, P., Scutari, G.: Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks 2(2), 120-136 (2016)
10

---

[10] Fang, W., Han, DJJ., Brinton, C.G.: Submodel partitioning in hierarchical federated learning: Algorithm design and convergence analysis. In: ICC 2024-IEEE International Conference on Communications. pp. 268-273. IEEE (2024)
[11] Fang, W. Yu, Z., Jiang, Y. Shi, Y., Jones, C.N., Zhou, Y.: Communication-efficee stochastic zeroth-order optimization for federated learning. IEEE Transactions on Signal Processing 70, 5058-500 (2022)
[12] Haddadpour, F., Mahdavi, M.: On the convergence of local descent methods in federated learning. arXiv preprint arXiv: 1910. 14425 (2019)
[13] Hosseinalipour, S., Azam, S.S., Brinton, C.G., Michelusi, N., Aggarwal, V., Love, D.J., Dai, H.; Multi-stage hybrid federated learning over large-scale D2D-enabled fog networks. IEEE/ACM transactions on networking 30(4), 1569-1588 (2022)
[14] Hosseinalipour, S., Brinton, C.G., Aggarwal, V., Dai, H., Chiang, M.: From federated to fog learning: Distributed machine learning over heterogencous wireless networks. IEEE Communi- cations Magazine 58(12), 41-47 (2020)
[15] Jiang, X., Zhu, H.: On the convergence of hierarchical federated learning with partial worker participation. In: The 40th Conference on Uncertainty in Artificial Intelligence (2024)
[16] Jiang, X., Rodomanov, A., Stich, S.U.; Federated optimization with doubly regularized drift correction. In: Forty-first International Conference on Machine Learning (2024)
[17] Kairouz, P., McMahan, H.B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A.N., Bonawitz, K.,
Charles, Z., Cormode, G., Cummings, R., et al.: Advances and open problems in federated learning. Foundations and trends@ in machine learning 14(1-2), 1-210 (2021)
[18] Karimireddy, S.P., Kale, S., Mohri, M., Reddi, S., Stich, S., Suresh, A.T.: SCAFFOLD: Stochastic controlled averaging for federated learning. In: International conference machine learning. pp. 1133-5143. PMLR (2020)
[19] Khaled, A., Mishchenko, K., Richtárik, P.: Tighter theory for local SGD on identical and heterogeneous data. In: International Conference on Artificial Intelligence and Statistics, pp. 4519-4529, PMLR (2020)
[20] Kim, H., Feamster, N.: Improving network management with software defined networking. IEEE Communications Magazine 51(2), 114-119 (2013)
[21] Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., Stich, S.: A unified theory of decentralized SGD with changing topology and local updates. In: International Conference on Machine Learning. pp. 5381-5393, PMLR (2020)
[22] Konecný, J., McMahan, H.B., Yu, F.X., Richtárik, P., Suresh, A.T., Bacon, D.: Federated learning: Strategies for improving communication efficiency. arXiv preprint 1rXiv:1610.05499 8 (2016)
[23] Krizhevsky. A., Hinton, G., et al.: Learning multiple layers of features from tiny images. Toronto, ON, Canada (2009)
[24] Lan, G., Liu, X.Y., Zhang, Y., Wang, X.:
Communication--ffician federated learning for resource-constrained edge devices. IEEE Transactions on Machine Learning in Communications and Networking (2023)
[25] Li, H., Ota, K., Dong, M.: Learning iot in edge: Deep learning for the internet of things with edge computing. IEEE network 32(1), 96-101 (2018)
[26] Li, T. Sahu, A.K., Talwalkar, A.. Smith, V.: Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine 37(3), 50-60 (2020)
[27] Li, T., Sahu, A.K., Zaheer, M., Sanjabi, M., Talwalkar, A., Smith, V.: Federated optimization in heterogeneous networks. In: Proceedings of Machine learning and systems. vol. pp. 429-450 (2020)

---

[28] Li, X., Huang, K., Yang, W., Wang, S., Zhang, Z. On the convergence of FedAvg on Non-IID data. In: International Conference on Learning Representations (2019)
[29]
Liang, X., Shen, S., Liu, J., Pan, Z., Chen, E., Cheng, Y.: Variance reduced local SGD with lower communication complexity. arXiv preprint arXiv: (2019)
[30] Liu, L., Zhang, J., Song, S., Letaief, K.B.: Client-edge-cloud hierarchical federated learning. In: IEEE International Conference on Communications, pp. 1-6 (2020)
[31] Liu, L., Zhang, Song, S., Letaief, K.B.: Hierarchical federated learning with quantization: Convergence analysis and system design. IEEE Transactions on Wireless Communications 22(1), 2-18 (2022)
[32] Liu, Y., Lin, T., Koloskova, A., Stich, S.U.; Decentralized gradient tracking with local steps. Optimization Methods and Software pp. 1-28 (2024)
[33] Ma, J., Long, G., Zhou, T., Jiang, J., Zhang. C.: On the convergence of clustered federated learning. arXiv preprint arXiv:2202.06188 (2022)
[34] Malinovsky, G., Yi, K., Richtárik, P.: Variance reduced ProxSkip: Algorithm, theory and application to federated learning. In: Advances in Neural Information Processing Systems. vol. 35, pp. 15176-15189 (2022)
[35] McMahan, B., Moore, E., Ramage, D., Hampson, S., y Arcas, B.A.: Communication--fficee efficcien learning of deep networks from decentralized data. In: Artificial intelligence and statistics, pp. 1273-1282. PMLR (2017)
[36] Mishchenko, K., Malinovsky, G., Stich, S., Richtárik, P.: ProxSkip: Yes! local gradient steps provably lead communication acceleration! finally! In: International Conference on Machine Learning- pp. 15769, PMLR (2022)
[37] Nedic, A., Olshevsky, A., Shi, W.: Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization 27(4), 2597-2633 (2017)
[38] Nguyen, V.D., Chatzinotas, S., Ottersten, B., Duong, T.Q.: Fedfog: Network-aware optimiza- tion of federated learning over wireless fog-cloud systems. IEEE Transactions on Wireless Communications 21(10), 8581-8599 (2022)
[39] Pathak, R., Wainwright, M.J.: Fedsplit: An algorithmic framework for fast federated opti-
mization. In: Advances in Neural Information Processing Systems. vol. 33, pp. 7057-7066 (2020)
[40] Scutari, G., Sun, Y.: Distributed nonconvex constrained optimization over varring digraphs. Mathematical Programming 176, 497-544 (2019)
[41] Stich, S.U.: Local SGD converges fast and communicates little. In: International Conference on Learning Representations (2019)
[42] Tian, Y., Sun, Y., Scutari, G.: Achieving linear convergence in distributed asynchronous multiagent optimization. IEEE Transactions on Automatic Control 65(12), 5264-5279 (2020)
[43] Wang, H., Chi, Y.: Communication-effiiiaiii federated optimization over semi-decentralized networks. In: ICASSP 2024-2024 IEBE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 13241-13245. IEEE (2024)
[44] Wang, J., Charles, Z., Xu, Z., Joshi, G., McMahan, H.B., y Arcas, B.A., Al-Shedivat, M.. Andrew, G., Avestimehr, S., Daly, K., Data, D., Diggavi, S., Eichner, H., Gadhikar, A., Garrett, Z., Girgis, A.M., Hanzely, F., Hard, A., He, C., Horvath, S., Huo, Z., Ingerman, A., Jaggi, M.. Javidi, T., Kairouz, P., Kale, S., Karimireddy, S.P., Konecny, J., Koyejo. S., Li, T., Liu, L., Mohri, M., Qi, H., Reddi, S.J., Richtarik, P., Singhal, K., Smith, V., Soltanolkotabi, M., Song, W. Suresh, A.T., Stich, S.U., Tarwalkar, A., Wang, H., Woodworth, B., Wu, S., Yu, F.X., Yuan, H., Zaheer, M., Zhang, M., Zhang, T., Zheng, C., Zhu, C., Zhu, W.: field guide to federated optimization (2021)
12

---

[45] Wang, J. Liu, Q., Liang, H., Joshi, G., Poor, H.V.; Tackling the objective inconsistency problem in heterogeneous federated optimization. In: Advances Neural Information Processing Systems. vol. 33, pp. 761 1611-7623 (2020)
[46] Wang, J. Liu, Q. Liang, H., Joshi, G., Poor, H.V.: A novel framework for the analysis and design of heterogeneous federated learning. IEEE Transactions on Signal Processing 69, 5234 5244-5249 (2021)
[47] Wang. J., Wang, S., Chen, R.R., Ji, M.: Demystifying why local aggregation helps: Convergence analysis of hierarchical SGD. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 36, pp. 8548-8556 (2022)
[48] Wang, S., Ji, M.: lightweight method for tackling unknown participation statistics in federated averaging. In: International Conference on Learning Representations (2024)
[49] Wang. 7., Xu, H., Liu, J., Huang, H., Qiao, C., Zhao, Y: Resource-efficient federated learning with hierarchical aggregation in edge computing. In: IEEE Conference on Computer Communi- cations. pp. 1-10 (2021)
[50] Wu, F., Guo, S.. Qu, Z.. Hc, S., Liu, Z., Gao, J.: Anchor sampling for federated learning with partial client participation. In: International Conference on Machine Learning. pp. 37379-37416. PMLR (2023)
[51] Wu, F., Guo, S., Wang, H., Zhang, H., Qu, Z.,, Zhang, J., Liu, Z.: From deterioration to accel- eration: calibration approach to rehabilitating step asynchronism in federated optimization. IEEE Transactions on Parallel and Distributed Systems 34(5), 1548-1559 (2023)
[52] Wu, F., Li, Z., Li, Y., Ding, B., Gao, Fedbiot: Llm local fine-tuning in federated learning without full model. In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pp. 3345-3355 (2024)
[53] Xiao, H., Rasul, K., Vollgraf, R.: Fashion-MNIST a novel image dataset for benchmarking machine learning algorithms. arXiv preprint
(2017)
[54] Xu, J., Tian, Y., Sun, Y., Scutari, G.: Distributed algorithms for composite optimization: Unified framework and convergence analysis. IEEE Transactions on Signal Processing 69, 3555-3570 (2021)
[55] Yang, H.: H-FL: hierarchical communication-eliicinnn and privacy-protected architecture for federated learning, arXiv preprint arXiv:2106.00271 (2021)
(56) Yu, H., Yang, S., Zhu, S.: Parallel restarted SGD with faster convergence and less communica- tion: Demystifying why model averaging works for deep learning. Proceedings of the AAAI conference on artificial intelligence. vol. 33, pp. 5693-5700 (2019)
[57] Zhang, X., Hong, M., Dhople, S., Yin, W., Liu, Y.: FedPD: A federated learning framework with adaptivity to Non-IID data. IEEE Transactions on Signal Processing 69, 6055-6070 (2021)
[58] Zinkevich, M., Weimer, M., Li, L., Smola, A.: Parallelized stochastic gradient descent. In: Advances in Neural Information Processing Systems. vol. 23 (2010)
13

---

Appendix
Connection Between HFL and Cluster FL
15
Additional Experiments on CIFAR-10
15
Experiments on Distribution Shift Datasets
16
Additional Experiments on CINIC-10 and Shakespear Datasets
17
Extension to the HFL System with Arbitrary Number of Levels
17
Proof of the Main Results
Preliminaries
19
Proots of Theorem 4. and Corollary 4.1
19
Proof of Theorem
2.2
Proof of Corollary 4.
22
Proofs of Lemmas F.2 F2.7
22
Proof of Lemmal F2.
22
Proofs Lemmas F2 and F2.6
24
E3333
Proof of Lemma F2.3
25
4
Proof of Lemma F
28
K3.5
Proof of Lemma 22.5
29
E.3.6
Proof of Lemma F2.7
32
Recovering SCAFFOLD's Results
34
14

---

A Connection Between HFL and Cluster FL
Our work focuses on HFL, employing 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 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.
B Additional Experiments on CIFAR-10
4, B1g
25
30, Ny
25,
Kjj
N - 50, xy
0.85
0.85
0.80
0::0-
0.50
0.90
6:25
6:20
14.20
0.20
Trattre
6.70
Comnection Commettion
Cannetion
Gommition
Gall Conmertonn
HEslAre
EPolivs
0000
11:2
0.03
[U90
Figure 5: Comparison testing accuracy versus global communication round across different system parameters under both group non-i.i.d. and client non-i..d. setup. E and H are set to 30 and 20, respectively.
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., ny 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.
Chll Lidd. & client mon-lad
Chll noni..dd & cliene Sidd.
Buth Chill moiild. & client non-lid.
0.85
0.85
0.85
0.80
0.80
0.80
Texine Aeoumn
Textng Ancumay
Toxtng Accumnyy
0.70
0.75
0.75
0.70
10, 8
70
0.70-
10,1 1f
70
0.
R 10,
70
10. 11
10. 11
E
10, 1
0.63
0.60
0.65
30
20,
30
20, 3 30
0.00
0.60
0.60
100
100
Rounch
Rounch
Rounds
Figure 6: Performance of MTGC under a different number of local iterations, i.c., H, and a different number of group aggregations, i.e., E. The number of groups and clients in each group is set to N = 10 and n = 10, respectively.
The impact of local iteration and group aggregation: Fig. depicts the performance of MTGC under a different number of local iterations, i.c., H, and a different number of group aggregations, i.c., E. It's clear that MTGC achieves speedup in the number of local iterations and group aggregations.
Communication cost comparison. Compared to HFedAvg. MTGC requires initializing the correc- tion variables at the start of each global round, which adds additionaly communication overhead. Specifically, for every E steps of group aggregation, MTGC incurs an additional communication cost equivalent to one transmission of the model parameters. In other words, the per-aggregation communication complexity of MTGC is E+1 times that of HFedAvg. To show this impact, we have added experiments comparing the communication cost and testing accuracy at the client side. This
E
15

---

Teeting
Rumning
SCAFRILD
Leditie
20.0 9800
8038
3040
13800
3000
SCAFFOLD
Commuication Coal (Mibs)
(8) Testing accuracy versus communication cost
(b) Running time comparison
Figure 7: Comparison of communication cost (a); and running time for attaining 75% testing accuracy and finishing 100 global rounds CIFAR-1O (b)
experiment was conducted on CIFAR-10 dataset with E = 30 and H 20 under both client and group non-ii.d. setup. The model and other parameters are the same in the original manuscript. The results are shown Fig. 7a The results demonstrate that MTGC achieves higher testing accuracy for 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 the CIFAR-IO dataset with E 30 and 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 neural network using backpropagation.
under both client and group non-i.i.d. setup. The model
C Experiments on Distribution Shift Datasets
SCAFPOLD
SCAFTOLD
HFWlAAg
StalPrux
FialPaux
Ohdeal
(a) Performance comparisons under label shift on (b) Performance comparisons under feature shift on Fashion-MNIST
Fashion-MNIST
Figure 8: Performance comparisons on Fashion-MNIS" under label shift and Pashion-MNIR under feature shift
To further show the robustness, studied the performance of MTGC under another two different non-i.id. scenarios: label shift and feature shift, as referenced in 33 These experiments were performed using the Fashion-MNIST dataset.
we randomly assign 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
For label shift 3 33
3 label shift adds more heterogeneity to this system. According to results shown Fig. Sa is clear that the proposed algorithm is more robust against data heterogeneity. Specifically, there is less oscillation MTGC compared with HFedAvg and the attained accuracy of MTGC in the given communication round is higher than all basclines.
16

---

MICC
MIOC
SCAFFOLD
SCAFFOLD
LEFolAvg
LiPedAvg
FedPProx
RedPProx
Chaned
Clobed Chesernintion Blrenh
(a) Performance comparison on the Shakespeare dataset hased on LSTM model
(b)
Performance comparison under CINIC-10
dataset
Figure 9: Performance evaluation on Shakespeare and CINIC-10
For feature shift [], first partition data following the group non-i.id. & client non-ii.. case as in our original manuscript, and then let clients at different groups rotate images for different angles. 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 this classification task. In Fig. 8b we see that MTGC attains the best performance among these baselines.
D Additional Experiments on CINIC-10 and Shakespear Datasets
We conducted additional experiments 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 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 3 times that of CIFAR- (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 [., and set the learning rate 0.5, the baseline methods in larger datasets.
75, and E 30. seen that MTGC consistently outperforms
The CINIC-10 dataset contains 90,000 training images, 90,000 validation images, and 90,000 test images, significantly larger than CIFAR-10 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-I0 task shown in the original manuscript. As illustrated in Fig. 9b) MTGC maintains its superior performance the CINIC-10 dataset, consistent with performance on other tasks.
E Extension to the HFL System with Arbitrary Number of Levels
We extend MTGC for the HFL system with M levels in this subsection. For presentation ease, we adopt different notations than those used the main text. Specifically, we denote the number of total iterations at clients as The aggregation periods for level are denoted as Pm. This means that the mith level aggregator aggregates the model from the clients within its coverage after every Pm local iterations. The global server is treated as the first level aggregator. Note that Pm. Pm+1 and Pm+1 Pm, Vm = ......,AA M 1. We denote the model maintained at the nodes connected to the m-th level aggregator (K1, k2,.................. km-1) o Tk..... where km {l,..., Nm). The gradient correction term between nodes (k), k...... ... km and (k1, K2...... The overall procedures are summarized in Algorithm
... km.) is denoted v ky..k.........
17

---

Algorithm 2: MTGC for the HFL System with Arbitrary Number of Levels
Imput: 7; {P:: : .,2
Initialize: U/j Kgg. Aa...... Vki, .2...., ..
0, 1,..., do each client (A1,.... kus) in parallel do Compute stochastic gradient: Db......ks
Fh. 4h, Ku -Y (g...... + Vhy + +b +...tttt... t tu km)
level i M,..., do
if P. r then
i-th level model aggregate:
s KI.....k Ng...Nar >N 2,;-1" NNN rr1 Recendder Vhi,....,
a+1
i-th level correction term update:
ka........kk Aeinn & 7hs KI...k a ske Model dissemination: o Ky. t rtl
10
Kki....yy Whi, KM
11
Initialize Vk K2......, Vk kaminn Vki, k2,... lim
12
else
Uk
whi 1 Mes A22 ... M banksnn
Mas keu..ke Vk .2,..., k.
14
break
layer aggrogator
My
level
(Av)
2+ layer aggregatior
Ps.2
(2)
2el level correction
(Rs Aa)
layer aggregator
M2,22
(1.1)
(2, 2)
y level conrection
(Ay Ag. As)
(1.1.)
(1.1.2)
(12,1)
(1,2,2)
(2,1,2)
(2.2.1)
(2.
Figure 10: HFL system with 3-level topology
CACNISTNG
CEPAB-1P
CEPAR--00
Vesting Genneyy (h)
50
100
25
20
303
30
110
118
Boands
Figure 11: Performance of MTGC for three-level HFL with data non-i.i.d. across each level. Parameters set to N₁ = 4, N₂ 5, N3 5, Pi 500, Pa 100, P3 10.
We numerically validate the performance of MTGC by conducting experiments the three-level case shown in Fig. [0] The results are shown in Fig. 11] The total number of clients is set 100 while Nj 4, N₂ = 5, N₂ = Additionally, the aggregation periods are set to be P 500, P3 100, Pa 10. The data is non-i.idd distributed across each level.
18

---

F
Proof of the Main Results
E.1
Preliminaries
Before 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 of K vectors (pElE=r
K
1/2 Pe
k E
2
R EE
R
EK k== Pe
3
<K
K k=
||px|
1 and
K
K
1
1
1 Pk
Pk
Pk
Ipk
K
K
Lemma F.1.2. For any two vectors p. E Rd, lp + qll S (1 + a) ||p|2 + (1+ 1) |l
Lemma F.1.3. Suppose a sequence of random vectors k= satisfy E[pa] 0, Vk. Then,
K
E
Pk
E 1
Suppose a sequence of random vectors {pulk=1 K Elps PH-11PP-2........ PI O, Vk. Then,
Lemma F.1.4. 446
Lemma 2]
satisfy
K
K
E
P
E
| 112
Lemma F.1.5. (1 Lemma 17] For any 0o 2 0, 2 0,C 2 0,
> O, there exist constant 1) S 1
such that
1/2
ao Tn + by + en2 <
agb T
+ 26
ao
dao
(10)
T
T
F22 Proofs of Theorem 4.1 and Corollary 4.1
For the convenience of presentation, we introduce the following notations
F-1
N
R-1
N
Σ
E
E te
VE V.J -V
(z)"0)²
<=0
iEC
F-1
Σ
E |
V.z (0t.0)
V (
N
e=0
j=1
6=0
E-1
D. =
Σ
E
25.0
(11)
e=0
F-1
# 1-1 sEC,
Q
B
NH
h=0
N
E-1 1
where 2, and y characterize the biases between client-group correction term z and VF, (a) f (z) and between group-glos gooual correction term y and f ( (**s), respectively, D, and Q, denote the group model drift and client model drift, respectively, and 0) represents model progress for group j.
To prove the convergence of MTGC, we start with characterizing the evolution of the global loss, i.e. f(x) through the following lemma.
19

---

Lemma F.211 Suppose that Assumptions Algorithm satissy
and
then the iterates generated by hold and v 2HD
R-1 B V
N
Ef( <Bf(
+yL'H (Q.+D.)+ LEH +
0
(12)
N
Lemma F.2. implies that need further study the evolution of Q₁ and Dr. In particular, establish upper bounds for Qi and D, in Lemmas F.2.2 and
F.2.3| respectively.
Lemma F.2.2. Suppose that Assumptions and hold and y S 8HL' then the client model drift Qu.
defined in 11). can be bounded
Qe 524 H² 12 H
2 + 127
(13)
E-1
24 2 H²
E
/
3EHH" 0².
Lemma F.2.3. Suppose that Assumptions Dr, defined in (I), can be bounded as
and
hold and 7 S TOFHT. Then the group model drift
N
D. s 24 2 +
+
(14)
N
The results shown in Lemmas F.2.2 and F2.3 suggest that Zj and y are crucial for understanding the dynamics of MTGC. Hence, we derive upper bounds for z and Y which are presented in Lemmas F.2.4 and F.2.5 respectively.
Lemma F.2.4. Suppose that Assumptions 7 and 2 hold. Then the bias between client-group correction term and F,, (z),)) f (a)"), i.e., 23e can be bounded as
E-1
E-1
N O
ΣNΣ 4L 4
Σ
Σ
22
+2
-200++00
(15)
Lemma F.2.5. Suppose that Assumptions 7 and 2 hold. Then the bias between group group-global global
correction term y and V, (6t--) V (.tt.e i.e. Y defined 11.. Z 1, can be bounded as
y 2 (SL2
(Qm + Da1) + 48 2 L E H² (Q.
E 1
4 F. 2
[|
-B
||
(16)
2
2 1
n
Additionally, when 0, y can be bounded as
Σ
5
<E
N
0²
=0
(17)
In addition, the upper bound of 6 is presented in the following lemma.
Lemma F.266. Suppose that Assumptions 7 annd hold. Then the group model progress at the (1, e)-th
round, i.e., 0 defined in II), can be bounded as
3
rte
(18)
E-1
N
+ +8 2 2
Vf (8
(1')
1|
+
+ EH
n
20

---

Recalling Lemma 12.ID. we can see that what we actually need is the evolution of Q₁ D.. With
Lemmas F.2.2 F.2.6 we can characterize this evolution which is formalized in Lemmal F22.7
Lemma F.2.7. Suppose that Assumptions and
hold and r S 33EHL the model deviation
I Qi D, satisfies
T, T + (1152~<1' 11''
722
E H
[| + 2917 E Ho²
2
E-1
To (6187" 11"85"'1'''' +222 E I
El| V (*")))
+146
e=0
The proofs of Lemmas F.2. F.2.7 are provided in Appendix
F33
With these lemmas, we are ready to
prove Theorem 4.1
F221 Proof of Theorem 4.1
Starting with Lemma F22 i.e.,
7H E-1
Ef(x - HT', <BI(w')-
Σ E V
LEH
(19)
2
N
where 1 = Q + Dr. Adding 2yL² HI', on both sides of the above inequality and utilizing Lemma F2277 we have
,T + + HT 7 E-1
LEH
N T2j
B-1
x 2 HO² (23047 H + E H
V ||
+ V
For notation ease, denote 1 E
Ef( - f-
- +2 v 2 0. Vt > 0. As long as
in Theorem 4.1 2304 < 3 we thus have
8HE
7H R-1
R-1
4.11 50.
+80 3 1,
(20)
+2yL2 x 291
2 Ho² +
LEH
N² j=1 n2
When 7 S 4 we have
360 3 3
Telescoping the above inequality from
t 1 to T - 1, we have
Φ <
7
E Vf( +180 F
||(
(21)
25 Ho -
02
N7
1=1
According to Lemma F2.1 when t = 0.
7H E-
Es(ō') SEf(#))
>
E
El|
+ + HT LEH
(22)
2
N2
T2y
emu
follows that
Ef(2') + SEf(# 7H F-1
N
LEH Vf(*0>)) 2 HT LEH
1
(23)
N2
n,
21

---

Combining (23) with (1 and plugging the upper bound of To. established in Lemma F22.7 into the inequality, have
N 1
Tr <BS(x') - +2, H x 1467 E o2 + +2-TL' x 2927 E HO² +7
TLEH
N2
7H
1807 $ F. 11² (0 F3
11
B-1
Σ
V.
2
H T-1E-1 [ t=l
The setup of 7 presented Theorem 4.1 is enough to guarantee 24 12 (648y* 4 HH +-2 =2) 2 ?H Therefore, combining the last terms and taking some basic algebra operation, we have
1-18-1 ΣΣ I=U
B
E
+
Σ 0² jml
N
1168
TE
YTH
N2
n2 T
The above bound can be further simplified to
T-1E-1
B(()))
فماا 2
TE EE 21
+1
(24)
7TEH
N
This completes the proof of Theorem 4.1
F.2.2 Proof of Corollary 4.1
Rewriting the bound in 24
[ ||?
(EF( T(yEH)
4Lo"
(3 (*HH))
(25)
TE
NEH
and recalling Lemma F.1.5 one can claim that there exists a learning rate (TEH) <
such that
12
((()))-+)La
(Ef(x²) (Ef(x))-S"'LL L'')
d(ES(=))-S)
E
||
96
+
TE
NTEH
T
T
FoLoz NTEH
(FoLo) T
3
dFo
0
T
(26)
Given that we need 7 S 10HHL for Theorem we can set 40L. We thus can find step size in the range of (yEH)= S 207. i.c., 7 S 4EF.. such that
T 18-1
ΣΣ
E|V so VYTEE +
co
(V
T
FoLo
+
LFo
(27)
TE
T
This completes the proof of Corollary 4.1
E3
Proofs of Lemmas E2.1 F22.
F33.1 Proof of Lemma E2.1
Under the framework of MTGC, the virtual global model obeys the following iteration:
H-1
4 1
(VF (ait 2. +9
nl 1EC
km
22

---

As Liec, ===
= 0 and Σ)= f3 = O, the the virtual global model iteration reduces to
a @
F (et <1,0)
(28)
ieC h=0
With Assumption we have
f(U) s <<a))<<\((a)))
- x> +
+
11 2
(29)
2
Plugging
28
into 29
we have
N
H 4
(f( <Bf( -BB V[(("')
1
VF (ie
N
n1
5=1
iEC; h==
(30)
N
F, (a (1,n))
n
kee,
h=0
T2
Utilizing E Eiec, En=o
(at: ct1))
N E Ene,
1
0, we
rewrite Ti as follows
N
H-1
Ti -HE V)(E")),
VF((o()))
NH
Tīj
F=1
iECg
1m0
N (ā)t")
H 1 ΣΣ
7H - V ((
V F
V (w
NH
1ly sEC h=0
H
N
#-1
2
NH
Tij
IEC;
Σ
V
S5 (
HH
(
ΣΣARANNN
NH j=1
Ø=1
ieC;
7H1 E 2
E
Pi (xf
2
NH 1=1
veC, h=0
H-1 V
HHS N
B\ - A5
|| +
NH
IEC h=0
H
||| 0||
7H
E
(
2
2
NH
==1
KEC
hm0
SHHL'
Σ E -0 1/-1?
+
N 1=1
NH 1=1
7H
HH R
2
N
n
iEC,
h=0
where the last inequality comes from Assumption
I
23

---

On the other hand, we can bound Tp as follows
72 1
(V
(.(())))
+E
F (1)
nl
iEC
KEC)
E
Σ
gihh
(1 5
Σ
N²
iEC,
Ho² N
+
VF (2
IEC
h=0
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₁ and T2 into 30 and utilized 7 S 2HL we obtain
Ho² N
Ef(Ahett) SRf(ahe)) - THl
E //((te))1
7
+
Σ
1
2
N2 j=l n2
N Ø-1
N
+YHL² 1
E
the
te
+
HHI?
Σ B
te
2//011
NH
ny
N
h=0
iEC
==1
Telescoping the above inequality from = 0 to H-1 gives rise to Lemma F2.1
F.3.2 Proofs of Lemmas F.2.2 and F.2.6
Part I (Lemma :2.2: : Let 9gth = 1 ny Eiec, E a
- -
1e 1 te
44,0 =0. 0. For 0 H we have
Σ E 1 - (VR (o +1 + -
IEC
<
1+ H-1
E 1 x 11 + H
E ||7 (V +x)+))+++++++1 +o
#EC,
|+ H-1
El El क + 2
E V.,
(2 V
VR
(2/1)
iEC
FVI, (a'-7) F V/
+b/ + + nyn
< 14 #-1 +4.2H1²
EEllat - 2/
4.7 2 H Σ E ||
vF. (क) -V,, (1)
Tec,
iEc;
4,² HnH u/ V (8
v (6
||
+
8 2 HL
n
- i" E
Hn V (1'
+ 0
where the first inequality comes from Lemma F.1.2 and Assumption 2 and the second inequality
follows Lemma F.1.1
Let PI = 1 + - 42 2 As 7 S aHL we have p < pf H-1 <
H-1
(1 +
S Seg
<3 and EH1 o S 3H, where eg denotes Euler's number. We
1-1
16
H
1)
24

---

thus have
Σ pi)
17/ F + ( - (1))) +8 -
iEC;
+ +47 Hn,BB |1/// + V.4 (z) / 8, Hr
+ m))?0²
$129 H² Σ B + +VF (a))) V +1 H
(E' -V (
+24 H L n, n, |ي where the last inequality follows Assumption
+24 ,
( +3
Plugging the derived upper bound of nggjiht into Qi E
1 N Σラ= [ Emo giah) gives
rise to Lemma E2.2
Part II (Lemma F2.6; First, x//t1 = =t +
+ H- 1 m== ny
Eiec, (VF. (iitt Si,h +2, + n₁)
st.c)
As Eiec, 2,"
0, we can rewrite 0
H
V ( (t.) +
0/-- E 1
E
h=0
iEC,
Next, we establish an upper bound for of as follows
=
(V
+2
(2 ( v (2)
T
A= T1i VECs
h=0
KEC
#11
<27²11 H
Σ km0
E
1
VF. (a) + +
+ 2
Σ
(V
fi ( i,h+
<:10
vF, (a
Ti
iEC
iEC
H-1
+ 2 Ho²
<27²11 H
E
VF. (M F FV (3) F AL ( +4ب
Ti iEC
11
h=0
111
<87 21
E -
1T 1 + Viz (5 Vʃ (3*
h=0
ICC
HO²
8 11 11'
a 1 +
( [1)
2-
ny
where the second inequality holds due to Lemmas F.I.I and F.I.3. the second third inequality comes from Lemmas F.1. and Assumption
2, and the last inequality follows Assumption [ Plugging this
upper bound into 2e=0 N カ
F-1
0 gives rise to Lemma F.2.6
F.3.3 Proof of Lemma F2.3
To bound D.- = De- 1 N
E5 Bgllate - 1/
we first rewrite 1R Bllatett gget1| 2
as follows
N
1et1 3 - 2
H-1
=E
1
(VF
(a) <.1) + 2) + 2(-)
n
iEC; h=0
N
#
7
(V F
(x) h
c(:) 2) + +
N j=1
iEC h=
H-1
N
1
E
Σ
2 +
VF
(of
Σ
n1
iEC, h=0
==1 n
IEC
h=0
25

---

where we utilize N ش/= w² =0 =0and and xj Eiec, z = 0. Next, we bound Bl|a)tt]
1/ as follows
El
[ gettt - 11
H-1
H-1
1
E E||20
1110 + +7 EE
Σ 5J
VE (.))
E --1
iEC
M-1
FR (.)
Σ
VF (2tt)
VF (a))))
Tl
Tl
ny VEC
6=0
FEC
EE
h=0
+ E
E 1 1 2
+ +2y FR
Σ V
(
VR, (mf(1a)
A=0
VEC
sEC
+ +2 FE
VR
Σ VR, (aiAa)
h=0
ICC
h=0 sEC;
8-1
N
Σ
Σ
VR (4 (.
Σ Σ
Σ VF. (20t:1)
n2 sEC,
n
j=1
iEC,
where the first inequality comes from Lemma
F.1.2 We thus have
E |
5 2
N
1+
B
E
N 1=1
+ 2 EH2 2HH2
2
1
E
V (w
v F: (at
N
j=1
H
h=0
n1 iEC
N j=1
n
iEC
N
#-1 Σ
(31)
22 F N
N 1
R
Σ Trj sEC;
Σ
v.. (af(
KEC
h=0
<
1+ E
1
N
B| 1100 +
EH
1
N
1 22
N2
3=1 n1
+ 2222
H E
+
VF. (x)
VF (x.11)
N j=1
iec
26

---

where the first equality comes from Lemmas F.I.1 and F.1.4 Additionally, we bound T3
and the second inequality follows Lemmas F.1.3
Ta-
E
33
VF
V
(ath))
N
Th IEC
N
k=0
VEC
H-1
E 3
-
(+
+
E
Σ
VR. (aita) - v, ($
nj
SECs
1 N
Σ
Σ
VF (1f - vs (a
iEC;
H-1
22 N
1
|
f3
)1+
+2
1
Σ
1
1
Vi (2 - VS (0t)))
H
N
n4
h=0
y=1
iEC,
<17.2 1
Σ
=
+ A1,2
1
Rl|aa 100013
N j=1
T2j iEC;
H
N
h=0
N NV
2
B
+
Vi (1 - VS (1**)))
j=1
where the second inequality follows Lemma F.I.1 and the last inequality follows Assumption I
Plugging the derived upper bound of T3 into 31 gives rise to
N
1'= 1+ E-1
+
11
2
Σ
0²
N
N2
j=1 n
N Σ
4-7 2
El Elb V.J (0 ( || EH
Σ Bla 2²) 1/.
N
N iEC,
j=1
h-O
Let
P2
1
B-1
+ EHHLL
As 7
S
I0EHL.
we have P2
S
P2 F-1
[ +
+ 12(E-1}
S e _
< where eo denotes Euler's number. Therefore, we have
E-I
1 N
E
1 h--1 0//0t11
N
j=1
N
2
27 FH
N
1 0²
2
1
Σ
|3 + V& (0* - Vs (at"1))
N²
n2
N
H
+ +8max EH 2
B Bl - 13
N
H
w=
1=1
iEC;
h=0
N-1
N
N
$6>2 + 1)HH
2
2
E |3 +
Vi (at"") v (1
N2
j=1 n2j
P=0
+ 2AH2? 1.2
T3
1
j=1
iEC
(32)
Hence, for D, = Σ ===
1
Bi
we have
N
N
E
D. 53323 11
1
+
12
VV
(atie)
(
N2
==1 n2j
N
e=0
1=1
(33)
8-1
+ 24 2
1
B
be
1
H
J-1
h=0
This completes the proof of Lemma
F23
27

---

F33.4 Proof of Lemma F22.4
Fore = 0, 2
4.0
VFF
03.0: S1.0)
1,0 ct.u)
+ L
n, Eiic,,
1.0 VB,
03,0: $0.
where 2/ = 27.0
we have
2,
1
B
VF (z)
1.0
:5,00)
21.0
VF (α) 4.0
(459)
Tij aEC;
iEC
(34)
V..
(5) )) VF (a) 11 < o²²
n sEC,
where the first inequality follows Lemma F.I.1 and the second inequality holds due to Assumption In addition, when e 2 0, z obeys the following iteration
2
00.0 ny IEC
x0,6)
Hy
H-1
(VF: (a)
+2I - 2(/0)
Σ (VF
H
Mi 1EC
h-o
As Eiec, 2i
O. we thus have
Gel
1
Vii (o (.1) (af <hi)
EEC
To establish an upper bound for
E-1
EN
2-0t1
we start with bounding Zj/º as follows
N L==1
Zj0tt
E
VR
VB (ml
+VR
(at
Vzz (afett)
KEC
IEC;
111
H-1 H h=0
E
VF (a 1
vn V1
Vv (a +,,0
T1 iEC,
H
h=0
iEC,
1 Σ E
VA ( b
vr
iEC,
#11
Σ 18
H ΣΣ
V (at
VA (2/ (., F VA (zt
n iEC
h=0
<2 R3 IEC
Σ
V ( V (xfia))
+2
VE - VA (2 (21)
n2 sEC,
VF (Il +2 o²
<2 11, iEC;
E VR (
2,,||" +2 o²
221² 12
-
H
<AI,2
H-1 Blaad
15.011 +
41. || 15.011 +
0²
n
FEC,
(35)
where the first incquality comes from Lemma F.I.I the third inequality follows Lemma F.1.4 and Assumption 2] and the fourth inequality follows Assumption thus obtain Lemma F2.4 i.c..
[ Combining this bound with 34
E o +2 2 2² + o
Z < 4 + 412
(36)
H
e=0
28

---

E3.55 Proof of Lemma F22.5
be Part I (t 2 1): As Esec,
0, the updating rule of y can be simplified as
2i
V/ 1-1 1 R- H-1
1 E-18-1 IVR
ΣΣ N 1=1
Σ Ec,
VA
(2 (11)
ΣΣ Σ
(37)
EH
ny
EH
ny BEC,
7=0 h=0
D=u kmd
We next bound Y4 as follows
+
VJz
Vff V ($t
N
E 18-1
1-18 Σ VP, (a (t.) EH
E
Σ
VF. (t.)
N
EH
ny
ny EEC
1EC
+ +VIJ (a (1))
vs (a 1| |
N
Σ
E
(V
45) + VVA (c(N))
N
EH T=D
n2 GEC
h=0
B-18-1
ViJ (#
Σ T=0 AmD
vF V (a)ta)
Σ
N
EH
1=1
B-1 Σ
+
2
E
(VR (a h <,) - VA (at:a)
NE
HEC
R-18-1
2
ΣΣΣΣ
E
VR (a (m))
v. (attl.r)
2 1
0²
NEH
EH
N J=1 72-
2
E VR (x:
VF (*ttle)))
)|(
2 1
1 0
NEH
EH N 1=1
72-
IEC
NEH ΣΣΣ E 7= J=1
2L
B-1H-1
2
1 1 2
EH
N
Vec
(38)
where the first inequality holds due to Lemma F.I.I the second inequality follows Lemmas F.I.I and F.1.3 the third inequality follows Lemmas F.I.I and F.1.4an Assumption [ the fourth inequality
follows Lemma F.I.I and the final one comes from Assumption [
Given the above inequality, it follows that
E-IR-I N NEH 7=0
N
yol 2L
Σ
El - x 102
2
n
H
N
1=1
hmD
3=1
(39)
Additionally,
B |
s 11
<B ||
F Fa3 a F g2
<4 | x 11a + 4E |:077 11'
(40)
EE
||| - क 11 + ME + 4 1
which implies that we need further to bound E - ||0677 Under the framework of MTGC, the virtual global model obeys the following iteration:
1| and IE || a 4t1
* L+Le
(VR (wtt) (ith + 2l 24t1.1 + ))
IEC 7=0 KmD
29

---

As Eiec, 2,t1,,_ = 0 and و== f/ f-1
0, the the virtual global model iteration reduces to
1 ΣΣΣ VA (.t"""""""))
x
f2 SEC, ==0 h=0
For E ||
1 ||²
we have
E 1 02
x 11
N N
H-1
1-11
=y²F
Va (
nlj IEC 7=0 h=0
ECC
7=0 h=D
N fly
H 1
H-1
$
Σ
(a(
n2y IEC, h=0
iEC, 7= h=
H-1 V (I.T
+ B
n iEC,
c- Ø-1
H-11
22 N2 1=1
E
Σ
VR Sit (l
ΣΣ
Fx (1))
KEC,
h=0
7=0 A==
N
Ø-1
2 E
(
N
J
j=1
iEC
+=0 h-U
11-1
EHH N2
N
229 eH
VF (w 41 F
Σ
( (((
+2y
n iEC
==0
j=
<602 eH
c-14-1
( Hl. (.5
+ 2
2
EH N
1 5
カh EEC
c-1 H-1
+6y-eH
( - (5(
+ +6y2HH
E Vf(
T=0
T=0
2 EH
- + - -
LEH
B |
iEC
+ 67²
E 2
E
+27
2
EH
1 723
0.
N
(41)
where the second equality holds due to Lemma Assumption 2 the third inequality comes from Lemma F.I.T. the last inequality follows Lemma
F.1.3 the second inequality follows Lemma F.1.4 and
and Assumption I
Similarly, we can bound E || z42 |
as
E - z 44
<6² 2 L2 EH
13
pot -
1 +6 12 EH 2 Σ
7'=0k=0
n2 iEC,
(42)
+ 63 EH²
E
V ||²
+ 27
EH
1 0²
N2
72-
30

---

Given 41 and 42). it follows that
E| El 1/ + E || 142
EHH Q+1 + L2 Des + 6y EH²
E-1
E =|<
+
27
EH
N
Nº 1=1 11j
(43)
+ 6 2 D. + 6n E
E \
27
EH
N
Combining
39
and 40
we can obtain
ttLe
8-1
2 N
<2L
E
- 10
0²
NEH
n2 EEC
H N
j=1 R2j
6=0
+=0
K=0
(44)
H
E-1 N
S8L²
B
23-1
+L8
+LL
1 N
Σ
E ||
-
NH
T-U
h=0
SEC
T-U f=1
R-1
R-1
2 N
8L
B |
2411"
+ 8L
Σ
B1 44
x 42
0
H N y=1
n23
T=0
e=
Plugging 43 into
44 we have
E-1 Σ
< S8L2Q,+ + + 2
H
1
2 1 H
N
flj
72j
j=1
j=1
E-1
187
(
+18 2.
D 1
VJ
Part 11 (t = 0): On the other hand, when t 0, we have
N 1=1
Σ
E
V
200 1 1
Vii de ((0) (z - vf (8
N
KEEs
iEC
Σ
V/ VF -000 + (x
VVR(E -
Vl (=9)
N Ø=1
iEC,
E-1
E V (#
\ V (
1=1
N
E-1
L
B 3 -1 -811
31

---

Similar to
41
we have
8
c=0
E
11-1
N
E
L6'L
B
| - [1
10
EECs
E-1
E H
+
Vf
27
Σ
N
n2j
Combining the above two inequalities gives rise to
Do
SE
Σ R )|
nlj
+ 2 L
F
N N
1 0²
n
To this end, we complete the proof of Lemma F.2.5
E3.6 Proof of Lemma F2.7
E-1 Part I (t 2 1): Replacing Le=0 N Lj=1
Le in 15
with an upper bound established in Lemma
F2.6 (i.e.. (8)). and then plugging it into
13
we have
E
N
Q. 524 2 D. H²
4L +
8
H²
Σ
N
emm
48y2 2
B-1
E.l Vf ( (1 ||2 +22 F.
1
0
+2 2
0
N
n2
11
==1
1-
+12
the + 24 Σ
V
|| + +3HH220
(45)
-(48>² H² La + 3847 * L") Qc+ (24 H
3384 L*) D.
21
B-1 N
+38817 H 2 +2 H²²
Σ
E V/
(384 H² 127 H²
Σ
y
cmd
+96, 1?
-f 2
2
+12
Summing (45) with the inequality established in Lemma F.2.3 and utilizing the upper bound of established in Lemma F.2.5 we have
ΣB-1 N j= yie
Qi+D. D.
H L +24 E 2F
D.
+ (3847* "H
E V f (1'-))1
+ 12,
(8L2+4872 2 (Qm + Daa)
V
+ /
2.2 2 H
0
1
3
2
1
NZ
HN
1=1
1=1
N
+907* "
1
1
0²
+277
2
EHo²
2
H
N
1
N
n2
N2
n,
32

---

Reorganizing the above inequality gives rise to
Qi+Di
< wwwp://www.aat.........../////..
x x,0- +
+ |1
8-1
[ || +
+ (3817/ 1 12 2 2 E2²22= 327 12
1
1
N
flj
H
+96,"EH*
N Σ +2 "
N
N
n
N2
When S FENT. we have 28 < and
(1 (1- 10= (Qu+t))))))
(Q++
$
H (Q+1 + D--))
(46)
N 1 0²
n2j
N N N2
+96" EH 1,2
1
Σ
1 _ 27 EHO 2 + 12 H +3
1
N
1=1 n1j
As S 3EEHL we have 1- Hence, (46 can be simplified as
11 43 N and 3840
120-² 12222+ E 1 < 3.
1 D. S (Q Do "2
R-1
" + 0(7,07),
where
N
017,02) - -172811 H L1 +216 2²2 22)
1
o²
+
144
EH
o²
N
f2j
N
+ 2 2 5 E
H
N
Further, we establish an upper bound for Φ(7, o²) as follows,
-1288) 12 π
+14, 1 o²
n EH L"0 2
216 E
+12HH+18H2+5
E H
n
7
$1728 EH L2 0²
11728~>EH31
EH L'2
2 2
+281
HO²
n
5294">
where the last inequality holds due to 1 = Σ 1 < and <
VRE < 3ЗEН..
12HL
33

---

Part II (t = 0): Summing 45
with the inequality established in Lemma F.2.3
and utilizing the
upper bound of _ 2ー=1
established in Lemma F.2.5 we have
To (187 3 1²' 1. 2 "
To + (381" 244 HT
V )|
+ (3817 "10 1,2 12 212 + +12 2
E.
1 0²
B-1
E² H
L3 H² emU
E (
+ 2-
Σ
N
R
j=1
+967* +967"EEHTT T.2
of 27
EHo
N - N2
fg
Reorganizing the above inequality gives rise
To s 130
To (26
V (a ||
13817"11'
E
+
2
b H
1
113
N
11
==1
==1
+96,"EH"
Σ 0² - Ean4"HH* 12
0
n,
n2
Following the same derivation in Part I, we obtain
To S (6 H²)
Σ Bll (8
+ 1'
(0"0)]1²=
where
=67,02)= (1044 (1046""''" 72-
1
1447" 1 EH
_
N
n
+42-² 2or22Eoo++15 2
+5 3 E
Utilizing #/2 N4 プソ= N
5 5 and 7
- 1HHL
we can further bound (/ o²) as
my
3EHL.
H 12 (1
1
1
72j
N
N
H42 H 5y
2
Σ
N
n2
j=1
H²
EEH 15--++----
=1044 =1014y'EH"" 144 L EH
t720²
72
+2EH 18H2
<146
To this end, we complete the proof of Lemma P2.7
G Recovering SCAFFOLD's Results
By comparing the communication complexity T required achieve a c-stationary solution, we can see that our result recovers that of SCAFFOLD when N = and E 1. Specifically, for our MTGC algorithm, to achieve an e error bound, according to Corollary 4.1
we can find a to satisfy
2oLo² NTEH
FoLo T
LFo
3'
3
T
34

---

Equivalently, T
Lo NEH
T> LaFa and T 2 Lia In other words, the MTGC algorithm will (c)
have expected error smaller than if 7 satisfies
Lo LoFo NEH
LFu
T=o
(c)
According to Theorem [18] to achieve the e error bound, the number of global communication rounds SCAFFOLD needs to take can be expressed
Lo nyHe?
LFo
T=
where we have converted the notation from
[8 to notation.
We see that the dominating term of the MTGC, O La Fo
recovers that of SCAFFOLD when
NEH
N = 1 (i.e., N = ny) and 1, which corresponds to the case of single group with a single (global) aggregator.
35

---

NeurIPS Paper Checklist
1. Claims
Question: 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 con- tributions made in the paper. Additionally, the claims made in the abstract and introduction are supported by the theoretical analysis (see Sec. and experiments (see Sec.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitation are included Sec.
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
36

---

Answer: [Yes]
Justification: All the theorems, formulas, and proofs in the paper are numbered and cross- referenced. All assumptions are clearly stated in Sec. 4 and referenced in the statement our theorem, i.e., Theorem The proofs are provided in the supplemental material. Theorems and Lemmas that our proof relies upon properly referenced.
Guidelines:
The answer NA means that the paper does not include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper discloses all necessary information reproduce the main experi- mental results in Sec. S
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
37

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
All the datasets used in this work are open-sourced while the information about the models and parameters clearly reported in Sec. [ For the convenience of reproducibility, the code is attached to our submission.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.co tttpcc//pbbb. waccc/pullc//eee www.///gg//ee/eeeeeeeeeeee tttpg/dde//eeeeubbmmbmecese wwwp//oooeeesssiieeoaa wammisssioooiccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details about the setting of our experiments reported in Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the standard deviations which are computed based on random trials (see Sec. (5.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
38

---

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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
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 include experiments.
The paper should indicate 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 (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics Ethics/https/
Answer: [Yes]
Justification: Our work adheres the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
39

---

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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include 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.
40

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. Crowdsoureing 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 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 the supplemental material is fine, but if the main contribu- tion 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.
15. 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
41

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
42


Reviews:
[{"review_id": "LcIxSeahz6", "reviewer": "Reviewer_rcWg", "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.", "questions": "See weaknesses section.", "limitations": "The authors adequately addressed the limitations  of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "- The paper places itself correctly in the existing literature, is well-structured and easy to follow.\n- The problem of hierarchical FL is relevant and fairly interesting for the ML community.\n- The proposed algorithm is natural and easy to understand.\n- Both theoretical and numerical results are provided.", "weaknesses": "- 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.\n\n- Minor typo: on line 110 in \"However, their is\" should be \"However, their algorithm is\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's constructive feedback. We are glad that the reviewer acknowledges the problem we studied is interesting.\n\nWe would like to emphasize that theoretically showing that the proposed MTGC algorithm guarantees convergence and achieves linear speedup in terms of both $H$ (the number of local updates) and $E$ (the number of group aggregations) was quite non-trivial. \nIn this response, we will provide more detailed descriptions of the theoretical challenges and our proof techniques to better highlight the contributions compared to SCAFFOLD, which was developed in a single-level scenario.\n\n### **Difference in the analysis of the correction terms**\n\nIn SCAFFOLD [12], the theoretical analysis of correction terms appears in the proof of Lemma 18.\nHere, the correction error can be easily bounded using $\\beta$-smoothness:\n$$\n\\mathbb{E}||c^{r-1}-\\nabla f({x}^{r-1})||^2+ \\frac{1}{N}\\sum_{i=1}^N \\mathbb{E}||c_i^{r-1}-\\nabla f_i({x}^{r-1})||^2 \\leq \\frac{2 \\beta^2}{K}\\sum_{k=1}^K\\mathbb{E}||y_{i, k-1}^{r-1}-x^{r-1}||^2.\n$$\n\nIn our work (with multi-level, multi-timescale updates/aggregations), we\nbound the new correction errors\n$$\nZ\\_j^{t,e} = \\frac{1}{n\\_j}\\sum\\_{i \\in \\mathcal{C}\\_j} \\mathbb{E} ||\\boldsymbol{z}\\_i^{t,e} + \\nabla F\\_i(\\bar{\\boldsymbol{x}}^{t,e}\\_j) - \\nabla f\\_j(\\bar{\\boldsymbol{x}}^{t,e}\\_j)||^2, \\ \\ \\text{and} \\ \\ \\ \nY\\_j^{t,e} = \\mathbb{E} || \\boldsymbol{y}\\_j^t + \\nabla f_j(\\hat{\\boldsymbol{x}}^{t,e}) - \\nabla f(\\hat{\\boldsymbol{x}}^{t,e})||^2\n$$\nin Lemmas C.2.4 and C.2.5, \nfor characterizing client and group model drifts, respectively. As shown in the proof of Lemmas C.2.4 and C.2.5, the analysis of the correction variables in our work involves new difficulties. In particular, in the analysis of upper-level correction term $\\boldsymbol{y}$, we need to bound the discrepancy between $\\boldsymbol x_{i,h}^{t,\\tau}$ and $\\hat{\\boldsymbol x}^{t+1,e}$ (see line 628 of our manuscript), where two models appear in two different global rounds. We note that different from SCAFFOLD, $\\boldsymbol{y}_j^t$, $\\nabla f_j(\\hat{\\boldsymbol{x}}^{t,e})$, and $\\nabla f(\\hat{\\boldsymbol{x}}^{t,e})$ in $Y_j^{t,e}$ are in two different timescales. Moreover, the upper bound of $Y_j^{t,e}$ is influenced by the gradients and model drifts of two consecutive rounds, highlighting the increased complexity compared to the single-level case.\n\n### **Detailed technical challenges**\n\n**First**, the upper bounds of correction errors $Y_j^{t,e}$ and $Z_j^{t,e}$ shown in Lemmas  C.2.4 and C.2.5, are impacted by model drifts $D_t$ and $Q_t$, and $\\Theta_j^{t,e}$. Meanwhile, the upper bounds of $D_t$, $Q_t$, and $\\Theta_j^{t,e}$ are also impacted by $Y_j^{t,e}$ and $Z_j^{t,e}$. The interplay between these terms makes the analysis non-trivial. **Second**, (i) global aggregation, (ii) the update of upper-level correction variable $\\boldsymbol{y}$ and local aggregation, and (iii) the update of lower-level correction variable $\\boldsymbol{z}$ are performed at different timescales. Note that in SCAFFOLD, since there is no local aggregation step, the convergence is presented using the global aggregation timescale, i.e., $\\{\\nabla f(\\bar{\\boldsymbol x}^{t})\\}$. However, in MTGC, if we directly consider $\\{\\nabla f(\\bar{\\boldsymbol x}^{t})\\}$, it is difficult to capture the effects of group aggregation and correction variable $\\boldsymbol{z}$. Moreover, it is hard to establish a tight connection between $\\nabla f(\\bar{\\boldsymbol x}^{t})$ and $||\\boldsymbol x_{i,h}^{t,e} - \\bar{\\boldsymbol x}^{t}||$, $\\forall e, h$ since there is a large lag between $ {\\boldsymbol x}_{i,h}^{t,e}$ and $\\bar{ \\boldsymbol x}^{t}$. \n\n### **Our approach**\n\nFor the **first challenge**, we extracted a recursive relationship of $\\Gamma_{t} = Q_t + D_t$ hidden behind Lemmas C.2.2-C.2.6, as summarized in Lemma C.2.7. With this recursion, we design a novel Lyapunov function as $\\Phi_{t+1} = \\mathbb{E} f(\\bar{\\boldsymbol x}^{t+1}) - f^* +\\gamma L^2 H \\Gamma_{t},$ to derive the recursive relationship between two global rounds. This new Lyapunov function with recursive components enabled us to mitigate the coupling effects between $Y_j^{t,e}$, $Z_j^{t,e}$ and $\\Theta_j^{t,e}$ (see proof of Theorem 4.1 in our Appendix).\n\nFor the **second challenge**, we introduce a new metric, which is the gradient $\\nabla f(\\hat{\\boldsymbol x}^{t,e})$ at virtual sequence $\\{\\hat{\\boldsymbol x}^{t,e}\\}$, to characterize the convergence of MTGC. This introduction makes our analysis tractable by building connection between $\\boldsymbol x_{i,h}^{t,e}$ and $\\hat{\\boldsymbol x}^{t,e}$ as follows: $\\boldsymbol x\\_{i,h}^{t,e} \\rightarrow \\bar{\\boldsymbol x}^{t,e}\\_j \\rightarrow \\hat{\\boldsymbol x}^{t,e}$. Accordingly, we introduce two characterizations, $||\\boldsymbol x_{i,h}^{t,e} - \\bar{\\boldsymbol x}_j^{t,e} ||^2$ and $||\\hat{\\boldsymbol x}^{t,e} - \\bar{\\boldsymbol x}_j^{t,e} ||^2$, to capture the local and group model drifts, respectively. The former quantifies the progress made by each client from $(t,e,0)$ to $(t,e,h)$-th iteration while the latter characterizes the group model deviation from the virtual global model at the $(t,e)$-th group aggregation, making our analysis distinct from SCAFFOLD.\n\nIn the revised manuscript, we will illustrate these new challenges and our solution in more detail. Considering that the exploration of FL  under practical hierarchical setups is quite limited, we believe that our work presents a meaningful contribution to the community. Our work bridges this gap by developing the MTGC algorithm with desired theoretical properties (convergence guarantee with linear speedup in the numbers of clients, local updates, and edge aggregations), where the analysis from single-level to hierarchical is not a trivial extension as supported by our response above. \n\n### **Typo**\n\nWe double-checked the manuscript and corrected this typo.\n\nAgain, thanks for your time and efforts! Please let us know if you need any further clarification.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3lLwnZXAti", "reviewer": "Reviewer_r1S6", "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.", "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.\n\n2. How about the runtime of the algorithm? Would it be possible to include comparisons of runtime with the baseline in the experiments?\n\n3. In the experiments, does Eq.5 require the addition of regularization coefficients for correction terms $z$ and $y$?\n\n4. Could you include some measurements of the additional communication costs in the experiments?", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The writing is clear and easy to follow.\n2. I have initially checked the proofs and did not find any issues so far.", "weaknesses": "1. It would be beneficial to include comparisons of additional computational and communication costs of MTGC in the experimental section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's constructive feedback. We appreciate the reviewer for carefully checking our proof and are glad to receive your positive feedback on the writing of our paper. Our responses are given as below:\n\n### **Communication cost comparison**\n\nCompared to HFedAvg, MTGC requires initializing the correction variables at the start of each global round, which incurs additional communication overhead. Specifically, for every $E$ steps of group aggregation, MTGC incurs an additional communication cost equivalent to one transmission of the model parameters. In other words, **the per-aggregation communication complexity of MTGC is $\\frac{E+1}{E}$ times that of HFedAvg**. \nTo show this impact, we have added experiments comparing the communication cost and testing accuracy at the client side. This experiment was conducted on 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. \nThe results are shown in **Figure R1(a)** of the attached PDF. The results demonstrate that MTGC achieves higher testing accuracy for a given communication cost, highlighting the efficiency and effectiveness of our approach. \n\n### **Running time and computational cost**\n\nDuring the rebuttal phase, we compared the runtime of our MTGC algorithm with the baselines. Using one NVIDIA A100 GPU with 40 GB memory, we conducted experiments on the CIFAR-10 dataset with $E = 30$ and $H = 20$ under client/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 **Figure R1(b)** of the attached PDF of the global response. We see that although our approach incurs extra operation induced by the correction variables, this is the cost for achieving a significant performance improvement by effectively handling the data heterogeneity problem. We also note that the computation cost incurred by the correction variable is relatively small compared to computing gradients in a neural network using backpropagation, which is a step that is required in all methods. Overall, the results confirm the advantage of our method compared with baselines.\n\n### **Distinguishing the update of $  \\boldsymbol{x}$, $ \\boldsymbol{z}$ and $ \\boldsymbol{y}$**\n\nThanks for your kind reminder. We will highlight the updates of three variables with different colors in the future version.\n\n### **Does Eq.5 require the addition of regularization coefficients for correction terms $ \\boldsymbol{ z}$ and $ \\boldsymbol{y}$?**\n\nBased on our theory and experiments, we don't need to apply coefficients to $\\boldsymbol{z}$ and $\\boldsymbol{y}$.\nFor ease of explanation, we state equation (5) as follows:\n\n$$ {\\boldsymbol{x}}^{t,e}_{i,h+1} = {\\boldsymbol{x}}^{t,e}\\_{i,h}  - \\gamma \\left( \\nabla F_i({\\boldsymbol{x}}^{t,e}\\_{i,h}, \\xi\\_{i,h}^{t, e}) + \\boldsymbol{z\\_i}^{t,e} + \\boldsymbol{y\\_j}^t \\right) $$\n\n$\\boldsymbol{z}$ and $\\boldsymbol{y}$ play the role of tracking the gradient difference between the local gradient and the group gradient and the difference between the group gradient and the global gradient. By utilizing $\\boldsymbol{z}$ and $\\boldsymbol{y}$, our aim is for the correction updating direction $\\nabla F_i + \\boldsymbol{z_i} + \\boldsymbol{y_j} $ to approach the global gradient direction. On the other hand, if we apply coefficients $\\lambda$ for $\\boldsymbol{z}$ and $\\boldsymbol{y}$, consider an ideal example where we have attained the optimal point $\\boldsymbol{x^*}$ and\n$\\boldsymbol{z_i} =  \\nabla f_i(\\boldsymbol{x^*}) - \\nabla F_i(\\boldsymbol{x^*})$ and $\\boldsymbol{y_j }= \\nabla f(\\boldsymbol{ x^*}) - \\nabla f_j(\\boldsymbol{x^*}) $.\nIf we apply a coefficient $\\lambda$ into our iteration, equation (5) becomes\n$$\\boldsymbol{x^*} - \\gamma \\left(\\nabla F_i(\\boldsymbol{x^*}) + \\lambda \\left(\\nabla f_j(\\boldsymbol{x^*}) - \\nabla F_i(\\boldsymbol{x^*}) +  \\nabla f(\\boldsymbol{x^*}) - \\nabla f_j(\\boldsymbol{x^*}) \\right)  \\right).$$\n\nThis iteration is not stable at $x^*$ as $(1-\\lambda) \\nabla F_i(\\boldsymbol{x^*})$ is generally not equal to zero unless $\\lambda = 1$. Due to this, we did not apply coefficients to $\\boldsymbol{z}$ and $\\boldsymbol{y}$. \n\nAgain, thank you for your time and efforts for reviewing our paper, and providing insightful comments. If there are any more clarifications we could provide, we would be grateful if you could let us know.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FzvF1hjuX5", "reviewer": "Reviewer_fhg9", "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.", "questions": "Please refer to the weaknesses mentioned above.", "limitations": "The limitations of the study are discussed, and no potential negative societal impacts of the work have been identified.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed MTGC algorithm is simple and easy to implement, introducing client-group and group-global correction terms. The paper clearly defines the problem it aims to solve. The motivation is clear and well-articulated, highlighting the gap in existing HFL algorithms.\n- The inclusion of theoretical analysis adds depth to the paper, providing a solid foundation for the proposed approach. The theoretical results show that MTGC achieves linear speedup in the number of local iterations, group aggregations, and clients. \n- The convergence bound of the proposed algorithm is immune to the extent of data heterogeneity, which is a significant strength.", "weaknesses": "- 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.\n\n\n- 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.\n\n- 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.\n\n- The paper could also be strengthened by providing more insights into the practical implications of the theoretical results.\n\n[1] An Efficient Framework for Clustered Federated Learning. NeurIPS 2020.\n\n[2] Optimizing the Collaboration Structure in Cross-Silo Federated Learning. ICML 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's positive comments and feedback. We are glad to receive your appreciation of our motivation and results. Our responses are below:\n\n### **Discussion on CFL**\n\nOur 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. [R1] demonstrates how dynamic clustering based on data distributions can enhance model performance. [R2] explores alleviating negative transfer from collaboration by clustering clients into non-overlapping coalitions based on their distribution distances and data quantities.\n\nWe will add this to our updated manuscript.\n\n### **Experiments on other types of tasks**\n\nPlease refer to the global response.\n\n\n### **Experiments on distribution shifts**\n\nPlease refer to the global response.\n\n### **Generalization bound**\nDuring the rebuttal, inspired by the paper [R2] shared by the reviewer, we studied the generalization bound of our algorithm as follows:\n\nGiven a model $\\boldsymbol{x}$, we denote the expected risk, defined on $\\mathcal{D}$, as $\\mathcal{R}(\\boldsymbol{x})$.\nIn the training stage, we aim to minimize the empirical loss $f(\\boldsymbol{x})$ defined on finite samples $\\hat{\\mathcal{D}}$. The generalization error $\\mathcal{R}(\\boldsymbol{x}^t)-\\mathcal{R}(\\boldsymbol{x}^*)$, $\\boldsymbol{x}^* = \\arg\\min \\; \\mathcal{R}(\\boldsymbol{x})$, can be expressed as\n$$\n\\mathcal{R}(\\boldsymbol{x}^t)-\\mathcal{R}(\\boldsymbol{x}^*) = [\\mathcal{R}(\\boldsymbol{x}^t)-f(\\boldsymbol{x}^t)] \n +[f(\\boldsymbol{x}^t)-f(\\hat{\\boldsymbol{x}}^*)] \n +[f(\\hat{\\boldsymbol{x}}^*)-f(\\boldsymbol{x}^*)] \n +[f(\\boldsymbol{x}^*) - \\mathcal{R}(\\boldsymbol{x}^*)],\n$$\nwhere $\\hat{\\boldsymbol{x}}^* = \\arg\\min f(\\boldsymbol{x})$. According to [R2], one can claim that for any $\\delta \\in (0,1)$, with probability at least $1-\\delta$, there is a quantity-aware function $\\phi$ such that\n$$ \n|\\mathcal{R}(\\boldsymbol{x})-\\mathcal{R}(\\boldsymbol{x})| \\leq \\phi (|\\hat{D}|,\\delta), \\forall \\boldsymbol{x}.\n$$\n\nTherefore, with probability at least $1-\\delta$, we have\n$$\n\\mathcal{R}(\\boldsymbol{x}^t)-\\mathcal{R}(\\boldsymbol{x}^*) \\leq 2 \\phi (|\\hat{D}|,\\delta)\n +f(\\boldsymbol{x}^t)-f(\\hat{\\boldsymbol{x}}^*). \n$$\nNote that this bound is influenced by $\\phi (|\\hat{D}|,\\delta)$ and $f(\\boldsymbol{x}^t)-f(\\hat{\\boldsymbol{x}}^*)$. The former is determined by $\\hat{D}$ while the latter will be impacted by the training algorithm, local data distribution, and network topology. \n\nIn our manuscript, we characterize the upper bound of $||\\nabla f(\\boldsymbol{x})||^2$ rather than $f(\\boldsymbol{x}^t)-f(\\hat{\\boldsymbol{x}}^*)$ as we focus on non-convex setting. For illustration, suppose we convert the upper bound for $||\\nabla f(\\boldsymbol{x})||^2$ to $f(\\boldsymbol{x}^t)-f(\\hat{\\boldsymbol{x}}^*)$ by assuming the PL condition $f(\\boldsymbol{x}^t)-f(\\hat{\\boldsymbol{x}}^*) \\leq \\frac{1}{2\\mu} ||\\nabla f(\\boldsymbol{x})||^2$. This gives a generalization error bound \n$$\n2 \\phi (|\\hat{D}|,\\delta) + \\frac{\\Delta}{2\\mu},\n$$\nwhere $\\Delta$ is the error derived in Corollary 4.1.\n\nDifferent from CFL [R2] which tries to approximately minimize $\\phi (|\\hat{D}|,\\delta)$ by clustering clients, i.e, optimizing $\\hat{D}$, in our setting, $|\\hat{D}|$ is fixed, and thus $\\phi (|\\hat{D}|,\\delta)$ is fixed. \n\nIn addition, regarding the impact of model drift on the generalization bound: Unlike CFL, where the clients end up with different models, in HFL, model drift will converge to zero at the end of training for MTGC due to its convergence. Model drift is a characterization metric used in the intermediate process for convergence analysis. As you can see, there is no model drift term in our generalization bound.\n\n\n### **Increasing hierarchical communication levels**\n\nNote that the main objective of our paper is to develop a convergent algorithm for a given HFL topology, treating the number of layers as an intrinsic system parameter. Hence, we predominantly assume the topology to be predetermined in our work. To address this comment, during the rebuttal period, we empirically studied the impact of hierarchical levels on FL performance, in terms of testing accuracy versus communication time. We find that the benefit of additional layers varies based on the configuration. Please refer to the global response for the experimental details.\n\n\n### **Practical implications of the theoretical results**\n\nThanks for the comment.  As shown in Corollary 4.1, the upper bound is mainly dominated by the first term $\\mathcal{O}\\left(\\sqrt{\\frac{\\mathcal{F}_0L\\sigma^2}{\\tilde{N} T EH}} \\right)$. Due to the speedup in the number of local iterations $H$ and the number of group aggregations  $E$, we can reduce the global communication round $T$ by increasing $H$ and $E$ in practice. We empirically validate this in Table 5.1 in the original manuscript and Figure 6 in the Appendix, connecting theory and practice. On the other hand notice that there is an upper bound for the learning rate, i.e., $\\gamma \\leq \\frac{1}{40EHL}$. When we increase $E$ and $H$, the upper bound of the optimal learning rate will decrease. We will highlight these insights after Corollary 4.1 in the revised manuscript.\n\n[R1] An efficient framework for clustered federated learning. NeurIPS 2020.\n\n[R2] Optimizing the collaboration structure in cross-silo federated learning. ICML 2023.\n\nAgain, thanks for your comments. If we could provide any more clarifications, we would be grateful if you could let us know.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3hHZGnZ5El", "reviewer": "Reviewer_zFr1", "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.", "questions": "1. What are the practical applications of HFL?\n2. Are there any techniques implemented for preserving the privacy of the model?\n3. The model has been tested on small datasets; how does it perform on larger datasets?\n4. The ablation study is missing. How does the model perform when only one of the corrections is used?\n5. How about the stability of the proposed method?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The idea of correcting gradients is interesting \n2. The proof seems correct.", "weaknesses": "The model is tested on small datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the valuable comments. We also thank the reviewer for acknowledging our idea as interesting and for taking a look at our proof. Our responses are given below.\n\n### **Practical applications of HFL**\n\nHFL can play a key role in most of the real-world networks comprised of a hierarchical architecture such as edge/fog computing systems or software-defined networks. In autonomous vehicle applications, each small base station (local aggregator) aggregates the models sent from the vehicles (nodes) in its coverage region, and then sends the aggregated model to the macro base station (global aggregator). Other applications of Internet\nof Things (IoT) sensors also operate under similar settings.  In healthcare applications, individual hospitals (nodes) send the model to regional health centers (local\naggregators), and the national health authority (global aggregator) aggregates all the models. This HFL process involves nation wide data points, improving the performance of disease diagnosis models. Finally, in financial fields, individual financial institutions (nodes) collect transaction data and train local models for fraud detection and credit scoring. These models are aggregated at regional financial hubs (local aggregators), and the aggregated models are then sent to national or global financial authority  (global aggregator) to create a global model. We will illustrate these key applications more clearly in the revised paper.\n\n### **Implementation of privacy-preserving techniques**\n\nSince our primary focus was to tackle the data heterogeneity issue from the perspective of designing optimization algorithms in the hierarchical setting, we have not considered applying additional techniques like privacy preservation that are orthogonal to our approach. Nonetheless, existing privacy-preserving techniques such as secure aggregation or differential privacy (DP) can be incorporated into our framework. To be specific, secure aggregation can be directly applied during the local aggregation process, as the local aggregators only need to obtain the average of \nmodels within its coverage rather than individual local models. Similarly, secure aggregation can be directly applied during the global aggregation process to preserve privacy as well. \n\nFor DP, we can apply noise injection to local and global model aggregation (Steps 8 and 10 of Algorithm 1 in the original manuscript) to protect privacy. For instance, in Step 8, clients upload local models to the group server. In practical implementation, they only need to upload the model update \n$\\Delta_i = \\boldsymbol{x}_{i,H}^{t,e} - \\bar{\\boldsymbol x}_j^{t,e}$. \nFor applying Gaussian noise to protect the model's privacy, we first clip $\\Delta_i$ to ensure that its norm does not exceed a predefined threshold $C$:\n$\n\\tilde{\\Delta}_i = \\Delta_i \\cdot \\min\\left(1, \\frac{C}{||\\Delta_i||_2}\\right).\n$\nNext, we can apply Gaussian noise to the clipped model update\n $\n\\hat{\\Delta}_i = \\tilde{\\Delta}_i + \\mathcal{N}(0, \\sigma^2 I).\n$\nHere, $\\mathcal{N}(0, \\sigma^2 I)$ represents Gaussian noise with mean 0 and covariance matrix $\\sigma^2 I$. Note that the procedures of applying the DP mechanism to MTGC are similar to FedAvg [R1]. The specific analysis of the DP-assisted MTGC is beyond the scope of our work and is best left for future research.\n\n[R1] Understanding clipping for federated learning: Convergence and client-level differential privacy, ICML 2022.\n\n\n### **Experiments on larger datasets**\n\nPlease refer to the global response.\n\n### **Ablation study with only one correction term**\n\nIn Figure 4 of our original manuscript, we have already reported the results of using only one of the correction terms. Specifically, we applied either the local correction, $\\boldsymbol z_i^{t,e}$, or the group correction, $\\boldsymbol y_j^{t}$, to HFedAvg. It is observed that in the group i.i.d. \\& client non-i.i.d. scenario, local correction performs better than the group correction, as data samples are non-i.i.d. across the clients.\nConversely, in the group non-i.i.d. \\& clients i.i.d. scenario, the opposite holds. More detailed discussions on these results are illustrated in lines 311-327 of our original manuscript.\n\n### **Stability of our method**\n\nIn the original manuscript, we proved the convergence of MTGC without relying on extra data similarity assumptions. In the simulation, we show the stability of our algorithm in 4 different ways: We conducted experiments (i) using 3 random realizations (with different initial models) in Figure 3, (ii) under 3 different data distribution settings in Figure 4, (iii) using 4 different datasets, (iv) using varying parameters in Table 5.1 and Figures 5 and 6. During the rebuttal period, we have also added two more datasets (Shakespeare and CINIC-10) to further validate the advantage of our method. Moreover, we ran experiments with four more random realizations corresponding to Figure 4. Due to space limitations, we have selected one representative figure for CIFAR-10 to show for the rebuttal. Please refer to **Figure R4 (c)** of the attached pdf. \nOur MTGC consistently outperforms baselines across all scenarios and the performance gains beyond the standard deviation, showcasing its stability.\n\nAgain, we appreciate the reviewer for the helpful comments. In case there are remaining questions/concerns, we hope to be able to have an opportunity to further answer them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate all reviewers for providing constructive comments. In this global response, we will describe the additional experiments we have conducted, suggested by **Reviewer r1S6**, **Reviewer fhg9**, and **Reviewer zFr1**, that may be of interest to all reviewers. The figures are included in the attached PDF. The responses to all other comments are provided individually for each reviewer.

### **Experiments for Reviewer r1S6**

**Computation and communication costs**

We reported the computational and communication costs of MTGC and baselines in **Figure R1** in the attached PDF. 

### **Experiments for Reviewer fhg9**

**Experiments on other types of tasks**

We have conducted additional experiments using the Shakespeare dataset, an NLP task. We use the LSTM model where the model starts with an $80$-character input sequence, which is converted to an $80 \times 8$ sequence through an embedding layer. This embedded sequence is then processed by a two-layer LSTM, each with $100$ hidden units. The final output is passed through a softmax layer to make predictions. The performance comparison is presented in **Figure R2(a)** of the attached pdf, where we set the learning rate $0.5$, $H=75$, and $E=30$. It is observed that our MTGC consistently outperforms baseline methods.

**Experiments on distribution shift datasets**

We have conducted additional experiments to include two different non-i.i.d. scenarios: label shift and feature shift, as referenced in [R1,R2]. These experiments were performed using the Fashion-MNIST dataset.

For **label shift** [R1,R2], 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 [R1], label shift adds more heterogeneity to this system. According to the results shown in Figure R2(b), 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.

For **feature shift** [R1], we first partition data following the group non-i.i.d. \& client non-i.i.d. case as in our original manuscript,  and then let clients at different groups rotate images for different angles. Concretely, for the clients at the $i$-th group, the angle is $-50+10 \times 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 **Figure R2(c)**, we see that MTGC attains the best performance among these baselines.

[R1] Optimizing the collaboration structure in cross-silo federated learning, ICML 2023.

[R2] On the convergence of clustered federated learning, arXiv preprint 2022.

**Experiments on hierarchy levels**

To evaluate the impact of hierarchy levels, we compared the testing accuracy versus communication time. We considered three scenarios: single-level (100 clients), two-level (100 clients grouped into 10x10), and three-level (100 clients grouped into 4x5x5). The experiments were conducted using ResNet-18 (44.6 MB) and the CIFAR-10 dataset. We considered different cases of link bandwidths in each HFL architecture, which impact the speed of communication through the system.

The results are shown in **Figure R3** of the attached PDF. In **Figure R3(a)**, the communication bandwidths were set to 0.5 MB/s for single-level, and 0.6 MB/s and 20 MB/s for upper and lower links in two-level, and 0.7 MB/s, 5.5 MB/s, and 20 MB/s for three-level. Results show performance improvements from single-level to two-level, and from two-level to three-level.

In **Figure R3(b)**, considering a faster network, bandwidths were adjusted to 3 MB/s for single-level, and 3.5 MB/s and 20 MB/s for upper and lower links in two-level, and 4 MB/s, 5.5 MB/s, and 20 MB/s for three-level. Results indicated performance improvement from single-level to two-level but a decrease from two-level to three-level. This highlights that performance can vary with different configurations. Generally, increasing intermediate layers is beneficial when the central server is far from clients with high transmission latency.

### **Experiments for Reviewer zFr1**

**Experiments on larger datasets**

During the rebuttal, we have 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 **Figure R4(a)** of the attached pdf, where we use the LSTM model 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 **Figure R4(b)** of the attached pdf, MTGC maintains its superior performance on the CINIC-10
dataset, consistent with its performance on other tasks.

Meta-review: 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.
Decision: Accept (poster)