Unified Analyses for Hierarchical Federated Learning: Topology Selection under Data Heterogeneity
Authors: Ziyi Zhou
Yipeng Li
Xinchen Lyu
Venue: ICLR 2026 Poster (2026)
Keywords: Hierarchical Federated Learning
Convergence Analysis
Heterogeneous Data
Primary area: optimization

Abstract: Hierarchical Federated Learning (HFL) addresses critical scalability limitations in conventional federated learning by incorporating intermediate aggregation layers, yet optimal topology selection across varying data heterogeneity conditions and network conditions remains an open challenge. This paper establishes the first unified convergence framework for all four HFL topologies (Star-Star, Star-Ring, Ring-Star, and Ring-Ring) with full/partial client participation under non-convex objectives and different intra/inter-group data heterogeneity. Our theoretical analysis reveals three fundamental principles for topology selection: (1) The top-tier aggregation topology exerts greater influence on convergence than the intra-group topology, with ring-based top-tier configurations generally outperforming star-based alternatives; (2) Optimal topology strongly depends on client grouping characteristics, where Ring-Star excels with numerous small groups while Star-Ring is superior for large, client-dense clusters; and (3) Inter-group heterogeneity dominates convergence dynamics across all topologies, necessitating clustering strategies that minimize inter-group divergence. Extensive experiments on CIFAR-10/CINIC-10/Fashion-MNIST/SST-2 with ResNet-18/VGG-9/ResNet-10/MLP validate these insights, and provide practitioners with theoretically grounded guidance for HFL system design in real-world deployments.

Published as a conference paper at ICLR 2026
UNIFIED ANALYSES FOR HIERARCHICAL FEDERATED LEARNING: TOPOLOGY SELECTION UNDER DATA HETEROGENEITY
Ziyi Zhou', Yipeng Li Xinchen Lyu**
National Engineering Research Center for Mobile Network Technologies, Beijing University of Posts and Telecommunications
TTinghua Shenzhen International Graduate School, Tsinghua University
(zhouzy0821, 1vxinchen] hww.:/ettpp....u..eeooooeuu cn, 1iyp25@mails ht edau. cn
ABSTRACT
Hierarchical Federated Learning (HFL) addresses critical scalability limitations in conventional federated learning by incorporating intermediate aggregation lay- ers, yet optimal topology selection across varying data heterogeneity conditions and network conditions remains an open challenge. This paper establishes the first unified convergence framework for all four HFL topologies (Star-Star, Star- Ring, Ring-Star, and Ring-Ring with full/partial client participation under non- convex objectives and different intra/inter-grow group data heterogeneity. Our theo- retical analysis reveals three fundamental principles for topology selection: (I) The top-tier aggregation topology exerts greater influence on convergence than the
forming topology, with bnng-based top-tier configurations generally outper- alternatives, (2) Optimal topology strongly depends on client grouping characteristics, where Ring-Star excels with numerous small groups while Star-Ring is superior for large, client-dense clusters; and (3) Inter-group heterogeneity dominates convergence dynamics across all topologies, necessitat- ing clustering strategies that minimize inter-group divergence. Extensive exper- with ResNet-18/VCGr
iments on 10I-II/IIIIC-///Faaiiio0 9/ResNet- 1 10/MPP validate these insights, and provide practitioners with theoreti- cally grounded guidance for HFL system design in real-world deployments.
INTRODUCTION
Federated Learning (FL) (McMahan et al., 2017) has revolutionized collaborative machine learning by enabling distributed model training across decentralized devices while preserving data privacy. However, conventional single-tier FL faces critical scalability challenges in large-scale deployments, including communication bottlenecks, synchronization latency, and vulnerability failures. Hierarchical Federated Learning (HFL.) (Liu et al., 2020) has emerged as promising paradigm, introducing intermediate aggregation layers (such as edge servers or cluster heads) to form two/multi-tie architecture that distributes the coordination burden for massive deployment. Despite its promise, the thcoretical understanding of HFL remains nascent, particularly under real- istic conditions of data heterogeneity and diverse hierarchical topologies.
single-poine
two-tier HFL frameworks, each level of aggregation can be performed via parallel updates (star topology) sequential updates (ring topology), yielding four distinct configurations: Star-Star, Star-Ring, Ring-Star, and Ring-Ring (see Figure 1). These topological choices fundamentally in- fluence the convergence dynamics, robustness to data heterogeneity, and communication efficiency. For instance, star aggregation enables parallel client updates but may suffer from abrupt synchro- nization of divergent models, while ring updates propagate sequentially, potentially mitigating client drift in non-lID settings (Li & Lyu, 2023; 2025).
Literature Review. Existing theoretical analyses of HFL have largely focused on the Star-Star topology on non-convex functions (Zhou & Cong, 2019; Castiglia et al., 2021; Wang et al., 2022),
"Xinehen Lyu the corresponding author.

---

Published as a conference paper at ICLR 2026
data heterogeneity (Wang et al., 2022), partial client participation (Jiang & Zhu, 2024), and other variants (Liu et al., 2022; Yang et al., 2023). Some recent works explore Star-Ring topology (Chen et al., 2020; Lee et al., 2020; Fang al., 2022; Ding al., 2024) and the Ring-Star topology (Chaoyang et al., 2020; Huang et al., 2024; Yan et al., 2025). However, a unified convergence analysis that compares all four topologies is still lacking. This theoretical gap impedes informed topology selection in practical deployments, where system performance is highly sensitive to data distribution and network conditions.
(a) Star-Star HFL
(b) Star-Ring HIF
(c) Ring-Star HIFL
(d) Ring-Ring HIFL
Figure 1: Different topology configurations HFL
Research Question. The central research problem is:
How should practitioners select the optimal HFL topology configuration when facing varying de- grees of intra-group and inter-group data heterogeneity, diverse client grouping characteristics, and constrained network conditions?
This research problem is of practical importance for system convergence. For example, in systems with high inter-group heterogeneity (such as clients clustered by geographic region with distinct data distributions), selecting star topology the top tier may amplify inter-group divergence through abrupt parallel synchronization. Conversely, ring aggregation at the top tier enables gradual, se- quential alignment that may better accommodate distributional differences. This topology selection problem is further complicated when considering diverse client grouping characteristics in HFL.
Analytical Challenges. Establishing comprehensive convergence framework encompassing all four HFL topologies presents key challenges:
HFL exhibits a cascading heterogeneity where inter- and intra-group data distributions interact non-trivially, Since local model divergence directly exacerbates global inconsistency, convergence bounds must explicitly account for the interaction between intra- and inter-group divergence.
The two-tier aggregation architecture creates a cross-tier dependency where updates at one tier directly influence error propagation at the other, making the effective learning rate topology- dependent.
Star and ring topologies introduce fundamentally different statistical properties (unbiased high- variance vs. biased low-variance sequential updates) that compound across layers. These topology-specifi етror propagation patterns require sophisticated analysis to track how topology choices modulate the cross-tier bias-variance tradeoff.
Contributions. This paper establishes unified theoretical framework for analyzing and comparing all four HFL topology configurations (Star-Star, Star-Ring, Ring-Star, and Ring-Ring Ring) under non- convex optimization and varying data heterogeneity conditions (see Theorem I and Table 1). Our convergence bounds explicitly quantify the effects of key system parameters, including number of groups (G), clients per group (M), local steps (K), and group rounds (P), and reveal how topology choices interact with intra/inter-grout group heterogeneity we provide a proof extending Theorem 1 to settings with a random-shufft execution order. The framework also extends to partial client participation settings with corresponding convergence guar- antees (see Theorem 2). Our analysis yields three insights for HFL system design:
shape convergence behavior. Furthermore,
(1) HFL prioritizes scalability over convergence acceleration. Counterintuitively, HFL is primarily valuable for enabling large-scale deployments where single-tier FL becomes impractical, rather than inherently accelerating convergence. Crucially, HFL with ring aggregation at the top tier (Ring-Star,
2

---

Published as a conference paper at ICLR 2026
Table I: Comparison of convergence rates under full participation. We omit constants and some terms. Notation: R (global rounds); G' (groups); P (group rounds); M (clients/group); K (local
steps); (variance); 6, Ç (inter/intra- hheerr/ntaa-etttrogeeeett)): (smoothness).
Topology
Convergence Rate!
PFL
(Koloskova et al., 2020)²
14/2g VMKR
/2/3,2/3
+ //2
(K12)3
(1R)
1./3g VMKR
L2/302/8
2//282/8
SFL
(Li & Lyu, 2023)
(MKR9)3
(R2)
Star-Star
Theorem
1117 VGPMKR 1/2 VGPMKR
LA13
+
1,213
L2/382/3
(PAKRA)
(PMKR4)
(P2R4)
(R2)3
1/33
,/3
22/3
1,2/88/33
(Wang al., 2022)
(P2KR))
(PMKR))
(P2
(1P)
Star-Ring' Theorem
1 VGPMKR
1
12/a8//5
(PMKRAJ
(P=R3)
(12)
Ring-Star' Theorem
1
1222
JCPMKR
(G"PaKRR)
(GPMKR2)
(G*PaRaj
(82)
1NI VGPMKR (GPMKR))
12/3
Ring-Ring Theorem
(G*P2Ra)
(RR)
Terms highlighted in color, e.g.. G' and G denote the additional denominator terms introduced by the top- level Ring topology (i.e.. King-Star Star-Star, Ring- Ring Star BannRRing.. FedAAg, non-IID, non-convex. If there is only one client in each group (i.c., = M and ç O),
Star-Star reduces to FedAvg.
case, our rate becomes O 1.1/a 1//3,2/3 VMKR (KCR2)173 (R2y175
1//3///3 which matches
that of FedAvg.
Even though similar algorithms and some preliminary convergence analyses have been studied. the advanced convergence analyses are still missing for Star-Ring and Rtar.Star. For example, Chen al. (2020) and Yan (2025) used the bounded gradient assumption, meaning the stochastic gradient is uniformly bounded by a constant.
Ring-Ring) consistently outperforms star-based counterparts under data heterogeneity. This reveals that carefully selected single-tier FL configurations may actually converge faster than two-tier HFL, positioning HFL as solution for scalability constraints rather than convergence accelerator.
(2) Inter-group heterogeneity dominates convergence dynamics. We establish that inter-group data divergence (8) exerts across all four topologies. This finding fundamentally reshapes client clustering strategies, indicat- ing that minimizing inter-group distributional differences should take precedence over optimizing homogeneity. Effective grouping, such as forming clusters with approximately IID inter- group distributions, would converge faster than fine-tuning intra-group group training dynamics.
significant impact convergence than intra-group heterogeneity (()
(3) Optimal topology selection depends critically on group structure. Our analysis reveals optimal topology selection depends critically on group structure. Ring-Star excels when numerous small groups exist, as sequential inter-group updates benefit from increased parallelism at the lower tier and tine-grained global alignment. Star-Ring preferable for few large, client-dense clusters, where intra-group ring aggregation enables deep local refinement before global synchronization.
We validate these theoretical insights through extensive experiments using MeANett-8/VGG-9 on CIFAR-10, ResNet-18 18 on CINIC-10, ResNet- on Fashion-MNIST, and MLPP on SST-2 under four distinct heterogeneity scenarios. The results consistently demonstrate accuracy gains from informed topology selection, with ring- top-tier configurations showing particular advantages in hetero- geneous environments. Beyond establishing the first convergence analysis for the previously unstud- ied Ring-Ring topology, framework overcomes critical limitations of prior work by: (i) adopting consistent, general non-convex assumptions across all topologies, whereas previous studies relied on heterogeneous assumptions that prevented direct comparison; and (ii) deriving tighter convergence bounds of 0(1/VGMMKR) for Star-Ring and Ring-Star topologies, versus O(1 ((1/RR) in prior
3

---

Published as a conference paper at ICLR 2026
literature (Lee al., 2020; Yan al., 2025). These contributions provide system designers with theoretically grounded principles for topology selection based on specific deployment constraints.
2 CONVERGENCE THEORY
This section presents unified convergence analysis of HFL under non-convex optimization objec- tives. In the following, we formalize the setup of HFL with four different topologies, introduce general assumptions, derive the convergence bounds, and extract actionable insights for topology selection in practical deployments.
2.1
SETUP
We begin by formalizing the HFL framework and the update mechanisms for each topology config- uration. In two-tier HFL, the global objective to minimize:
1 2 G
1 Fg(x))
min XER
F(x)
9 g).
G
M
where F3 denotes the average local objective function over all clients in group g (g [G], and F f..m denotes the local objective function client m (m [M] in group g. Specifically, defined as Fg. gg (2) Eg.DD.. If (2; {)], where Dm is the local dataset of client
In the full participation setting, the HFL process with four topology configurations operates accord- ing to distinct update rules:
(1) Star-Star: Each group initializes its model as x x()), Within each group, clients initialize (r) their models as g.p.m.0 xf" perform K parallel local updates, and send updates the group server for aggregation. After P group updates, the global server aggregates group parameters to generate the next global parameters x (r1+))
(2) Star-Ring. Each group g initializes its model as x x ( Within each group, clients initialize their models from the previous client in sequence and perform local updates. The group server receives the latest parameters from the last client. After P groupp updates, group servers send their updated parameters to the global server for aggregation.
(3) Ring-Star. Each group g initializes its model with the latest parameters from the previous group.
9.p.m..0 = xg. perform parallel local updates, and send updates to the group server for aggregation. After P group updates, group servers send their updated parameters to the next group in sequence.
Within each group, clients initialize their models as (r)
(4) Ring- Ring. Each group g initializes its model with the latest parameters from the previous group. Within each group, clients initialize their models from the previous client and perform local updates. The group server aggregates the latest parameters from the last client. After P group updates, group servers send their updated parameters to the next group in sequence.
Crucially, for ring-based topologies, distinguish two cases: (i) under full participation, the cution sequence is fixed (see Appendix A.I); and (ii) under partial participation (where S₁ groups and S2 clients active), the execution sequence is random.
2.2 ASSUMPTIONS
Assumption (L-Smoothness)) Each local objective function Fg.m is L-smooth, i.e., there exists F.
constant L such that F V (y))l < L|x yll, for all g {1....,G) G}, {1....,M) M and x, y IRd.
Assumption 2 (Bounded variance). For the local objective function Fg the stochastic gradient F Fx.m(x {) computed using a mini-batch &. sampled from local dataset D gg.m- is an unbiased FFg.(()) The variance of the stochastic gradient each client bounded: Rg-D,,.,. [ m (x, V gg (x)]12] < ²
estimate, i.e., Eę-D
4

---

Published as a conference paper at ICLR 2026
Assumption (Bounded Inter- Heterogeneity). There exists constant 8 such that
E VF(x) - (x)( 8
(2)
Assumption (Bounded Intra-Group Heterogeneity). For any g E (1, ........Gr,, G}, there exist con- stants lg such that
D Em=1l VV -FF _ Sg. M
(3)
Furthermore, we define the average intra-group heterogeneity as (² = G E 2
The first two assumptions are standard in non-convex optimization (Ghadimi & Lan, 2013; Bot- tou et al., 2018). Assumptions 3 and 4 extend standard FL analysis to the hierarchical setting, explicitly bounding inter- and intra-group data heterogeneity (Wang & Ji, 2022). Notably, the global heterogeneity be naturally decomposed into the inter-group and intra-group terms defined above. Specifically, we have: G Eg= Em=1 | g. (x) VF(x)]|2 è Eg= (x)
VF(x)]1²+ Eg= MT Em=l FV (x) FF, (x)(x)) This equality an implementation the law of total variance. This shows that inter- and intra- group heterogeneity are, in fact, partition of the global heterogeneity.
2.3 CONVERGENCE ANALYSIS
Theorem 1. (Convergence with Full Participation). Let A = F(x(()) F- denote the initial opti-
mality gap. Here 3. is defined as model uniformly sampled from the x0 ..... ,...,,(R-1. (B-1) previous iterations, and < hides universal constants. Under Assumptions 2-4, the following convergence bounds for each HFL topology.
Star-Star: There exist îj = PKm. and i 1 such that
V30L"
πR GPMK + 0² L2ii002
A Lñjo
g2 L221202.
(I)))((((R))
+ p2
P2K PMK
Star-Ring:
There exist `j = PMKn, and îj S Vool' such that
BIIVF(E A
GPMK + L'iF L2
Lūjz²
12
(5)
Rj
PMK
p2
Ring-Star:
There exist rj = GPKn, and ij S "Bor."
1
such that
BIIVF( A Tija² 1221202 1,2i802
T22
GPMK GPPK GPMK + G2 +1228802
+
îR
Ring-Ring:
There exist ij = GPMKn, and in S ioL such that
1
Lijo L'RRO2 L2TR22 RR GPMK + GPMK G2p2 + 12 +
(1 1
Theorem (Convergence with Partial Participation). Under Assumptions 2-4, where in each global round, subset of Si groups are sumpled uniformly at random from the G total groups, and within each selected group, a subset of S2 clients are sampled uniformly at random faom the M total clients, the following convergence bounds hold for each HFL topology.
Star-Star: There exist i PKn, and ij IOI.
1
such that
A
Lñj²
LñÇ
Liyo
(()
+
(8)
TR
S,PS2K
S2
S
L2
L2
+ 2,2
(9)
PKK
PS₃K
p2
S2
Star-Ring:
There exist πj = PMK1, and πj S TsI,
such that
A
Tújo2
Lnpz
1:21022
1.215
S2 +
+
1.22282
(10)
R
S.PSKK
S
PS,K
S2
5

---

Published as a conference paper at ICLR 2026
Ring-Star: There exist î GPKn, and fj S
1
such that
15L
Líjo²
Lis
Líjo²
|||
+
+
+
(11)
RR
P,P
S2
Si
1221202
12
1,21282
+ P2K
+
(12)
P2K
SPPSKK
S/² p2
S2
S1
Ring-Ring: There exist fj GPMKn, and ñj
I. 201 such that
Lijo² P.PS S + S1
Liis Lii
L'i
L'7'5² L'7P882
EIIVF( R
+
+
+ S,PS,
(13)
S₂
S1
Effective Learning Rate. Theorems 1 and introduce iopology-dependent effective learning rate, denoted by îj. which incorporates key architectural parameters: the number of groups G, group rounds P. clients per group M, local update steps K, and global rounds R. This effective learning rate captures how hierarchical updates affect convergence. The derived bounds comprise opti- mization term that decreases with R, and enror terms from stochastic noise and data heterogeneity. A larger accelerates optimization but amplifies errors. Corollary 1 and Corollary 2 specify an optimal i that minimizes the overall bound.
Corollary 1. (Convergence with full participation under effective learning rate). With the learning rate the convergence rate satisfies the following, where O()) hides absolute constants:
LA R
VGPMKR +T)
(Lo*A)1
V[ (R) = o
(14)
and T denotes the topology-dependent terms defined as follows:
Star-Star:
(2
(L"A202)1/3
(2
(L2A282)1/8
T
(15)
(P2KR2) (PMKR3)US
(P2 1/3
(R2)1/3
Star-Ring:
T (12A202)1//3
(17
(12A389)113
(16)
(PMKR2)1/S
(22
(R2)1/3
Ring-Star:
T (12A202)1113
(12A203))1/3
(22A353)2//3
(L2
+
(17)
(G2P2KRR)IIS (GPMKR2JUS
(G2P2R?)1/3
(R3)
Ring-Ring:
(1
(1
(L2A282)1/3
T (GPMKR9) P2
(18)
(R2)
Corollary 2. (Convergence with partial participation under effective learning rate). With the learn- ing rate iJ, the convergence rate satisfies the following, where O(-) hides absolute constants:
(1.A02)1/2
(L/C2)1/2
(TA88))/22
+ +T)
E
+
+
(19)
VSTPS2RR
VS2Rt
VSR
and T denotes the topology-dependen terms defined as follows:
Star-Star:
(1)7202))133
(1.23022)133
(1/3222))133
(12A352)1133
(12A262)1/3
T
(20)
(P2RR))113 (PS
(P2
(52R3)1/3
(R3)1/3

---

Published as a conference paper at ICLR 2026
T (L2AAO2)1//5
(1
(L2A269)1/3
(21)
(P52K18311/8
(S212)1/3
(1F))/33
Ring-Star:
(13A202)1118
(LPA303)113
(3
(
(L2A289)1/8
T (S)P2KR)JUB
(S)P2R9)133
(S2R2)
(S
(22)
Ring-Ring:
(2'AP22)1/3
(L
(L2A38331/33 (8, (8///
T
(23)
(S
(S212)1/3
2.4 KEY IMPLICATIONS
The Top-Tier Dominance Principle. Contrary intuition, the synchronization mechanism the global tier influences convergence significantly more than intra-group topology. This principle is quantitatively demonstrated Corollaries and 2. Specifically, for ring-based top-tier topologies, the error terms include an additional scaling factor of G or S in the denominators of the SGD vari- ance along with the intra-group heterogeneity terms, under full or partial participation respectively. This also implies that under partial participation, increasing the number of participating groups or clients accelerates convergence. Furthermore, random shuffling introduces additional factors S and S2 to the heterogeneity terms (Li & Lyu, 2023; 2025). Consequently, ring-basei updates are inher- ently more robust to both stochastic noise and data heterogeneity. Such robustness manifests two crucial ways: (i) Ring-based top-tier configurations (Ring-Star, Ring-Ring) consistently outperform star-based alternatives under data heterogeneity, with the gap widening as inter-group divergence increases. (ii) The performance difference between top-tier topologies exceeds that between lower- tier configurations. For example, Ring-Star typically outperforms Star-Star by a larger margin than Star-Ring outperforms Star-Star, despite both differing only in the lower tier.
Inter-Group Heterogeneity as the Fundamental Bottleneck. Our analysis quantitatively estab- lishes that inter-group heterogeneity (6) is the primary convergence bottleneck across all topolo- gies. For instance, under full participation, while all topologies share the same asymptotic con- vergence rate of O(1/VGPM R), the practical convergence speed is dominated by inter-group divergence, which decays slowly at O ( (1333
regardless of topology choice. Intra-group in ring-based top-tier configurations
R478
heterogeneity (() decays significantly faster-particull
(C2A2 ( Re/3G4/sp777 ) -making it secondary concern compared to inter-group divergence. This insight provides a principled foundation for system design: to accelerate convergence in heterogeneous en- vironments, minimizing inter-group divergence should be prioritized. Practical strategies such as intelligent client clustering, e.g., grouping clients with complementary data distributions to approx- imate the global distribution (Zeng et al., 2022), are more impactful than optimizing local training dynamics within groups.
SstrutyySttuuttuee Compatibility Principle. The optimal topology selection depends critically on the underlying client grouping structure, creating fundamental design trade-off. Ring-Star excels with numerous small groups. When clients naturally form many small clusters (e.g., loT devices, retail outlets), Ring-Star leverages parallelism at the lower tier while benefiting from the smoothing effect of sequential global updates. Its convergence rate improves dramatically with increasing G, making it ideal for deployments with abundant but sparse client clusters. Star-Ring dominates with few large clusters. settings with limited but data-rich clusters, Star-Ring's intra- group ring aggregation enables deeper local refinement before global synchronization, producing higher-quality group models. This topology shows diminishing returns as G increases beyond a certain point. Star-Star consistently underperforms. Despite its conceptual simplicity, the double averaging in Star-Star significantly dampens the effective learning rate, making it the least efficient configuration across all heterogeneity scenarios.
Wall-Clock Time Considerations in Practical Deployments. While convergence properties guide theoretical topology selection, real-world deployments must account for wall-clock execution time
7

---

Published as a conference paper at ICLR 2026
under bandwidth constraints. Our analysis in Appendix A.2 reveals that star topologies don't al- ways achieve ideal (1)) parallelism in practice due to straggler effects and diluted bandwidth re- sources. The total wall-clock time follows Eq. (24), where communication overheads scale with group and client counts. In bandwidth-constrrined edge environments, ring-based topologies of- demonstrate competitive performance despite sequential updates, they avoid synchroniza- tion bottlenecks and uplink transmission constraints, This insight suggests that in networks with heterogeneous bandwidth capabilities or significant straggler effects, ring-based top-tier configura- tions (Ring-Star, Ring- -ingg may offer better practical performance than theoretically optimal but communication-imeee -inteiiiiviineeivveeeeee star- bas-based alternatives, especially when inter-group heterogeneity is high.
EXPERIMENTS
3.1 EXPERIMENTAL SETTINGS
We employ ResNet-18 (Lin et al., 2020) and VGG-9 (Acar et al., 2021) for CIFAR-10 (Krizhevsky al., 2009), ResNet-18 18 for CINIC-10 (Darlow al., 2018), ResNet-10 for Fashion-MNIST (Xiao et al., 2017), and MLP for SST-2 (Socher al., 2013). We simulate hierarchical setup with N = 100 clients distributed across G = 10 groups under four data partitioning schemes: (1) IID- IID, (2) Non-IID-IID, (3) IID-Non-IID, and (4) Non-IID-Noo-IID. To ensure fair comparison, the learning rate (1) was tuned individually for each topology. We consistently observed that to maintain comparable convergence, the required raw learning rates follow the pattern: T/Star-Sur > //Star-Ring Sting-Star > Ring. This empirical observation aligns perfectly with our theoretical findings. Detailed descriptions of the hyperparameters (e.g., batch size, momentum), specific definitions of the data partitioning schemes, and the complete search space for learning rates are provided in Appendix B.I.
3.2 EFFECT OF TOPOLOGY
Figure presents test accuracy curves for the four HFL topologies under the four heterogeneity settings. The results consistently show that topologies with ring-based top-tier aggregation (i.e., King-Star and Ring-Ring) achieve superior convergence speed and higher final accuracy compared to their star-based counterparts. Notably, the classical Star-Star configuration (cquivalent standard HFedAvg) performs the worst across all settings. This is attributed to its conservative update mech- anism, i.e., the double averaging at both group and global levels dampens the effective learning rate, slowing convergence. abling more aggressive and continuous model refinement. This allows the global model to traverse the loss landscape more rapidly, especially in heterogeneous environments. However, this perfor- mance advantage necessitates careful operational considerations. Empirically, ring topologies may exhibit greater sensitivity to data distribution skewness, manifesting as slightly higher volatility in training curves compared to other topologies. This suggests that client with highly skewed data could influence the update chain, implying that hyperparameter tuning (e.g., learning rate calibra- tion) becomes more critical to maintain stability.
contrast, ring-based top-tier updates propagate changes sequentially, en-
(ockoane//))
To hutweyyh
Tex Mnrhew////
Stan
Sax Sex Rig
Sor Sun Reg
12:00
1050
2024
<000
120
2323
2000
<io
35
4000
G2nnel
Olind Kumat
(a) Groups IID and Clients (b) Groups IID and Clients Non-IID
(c) Groups Non-IID and Clients IID
(d) Groups Non-IID and Clients Non-IID
IID
Figure Comparison of the four HFL topologies on CIFAR-10 Dataset
8

---

Published as a conference paper at ICLR 2026
Table 2: Test accuracy (%) on CIFAR-IO, CINIC-10, Fashion-MNIST, and SST-2 under various
HFL topologies and data partitioning approaches. The non-IlD partitions are generated using Dirichlet distribution (Yurochkin al., 2019; Hsu al., 2019).
Heterogeneity
Topology
Dataset
Model
Inter
Intra
Star-Star
Star-Ring
Ring-Star
Ring-Ring
IID
88.48
90,30
90.40
91.53
Non-IID
87.01
89.55
89.75
91.10
ResNet-18
IID
87.03
88.22
89.15
90,94
Non-IID
CIFAR-10
Non-IID
86.78
87.40
90.01
90.33
IID
84.83
87.30
87.77
89.10
IID
Non-IID
84.21
85.33
87.81
88.17
VGG-9
II
85.00
85.42
86.16
88.12
Non-IID
Non-IID
83.80
85.04
87.05
87.63
IID
76.88
78.59
78.70
79.56
IID
Non-IID
74.25
76.09
78.23
78.35
CINIC-10
ResNet-18
Non-IID IID
74.20
72.53
75.83
76,23
Non-IID
73.63
74.21
77.11
76.78
89.70
92.59
92.67
93.01
IID
Fashion- MNIST
Non-IID
87.45
92.33
92.76
93.07
ResNet-10
88.21
89.41
91.40
91.33
Non-IID
Non-IID
88.04
92.18
92.27
93.33
IID
69.61
72.36
80.50
81.42
IID
Non-IID
69.95
73.17
79.59
80.50
SST-2
MLP
IID
68.12
73.85
79.13
81.08
Non-II0 IID
Non-IID
68.12
73.97
78.44
81.65
3.3 EFFECT OF DATA HETEROGENEITY
Table reports the final test accuracy for all topology and data partition combinations. A key observation is that inter-group heterogeneity has more detrimental effect model performance than intra-group heterogeneity. For instance, on CIFAR-10 with ResNet-18 under the Star-Ring topology, shifting Non-III group distributions causes 2.08% accuracy drop (from 90.30% to 88.22%). whereas Non-IID client distributions lead to a smaller drop of only 0.75% (to 89.55%). The effect is more pronounced on CINIC-10, where in the same setup, inter-group heterogeneity results in a substantial 6.06% performance degradation (from 78.59% to 72.53%), compared to 2.50% drop for intra-group heterogeneity. This trend also holds for Mushion-MNIST" with ResNet- 10, where inter-group heterogeneity causes a significant 3.18% accuracy drop (from 92.59% to 89.41%) %), while the impact of mutra-group heterogeneity a negligible 0.26% decrease.
This empirical finding strongly supports our theoretical conclusion that inter-group divergence()) the dominant bottleneck in HFL convergence. It suggests that system designers should prioritize clustering strategies that minimize distributional differences between groups even at the expense of increased intra-group heterogeneity. For example, grouping clients by semantic similarity of data (e.g., geographic region, user demographics) rather than arbitrary network proximity can signifi- cantly improve convergence.
3.4 EFFECT OF GROUPS
We further investigate how the number of groups influences performance, focusing on the hybrid topologies (i.e., Star-Ring and Ring-Stte Star) as they offer practical balance between convergence ef- ficiency and stability. With the total number clients N = 100, we vary the number of groups G (1,5, 10, 20, 100) and tune the learning rate for each configuration ensure optimal perfor-

---

Published as a conference paper at ICLR 2026
mance. Figure illustrates the convergence of Star-Ring and Ring Star under both IID and Non-IID settings. We can find two distinct patterns:
(1) Star-Ring performs best with fewer, larger groups, i.c., small values of G. This is because intra- group ring aggregation benefits from longer update chains: sequential updates allow for deeper local refinement before global synchronization, producing higher-quality group models.
(2) Ring-Star contrast, excels with more, smaller groups, i.e., large values of G. Here, parallel intra-group aggregation (star) is less effective in large groups due to the averaging of divergent local updates, which can dilute valuable gradients. Smaller groups reduce this averaging effect, and the sequential inter-group updates in Ring-Star enable fine-grained global alignment.
is worth noting that our conclusion continues to hold even in the extreme cases cases-Ringe Ring-Star with G == N and Star-Ring with G 1, both degenerating conflict with the notion of "catastrophic forgetting" in sequential federated learning, because the step size is not fixed. We scale it with the number of groups to keep the effective learning rate constant. Under the same effective learning rate, selecting an appropriate G therefore yields optimal performance. These results highlight critical design principle: optimal topology selection depends on the underlying group structure. In applications with a few large, data-rich clusters (e.g., hospital networks), Star-Ring is preferable. contrast, systems with many small or independent units (e.g., IoT devices, retail outlets) benefit more from the Ring-Star topology.
pure ring topology. This does not
100
10
G-1
6-5
G-1
0-5
41
6:10
0-10
0-10
C-11
6:33
0-30
0-20
0-22
6-000
0-100
0-100
0-130
10
Calaa Roa
Gaba 3aaao
Gl4b Juca0
Cloba 2o40
(a) Star-Ring (IID)
(b) Star-Ring (Non-IID)
(c) Ring-Star (IID)
(d) Ring-Star (Non-IID)
Figure 3: Comparison of Star-Ring and Ring-Star topologies with different numbers of groups on CIFAR10 Dataset
CONCLUSION
This paper presents the first unified convergence analysis for all four HFL. topologies under non- convex objectives and intra/inter-group data heterogeneity. Our results reveal that: (1) top-tier topology dictates convergence behavior, and ring-based top-tier aggregation generally converges faster than star-based methods; (2) inter-group heterogeneity is the dominant bottleneck, outweigh- ing intra-group effects; and (3) optimal topology depends on group structure, where Ring- Star suits many small groups, while Star-Ring excels with few large clusters. These findings enable sys- tem designers to move beyond heuristic topology choices and instead make informed, theoretically grounded decisions based on deployment-specifie constraints such as network scale, client distribu- tion, and data heterogeneity profiles.
ACKNOWLEDGMENTS
This work is supported in part by National Science and Technology Major Project of China under Grant 4025ZD1302200 and in part by National Natural Science Foundation of China under Grant 62371059.
REFERENCES
Durmus Alp Emre Acar, Yue Zhao. Ramon Matas Navarro, Matthew Mattina, Paul N Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. arXiv preprint arXiv:2111.0426: 2021.
10

---

Published as a conference paper at ICLR 2026
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-33 -11,, 2018.
Timothy Castiglia. Anirban Das, and Stacy Patterson. Multi-level local sgd: Distributed sgd for heterogeneous hierarchical networks. In International Conference on Learning Representations, 2021.
HE Chaoyang. M ANNAVARAM, and S AVESTIMEHR. Group knowledge transfer: Collaborative training of large cnns on the edge [j]. arXiv preprint 1455: 2020.
Cheng Chen, Ziyi Chen, Yi Zhou, and Bhavya Kailkhura. Fedcluster: Boosting the convergence of federated learning via cluster-cycling, In 2020 IEEE international conference on big data (Big Data), pp. 5017-5026. IEEE, 2020.
Luke N Darlow, Elliot Crowley, Antreas Antoniou, and Amos Storkey. Cinic- 10 is not imagenet or cifar-10. arXiv preprint 180.:0088. 2018.
Yucheng Ding, Chaoyue Niu, Yikai Yan, Zhenzhe Zheng, Fan Wu, Guihai Chen, Shaojie Tang, and Rongfei Jia. Distributed optimization over block-cyclic data. In Proceedings of the 6th ACM International Conference on Mullimedia in Asia Workshops, pp. 1-6, 2024.
Qingze Fang, Zhiwei Zhai, Shuai Yu, Qiong Wu, Xiaowen Gong, and Xu Chen. Olive branch learn- ing: topology-aware federated learning framework for space-air-ground integrated network. IEEE Transactions on Wireless Communications, 22(7):453444511, 2022.
Wenzhi Fang, Dong-Jun Han, Evan Chen, Shiqiang Wang, and Christopher Brinton. Hierarchical federated learning with multi-timescale gradient correction. Advances in Neural Information Processing Systems, 37:78863-78904 2024.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM journal on optimization, 23(4):234)-2368, 2013.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint (rXXiv:109.063: 2019.
Jianjun Huang, Lixin Ye, and Li Kang. Fedsr: A semi-decentralized federated learning algorithm for non-iidness in iot system. arXiv preprint arXiv:2403.14718. 2024.
Xiaohan Jiang and Hongbin Zhu, On the convergence of hierarchical federated learning with partial worker participation. In The 40th Conference Uncertainty in Artificial Intelligence, 2024.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International conference on machine learning, pp. 5381-5393, PMLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Jin-woo Lec, Jachoon Oh, Sungsu Lim, Se- Young Yun, and Jac-Gil Lee. Tornadoaggregate: Accurate and scalable federated learning via the ring-based architecture. arXiv preprint arXiv:2012.03214, 2020.
Yipeng Li and Xinchen Lyu. Convergence analysis of sequential federated learning on heteroge- neous data. Advances in Neural Information Processing Systems, 36:56700-5611 2023.
Yipeng Li and Xinchen Lyu. Sharp bounds for sequential federated learning on heterogeneous data. Journal of Machine Learning Research, 26(70):1-55, 2025.
Wei Yang Bryan Lim, Zehui Xiong, Chunyan Miao, Dusit Niyato, Qiang Yang. Cyril Leung, and H Vincent Poor. Hierarchical incentive mechanism design for federated machine learning in mobile networks. IEEE Internet of Things Journal, 7110)9575-9588. 2020.

---

Published as a conference paper at ICLR 2026
Wei Yang Bryan Lim, Jer Shyuan Ng. Zehui Xiong, Dusit Niyato, Chunyan Miao, and Dong In Kim. Dynamic edge association and resource allocation in self-organizing hierarchical feder- ated learning networks. IEEE Journal on Selected Areas in Communications, 39(12):3640-3653 2021.
Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. Advances neural information processing systems, 33:2351-2363, 2020.
Chang Liu, Jun Zhao, and Yitong Wang- Computation and communication resource optimization for efficient hierarchical federated learning. IEEE Transactions on Networking, 2025.
Lumin Liu, Jun Zhang. SH Song, and Khaled Letaief. Client-edge-cloud hierarchical federated learning. In ICC 2020-2020 IEEE international conference communications (ICC), pp. 1-6. IEEE, 2020.
Lumin Liu, Jun Zhang, Shenghui Song, and Khaled B Letaief. Hicrarchical federated learning with quantization: Convergence analysis and system design. IEEE Transactions on Wireless Communications, 22(1):2-11) 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-cffiiciii learning deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1288 PMLR, 2017.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language pro- cessing, pp. 1631-16444 2013.
Jiayi Wang, Shiqiang Wang, Rong-Rong Chen, and Mingyue Ji. Demystifying why local aggrega- tion helps: Convergence analysis of hicrarchical sgd. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 8548-8556 2022.
Shiqiang Wang and Mingyue Ji. A unified analysis of federated learning with arbitrary client par- ticipation. Advances in neural information processing systems, 15:19124-19137, 2022.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint 1788v0770.00747, 2017.
Xingrun Yan, Shiyuan Zuo, Rongfei Fan, Han Hu, Li Shen, Puning Zhao, and Yong Luo. Sequential federated learning in hierarchical architecture on non-iid datasets. IEEE Transactions on Mobile Computing, 2025.
Zhengjie Yang, Sen Fu, Wei Bao, Dong Yuan, and Albert Y Zomaya. Hierarchical federated learn- ing with momentum acceleration in multi-tier networks. IEEE Transactions on Parallel and Dis- tributed Systems, 34(10):269--244) 2023.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. Interna- fional conference machine learning, pp. 7252-7261. PMLR, 2019.
Shenglai Zeng. Zonghang Li, Hongfang Yu, Yihong He, Zenglin Xu, Dusit Niyato, and Han Yu. Heterogeneous federated learning via grouped soneeniil-tooparallle training. In International Conference Database Systems for Advanced Applications, pp. 455-471. Springer, 2022.
Fan Zhou and Guojing Cong. distributed hierarchical sgd algorithm with sparse global reduction. arXiv preprint 1003.09900055550 2019.
12

---

Published as a conference paper at ICLR 2026
Appendix
Discussion
14
A.1
Algorithm Details
14
A.2
Wall-Clock Time Analysis
15
B Experimental Details and Additional Results
16
B.1 Detailed Experimental Settings
16
B.2 Comparison with Single-Tier FL
17
Effect of Group Rounds P and Local Steps
17
C Notations
18
D Proof of Theoreml
19
D.I Find the per-round recursion
19
D.2 Proof of Theorem for the Star-Star Case
21
D.3 Proof of Theorem for the Star-Ring Case
"...............................
24
D.4 Proof of Theorem for the Ring-Star Case
27
D.5 Proof of Theorem for the Ring-Ring Case
31
E
Random-Order Extension of Theorem
35
E.1
Random-Order Extension of Theorem for the Star-Star Case
................................
35
E.2
Random-Order Extension of Theorem for the Star-Ring Case
39
E.3 Random-Order Extension of Theorem for the Ring-Star Case
42
E,4
Random-Order Extension of Theorem for the Ring-Ring Case
46
Proof of Theorem
F.1 Find the per-round recursion
51
F.2 Proof of Theorem for the Star-Star Case
53
F3 Proof of Theorem 2 for the Star-Ring Case
55
F.4 Proof of Theorem 2 for the .i..............................
Case
57
F55 Proof of Theorem 2 for the Ring-Ring Case
60
13

---

end for Published as a conference paper at ICLR 2026
A DISCUSSION
A.1 ALGORITHM DETAILS
For clarity and completeness, this appendix provides the detailed pseudocode for the four HFL topologies mentioned in the main body of our paper. Each algorithm outlines different communi- cation pattern for both inter-group and intra-group model aggregation.
The Star-Star topology (Algorithm 1) represents fully parallel framework. Both the groups at the server level and the clients within each group perform their training and updates parallel, synchronizing with their respective servers before aggregation.
Algorithm Star-Star Star Hierarchical FL
1: for global rounds r - 0, I,.... R do
2: for groups 9 1,2..... G in parallel do
3: Initialize group model: (r) x()
for group rounds p 0, f, 9.0 clients m 1, 2, ..... M in parallel
4:
P do
5:
.
6:
Initialize local model: x g.n.m. 0 = X..
7:
for local steps h: 0, 1, ..... K do
X g.p.m,k+1 = (r) end for end for
(r)
8:
K.p,m, m...p.m.k
9:
11: Group aggregation: x g.p+1
17 ΣM (r)
9.p.m.K
12: end for
14:
Global aggregation: x (r+1)
G
g.P
15:
end for
The Star-Ring topology (Algorithm 2) combines parallel inter- group communication with sequential intra-group updates. While groups update parallel with the global server, clients within each group form ring, passing the model sequentially from one client to the next.
Algorithm Star- Rinn Hicrarchical FL
1: for global rounds r = 0, 1, ...,, R 1 do
2: for groups g 1,2, ..., G in parallel do
3: Initialize group model: (r) (²)
4: for group rounds p = 0, 1 P do
5:
for clients m 1, 2, ..... M in sequence do (r)
Initialize local model: x (r)
g.p
if m 1
6:
0.
x
m.p.m-1.K
1.K
m
7:
for local steps 1: = 0, K (r)
do
(r)
(r)
8:
0.p.m.k+11 g...pm..k 178..p...t
9:
end for end for
10:
Group model: x (r) end for
x (r)
11:
9.p+1
M.P.K.KK
12:
13:
end for
14:
Global aggregation: (r+1)
EG
15:
end for
Conversely, the Ring-Star topology (Algorithm 3) employs sequential communication among groups and parallel updates within them. The groups form a ring at the global level, while clients inside each group operate in standard star configuration.
14

---

Published as a conference paper at ICLR 2026
Algorithm 3 Ring-Star Hierarchical FL
1: for global rounds r = 0, 1..... R do for groups ! = 1, 2...... in sequence do (
2:
3:
Initialize group model: x
(r)
g =
g
9-1.P
4:
for group rounds = 0, 1,............. for clients m 1, M in parallel do
do
5:
6:
Initialize local model: x 9.p.m = X
7:
for local steps k = 0, 1, ................................ K do (r)
x (r)
(r)
8:
S.p.m,k++ g.pmm, 11 p. m.
end for 10: end for
9:
11:
Group aggregation: x gptl 17 Em=1 K.P.m,KK end for
(+)
1
13:
end for
Global model: x (r+1)
(r) X..
14:
15:
end for
The Ring-Ring Ring topology (Algorithm 4) implements fully sequential communication protocol. Both the groups at the global level and the clients within each group update their models in a sequential, rang-based manner.
Algorithm 4 Ring- Ring Hierarchical FL
1: for global rounds 0, 1, ..... R - 1 do for groups = 1, 1,..... in sequence do (r)
2:
Initialize group model: (r)
if
if
1-1.P
4:
for group rounds p = 0, 1..... P 1 do
5:
for clients m 1, 1..,.... M in sequence do
Initialize local model: x (r)
Xg.pp
(r)
if m
6:
8.p.m.
x
g.p.m-l.A I.K
mm
7:
for local steps k = 0, K (r)
do
(r) g.p.m.R+I =x..p.mm
(r)
8:
1/8g.....k
9:
end for end for
Group model: (r) end for
(r)
11:
8.p+1 M.P.KKK
12:
13:
end for
14: Global model: (r+1) (r)
-XG.P
15: end for
A.2 WALL-CLOCK TIME ANALYSIS
To bridge the gap between convergence rounds and real-world training latency, analyze the total wall-clock time T. This defined as the sum of computation and communication overheads: = Teomp + Tromm Let S denote the model size, the computation time for node z, and rA-BB the transmission rate from node to B.
Single-Layer Analysis. In single-layer setting with M clients, the Star topology is limited by the straggler, i.e., T max, S Tm + Fn ), where the index 0 denotes the aggregation
S
server. Conversely, the Ring topology operates sequentially, accumulating latencies: Ring 8
ro-11
15

---

Published as a conference paper at ICLR 2026
S S While T theoretically offers O(1) communication scaling Fm-11-m PM--1 versus 7 s O(M), this assumes unlimited bandwidth, which rarely holds in edge scenarios.
Em Im Em
HFL Topology Analysis. The total wall-clock time for HFL over R global rounds, with P group rounds, can be unified as:
Twai R (Tinter + P. P Timma)
(24)
where iimrr represents the wall-clock time for inter-group updates, and Timra represents the wall- clock time for intra-group updates. Table 3 details these components for four topologies.
Table 3: Wall-clock Time Components for HFL Topologies. Here denotes the Intra-group Aggre- gation Server (Group Server).
Topology
Inter-Group Time (Timte)
Intra-Group Time (Tuna)
S
5
Star-Star
max
+
ILBX
+ Tymm
To-+g
gg
rg-+m.
Tm-+0.9
5
M
M
8
Star-Ring
max
Tg
max
T
70-49
gg-0
1G-+1.5
mm
mmmm-
PM--0.9
S
S
8
G
S
S
Ring-Star
+
Σ
max
Tg.m
1--1-9
TG-+0
FG-+m.
Im-1Gia
S
8
8
Ring-Ring
7ym
To-1
g-1
T--1-9
TG-0
TG-1..
mm 12
1m-1-mm
TM-0.00
Bandwidth Constraints and Practical Latency. Theoretically, the star topology offers advan- tages in parallel computation; however, in real-world scenarios, it often fails to achieve the idea O()) level of parallelism. In HFL, the total wall-clock time faces challenges similar to those in single-layer FL. Many studies (Lim et al., 2021; Liu et al., 2025) on HFL communi- cation optimization highlight that bandwidth resources are diluted as the number of users in- creases, c.g., Tm-1-mm.
Rg where Rg represents the total bandwidth resources of the group server and M denotes the total number of clients connected to that server. Substituting this relationship into the total wall-clock time for the Star-Star topology yields T Star--Stor R [maxG=1 2SG R
+ Tg.m [g.m)] }}). where the communication latency in the upper layer approaches ( while the communication overhead in the lower layer approaches (M). In particular, the uplink transmission rate of workers is major bottleneck in the training process that can lead to the straggler's effect (Lim et al., 2020). Therefore, in bandwidth- constrained real-world scenarios, the ring topology remains competitive option.
[ + P. max { /maxx=x11
M 2SSM R
B EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
B.1 DETAILED EXPERIMENTAL SETTINGS
All batch normalization layers in the models (ResNet-18, VGG-9, ResNet-10) are removed to ensure cleaner validation of our convergence bounds. We use SGD with a constant learning rate, zero momentum, mini-bater batch size of 20, and gradient clipping. The global model is updated over R = 5000 rounds (R- 1000 for SST-2), with each group performing each client conducting K 2 local steps.
group-level updates and
Data Partitioning Schemes. We simulate a hierarchical setup with N 100 clients evenly dis- tributed across G 10 groups, unless otherwise specified, and examine four data partitioning schemes (Fang et al., 2024): (1) IID within groups & IID between groups, where data is uniformly and randomly partitioned at both group and client levels; (2) NID- within groups & IID between groups, where groups receive statistically similar data distributions, but clients within each group assigned non-IID partitions via a Dirichlet distribution with parameter
0.1 (a 0.3 for SST-2); (3) IID within groups & Non-IID between groups, where clients within a group share IID data, but group-level distributions differ significantly, again using Dirichlet split across groups;
16

---

Published as a conference paper at ICLR 2026
and (4) Non-IID within groups & Non-IID between groups, where the entire dataset is partitioned using a Dirichlet distribution, resulting in heterogeneous data at both intra- and inter- geer-group levels.
Learning Rate Tuning. The learning rate (1)) tuned individually for each of the four topologies to ensure they all operate near their optimal convergence speed. Taking CIFAR-10 10 as an example, we explored search space of (2, 1, 0.5, 0.2, 0.05, 0.01] to identify the optimal vy. We found the optimal learning rates to be 1.0 for Star-Star, 0.2 for both Star-Ring and Ring-Star and 0.05 for Ring- Ring
Learning
B.2 COMPARISON WITH SINGLE- TIER FL
Figure 4: Test accuracies on CIFAR-I0 after training for 1000 training rounds with different learning rates.
To evaluate the performance of HFL. against traditional single-tier architectures, conducted comparative ex- periments using the CIFAR-I0 dataset with ResNet-18
model. The total number of clients was set N 100.
We compared our Star-Star and Ring-Ring HFL (G=10, MM=1) against standard single-tier FedAvg (denoted as Parallel FL, PFL) and single-tier Sequential FL (Li Lyu, 2023) (denoted as SFL).
The models were trained for 5,000 global rounds. The experimental results reveal distinct convergence correlations: (i) PFL. demonstrates convergence speed and final accuracy highly similar to that of the Star-Star HFL topology across both partitions; (ii) SFL exhibits performance characteristics compa- rable to that of the
001
Tex www.AAs
Ste-
Stan-tarr Bing-ting ting
HFL topology.
21.
1090 Giai Roaad
30.0
The convergence curves for the IID and Non- IID settings are visualized in Figure 5. These comparisons empirically validate that the hi- erarchical structure itself does not inherently accelerate convergence speed. Instead, the convergence characteristics of HFL topolo- gies strongly correlate with the synchronization mechanism (parallel vs. sequential) of their single- tier analogues. Consequently, the primary advantage of HFL lies in mitigating communication bot- tlenecks at the central server rather than improving convergence rates.
Glaba Beand
(a) IID
(b) Non-IID
Figure 5: Comparison with Single- -ier FL on CIFAR-10 Dataset
B.3 EFFECT OF GROUP ROUNDS P AND LOCAL STEPS K
To investigate the impact of computation and communication frequencies convergence dynamics, we evaluated all four HFL topologies on the CIFAR-10 dataset (Non-IID) under varying numbers of local steps (K {2, 5, 10}) and group rounds (P E (1,2,5) The convergence curves over the first 3,000 global rounds are presented in Figure 6 below:
Effect of Local Steps. Comparing the curves with fixed P 1 (Green: K 2, Blue: K 5, Or- ange: K = 10), we observe that increasing K consistently accelerates the initial convergence speed across all topologies. Increasing K increases the computational density per communication round, allowing the model to traverse the loss landscape further before aggregation. This confirms that greater local computation can effectively trade off communication rounds for faster convergence, particularly in the initial phase.
Effeet of Group Rounds. Comparing the curves with fixed K = 2 (Green: p= 1, Red: P 2, Purple: P = 5). increasing the number of group-level updates yields substantial improvement in convergence efficiency. Increasing P allows for more thorough intra-group group refinement before global synchronization. For Ring-Star, larger P means the model circulates among groups more times (or effectively allows more groups to participate sequentially if viewed as virtual steps), drastically reducing inter-group heterogeneity impact per global round.
17

---

Published as a conference paper at ICLR 2026
While both increasing P and K improve convergence speed, increasing group rounds (P) generally provides a stronger acceleration effect than increasing local steps (K) in our experiments. This suggests that for HFL, promoting consensus the group level (via larger P) is highly effective strategy for combating heterogeneity, especially for architectures with a Ring-based top tier.
183
Tou Po
Tou Accc (ho
Poi Ked
Pot Knd
Po1 Krd
Tea
2e1 Kel
P-IK-5
5-1K55
2-1K-5
K-10
K-10
2-1 5-12
K-17
P-2
7-23-90 K-2
K--2
K-2
Pod
7-5
18.
180
10:0
300
100
Star-Star
Star-Ring
Ring-Star
(d) Ring-Ring
Figure 6: Impact of P and K on Convergence of Four HFL Topologies
C
NOTATIONS
Table 4 summarizes the notations appearing in this paper.
Table 4: Key notations for HFL algorithm.
Symbol R,r r
Description
number, index of training rounds
G,g
number, index of groups
M,m m
number, index of clients each group
$1,81 81
number, index of selected groups under partial participation
S2, 82
number, index of selected clients each group under partial participation number, index of group steps number, index of local update steps learning rate (or stepsize)
P.v
K,
7j
effective learning rate
L-smoothness constant (Assumption 1)
upper bound on variance of stochastic gradients each client (Assumption 2)
8
constant in Assumption 3 to bound inter-group heterogeneity
C
constants in Assumption bound intra-group heterogeneity
C
average intra-group heterogeneity constant, defined Ç² Σ - S
F..
global objective/group p objective/local objective of client in group p global model parameters in the r-th round
(r)
(r)
local model parameters of the m-th client after & local steps in the g-th group after group steps in the r-th round
9.p.m.k
(r)
(r) Sg..mm, fo (x(
(r) n. E) denotes the stochastic gradients of F.m
Sg.p.m.
regarding g.p.m,k
18

---

Published as a conference paper at ICLR 2026
D PROOF OF THEOREM
In the following proof, we consider the full participation setting with a fixed execution order. Specif- ically, all G groups and all M clients participate every training round. We assume the execution follows deterministic sequence, corresponding to the natural indices (1, G} for groups and (1.2....,e 3f for clients, without random permutation.
D.I FIND THE FER-ROUND RECURSION
Lemma 1. Let Assumptions 1, 2 hold. If the learning rate satisfies 1 S 2TegPPMK then
E [((xlttl)) F(x(")]
)
T/² Lcg Lco GGMPKo
n cD 2
1
ΣΣΣΣ
G M
K-1
E
(r)
- x
g.p.m,R
g=1==0 K=D
where en is depelogy-dependent coefficient that takes values of 1/GM),, 1/G, 1/M, and for the Star-Star, Star-Ring, Ring- Star, and Ring Ring topologies, respectively.
Proof. In the following, we focus on a single training round, and hence we drop the superseripts r for while, e.g., writing a. k to replace x (r) a.p.m..k Specifically, we would like to use x to replace
(r) 1,0,1,00 Unless otherwise stated, the expectation is conditioned on x(r),
Starting from the smoothness of F (applying Assumption I, [x) VF S L||x y|D, have
[F (x + Ax) - F (x)
(x) Ax) + E||
A1
The model updates within a single global round for the four topologies can be represented by unified format,
Ax x (R+1) -())
Σ
CoT)
ga...m
g.P.m,k
where co denotes the dopology-dependent coefficient as defined in Lemma 1.
After substituting the overall updates Ax, we can get A
E (VF(x()) Ax
K-1
VF( 7000 Σ
(r) my...mmk
g
(2.m))) }
E
VF(x(1),
7 Σ ΣΣΣΣ
FF g.m (xx(r) (r)
G
P-1
M
VF(x()) 700
VF g.m (xx ppp.m.))) (
( 760
0
ΣΣΣ
K=0
- ( (VF(x()),
ΣΣΣΣ (x())
0o
19

---

Published as a conference paper at ICLR 2026
1 S X
P-1 M
ΣΣΣ
VF g.m (x (ppmmk)))
2" GPMK
E
k=0
G M K-1 ΣΣΣΣ
+ 7MGMKK
VF g. (x (x
V V. (x((1)
1
F 11
2
G M
+
7GGMPKK
Ff g.
(xc (pmmm)e)
V g.m 9 (xx(1))
K
ΣΣΣΣ
VF g. (x (pmmm))))
1100 GPMK
K=
P M K-1
2 (OGMMPKE//FF>>>
( 11 2" nL'co
ΣΣΣΣE
E
((r) xxpmm - x(0o|[]]
K=0
G M
ΣΣΣΣ
2 100 GPMK
k=0
|a - b12 for the first inequality and use Jensen's 's inequal- ity, Σ a 22 n Σi=1 | 2 for the last inequality.
where we use (a,
|a|| + |61|
Next, we bound the term A2.
G K-I
2
- = 2
LE
7700
ΣΣΣΣ
p.p.m.
9=1 p=
P-1 M C0 ΣΣ M
177
$ LI
gg..mm.k
V. g. (xe(r)
p.p.m.k)
p
0=0
+ 1 LE
ΣΣΣΣ
V a. (x((r)
k.p.m,k)
K=U
Let 17 S 2LcGGMKK we have
F((((-1)) F(x(1))
<E (VF(x!")) xx))
1 LE Ax 11
1
Log GMPKO
2 II20
1
ΣΣΣΣ E
[ x
(1 LooPPM Co77
P-1 M K-1 ΣΣΣ
g. k.p.m.k
GPMK
m=1 km
20

---

Published as a conference paper at ICLR 2026
0 P-1 M K-1
2
1
CD
Σ
E
(t) g.m.m.k - -x
9=1 p=0
m=1 k=
We define the client drift in HFL:
G P-1 M K-1 E, ΣEΣD
E (t)
g.p.m.k - -x
p=0
D.2 PROOF OF THEOREM 1 FOR THE STAR-STAR CASE
For Star-Star,
M
K-1
X ggp.m.k
X
gg.p.m,
Ba.p' and Kk-
M
D'=0
To bound E,,, we first bound El|x - x||2
B| X Kg.p.m,k - x
M K-1
=n²B|
Σ
Σ
8g.p' .m k 11
m.
M
k==
p'=0
m/=
M
K-1 1
S 2
gg.p.m,k
Σ
Σ
Sa ml M
V Fggm (x....mk))
M
k'=0
m/=1
K==
k==0
M K-1
V Fg (X5gpp .x)x 1|?
m
1=
p-1
M
K
k-1
+57 E
V g.m (x +
V F g.m (x
V F (x)
M
k==0
p==0
m'
k==0
M K-1
VF
Fm (x) 1|?
x²=0
m K==0
1-1
M K-1 Σ
k-1
+ BI
V.g.m (x)
gm (x)
Σ
VF, (x)
===
K==
K-1
(Fg(x)) 1
M
K-1
M K-1 Σ m'=1='00
+ B1l
VF, (x)
VF, (x) Σ (x
- 7/=0
(x)
K==
p'=0
===
K=
p-1
M
K-1
+
5n
E1
VF (x)
+
Σ M
0=
m'=lk' k==0
where we apply the Jensen's 's Inequality for the first inequality. The term E|xx - x|2 is de- composed into 5 components (e.g., local SGD noise, intra-group drift, inter-group drift, and global model discrepancy).
Bounding the first term in the left-hand inequality,
p p-1
M
K
5x E
gg.p.m.k
+
Σ
Bo ml k
V F.g. (xg.).mk))
M
='=0
F'=0
V
F g' (Xg.r", .m (rr 1|2
p'=0
21

---

Published as a conference paper at ICLR 2026
k-1
< 10m
2
E
B...m.k
V.g. (Xp.p.m I|
='=0
M K-1
10n²
Σ
E
Bg. mmikk' V go (x (C) 11?
M
0'=
k0=0
pK
S k0 + 10n
o²
M
Bounding the second term in the left-hand inequality,
p-1
5n/² E
gg.m (Xp.p.m,))
Fa.m (X mr)
k==
p'=0
k==0
M Σ
K-1
F g.m (x)
Σ
VF gggm (x) 1|?
M
p/=0
m
k'
k0
E
VF g.m (X..p.m,k))
V
F g.m. (x)112
k'=0
M
K-1
+ 100'ppp pMK
E
V F gam (X mmx,)))
F (x) 11?
M
TTX
m0
pK
p-1
K
S 100
E
x||
10L
11
E X 1 - x|1
M
pf
k'=0
Bounding the third term in the left-hand inequality,
M
K-1
M K-1
5m
El
F gaml
(x)
VFg (x)
M
M m22 =m =m==0
p'
0
mn
R
O
D' 0'=0
k
k-1
k-1
+
F g.m (x)
V g (x)
12
S
10r2 l
B F g.m (x) VFy (x)]1
A
0
0
The group objective function is defined as the aggregation of local functions, i.e., Fg M =1==1 Fg.m' Consequently, the summation of the deviations of local gradients from the group gradient vanishes.
1
Bounding the fourth term in the left-hand inequality,
K-1
K-1 VF (x)
5n EB
VF
V (x)
VF (x)
Σ
M
M
K=O
m='1
===0
F'=0
m'=1 ='=0
M K-1
PK
< 10 k
V F (x)
V
(x)i
+ 10n2
Σ
V (x) - VF (x)
M
k==0
p==m's 1000m=1kk ==
Bounding the fifth term in the left-hand inequality,
K-1
5 2
E
Σ
VF (x)
p²=0
===0
K-1
< 10 k
E
(x)
12 +
10mppMM
K
Σ (x)
M
k=
22

---

Published as a conference paper at ICLR 2026
Substitute these terms into Er,,
ko² + pK
E, S 10m)
Σ
M 0² + L2kk
B
g.
9.p.m.k
k==0
12
M K-1
k-1
+ L
g.pp J/ x11 + k
V
9.ms (x)
VFg (x)l
M
0 12
k'=0
k'=0
pK
p-1
M K
k
BI (x) (x)II
Σ
EI
-
M
m'=0m k'=
p-1
M K-1 Σ
k
(x) + PMM
B EVVF
M
m 1==0
Let C1 1=10 we have
F, R.c-0n/ccEK333---0000433------0-
+ +1IN::00AFEIT7711111/MMMMM1111""
< - 10n MK38
+ 20
After substituting E, into E [[ )x. we can obtain
B[F(x((+1)) F(x
PK
I -n)k 10 ( 1
GM
+ 1 + 5cm L P2 2
o² 5cm L 3 10c, 1'2
M
Let 02 12222 then
02 (F(x(1)) - F(x(
C2n 1
E [[[VF(( ||
0² T,
nRPK
GM
PK
+ 2,
0² + 12
10022
M
Let = ,,PK, and i - we have
V30L*
Lño²
L'
L'Fi002 12-PC22
())))
+
+ P2 + 1,22202
n
GPMK
P2K PMK
LA (LORA)12
(L'APO3)1/3
(L2A302)1/3
(
VGPMKR (P2KR2)
(PMKR2)113
(12A2333133 RP2
(T2
(33)
where z is defined as a model uniformly sampled from the (0) ...., rl (2- 12 of previous iterations, and & hides universal constants.
23

---

Published as a conference paper at ICLR 2026
D.3 PROOF OF THEOREM 1 FOR THE STAR RING CASE
For Star-Ring,
B-1
m-1 K-1
p-1 M K-1
Xgppmm.k - X
gy.p.m,k' +
Σ
Σ
8g.p.m ke +
Σ
Σ
gy.p' mm M
k'=
m'
k'=0
p'=0m ml
k=0
To bound Er, we first bound EE|
p.p.m.k - x||²
x||
k-1 1
1
K
M K-1
1
Sap.mm, +
Ba...m M +
Ba ml N I?
k==0
/=0m==
k-1
m- K-1 Σ
M
K
S 557
mg.p.m,k'
+
Σ
gg.p.ml
Σ
gy.v mlikk
V (xp.p.mk))
k==
ml
F== m k=0
k'=0
m-
K
M
K
F
VFa.m g.m² (x..p.m).e))
Σ
F
ga (x 1|
m' =1==1 K=
550m''1
+ +57 2
Vaa. g. (X
VF g.m (x)
Σ
Fg.m (x
k
m- 1 K-
M K-1
M K
V g. (x) +
Σ
F /.g.
VF
V.g.m
g.me (x) 112
m'
0
p'=0 ml
1' =0=0 ml
=1 k===0
R-1
m-
K-1
p-1 M K
k-
+ +51 |
VF (x)+
Σ
F gg (x)
Σ
Fam (x) - Σ
VFg (x)
K'=0
m/=1k=0
p'=Um k=0
k==
K-1
p-1
M K-1
VF, (x) Σ
Σ
VF, 11)
p'=0
K-1
M K-1
+ 5m El
VI (x) Σ
VV
ΣΣΣ VF, (x) EVE
VF
m/=1K=0
k=
M K-1
Σ
Σ
(x) Σ
Σ Σ |x)
m/=1 k=
p'=0 ml=1k=0
m-1 K-1
M K-1
+ +57
(x) +
Σ 3
(F)
ΣΣΣ (x) =0=
M=0
1==1==0
Bounding the first term in the left-hand inequality,
m-1 K-1
p
M
K-1
1
5n
gg.p.m, x
+
Σ
Σ
8g.p.mm Jo +
gg.p' m'
F (X
W
m
D 0
ml
k=0
M
K
F am (x x)
Fa.m (mt 112
m
p'=Um =0
< 15y
E Ba..m
V F.g.m (X
K-1
+ 15n²
Σ
Σ
E gg.p.m'.
V.g.m (x 32) 1|?
24

---

Published as a conference paper at ICLR 2026
1
M K-
+
15nj² Σ
E go.y m m
Vig.m (m xe) II?
p= m
=1 k0=0
< 15n + 1 mko2 + pM
Bounding the second term in the left-hand inequality,
m-1 K-1
51) I
g. (X
VF 9.m (x)
Σ
F gaml (xgs.m/,k))
m K
M
K-
1 M
K
FF g.ml (x)+
+
V
F.g.m
9:m" (X
F
g.m! (x) 11
// mm k'=0
D 0'=0
0
ml
k
S 115 k
E V a. (xp....))
g. (x)]|
k=0
K-
+ 15 mK
F g.ml (x V g,m" (x) 11?
m'= K==0
+ 15n PMK
Σ
E Vl gome (x m² x=)
V ggmm (x) 11?
8=0m
< <15L2'7²k
E g.I.y.p.m..
x11 + 15L3'f2m
Σ
E X x.pp'.n ,nd ,k x||2
k==0
m ===0
p-1
M K-1
+ 15L2n1'p PMK
Σ
Σ
E El|x
of x11
m
Bounding the third term in the left-hand inequality,
k-1
5n F
g... g.m. (x)+
F g. g.me (x)
V F g.ml (x)
Vlg (x)
=0=0
K-1
M
FF (x)
Σ
Σ
VF, (x) (x)
p'=
ml k==
K-1
< 15m2k k
V g.m (x)
VFg (2) + 15m² mK m
V g.ml (x) - VF, (x)112
k 0
M K-1
15n
15n2pMK PMK K
ΣΣΣ y'-Um'=1K'0
E
Bl go (x) - VI, (x)11
Bounding the fourth term in the left-hand inequality,
K-1
M K-1
2 E
(x)
Σ
(x)
K==
m==V==0
K-1 K-1
P-1
K-1
- (x)))
Σ
Σ (x
Σ ΣΣΣ (x
==
===
1- K-1
< 115
B
VF (x) - 22(x)]1
+ 15n mK
Σ Σ
EIVF - VF (x)
ml
25

---

Published as a conference paper at ICLR 2026
M K-1 VIVE (x) - VF (x)12
+
15njpMM
ΣΣ>
p==00==1
Bounding the fifth term in the left-hand inequality,
m- I K-1 Σ
M K-1
5n7 EI
(x)
V (x)
Fx)]l
p'=0m
p-1 1 1- K-1
< 15 k
F (x) 2 + 15m mk
Σ
(x)
k'=0
m
1===0
M K
+ 15n K
Σ
(x)]
V
Substitute these terms into E,,
E, S 15n7
Σ
kot + mKo + +MMK2 + L
Σ
E
x g.pmm. x||2
g.p.m,k
k==0
M
+ L mk
x11 E Kg.ppm'. - +
LMPMK
E Xg.p'' .m/,k' xx
k'=0
mr2 =1 k'=0
K-1
k
B F Fg.m Fx) - (x1(x)11 + mk
E V g.m fx - FF)(x)11
m ===0
( - VFxx)| mm
ΣΣ -
p-1 M
+ PMK
- -
P == ml
K-
M K-1 Σ ΣΣ B[
/X)F(()]I + mk
Σ Σ
(XFF(X))+PMMM)
m/=1k=0
v'=0m'=1
<
+
+ 1/ (V)
+ G + + 15L M 1 E,
Let CI 1-151'P'M'''pp we have
E, S 45c1 GP 4 4 GP3 & (x)]l²
After substituting E, into E (x(++)) - )x) we can obtain
[(F(x((+1)) F F(x(*))
1
45
1 PMK
<nMMPK(
0²
2
45
45
2 =nn"
1222 M2 + 15c L 2
26

---

Published as a conference paper at ICLR 2026
Let 02 2- 2 -- then
B[| B[IVF F ||
C2 (F(x(0)) F(x(1))
+ +
1
2 T
45
R
TRPMK
+ "
+ Goo' 2
45
L'
- and ñj
V60L* we have
A
Lijo²
L'
+ 1221888
PMK + P2
R
GPMK
E|| ( 0 LA +
(LOPA)U2
(L2A902)113
(I2A2C3)
R VGPMKR (PMKRT) (P2R3)
(R2)
where 2.R is defined as a model uniformly sampled from the ,0 ..... s. ,..,,......RR (R-1) of previous iterations, and S hides universal constants.
D.4 PROOF OF THEOREM 1 FOR THE RING-STAR CASE
For Ring-Star,
K-1
K-1
Σ
ΣΣNΣΣ
X g.pmm.k
Sg.pmm
Bg. m² ke+
M
oa mm M
8'=1==0
To bound E,, we first bound E
El|x, g.p.mk
x||
B
X g.p.mm.k
x||
k-1
M K-1
M K-1 Σ
= El
Σ
Jol 11?
&g...m.
8g. mr J
K-1
I 3 E
Σ
Σ
m.
M
gg.p'mm m' Me
gg mm .k
===0
k=
M K-1
gim. (Xg.mm,))
V Fg gime (X
k=0
K-1
Fo (x op mi we 1|?
M
k=
p-1
M K-1
+5
F g.m (xg.p.m,ke
V F gy (X mi,k))
m=l
k=
M K-1
R-
Σ
Σ
Fo mn (xe'' .p mmmmk))
V Fgm (x)
M
K-1
M K-1
V F
(x)
ΣΣ
Σ
V g' me (x) 1|2
y'1pp=0
0=0
K
+ T
g.m. (x)+
F oy (x)+
Σ
Σ
V Fg m' (x)
M
m=1
g'=1p'=0
k=0
27

---

Published as a conference paper at ICLR 2026
k-1
M K-1
M K-1
ΣΣ M
VF (x)
V (x)
Vy (x)
===
m=1 k=
m=1 k=0
p-1
M K-1
9-1 P-1
M K-1
+ BI
Σ
VFg (x) + Σ
Σ
VF (x)
Σ Σ
VFg' (x)
M
M
//=
m=
k=0
d'=l v =
m=1 k=0
p-1
M
K-1
9-1
M K-1
Σ
(x)
ΣΣ
VF (x) 1
K-=U
p²=0
m=1 k=0
s=1y==0
k=0
k-1
K-1
g-1 K-1
+ 5n
Σ
VF (x)
ME
VF
ME (x))
pf
g'=1p'0 k=0
Bounding the first term in the left-hand inequality,
M
K-1
K-1
ΣEM
5v/ 2 E1
m. +
Bg. an Je +
Sa' an
M
M
p²=0
m=1
k=
m=1 k=
k
M K-1
V gim (Xx...m.k))
V Fgmm (8g.2/ms
k=0
M K-1
V Fi mn ml 112
m=
0=0
k-1
$ 15 2
E gg.p.m.k'
g. (x..p.m,k))l 2|(
M==
M
K
+ +157
E Ba.p' mm 'k'
V F go (x (e) 1|2
M
p'=0
m12 =1=10
k0=0
M
K
+ 15
E Ellg B - Ff mn (x mm !1?
8'1 p'=0
m= k=0
2PK
2 29PK
< k0 2 + 15nj
0² + 15m
0²
M
M
Bounding the second term in the left-hand inequality,
M
K-1
Σ
5m
E
V Fgg. (X..p.,,k)
Figmi (xg.0' me x.)
D²=0
k=0
M
K-1
Vi mn smm"'
F
g.mm g.m. (x)
k=0
M
P-1
M K
F game (x)
VF
omm mmm (x) 112
M
m=1 0=
0'=l==0
m=1
k=
k-1
< <k k
El V Fy g.m (X.....)))
V
F. (x)]|
カ=
M
K
2 K
Σ
Σ
E
V
F
my (X
VF V.g.. gm (x) 1|?
M
00=0
===
28

---

Published as a conference paper at ICLR 2026
M K-1
+ 15n gPMK
E gy (f me,ee) - V V.g.m gime (x) 11?
M
m k'=0
pk p-1
M K-1 1
$ 15
E Xy.pmm,k x|| + 15L2 o
Σ p
Σ
x ml - x|1
M
R'=0
+ 2 P- M K-1
ΣΣΣΣ M
xg.p m/ - x|2 2
g'=lg'=0m=11
Bounding the third term in the left-hand inequality,
M
K-
M K-1
51
E
F g.m
(x)
A V Fa (x)
V Fg's an (x)
M
p²=0
k=
k-1
p-1
M
K-1
M K-1
V g (x)
VF (x)
Σ
V o' (x)
M
k' 0
p/
m=1
km0
km
k-1
$ <157 k)
|| V gg.m (x)
FFg (x)]12
k==0
+ 15n 2 pK
M
E
V F g.me (x) FF (x)]1
M
n' m m1 k==0
+ 15nj²
gPK
ΣΣΣ
g-1 P-1
M
E F (x) - FF (x)]
M
Bounding the fourth term in the left-hand inequality,
Σ
M
K-1
M K-1
57 "
(x)
Σ
Σ
VFg (x)
K'=U
//=0
d'=1p'=0
m=1 k=0
p-1
M
K-1
M K-1
Fx())
Σ
ΣΣ
M Σ
Σ
(x)
k=0
157² 2 pk
< 1
BI (x)
(x
EIVE, (x) - VF (x)]1
M
k==0
+ 157
2PPK M
ΣΣΣΣ
B - VF
Bounding the fifth term in the left-hand inequality,
p-1
M K-1
g-1
K-1
5n E
VF
(x)
+
Σ M
(x
ΣΣ
Σ Σ
VF (x)
M
M
===0
カ=
m=1 K=
g'=1p'=0
m=1 0=
M K-1
< 15m72k
F (x)
2
15 PMK
Σ
Σ
BJ|VF (x)
M2
==
1==1
1-1
K-1
+ +15n
Σ Σ
Σ {
M
d'=1'=0
M==1M=0
29

---

Published as a conference paper at ICLR 2026
Substitute these terms into Ey,
pK
9PK o² M
E, S 15n²
Σ
ko²
+
0²
+
M
9.p.m,k
k-1
pk
p-1 1 M
K
+ 1.2
m.pkm x||
E| Xg.g'. m' x|1
M
==0 m =1
+ 1 2
PP
ΣΣΣX M
g-1 P-1 M
o - x|| + k
V F - (x)11
g'=l p
k'
k-1
pk
K
+ k
V 2
(x) - VF(X)11
M
k'=0
p
gPK
ΣΣ
B ()) VF(x)]] VF(x)]1
M
0''=k=00'==k'''
p-1
M K-1
M
+pMK
Σ
Σ
CEMES
E (X))))
//=0
m==lk=0
g'=lp'=0 ='=
< 15/G
+
+1m + P
+
+ P + 15 + G (FF
+ K""'
Let C1 = 12 we have
E, GPMK GF + GPMK + 33
+45c,7 G M (x))
After substituting E, into (x((x(+11)) - F(x( we can obtain
((F(x(+t))-FF() -
45
GPK
S GPPK
2 an "
+
o²
M
+ 2 cn 'T'GK'' +150 1,2 p22
15
15
45
0²
M
2
Let 02 = p- then
C2 (F(x (()
1
B|]VF(>(>)1) <
conL 0² + 15
2 2 Ko²
R
RRGPK
M
GPK
15
45
+ +15c,om7 L
0² M
9 L2
2 cier
2
Let ij = GPPK and i - VBOL*
we have
A
Lio
L'11022 +
1A7322
E| (1)
GPMK GaPRK GPMK G2P2 + +128888
R
LA (LOPA)122
(IPAPO2)1/3
(12A202)1/3
( O
+
R
VGPMKR (G2P*KR²)13 (GPMKR8)1/
30

---

Published as a conference paper at ICLR 2026
13 (L2A302)1/33
+
PG 1/3 +
(R2)1/3
where x" is defined as a model uniformly sampled from the 110) ,...., .
(R- 1) of previous iterations,
and x hides universal constants.
D.5 PROOF OF THEOREM 1 FOR THE RING-RING CASE
For Ring-Ring,
k-1
m-1
K-1
p-1
M K-1
Σ
Σ
ggppm..k x =
gg.p.m.
+
Sg.pm +
gg m/ J
===0
m'=
K==0
p'=0
m
k=
M
K
ΣΣ
k=0 To bound E,, we first bound E Xg.p.m,k x||
m/
E
y.p.m. - x11
k-1
122 K
p-1
K-1
1 gy.p.m,k'
gg.p.m/ k
Σ
gg.p' an J
m
pf 0
M
Σ
Sat 3e mm m 11
K-1
M K-1
5n E
&g.p.m.k
Σ
Σe
go.p.m w
Σ
k=0
m'
p'=0 ml k==
M K-1
K
ΣΣΣΣ
8e o' J
g.g. g.m. (Xg...,ke))
Σ
V ga (x
k=0
k==
m m'=1k=0
M K-1
P-1
M K-1
F g.ms (Xg.0' me x)
Fg (x 1|?
F' m' ===0
p'=0
m =
m-1 K-1
+5n E
F (Xppp.m)
+
Fg (xg...m(.))
P-1 K-1
V F g.me (xg."mmt.))
ΣΣΣΣ
V F aa (f
k0=0
m-1 K-1
M K-1
VF g.m (x) -
VF
g.ml (x) - -E
V
g.ml (x)
m
k
1/ 10 10'm k=
M K-1
Fg m' 1x
K=
k-1
K-1
M K-1 Σ
+57 E
V
F. (x)+
Σ
Σ
VF m' (x) +
Fg.m (x)
P==
m'= 1F=1
p'=0 ml
==
M
m-1 K-1
ΣΣ
VF ml (x)
Σ
VF, (x)
VF, (x)
K==
w==1==00
P-1
ΣΣΣ
ΣΣΣ1
Σ
VFg 12
d'=lp=0m'=1l
K=
31

---

Published as a conference paper at ICLR 2026
k-
m- K-1
p-1 M K-1
+ 5n
B1
B1
vFg (x) +
Σ Σ
VFg (x)
Σ
Σ
(x)
=0=0
K==0
p'=0m'=1k'' K=0
g-1 P-1
M
K-1
k-1
m-1K-1 ΣΣ
ΣΣΣΣ
FFg (x)
Σ
(F(
/=11=00'=11
R=
R/=1V=0
Σ M K-1
8-1
M K-1
VF (x) Σ3
Σ
(F
>==0m=1k''
g/= 1
=
k-1
m-1K-1
p-1 M K-1
9-1 K-1
+ 5
VF
(x)+
Σ
VF (x) 0'=0m'n
VF ΣV
(x)1
my
Bounding the first term in the left-hand inequality,
K-1
K-1
5m
El
Sy.p.m.k
Bg.p.m K +
ΣΣΣ
gy ml
k
m
k=0
M
K-1
By v/
VF g.m (Kg..mm.k)
V Kg.p.me.e
p' ml
K=
k==0
m K'=0
M K
8-1 M K-
Fg (x
ΣΣΣ
V gg (x me !1?
g'=1p'=0'= 1==
1-1
< 20n²
E B.g.p.m..kk
Fg (x))).m..))
R'=0
K
+ 20n
gg.p.m
V F g.me (X )o) 1|
m A
M
+ 201²
E
/ m'
Fggm' (x and sz) 11?
//
+ 20m²
ΣΣΣΣ
E Bg of mm
go of Je) 112
< 20n ko² + 20n² mKo2 + PMK2 + 9PMK2
Bounding the second term in the left-hand inequality,
m- Σ
K-1 1
5T E
Fg.. (Xg...mk))
+
V Fggm (Xg.p.mter)
m'
M
M
K-1
VF gm (Xgg',ml
V F Fg
an
==
ml
=0=
M K-1 Σ
p-1
VF g.m (x)
V 9mm (x)
V F g.me (x)
D=
k'=0
P-1 M K-1
ΣΣΣ
F mr (x) 12
m
1-1
< 20n 3
E
V Fy.m (xp.p.m,k) V
(x)
k=
32

---

Published as a conference paper at ICLR 2026
m-- K
+ 200 mK
V g.m" (x V aim" (x) 1|?
m'
M
+ 200'pppKK
E
V g.ml (x mn xx) V F gyml (x) 11
M
K-
+ 220
E Fog. ml (f mn xx)
F mm (x) 1|2
k-1
K-1 1
S <00L?T²K
B - - -112 + 20 mK Σ
B x gg,g me me. - x11
+ +200,37/ pM
E g ml R x|1
p'=0
+ 20 gPMK
ΣΣΣΣ 0'=1p'=0m==1 1==
E Xg pt mm - xx1
Bounding the third term in the left-hand inequality,
K-1
5r7 E
F g.m (x)+
Vf (x)
Σ
Σ
V ag.m (x)
K'==
F'=U K==
F
P-1
K-1
(x) Σ K-1
Fg m/ (x)
EV
k'=0
M K-1
g-1 M K-1
Σ
Ff (x)
ΣΣΣ>
Ffg (x)
0 m M==0
g'm
0
K=
k-1
< 20/
k
EIIVE
g.m (x)
VR, (x)l + 200 mk
Σ Σ
B
g. (x) - VF, (x)11²
k==0
m 1k=10'=0
+ 20m2mmmp PM
B 9.ml (x) VF, (x)]1²
B
ml m0
P-1 M K-1
+ 20n 9PM
ΣΣΣΣ
V (x) - VFgr (x)112
Bounding the fourth term in the left-hand inequality,
m-1k-1
M K-1
5m 2
E
VFg
(x)
VV,
(x)
Σ
(x)
k
P-
M
K-1
k-
K-1 ΣVF(X
VF (x)
Σ (x)
F=0
W=
K-1
8-1P-1 M K-1
ΣΣΣ VF -
h-1
1- K-1
2007 2/
Σ
+ 20n mK
Σ
Σ
(x), -
VF (x)
K==
ml
33

---

Published as a conference paper at ICLR 2026
M K-1
+ 20n K
Σ
VI
(x) - VF
p'=0 mr
k==0
9-1
P-1 M
K-1
+ gPMK
ΣΣ
Bounding the fifth term in the left-hand inequality,
m- K-1
p-1
M K-1
5n E
VF (x)
VF VF
p-1
2k
V
(x)]]²
mk
Σ
E [x)
k'=0
M K-1
M K-1
+ 20m22pp pMK
BI + 20m gPMK
ΣΣΣΣ
[x)]
Substitute these terms into E,,
k-1
Frr S 20n2
Σ
ko² + mKo² PpMKo+++KPPP + 1.2k
Σ
E Xg.pmmk - x|1
9. M.P.m.k
17-1 K-
M
K
L m2
E Xg Jv- x11 + L3PM K
EB|l El|x m///m/// x11
p'
k/
P-1
L2 92MPMK
Σ
B B of m
x|| k
E VF V F.g.m(() (x) (x)(1
k=
K
mk
VF p.m (x) VE(())
V VF(3)1
K==D
m-
M K-1
m
(x) VF(x) + PM Σ
Σ
(x) - VF
===
M K-1
ΣΣΣ DEMEEVESE
+ +gPMK
g'=lp'=0m'=1
ΣΣΣ K-1
+ mK
[x + PMK
V
W==1==0
p'==0'=1
1IP- P-I-- K-1
+ 9P ΣΣΣΣ EE>>EVFFII VF(()
$ 20n GPMK3 2² + 2
+ POM
+ 200/6P/AK222--00/2233332--000010
+ GPM (PP-:/33---0NXPP23883--002----
20n X,wp://Awnnnna1111////////////"1
(1lp://f...1N11111"00001"""""""0 2X) (x)]l2
Let C1 = 1-201=G4 we have
F,, 80c11 p2 +0mn + 80c '2
34

---

Published as a conference paper at ICLR 2026
+ 8 V (x)]l
After substituting E, into [F ((+1)) - ))x we can obtain
E[F(x(()))- [1
1 <-nGPMK(, 40c1 -
40c 1 2
Let 02 1
then
-[I]F((()))1] [||]] 02 (F(x - -((x
+ 2 4GPMe
R
RGPMK
Let 1j = MMMM, and 5 I0Z we have
A
LNjo²
12'1002
12
E|| (1)))
nR
GPMK
GPMK"
G2p2
|]] 0
LA +
(LORA)U2
(IPAPO21113
(12A3
R VGPMKR (GPMKRB) (G2P"
(13A28991138
(R2)
where R is defined as a model uniformly sampled from the (0)) (R-1) of previous iterations, and Z hides universal constants.
E RANDOM-ORDER EXTENSION OF THEOREM
In the following, consider the full participation setting under random execution order. The overall proof strategy parallels that of Theorem 1, and in particular shares the same auxiliary result (Lemma 1).
The main difference between the fixed-order and random-order settings lies in the treatment of the heterogeneity terms > V (x) Vfg (x)ll² and Σg E (x) Vf, (x)] The distinction arises because under a random order, the expectation no longer scales with this prefix length, since the execution position of each client itself random. The constants differ significantly due to the random-order execution, a random shuffle of the participating clients at the beginning of each round. comprehensive comparison of the resulting convergence rates under both fixed-order (F') and random-shufie (S) settings is summarized in Table 5. As observed in the bounds, the ran- dom shuffling mechanism actively mitigates the accumulation of topology-speciie sequential updates. Mathematically, this is reflected by the emergence of additional scaling factors, G and M, the denominators of the heterogeneity and variance terms for configurations involving ring topologies. Because these error terms are further suppressed by G and M, the random-order exccution yields a strictly tighter convergence upper bound compared to the fixed-order setting, demonstrating its superior robustness against data heterogeneity.
bias inherent in
Since Lemma remains applicable, the proof proceeds by first bounding the client drift under differ- ent topologies, after which derive the corresponding recursion. Notably, the per-round recursion retains the same structural form as in Theorem For completeness, we provide the full proof below.
E. RANDOM-ORDER EXTENSION OF THEOREM FOR THE STAR-STAR CASE
For Star-Star,
K-1
Σ Σ
X Xy.pmm.k
gg.p.m,
Bg.p' yrt Kk-
M
k==0
==
k==0
35

---

Published as a conference paper at ICLR 2026
Table 5: Comparison between Fixed-Order and Hundom-Shuflte convergence bounds.
Topology
Convergence rate
Star-Star(F)
LA
ALo
(LPAPO))
(1PAPC))
R
VGPMKR
(P2KT2)
(PMKлT)
(P2
(ne))
Star-Star(S)
LA
(La
(12A802)
(E2AP(2)
R
VGPMKR
(PIKR))
(PMKR
(P2R))
(R2)
Star-Ring (F)
LA
(LO*Aj+
(L)A
(
VGPMKR
(PKR2)T
(PPMR9)
(R9)3
Star- (Sar))
LA
(12A9.2)3
VGPMKR
(PMКT))
(
(R2)3
Ring-Star (F)
LA
(LO
(LPAPO9)
(LPAPOO))
(LAA)
(LPA388)3
R
VGPMKR
(GPP*KRA)
(GPMKR))
(G2P2RA)
(Re)
(13426833
Ring-Star($)
LA
π
VGPMKR
(GPP
())
(Gamanay
(GRe)
Ring-Ring (F)
LA
(LOPA)
(LPA8AA)
(
(
VGPMKR
(GPMKR))
P2)
(R2)a
Ring-Ring(S))
LA
(LO
(L'APOP)3
(
(
R
VGPMKR
(GPMKR
(R
(GR
To bound Ep, we first bound ppp.p... x||
B|| g.p.m - x|1
M K-1 Σ
8g.e' mm Jkl 112
mg.p.m,
M
p'
55 E
mg
By.p' ml k
V Fg (x.)).m,)))
M
1/2 ='=0
K-1
Σ
V F gaml (xpp",m(ar)) 1|?
m' k'=0
M K-1
k-1 1
+5 E
V g.m (X..p., +
F g.ms (x x0)
V
g.m (x)
M
0
p==
171
k
M K-1
g. [x)
2'=0
m ===
k-1 1
p-1
M K-1 Σ
k-1
+ 5m
E|
F F.m (x)
Σ
Fg (x) - Σ
VF, (x)
M
===0
k==
VF
11
K-1
5n 2
VF (x)
Σ
Σ
VF
VF (x) Σ M
VF
==
p'=0
m==lk=0
k=
y==0
m==kks ==
36

---

Published as a conference paper at ICLR 2026
M K-1
+ +5
Ell
VF (x) +
Σ p²=0
Σ
VF (x)]?
k==0
m/=1k==0
where we apply the Jensen's Inequality for the first inequality. The term Bi| g...m.kk - x11² is de- composed into 5 components (e.g.. local SGD noise, intra-group drift, inter-group drift, and global model discrepancy).
Bounding the first term in the left-hand inequality,
p-1
M
K
5n
mg.p.m.k'
+
Σ
By. ml
F.g.m g. (Xg.p.m,k))
M
1 =0
V' =
k/=0
k=
M K-1 1
Fa (ma. 1|?
F'=U
m
< 101
E B...m.k
Vgg. (X
k=0
M K
+ 10n
Σ
E gg.y .mi
V g,me mm 11?
M
m'
K0=
2 PK
< 10
101
M
Bounding the second term in the left-hand inequality,
p-l
M
K
1
5n
E
F (Xg.p.m,)) )
Σ
V
F Fg (Xg.z
M
p²=0
M
K
fm (x)
Fomm (x) 1|?
D0=0
k-1
10n22
El V g.m (Xg.p.m.k)
F
V
F.g.m g.m (x)]1
M K
+ -1n2² PMK
E V F m' (Xa. smi - V Fggm (x) 11?
mn' =1 Xy...m,kk
=1=00
pk
M K-1 Σ M
p-1
$ 1
E
x||
10L 1
X g. mi x|1
0==0
p²
Bounding the third term in the left-hand inequality,
M
K
M K-1
5v/
gg.m (x)
VF,
p'=0
m
===0
m V'=0
k=
k-1
g.m (x)
Σ (x)
10n 2k
B BIVF g. (x) VPy (x)11
The group objective function is defined as the aggregation of local functions, i.c., Fg t Σm== Fg.m' Consequently, the summation of the deviations of local gradients from the group gradient vanishes.
37

---

Published as a conference paper at ICLR 2026
Bounding the fourth term in the left-hand inequality,
K-1
K-1
5n E
Σ
Σ Σ
(x)
VF
Σ
Σ Σ
V (x)
k==
y'=0
m/=1
k==
m'=l
M
pK M
< 101 k
B
(x)
VF F
+ 10nj
B - (x)12
k0=0
p m'=0m'=1
Bounding the fifth term in the left-hand inequality,
Σ
K-1
5ny "
E
VF (x)
p'=0
m==l==0
K-1
< 101 k
E
F [x)
12 10n0pppM K
[x)
M
k==
m/=1 k==0
Substitute these terms into Er,
pK M
E, S 10m²
Σ
koz +
0² + +Lak
E X Xg..mm x|2
M.D.m.k
====0
p
p-1
M K-1
+ 1
g.rl m x12 + k
V g.m (x) Vig (x)]1
M
y/ m
pK
p
M
k
V (x) (x)11
BI - VF
M
0'=0m=11 k==0
p-1
K-1 Σ
RI/FF 2 + PM
Σ [
M
n'=1
k'=1k'00
Let C1 1-10L'P'R7.F we have
E, S GP 1000://PM338++00000000"00
+ +ctooi/CchMEYYYYYIIIllllllllHAA"
+ 20c M
After substituting F,r into F (x(++))) - F(x(t))), we can obtain
E[F(x(++1) (()(
< - 2 10c ""= -1 PK 12
+ 5c1 L + 2 p2
o² + L22 + 10c 1229 M
Let C2
1- then
R-1
02 (F(x(1)) F
+ 12n 1 0² 102 + =2, Ko² 22²Ko
E[] ||
π 0=0
nRPK
GM
38

---

Published as a conference paper at ICLR 2026
PK
+ L22
M 0² + L 100=
Let fj = nPK, and îj 5 V/30 we have
Lñjo²
+ L2iP0²
PKK + L'iI002
L
+
PMK +
p2 + 1,2
R
GPMK
LA +
(ToPA)12 (T2A
(I2A2022)/33
( = -
R VGPMKR (P2KR))US
(2 1/3
(L2AP
(L2A289)1133
(P2R2)
(R2)1/S
where x" is defined as a model uniformly sampled from the (0)) and S hides universal constants.
x (R-1) of previous iterations,
E.2 RANDOM-ORDER EXTENSION OF THEOREM FOR THE STAR-RING CASE
For Star-Ring,
K-1
p-1
M K-1
Σ Σ
Σ Σ
X.p.mm.k
m..p.mm. +
8g.r.mm K +
gg.pl.m mm ,kt
m
0'm0m==
To bound E,,, we first bound E p.pmm. - x||
E| X p.p.m. - x|1
K-1 Bg.p.m N
K-1
=n'E|l
mg +
Σ
Bg.e' mnd K ||?
k'=0
K
km
K-1
M
K
< 5n/ B1
Sg...m,
Sg..mm M
Eg.p' mm R
V Fg g:m (Xp...,)))
k==0
m'=lk'= ='=0
p0=0m m'=l k=0
k==0
m- K-1
M K
F g.ml (X....m'.))
Σ
V
gg (Xp.m.m) 11?
m' ==
==mm =1 ==
K-1
+5 E
Fg (Xp.p.m.))
V (x)
+
Σ
Fg.m (xxgp..m.k)
m==1ka
K==
K
M K-1
M K
F g.me (x) +
V F gam! (x
V
gome (x) 112
m'
m' k==
m k'=0
m-1
K-1
p-1
M K-1
+ +5
V F g.m (x)+
Σ
VF g.me (x)
V
FF
g.m (x)
VFg (x)
0
m/=1
k=
P-1
M K-1
FFg (x) Σ
Σ
Σ
(1)
m'=1 m'=1k 10
p'=0m=1 11==0
m-1 K-1
M K-1
k-1 Vf, (x)
+ 5r 2|
VF, (x) + Σ Σ
(F, +
ΣΣ>
Σ
VF (x)
P=0
v'=0m=Ik'-0
k=
m-
p-1
M K-1
(x
Σ Σ
Σ
1x)
p
1-1
K-1 ΣX
m-1
M
2
Σ
VF
M=0
39

---

Published as a conference paper at ICLR 2026
Bounding the first term in the left-hand inequality,
m-1 K-1
M
R-1
5r 2 1
Sg.p.m, A
Sg.pim' &
Sg.p mm Mv'
V.g.m (xo...m.))
p
m
M
K
F gam! (xg.p,el,)))
F. mm 11?
p'=0m'= k==
S 15n
E gg.p.m.k' V gm (X
k==0
+ 15n
E ga..m R
F.g.m (X xe) 1I?
p-1
M K
+ 15n)
E ggg.r'.mm mm/kk
V.g.m (x 11?
7/=0m
k'=0
S 11512ko² + 15 m + p.
Bounding the second term in the left-hand inequality,
5n7 E
V gm (X....m.e)
VF g.m
(x)
Σ
Σ
V F
g.ml (X..p.ml kK)
W
m'
m
K-1
p-1
M K-1
p-1 M K
V om (x) +
Σ
Fa (Xg.0' ne)
ΣΣ>
F. (x) 112
#=0m
1==00
p
k==0
k-1
< 15m2 kk
Σ
|B|l F. (x
V.g.m (x)]1
k=
K
+ 15
E V Fg.m (xg...e.x)) - V Fg.m' (x) 1|?
m' m'=1ke
+ 111 PM
E V
Fggmm g.me (xg,0r me xx)
V F. game (x) 112
mmm ===0
< <15T.212k
E x g.p.m.k - x12 + m
E g.pp and Jo Jm
x||2
m ===
M K-1
+ 15L"nppMK
Σ
Σ
E
me
x|12
p'
Bounding the third term in the left-hand inequality,
K
M K
k
5n E
g. (x)+
+
F gmm
(x)+
VF
g.m (x)
VF, (x)
=
m m==1 =
k==0
K-1
p-1
M K-1
Σ
VP, (x) - Σ Σ
VF, 12)
F/= K==
m-1 K
< 15ny h: Σ
E V Fm (x) - VF, (x) + 15n K
Σ
Σ
E V
Fg.m
g.ml (x) - VFy (2)
0=
m
w== K
40

---

Published as a conference paper at ICLR 2026
g- M K-1
+ PM K
Σ Σ Σ
B V (x) - (x)l1
(x)ll²
Compared to the fixed-order case, the second term of the above equation 15n/ K
Em Σ =K= VF qm (x) F (x)] is missing a factor of m.
Bounding the fourth term in the left-hand inequality,
K-1
5np E
F (x)
EV (x)
E
Σ
(x)
K=
m'=1==0
M- K-1
M K-1
(x)
Σ Σ (x
ΣΣΣ
(x)
k=0
m==1k=0
=
K-1
< 1577 k
VP y (x) - 2x)] + 15n mK Σ Σ
FF (x) - VF (x))]
k'=0
m =1=0000
1- K-1
+ PMn
ΣΣΣ
E VIV (x) (x)1
Bounding the fifth term in the left-hand inequality,
I K-1 Σ
M K-1
5n7 E1 E
V
(x
Σ (x)
R==D
m'=1ka K=
p'=0m'=1k'=
1 m- K-1
< 15n² k
V (x) + 15n mk
(x)
#==0
p'=0 m2 m'=1k'=0
p-1
M K-1
+ 157'pMMK
(x)1
1 1==
Substitute these terms into E,,
E, S 15n2
Σ
ko mKo² +pMKo² T12k
E Xg.p.m. x|12
8.P.m.k
m-1 K-1
M
K
+ L mK
EE Dg.ppm'. - -112 + L3PMK K
E Xg.p' ,m/
x
=0= m
k==0
k
BI 9.
(x) - (x) +K
E| F g.me (x) (x1(2))12
M=
m- K-1
k
(x)VF(()) - VF(x)11 mk
-
p-1 M K-1
+ +pMK
(x)
p=00 m
m-1K-1
p-1 M K-1
E||F(()) +
ΣΣ
BIVF(X))
Σ [X]EF())11
W=
p'=0m'=1k'a
< <15y + R2M 1
41

---

Published as a conference paper at ICLR 2026
+
15
+
Let 01 1-1012 we have
Er S 45cm GP' + 30M + 45c G 33388
+ G (x)]]
After substituting E, into E F ( F Fx we can obtain
B[F(x F(
$ ~nMPKK -ー-20/1 | PMK o²
G
45
2 cnn 11222 + 15 L + 2 L
45
Let 02
1 -apaaaaa then
R-1
| (F(x(0) F((
+ + 1 45
E|| VF
-2
R
1RPMK
+ 15c: e212 L3MK +
45
LP
2
= and i VBOl"
we have
A 1
Lijo²
+ 1.21802
PMK + 1,2i5(2
E| V|/ R
+ +122888
GPMK
P2M
L.A
(T21222)2/3 R VGPMKR (PMKRA) (P2MR3) 1/3
(LO2A)12
+ (T2A302)1/3
O
+
(R2)
where h is defined as a model uniformly sampled from the (0) x (R-1) of previous iterations, and $ hides universal constants.
E.3 RANDOM-ORDER EXTENSION OF THEOREM FOR THE RING-STAR CASE For Ring-Star,
k-1
p-1
M
K-1
9-1 M K-1
ggp.m.k X
gg. km.p
+
Σ
Σ
Bg.s'
Sg of and Je
M
===
p²=0
m=1
0=0
g'=1==00
m=
To bound Ep, we first bound [El|x
x||
E Bl..mmpmm.k
x|12
M K-1
M K-1
= 1
Σ
Σ
8g pt ml J ||
g..pmm.k
go me d
0=
k=
< 55 21|
Σ
Σ
Σ
Σ
8g. mm ,e'
8g mmmmk
M
#=0
k=0
42

---

Published as a conference paper at ICLR 2026
M K-1 1
F gim (Xp.p.m.k)
Σ
V Fome (f
m=1
P-1
M K-1 Fl / 1|?
ΣΣ
M
m=
K=
p-1
M K-
+51 E
V
V'...m g.o (x....m))))
aa (x mi xe)
M
F'=0
m=
k=U
P-1
M K-1
Σ
of (xg'pp..m mm.
g. (x)
M
9' /
K=0
M K-1
F g. (x)
Σ
Σ
V mm (x) 1|2
M
g'
K=U
K-1
K-1
E5
V g.m (x)+
FF (x)+
Vgg.m ml (x)
M
K=
g'=1''00
k=0
M K-1
9-1
M
K-1
VF
F 11
M m=1 k=
A'
m=1 k=0
p-1
M K-1
P-1
M K-1
+ 5v7 |||
Σ
Σ
V (x)
M
0==0
/'=0
m=
0/=1p=0
m=
k=0
p-1
M
K-1
P-1
M Σ
K-1
Σ (x)
VF (x)
Σ
Fx) 2
K==
p²=0
m=1
k=
m=1 k=0
1-1
p-1
K-1
P-1 M K-1 ΣΣ
+ 5n
E
VF (x)
(x
VF
VF (2)
8'-1-'0
k=0
Bounding the first term in the left-hand inequality,
p-1
K
M K-1
5m/
Σ
m.
+
Σ
Ba. and Jo
ΣΣ
M
Bg an 3t
M
M=
p'=0
k=
0'=1p==0
k=0
k-
M K-1
V F g.m (xp.p.,)))
V F Fg (Z m
00=
m=1 k=0
M K-1
F mn (x m se) 1|2
M
m=1
k-1 1
< 1572 2
V F.gm (x (x)
gg.p.m.k
M
K
+ 15n²
E Bg.p' mn
V Fg (x am', xx)) 112
M
122
k
P-1
M
K
+ +15 2 Σ
E Bi
VF am (pt amt (sr) 1|?
M
0'=
m=
k=0
< ko² + 15n7 PK
0² 15n² 2 9PK
0²
M
M
43

---

Published as a conference paper at ICLR 2026
Bounding the second term in the left-hand inequality,
M K-1
5nj
E
V F g.m (xg...m))))
Σ
V
g.m' (X5g.' me ())
M
0
m=1 R=
M K-1
Fg am (Xgg m'mmmm
VF g.m (x)
K=
M K-1
8-1
M K-1
F game (x)
Σ
Fg Fa'mm m (x) 11?
M
P==0
m=1
km0 0
g'=L==D
m=1
km0
S 15n k
E VF g.m (X...mmk))
F g.m (x)]1
km-0
M
+ 15m'pMM K
Σ
Σ
E
V F me (m - V Fg (x) 1|?
M
p'=0
m/
k=
M
K-1
+ +15n 9PMK
Σ
B
F.ggg.m g.m" xg. - VF g.ms (x) 11?
M
9'
m km
pk p-1
M K-1
S 15L2,22k
K.p.mmkk x|| +
E pa ml. J x||
M
k'=0
p'=0 ml ml=
+ 1 2PK
ΣΣΣ M
P-1
M K-
Xg.y ml Kk' - x1 2
g'=1p'00
Bounding the third term in the left-hand inequality,
k-1
p-
M
K-1
8- P-1
M K-1
5
Fg
(x)+
+
Foom (x)+ +
V Fg mn (x)
k 0
p²=0
m=1
k=
g'=1 0'=0
m=1 k=0
p-1
M K-1 Σ
g g-1 P-1 ΣΣ
K-1
Vg g (x)
VFg (x)
Σ
VFg (x) 1|
M
M
===
m=1
k=0
p'=1p'=
< 15m2*h k:
EI| F p. (x)
VF, (x)112
==
+ 157 pK
p-
M K-1
Σ Σ
E
V g.m" (x) FF, (x)
M
y'=0 ml =1
+ 15 2
gPK
ΣΣΣΣ
g-1 P-
M K-1
Fg (x) - VF (x)12
M
Bounding the fourth term in the left-hand inequality,
k-1
M K-1
P-
M K-1
57
2
E
Fg
(x)
Σ
3
V (x)
Σ
VFg. (x)
K'=0
#==
m=1
k=
g'=1p'=0
m=1 k=
A-1
p-1
M K-1
8-1
M K-1 Σ
Σ VF
Σ
Vx
Σ
Σ
(x) 1|
M
g'=1=/=0
k=
2 pK
< 15 k
Σ
B (x) VF()) 15n²
Σ
Σ
Σ
(x)
M
k=
44

---

Published as a conference paper at ICLR 2026
PK M
g-
P-1
M
K-1
+ 15np
B VFy (x) VF (x)
Compared 15n/ PK 3f
to the fixed-order case, the last term of the above equation B (x)
g/ Zy= Em
VF (x)]l is missing a factor of
Bounding the fifth term in the left-hand inequality,
p-1
M K-1 Σ
9-1 K-1
5n/ E
+
Σ
(x) VF
ΣΣ
Σ
VF (x)11
===0
g'=1y'=0 M K-1 Σ
k=0
$ 15m2k
(x)
2
15n PMK
Σ
M
//
K-1
=1n 15n'gg gPMK
ΣΣ M g'=1p'=0
ΣΣ (
m==1/=0
Substitute these terms into E,,
pk
0² 9PK 0²
E. S 15n²
Σ
ko² +
M
g.p.m,,k
M K
kk
+ I.2 k
E p.p.m
x|2
E xf...mmmm x11
M
k==0
p/
=1 k'=0
+ 1 PK
ΣΣΣ
M K-1
E a.0 mm Me - x|| + k
E V (x) (x)11
M
k'=0
Kk p-1
(x) 2
B)) VF(X)11
M
0=0
PK
M
+
ΣE
( -
E VF(x)
M
d'= pl
0=0
P-1 1
M K-1
M K-1 ΣE
+ +pMK
Σ
E
Σ
B[]E(())13
M
#== M'=1R'00
8'11'=0
w==
< of 15"
+
+
+ ==
Let 1 we have
E, < 15 + 30c G + G + P (x)
After substituting E, into [[F(x((+1)) - F(x( we can obtain
E(F(x(++1)) -((x
1 45
GPK
I G 2
L
o²
M
45

---

Published as a conference paper at ICLR 2026
15 + 2 an LG +15en 1? G2R2K2
of+ 15 La a paPLEPK
45
M
Let C2 - then
R-1
- - F(x(R)))
BIIVF(x!")))
+ t 1
+ 0²
0²
c0e K2²
R
RRGPK
M
2
GPK
15 2
45
c25 L2
M d²t
21022 L + c0n 2 L'GP2
Let i) = nPPK, and îj - vOOL*
we have
A R
Lijo²
G2P2K + LAio02
1770022
L2F 178888
B BII R) -
+
+
GPMK + G2p2 G
GPMK
LA O
(LoZA)U2
(124902)1/3
(1244922//3
||
R
VGPMKR
(GAP2KR²) (GPMKR3) (L'A363)1/3
(LPARC3)VS
P2
(GRe)
where h is defined as a model uniformly sampled from the z00) (R-1) of previous iterations, and S hides universal constants.
E.4 RANDOM-ORDER EXTENSION OF THEOREM FOR THE RING-RING CASE
For Ring-Ring,
m-1 K-1
p-1 K-1
Σ
ΣΣΣ
X g.p.m..k X
Sg.p. m
+
ga.p.m +
Sa. mn J
#=0
m 1
p'=0m'=1 k==
9-1
P-1
M K-1
Bg m/
R=
To bound E,, we first bound E X g.p.m,k x||2
E X g.p.m.
x||
T2 K-1
p-1
K-1
17 E
gg...m.k'
gg.p.m'.k k
ΣΣ
Σ
Bg.p' an J
W=
m
==
K-1
ΣΣΣΣ
Sa' mm B'''n',m'''' 11?
M K-1
5 E
Σ
gg.p.m '
m
K=0
p' p'=0 m' A=0
M K-1
K
ΣΣΣΣ
VF
g.m (x..).m,r))
F a.m (x kc)
K=
m' K=
M
P-1
M K-1
ΣΣ7
F (X an w
V
Fgmm
oe I|2
1-1
m-1 K-1
+ +5n E
V (x..p.m.k)+
+
Σ
Σ
VF
F. (X..p.m..k)
46

---

Published as a conference paper at ICLR 2026
MMM K-
g-1 P-1 M K-1
V gm (Xg.5 me (e)
Σ
Σ
V F (X5g) oo me
m
0
m000m======
k-
m-1 K-1
p-1 M K-1
F g.m (x)
Σ
V.gm (x)
ΣΣΣ
V g. (x)
me' =1= K==0
7'=0m' k=
M K-1
ΣΣΣΣ
Fg (x)
/'=1/'00==1H'
1-1K-1
p-1 M K-1
+5 E
VF g.m (x)+
Σ
Σ
VF
g.m (x)+ +
Σ
V g. (x)
m'=
p'=0
M
VF gg (x)
VFg
Σ
VF (x)
K==
M
VF, ΣΣΣΣ
V (x)
g'=lp'=0m
m-1 K-1
M K-1
+ 5n Bl
BI
(x) +
Σ
VFg (x)
Σ ΣΣX
VF (x)
k=
M=0
p'=0m k==0
M K-1
k-1
m-1 K-1
Vg (x)
Σ
(x) - Σ M (x
K==
m 1==
M K-1
8-1
M K-1
Σ
Σ
(x) Σ
Σ
Σ
12)
A' 0m
g'=1 p
ml
m-1K-1
K-1
M K-1
+ +
(x)+
Σ Σ
Σ
Σ
(x)+
VF VF (x))
W==W==
p'=0
0=00m=1k k=
g y=1p==0m=11k
Bounding the first term in the left-hand inequality,
K-1
M K-1
5m EI|
Σ
Σ
Ba.p.m K +
Σ ΣΣ>
Σe
Bg kk
=0=
F0=0 10001111 k=0
P-1
M K-1
K-1
Bg x/ mi.k
F g.m (Xg.p.mkk)
Σ
Σ
V
(X xt)
m' O=
K==
M
K-1
8-1 M K
Σ ΣΣΣ
V Fo (X m))
V
V. (Xo' of mn (x)))) I|?
=0=0
y'=1/=00
k-1
< 201²
g...m.k
V. (x)..mm)))1
K
+ 20n2
E Bg.p.
V F gam (x (x 1o) 1|2
p
M
+ -20m
E go me de' Fggm (xg me xe) 112
F/
9-1 P-1
+ 20mm
Σ3ΣΣ
E
pt Fy xm )e) 112
0'=
47

---

Published as a conference paper at ICLR 2026
mKo² + +0n"²mKo I ko² +
+ 20
Bounding the second term in the left-hand inequality,
mn-1 K-1
5ny E
V F gmm (xp.p.m.d)
+
Σ
V F
gam" (Xg.p.m² (6)
m/=1
k'=0
M K
M
K-1 1
Fggm (xg,0' m² xe)
V Fo (Xag' of me mo)
F ===0
y==pp=
VF g.m (x)
V gam (x)
Σ
V g.ml (x)
ml k==0
P-1 M K-1
ΣEΣ
F 12
m/= K==0
1-1
5 20n k:
EE E g.m (xp.p.m.)) - V g.m (x)ll
k'=0
+ 20
E
V g.me (Xg.p.me V F g.m (x) 1|?
m/=1
p
M
K-1
+ p0K
E
g.ml (Xg.pt, VF Vfg.m (x) ||2
F mm
9-1
P-1
M
K
+ 900
ΣΣΣ
V Fg an of (e)) V VF gy (x) 1|2
R-1
S 200L'12
Σ
El X x|| + +20L3'² mK Σ Σ
m
xg.0' mn x||
M K-1
+ 20 PMM K
E Xx - x11
p'=0
8-1
+ 20 gPMK
ΣΣΣ
X m' - x11
g'=1p'=0m=11k'
Bounding the third term in the left-hand inequality,
m-
M K-1
5n E
Fg
(x)
+
Σ V. (x)+
Fy.m' (x)
0'=0m'= ml
M
K-1
ΣΣΣ
VFg am (x)
(x)
Σ ΣΣVR
VF, (x)
M K-1
VF, (x) ΣΣΣΣ VF 12
k-1
K
< 20m2² k
E
V Fm (x) - (x) + 20n K
E VF FF (x) - V., (x)
k==0
m
M
+ 200
Σ
3
Σ
E
V g. (x)
-
2'=0m'=1''00
48

---

Published as a conference paper at ICLR 2026
P-1 M K-1
+ 20n gPMM
VF me (x) VF'g (x)
Compared to the fixed-order case, the second 20n² K
term of the above equation
Em== Σ
-R-1
gm (x) - FF (x)l missing a factor of m.
Bounding the fourth term in the left- inequality,
k-1
m-1k-1 Vig (x)
M K-1
5m
EI El
Σ
VF, (x)
Σ
Σ
Σ
(x)
=0=0
ΣΣΣΣ
VF (x) Σ
(x))
Σ
K=0
9-1 M K-I VF
I2)
4-1
K-1
< 201 k
- - + 20m mk Σ
Σ
BIVF (x)
VF (x)]1
k'=0
+ PM
Σ Σ
VI (x)1
F'=0'==1
M K-1
+ PMK PMK
ΣΣΣΣ
VFG (x) Fx()))
8'
Compared
to the fixed-order case. the last term of the above equation
(x) F (x)] is missing a factor of 20n' gPMK E >M E g-
Bounding the fifth term in the left-hand inequality,
K-1 ΣΣΣΣ VF (x)1
5n7 E
F
(
+
k'=0
ml
20 k
V F 2 + 20m
mk
(x)
K=0
p-1
M K-1
P-1 M ΣΣΣΣ
+ 20m PMK
Σ
( + 20n gPMK 90
V (x)
m= k
Substitute these terms into E,,
k-1
Fr, S 20n2
Σ
ko² mKo² +pKo22 gPMMo2 + 1.2k
Σ
E x Xg.p.m.k - x|1
M.P.m.k
m-
K 1
K
L2mK
E ggg.. M x112 + L3pM K
E X m/ x512
p'
12gPMMK
Σ ΣΣΣ
E Elxx pl
x|12 l
E V F VF5(x))12
0'=1p'=0m
49

---

Published as a conference paper at ICLR 2026
m- K-1
+
K (x)
+ mk
[x) V
m
=
k'=0
M
K-1
K
F -F((X)1 +PMK ΣΣ
Σ
VF(x)||
M K-1 9PMK ΣΣΣΣ
E VF2 - VF(x)| + VF
K-
M K-1
+ mK
W' VF(x]]]
PMK
E VF(x)]1
p'=0 m0==1 k=
P-1 M K-1
+ PPMK ΣΣΣΣ VF(x)]?
S ---- 200
20n
+ +00 XXNN:///IIIIIT//ACCCX/XXXXTT1111
+ 20/
Let C1 2-201.GPPMM*K we have
E, S S0c G2 + GPM G
+ M (x)]
After substituting E, into E| (x+1) - )x. we can obtain
B[F(x(1-1)) F(x
s < _ 40c,1 6²
+ 40c 3 L2GP2M2K' + 20c LGPM +40mm
Let 02
3-40c1 PAG then
R-1
C2 (F(x (()
+ tom + 400c
1RGPMK
20c 20 TT2M333 +40cc
=et GPMM, and 1) S ToL have
A
Lūjz
122002 1272(2
(1) S
+ GPMK G2PMM +
7R
GPMK
G
LAA
(Lo2A)1/2
(T2A202)1/3 (T222
E[I[FF( 119
R
VGPMKR (GPMKR3) (GPP'MR2)
(12228221133
(/33
where " is defined as a model uniformly sampled from the (0) ( R-- 1) of previous iterations, and & hides universal constants.
50

---

Published as a conference paper at ICLR 2026
F PROOF OF THEOREM 2
In the following proof, we consider the partial client participation setting, specifically, selecting partial clients without replacement. So we assume that m1 (1),
[ is per- 72 { =2(2).... ..., 22(M) is permutation of {1, ... M in a certain training round. And only the first S. selected clients T2 {r2(1), x2(2), (
mutation of ...,, G),
within the first S1 selected groups (1) =1))).... ((())) will participate in this round. Unless
otherwise stated, we use E[.] to represent the expectation with respect to both types of randomness (i.e., sampling data samples & and sampling clients T22).
F.1
FIND THE PER-ROUND RECURSION
Lemma 2. Let Assumptions 1, 2 hold. If the learning rate satisfies 17 S SPPP' then
[(x((+11) - -
1 L
s S
2
5 " 2
2" Lco 2ep S
2
Lco 2 S P2 k2
+ 2
5.
8 K-1
tn ΣΣ 2
Σ
p. 12.
===1p=0;==1k=
where co is a topology-dependent coefficient that takes values of 1/(5, 1/S,, 1/S2, and 1 for the Star-Ste Star, Star-Ring, Ring-Star, and Ring-Riin topologies. respectively.
Proof.
E FF Ax) F()) S E((V(()) +
The model updates within a single global round for the four topologies can be represented by unified format,
S
P
S
K-1
Ax (r) = (++1) x(()) -1cc
B (m
#1=1
p=0
#1=1
km
After substituting the overall updates Ax, we can get
E
F (x((xx(()) (1))) (x)
S1 P-
S.
K-1
E
VF(x())
-700
Σ
gm (n)
p=0
8==1
P-1
8 K-1
E
VF(x(")
-
VF (s. (262)) (xh
k=
P-1
8
K
E
vF(x()))
700
VF n. (o)) (x -VP(e))))
#2=1
k=0
(FF(X
P-
S2
VF(x()) 1
7/0
K=D
St (VF(x
5
P-1
S3
ΣΣΣΣ
V -V (e) (x())))
co
51

---

Published as a conference paper at ICLR 2026
1
8i
P-1 82
K
+ *700S,,
Σ
VF (e (xp
=1=
p=0
=2=1
-V (Fa(a))ana())))(((
7 (1)
8,
P-1 S1 K
+ 2
PKE
Co
ΣΣΣ
V
(+)
F (e
1==1p00pp
01
9 P-1 8 K-1
S
7 2 L
Σ ΣΣΣD
E
xipp.cak x(()) x
For the remaining term, we have
LE Ax||
8
P-1
S2
K-1
LE
1700
2
$1
92=1
81
P-1
8,
5
LB
Σ
(((e)))). - V V (x))) (x
2
60
=1=1
p=0
8
P-1
82
LIE
00
ΣΣ> Σ
V P (x (x)
V (x)
0=
2" "
5
80
ΣΣΣΣ
V (o)) V (2))) (x(())
P-1 8
2 77 LE
5
C ΣΣΣΣ
V F (z) (x))))))) -VF(x(1)
m2
$ P-1 PLIS K-1
" L
ΣΣΣΣ (F
82 K=0
3 "/ Leo
S P-1 S2 K-1
5
Σ
E p... 11
p=0
0=
5
2
Let S 3TooS1S,PR we have
E F(x(++1)) F(x(1))
E (VF( [x(m)]] + |
52

---

Published as a conference paper at ICLR 2026
- =-100S|SpPK
- SnnLoSSiSPPP [[IVF(((
La
5 "
La
+2 Lag 2 K2
+ 5
S
=
51 P-1 82 K
tr
5
ΣΣΣΣ
21.p.82k - -
11
1
5
S S
V[
2
2
Loo 2 P 22² + 5
+ 2" Leg S1S2 + 2"
Loo
2"
La
La ?
P- 82 K-1
tnl2000
ΣΣΣΣ
Pi 11.
p k==
F.2 PROOF OF THEOREM 2 FOR THE STAR-STAR CASE
For Star-Star,
p-1
8, K-1
Piskkk -x() x(1)= -1 (m(())))m))))))
17 Σ
Σ
S2
p==
4 k==
We first bound (r)
11. x (11)
E
S1...2, - 13]
1
S2 K-1
E
P. +1
Σ
Bag (t
S2
K==
y==0
8/4
=/=1k' ===0
< 10
(11))))))))))) VF (s)) (322) (x
p-
82 K-1
10
Σ
(m) - VF (2 s1rt
S2
=10,/E
Σ
V
(221 V (o)) (x()))
M=0
10
( VF FF ( (x((1)
52
10n'E
Σ
(((
V
VF (x(I
M=0
K
10,)EE
(x)
Vi (x(1))
2
===00
h-1
10
Σ
VF (x vF(x -
53

---

Published as a conference paper at ICLR 2026
R-1 82 K-1
E0
(x(()
VF((x())
52 #/=1 ==
10
Σ
K-1
10
Σ
Σ
2 =
I $10n²Ko ko² + +10n2p Ko²
S2
A-1
p
82 k-1
+ +10n 2:
L
x $1.P.02.1" - -x0')))+
L L
21. - x()
S2
k==0
p==0
#/2 1k==0
+10m"²²²² + 10m²2² 1
K2C²
S2
- =10n7'2202 + 00'2p2k'
=10"" 10n 107
S2 K-1
E
11
11=1 p=0 81=1
81 P-1 82
ΣΣΣ
Sp.p. x 11
(r)
===1
+ 100 + S 20m PD S382
+ B "
Let
8t P-1 S2
$1.p. - x1
=1
=2 h=0
$ S - 22
+ P0s, 3 + 10c, S₁ pa k332 + 22
+ +
F(x(++1))
- F(x((n)]
$ SPPPK
ILP
1
E 220
2
2
5
L
1
p
1
Ko²
2 L2p2
K202
2
5
S2
S2
5 2 " LP 22
k2 + 10c 1 L2p3 12
10a
K3R
S²
52
5
p2 22 + 21
5
54

---

Published as a conference paper at ICLR 2026
Let 02 2 2- 1 20c1n"
BIIVF(x [1) (2(((x())) - -F((!1))
11 0² ta
121
R
nRPK
S1
+ +2nLP KÇ² + 122
Ko² + [
S
S2
+ t2nn
PK8 + 4
R2 + tac
S1
S
Let =j nPK and 7j - I0r
E||l ( F(x (x) F(x(R))
Lijo
Liç Lij²
+
iR
SPPSKK
S2
S1
0²
L21102
12
L²
L272282.
P2K
PS2K
p2
S2
[[]
O
LA
(LA07)1/2
(LAÇ3)1/2
(LA82)1/2
R
PS
VS2R
VS
(12A222)1/3
(12A902)1/3
(IPA2
(P2KR2)
(PSgKR2)1/3
(P2R2)
(32
(L2
(S2R2)1/3
(R2)
where I.ft is defined a model uniformly sampled from the (0))
(R-1) of previous iterations,
and S hides universal constants.
F.3
PROOF OF THEOREM 2 FOR THE STAR-RING CASE
For Star-Ring,
K-1
x (r) s1.p,02.k -
Σ
S2
k 0
p'=0
#2=1 k
82 K
1
g (s))))pp)
S2
0
8/-1
We first bound [r[lx(r) (r)
E (r)
xx(1 11
< 15n" 2
V g (m()))).2200)))
82
+ 15
[m(6r))am0066... V Venl (x
1/
Sg K
+ BB
8m1(s))aplmaa())).. V (x))
p/ p'=0 K==
+ 1B
F (f
(r)
V (m)) (x)) (x((
M=D
55

---

Published as a conference paper at ICLR 2026
52 K-
+ 15
V (aa (a
V (2
M/2
8g
+ 15
Σ
V P (a (o
V (a(t
+ B
V V (xn) -V (x
K==0
K-
+ 1511"
Σ
V F (x)
VF VF
#1 K'=0
p-1 82 K
+ =157)
Σ
V V (eme))))))())))((())) (o
#'=0 2/ 1 k==0
+ 15
-
M==0
52 K-1
V (x -
+ +157/²
1/= k==0
8g
+ +1
Σ
V - (F(x())) -VP()))))))))>(((())))))
2 K==
+ 15
()(
P=0
K-1 Σ ()
+ 11
#/=1 K==
p-1 S₁ K-1
+ +1
Σ
ΣΣ1 (x
===
$ ko"
+ 157 82 Ko² + 15
PS2Ko*
k-1
+ +15122.2k
$1,p,80 & - x 11
k'=0
+ L5 s
112
1/ ===0
p-1
So K-1
+ L1 K
Σ
St - x 12
~===/11
+
2, S
+ 2=m2 s3 + 15m 2p K8
56

---

Published as a conference paper at ICLR 2026
+ A
E|I
" + VF (x)(()))))
51 P-1
82 K-
Σ
Σ
B B||| 11 - 1|
#1=1
p=0 #2=1 k=0
S, P2
81
P-1 82 K-1
45n 2
Σ
P
Let C1
15
8 P1 ΣΣΣΣ
Elllx f x1
=;=1p=0
$ 45 2 S₁ 52 K2 45 PS 4, P
+ 2 S K $ BII )1
Let 02 k
F(x(0)) F(x(R))
s C2
nRPS22
+ C2nL 2² + L'
Si
+ ConLPK + 45 2 L2p
822i PS2kK02 + 45c L3 12
+
2
51
Let ij nPSkK and ザ ك T
[[ (8) || き (x) (2)
LNjo²
LNK
Lij8
iiR
PS2
S2
S
1227202
+ 12
+ L28288
PS
S2
LA
(LA02)1/2
(LAC2)1/2
(LA83)//2
([I [2] = 0
R
PS
VS2Rt
VSRR
132
(1PAR53)1/33
(12
RPS,K
(S2R2)1/3
(R2)1/3
where R is defined as a model uniformly sampled from the (0)
(R-1) of previous iterations,
and S hides universal constants.
F.4 PROOF OF THEOREM 2 FOR THE RING-STAR CASE
For Ring-Star,
1
K-1
(x
Σ
X 8..p.
-1
k==0
p'=0
2 k=
57

---

Published as a conference paper at ICLR 2026
R-1
$=11==00
We first bound B[[|
[[[|x s... x1]]
El E||[ xx (r)
11
< BB
85 p.o.kk
VF FF (aa))) (r)
M==
K-1
+ 15n/"E
o/ 2g
V Vi (6)))))
p
K==0
82
+ 15
Σ
B - VL (e
52
p'=0
4/21 k==0
+ 15
V (x
(x)
V (en(
15
Σ
V Fe
VF ma
S2
p'
P-
+ 1E
Σ
VF (1)), F/p0
V ( (16)) (x(1))
52
1p==0
x/11
===
+ 15
V (x()) VF (x))
p-1
82 K-1
+ 15,"E
Σ
V (F - VF (x))
S2
$2
k-1
+ 15
Σ
Σ
Σ Σ
V VF VF (3)
(x(1)))))())
S2
$ ==1===
#=0
+ 15
VF
(x -VF(()))
15
Σ
(x -VF(x(1))
S2
(2
+ 1E
Σ
VF (x()) -VF(x())
52 1/.
K=0
+ 11
Σ (T)
K=0
58

---

Published as a conference paper at ICLR 2026
R-1
S K-1
+
E5
Σ
Σ
V ))(x(T)
2
p'
==
81
82
+ 15
Σ
ΣΣ1
Σ
Σ
VF(xd())
52
$4=1k=0
< $15m2Ko + 15n p
Ko² + 15n 81 P Ko²
S2
S2
R-1
+ L22
B[|
x
x 121
K
+ +15n2L2y
1
K
E
$1 S..P..a ..gk - x
S2
y==0
11=1
k==
81
P-1
K-
+ 15n 81
B "100" (11
+1=1
p'=0
1/=1
+15n"
15
1
k²²²
15n7 5p 3p K26²
+
+
11
+
81 P
82
K
$1.p. - 11
p= 82=
k=0
$ 151/ PSg
8 P-1 1
S2
K
+ Sp
(r)
x
PS + 307
p3 33
+ 4
+ 45n
V V|
EI
Let C1
1
S1
P-1
Sa K-1
Σ
Σ
$1
0=0 =2=1
< 15cm1 2 S K2' Spp22 "
+ 3
+
[[((((+))) - F(x(1))
1
5
S SSSKPPK
- - L2
2
2
+ "
5 2 L.S. P
1
Ko² + +1cn1 L PK2 0²
"L' K20²
S2
S
59

---

Published as a conference paper at ICLR 2026
5
7 LS p2 1 R² + +
53 1 ks
52
S2
2" PS +
Let 02 1 BBcccc
Σ EIIVF(x
TRS,PK
1 0² + 12 K2 + 200 P 1
Ko²
S2
52
5
1 P K ( L2 K2
52
52
C2nLPK6 + 45c L3
Let ij = 1 and 7 -
1
156
F(x(0)) F(x(R))
Lijo²
T
Lūj82
E | 2
+
iR
SjPS
S2
S1
I221002
1271002
12iRp22
1221p(2
1221282
+ 2
+
+
S2 +
SJPSKK
S
S
B/I |13 = -0(1) LA R + (LAO7)1/2
(LA
(LA03)1/2
(L2AA022)1/3
+
vS,PS,KR
VS2R
VS,R
(S (12
(12
(12
(2242
PS
(2
(S2/22)1/3
(Si
where R is defined as a model uniformly sampled from the (0) and $ hides universal constants.
(R-1) of previous iterations,
F.5 PROOF OF THEOREM FOR THE RING-RING CASE
For Ring-Ring,
82
K-1
-x(")=
Σ
(r)
81 P.
n
7
82 K
P-1
S K-1
p'
8/2
1/=1 =
===0k==0
We first bound [[[lx(r)
x 11.
p2.
Ell x (r)
- xx 112
s1.p.2..k
TT
Σ
V
VF
8g
+ 20
VF
(x
==
S2 K Σ
+ +2
B
VF
#==
60

---

Published as a conference paper at ICLR 2026
$1
8
+
2
Σ
3
V (an p
(r)
< 20
(s (x0))
VF (or)
#2 K-1
+ 20
V (enn (Tooss))
VF F1 (1)))))))))
1/
p-1
92 K
+ 20
Σ
V (() (.) - VF F ((0))))))))))(x
P-
82 K
+ 20
Σ
V Fn ( 1a
Fm (of) m.) (xx(1))
p'=
k-1
$ 20
Σ k==0
VF (51
(x))) (x
VF (51) (xx(11
82
+ 2
V (o V (x(()))))))))
$1
p-1 8
+ 2
Σ
V (a) V (x(()()((())))
p'=0x=11
+ 2
F (4) - V (x
k=
< 20
V
K==
K Σ
+ 20y22
(((()
-VF(x(())
11=
p-1 82 K
+ 2
Σ
V -
p= 11
#1 ΣΣΣΣ
2
- v -
(F
#=1='=0 04
< 'T
Σ (x((()))
k==
61

---

Published as a conference paper at ICLR 2026
82 K-1
+ 2
Σ VF(x(()
12=1 k==0
2-1 8 K- Σ Σ }
+ 20
#1 P-1 K-1
+ 20
ΣΣΣΣ ()
1/=1r'=0 2/
< =0722Ko ko + -20m'sgKe syKo² + 20n2 2 PS2Ko² 20mm²s PS
k-1
+ 2'2
Bl|l
11
K-1
+ 200 - 1)K
2.. - -x())
p-1
82
K-1
+ T.2p
Σ
S2
K
o'o.k - 11
p'=0
k=0
81-1
P-1
82
+ 20n -
P
S2
K
E
-x('19
x11
s1=1
y'=
1/11
k=0
+
+ 200
-1) 22
1)K28²
201 1) 1)
+
+
Let 1 12
$1 P- 8q K-1
ΣΣΣΣ
$1.P.8g.k 12
(c)
41 sgml k=0
< p2
P-1 K-1
+ S
E p.ekk x1
p=0 s2=1 k=0
+ S
+ 80c
+ 300""3>P""S)"<""|VVVV""""""1""
B(T(x(+t1)) - ((x
1
SSpK
B[IVFF((()) 1
2
LS + 80c1 52
+ 3"d
+ ""
L S, + L3
62

---

Published as a conference paper at ICLR 2026
+ n" LS + 20
Let 02
1
02 (F(x(0))
-
5
[9]
- - L
NRS
2
7=0
5
+ PK|
2
5
+ 2
Let =j= n PS,K and ij S
1
201.
E|| V| ~ F(x(0)) F(x(R))
Lijo²
Lij
Lij8²
iR
P.PSS
82
S
L 12211-02
1/
+
S₁ PS2K
S2
Si
LA
(2
(LAC
(LA63)1/2
R
VS2Rt
VSR
(1
(2
(L2A263)1/3)
(S) ReyK3
(S2R2)1/3
(S
where n. is defined as a model uniformly sampled from the (()) and S hides universal constants.
(R-1) of previous iterations,
63


Reviews:
[{"review_id": "2RtawoCXFA", "reviewer": "Reviewer_hta5", "summary": "The paper analyzes four kinds of two-tier HFL topologies (Star-Star, Star-Ring, Ring-Star, Ring-Ring) with respect to inter- and intra-group heterogeneities and the impact from top and lower layers. Then, the paper derives topology-dependent convergence bounds and claims that: 1. the top tier dominates the convergence over intra-group topology, while ring-based structure at the top helps more; 2. the best topology depends on overall grouping structure; 3. inter-group heterogeneity dominates the overall convergence. Experiments on CIFAR-10/CINIC-10/Fashion-MNIST datasets are carried out to support the claimed patterns.", "questions": "1. The derivation of the client drift bounds in Lemma 2 (Appendix C.1) is difficult to follow. For instance, the star-star derivation starts with \"<=5\" without justification for the constant '5'. Where is this number derived from?\n2. Do the conclusions still hold with standard BatchNorm+momentum training? Or what will be the difference?\n3. The analysis and experiments are presented in global rounds, which ignores the fact that a ring topology's round is slower than a star topology's. How would your primary conclusion that \"ring-based top-tiers are superior\" change if convergence was measured in wall-clock time?\n4. Can you provide experimental results comparing your best HFL topology to a well-tuned single-tier FedAvg with N=100 clients?\n5. How did you tune learning rate for the main results in Figure 2? Was it held constant across all four topologies to an unfair comparison, or tuned individually for each for a fair comparison?\n6. How will the performance of the topologies change under a more realistic partial participation scheme, where only a subset of clients are active?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a clear, unified scope across all four two-tier HFL topologies. It offers a single convergence framework for Star-Star, Star-Ring, Ring-Star, and Ring-Ring under non-convex objectives and both intra- and inter-group heterogeneity.\n2. The paper offers an actionable topology guidance by summarizing 3 critical and practical principles on top and lower tiers importance, topology selection and intra-/inter-group heterogeneities.\n3. The definition of effective learning rate is introduced to show the impact of hierarchical structure on convergence. It also provides the intuition for the trade-offs between optimization and noise/heterogeneity.", "weaknesses": "1. The paper claims a \"first\" unified comparison of all four topologies, but related work already analyzes subsets and topology variants. The author is suggested to clarify more clearly what is new in the math or convergence bounds beyond those existing researches.\n2. The analysis completely ignores communication costs and latency. The convergence rate is presented in terms of global rounds. This is misleading as the wall-clock time of a round differs vastly between topologies. A star topology is parallel (O(1) latency), while a ring topology is sequential (O(G) or O(M) latency), making it extremely sensitive to stragglers. The author is suggested to provide a formal analysis of the communication complexity for each topology. The final convergence guarantee should be presented in total wall-clock time or communication cost, not just rounds.\n3. The analysis and algorithms assumes full participation from all clients in all groups in every global round, while partial participation is mentioned in the existing researches. Full participation is a highly unrealistic assumption in federated learning. The author is suggested to redesign the scenario where a subset of groups, and a subset of clients within those groups, are sampled for updates.\n4. All experiments are image classification tasks, while no speech/NLP/time-series or cross-silo medical/IoT workloads where HFL is popular. The author is suggested to include at least one non-vision dataset.\n5. Different ~𝜂 definitions per topology in the convergence analysis make it tricky for fair lr tuning. The experiments tune learning rates but lack in details. The author is suggested to report a transparent learning rate tuning strategy to ensure the results match the analysis.\n6. The paper claims HFL is for scalability, not convergence acceleration and that \"carefully selected single-tier FL configurations may actually converge faster.\" This is a strong claim, but the paper provides no theoretical or experimental comparison to single-tier FL. The author should add comparisons vs single-tier FL with tuned participation/aggregation under identical budgets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "epas8zV69L", "reviewer": "Reviewer_qwXN", "summary": "This paper aims to provide a unified convergence framework for analyzing HFL topologies under non-convex objectives and heterogeneous data distributions. It addresses the lack of theoretical guidance on how to select optimal HFL topologies for real-world deployments, given different combinations of intra-group and inter-group heterogeneity.", "questions": "Please address all the weaknesses above.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "++The motivation behind the analysis of HFL topologies under heterogeneity is strong\n++The paper provides convergence bounds for all four topologies within a single analytical framework\n++Experiments were conducted on multiple datasets, architectures, and heterogeneity conditions", "weaknesses": "++Key proof steps (especially those establishing cross-tier coupling and topology-specific bias) are only summarized without detailed proof\n++The paper extends prior FedAvg-type analyses to hierarchical topologies rather than introducing fundamentally new analytical techniques, which exhibits limited novelty\n++Only small to medium-scale vision datasets are used. Large-scale, high-variance tasks (e.g., NLP, speech) are missing\n++There is no systematic study of how convergence changes with varying group size, local steps, or communication rounds\n++The claim that HFL prioritizes scalability over acceleration is made but not empirically validated\n++No variance/error bars or significance testing are presented in the figures", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Cj9BKYNj6i", "reviewer": "Reviewer_my4H", "summary": "This work studied the convergenve of an existing algorithm, hierarchical federated learning algroithm. They analyzed the convergence of this algorihtm over different topology, including ies (Star-Star, Star-Ring, Ring-Star, and Ring-Ring, under non-convex objectives.", "questions": "It is hard for me to understand why star topology lead to bad results. In my opinion, star topology enjoys the highest communication efficiency.\n\nIn Line 247, where do you define $\\bar{x}^R$? \n\nIn single tier topology, existing works have already proposed some algroithms and demonstrated convergence without data heterogeneity assumption. Is it possible to eliminate this assumption in hierarchical federated learning. \n\nThe ring topology scheme asks clients to update model sequentially, which is ineffective. You cannot enojy the benefit of parallel computation. The conclusion that ring topolgy should be carefully checked. Based on your logic, can I argue that fedavg is not good, we should let clients update sequentially?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper studied an interesting problem in hierarchical federated learning, which is relevant to scaling federated systems in practical deployments. It provides an extensive theoretical analysis covering multiple possible topologies (Star-Star, Star-Ring, Ring-Star, and Ring-Ring) under non-convex objectives, which is relatively comprehensive compared to typical HFL studies.", "weaknesses": "The discussion of related works is rather brief. Since the main focus of this paper lies in the analysis of hierarchical federated optimization algorithms, it would be beneficial to include a more comprehensive review of prior studies on hierarchical federated learning to better contextualize the contributions.\n\nThe comparison of convergence speed is also not convincing. The authors claim that the dominating term is $1/\\sqrt{R}$ (Line 304), but according to the derivations in Lines 270–290, it should instead be $1/\\sqrt{PMKR}$ for the star topology and $1/\\sqrt{GPMKR}$ for the ring topology. \n\nThe results derived fro star-star topology is not tight. Please comare your results with the existing results. For illustration, when the number of clients in each group reduces to 1, the hierarchical fedavg reduces to fedavg. The rate should be $1/\\sqrt{GKR}$. But your current results cannot recover this. I believe your derivation for star topology is not tight. \n\n\nFurthermore, the analysis of FedAvg under the star-star, ring-star, and star-ring topologies has already been studied in prior works. The assumptions adopted in this paper are largely the same as those made in the existing literature. Therefore, the contribution of this work appears incremental, and the novelty over established results is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "PYLCa6lkAi", "reviewer": "Reviewer_2b4g", "summary": "This paper establishes a unified theoretical framework for the topology selection problem in Hierarchical Federated Learning (HFL). In traditional HFL practice, topology selection often relies on intuition and experience, which the authors vividly describe as a “topology lottery.” To address this problem, the paper conducts rigorous convergence analysis under a non-convex setting for four HFL topologies composed of star-shaped (parallel) and ring-shaped (serial) aggregations. Theoretical analysis and extensive experimental results jointly reveal three key design principles: \n(1) the top-layer aggregation topology has a greater impact on convergence than the bottom-layer topology, and a ring-shaped top layer performs better under data heterogeneity; \n(2) inter-group data heterogeneity is the main performance bottleneck; and \n(3) the optimal topology depends on the client grouping structure (e.g., Ring-Star is suitable for many small groups, while Star-Ring is suitable for a few large groups).", "questions": "see the Weaknesses", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Important and Practical Problem: This paper focuses on a problem that is crucial for the design of large-scale federated learning systems. As HFL is increasingly applied in fields such as IoT and edge computing, providing theoretical guidance for its architectural design has become an urgent need.\n\n2. Novel Unified Theoretical Framework: This is the core contribution of the paper. To the best of my knowledge, no prior work has systematically compared all four mainstream HFL topologies within a single unified mathematical framework. This work fills that theoretical gap and integrates previously fragmented studies into a coherent whole.\n\n3. Insightful and Actionable Conclusions: The three principles distilled in this paper are clear and highly insightful. These findings go beyond being mere mathematical results—they serve as practical guidelines that can directly guide engineers and researchers in system design, significantly reducing design uncertainty.", "weaknesses": "1. The mathematical derivations in this paper are element-wise, and the four topologies are discussed separately. This differs from matrix-level derivations: for example, if the intra-group and inter-group communication processes could be modeled by a communication matrix $\\mathbf{W}$, then the convergence rate would be characterized by the eigenvalues of $\\mathbf{W}$. That would yield more general conclusions than those in this paper — for instance, one could compute the eigenvalues of $\\mathbf{W}$ corresponding to Ring–Star. Therefore, can the authors re-derive the convergence theory from a matrix perspective to obtain more general results?\n\n2. Could you please provide the learning rate settings for each part of the experimental section?\nThe specific magnitudes and relative values of the learning rates are crucial, as they directly affect the conclusions about the *effective learning rate* discussed in **Corollary 1**.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)