Towards Serverless Semi-Decentralized Federated Learning with Heterogeneous Optimizers

# Towards Serverless Semi-Decentralized Federated Learning with Heterogeneous Optimizers
Source: [https://arxiv.org/html/2606.06687](https://arxiv.org/html/2606.06687)
Su Wang , Mung Chiang, , and H\. Vincent PoorSu Wang and H\. Vincent Poor are with the Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ, USA\. Email: \{hw5731, poor\}@princeton\.edu\. Mung Chiang is with the Department of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA\. Email: chiang@purdue\.edu\.

###### Abstract

We investigate cluster formation, involving the number and composition of clusters, in decentralized federated learning \(FL\) with heterogeneous machine learning \(ML\) optimizers\. While clustering in centralized FL has enabled scalability and resource savings, its value and development in fully decentralized environments have yet to be explored\. Optimizing cluster formation in such environments is challenging, especially due to the complex coupling between network graph structures, local data heterogeneity, and different local ML model optimizers\. To address these challenges, we propose serverless semi\-decentralized FL \(SSD\-FL\), a methodology requiring no persistent server infrastructure\. In SSD\-FL, cluster formation occurs via a lightweight, one\-time device\-to\-device \(D2D\) initialization phase, after which actual ML model training \(alongside consensus and convergence processes\) is fully serverless\. Functionally, SSD\-FL segments global rounds into intra\-cluster and inter\-cluster regimes, ensuring global convergence and consensus through novel ”effective loss functions” that integrate device\-specific ML optimizers with network graph\-based regularization\. Next, SSD\-FL leverages the consensus gap via the Cheeger inequality to develop an iterative clustering algorithm evaluated against our derived convergence and consensus bounds, which incorporate a unique scoring metric to quantify data and optimizer heterogeneity across devices\. Finally, experimental evaluation against three categories of decentralized FL methodologies validate that SSD\-FL improves both convergence speeds and communication efficiency across various network graphs, datasets, and local optimizer regimes\.

## IIntroduction

Based on the edge/fog network, FL methodologies\[[51](https://arxiv.org/html/2606.06687#bib.bib18),[12](https://arxiv.org/html/2606.06687#bib.bib19),[43](https://arxiv.org/html/2606.06687#bib.bib5)\]are partitioned into centralized and decentralized FL\[[25](https://arxiv.org/html/2606.06687#bib.bib17)\], as shown in Fig\.[1](https://arxiv.org/html/2606.06687#S1.F1)\. While centralized FL relies on a server to coordinate ML model training processes\[[41](https://arxiv.org/html/2606.06687#bib.bib20),[40](https://arxiv.org/html/2606.06687#bib.bib21)\], decentralized FL\[[53](https://arxiv.org/html/2606.06687#bib.bib8)\]relies on D2D communications to incrementally propagate ML model updates, eventually yielding both consensus and convergence\. However, in large\-scale edge/fog networks, both classes of FL may struggle as devices may be far from each other and the server, specifically for centralized FL, leading to scalability challenges in terms of latency, convergence, and consensus\.

In response, existing works\[[52](https://arxiv.org/html/2606.06687#bib.bib6),[18](https://arxiv.org/html/2606.06687#bib.bib1),[1](https://arxiv.org/html/2606.06687#bib.bib3)\]introduce cluster formation, in which devices are grouped based on data distributions or network properties, to improve the scalability of FL in large\-scale edge/fog networks\. Referred to as semi\-decentralized FL \(SD\-FL\), these methodologies demonstrate faster convergence and improved efficiency by leveraging pre\-defined clusters\. But as clusters are given a priori, we still do not understand the properties for effective cluster formation, i\.e\., the number of clusters and the devices within them\.

Effective cluster formation requires balance between \(i\) macro\-level network properties, such as graph connectivity and varying device densities, and \(ii\) micro\-level device properties, such as heterogeneous datasets and ML optimizers \(both of which influence collaborative ML model training in FL\[[41](https://arxiv.org/html/2606.06687#bib.bib20),[38](https://arxiv.org/html/2606.06687#bib.bib23),[19](https://arxiv.org/html/2606.06687#bib.bib24)\]\)\. These challenges are exacerbated in decentralized edge/fog networks, as such networks lack continuous central server synchronization\. Instead, decentralized edge/fog networks are commonly treated as a single cluster\[[36](https://arxiv.org/html/2606.06687#bib.bib25),[24](https://arxiv.org/html/2606.06687#bib.bib26)\], which may be inefficient as large\-scale edge/fog networks exhibit extensive heterogeneity\. It may be more efficient to have multiple clusters so that overall cluster data distributions are similar to each other or so that clusters have a similar degree of graph connectivity\. To contextualize these ideas, consider the following potential applications:

- •Decentralized Energy Gridsrely on D2D communications without global/central control, such as those involving D2D solar energy trading\[[37](https://arxiv.org/html/2606.06687#bib.bib9),[17](https://arxiv.org/html/2606.06687#bib.bib10)\]\. Leveraging decentralized FL in these types of edge/fog networks can be problematic, owing to highly heterogeneous D2D links as well as densities, e\.g\., new home neighborhoods with local energy storage vs older subdivisions\. By carefully designing device clusters, SSD\-FL can enable both \(i\) faster localized/relevant consensus, minimizing the costs of frequent long\-distance or expensive D2D links, and \(ii\) simplify network\-wide coordination, as integrating \(locally\) synchronized clusters may be easier than a larger number of uncoordinated edge/fog devices\.
- •Ad Hoc Wireless Sensor Networksfor disaster recovery communications\[[28](https://arxiv.org/html/2606.06687#bib.bib28),[44](https://arxiv.org/html/2606.06687#bib.bib29)\]or multi\-domain unmanned vehicle networks\[[29](https://arxiv.org/html/2606.06687#bib.bib30),[55](https://arxiv.org/html/2606.06687#bib.bib31)\]are similarly massively distributed and reliant on highly heterogeneous D2D communication links\. In the case of natural disaster communications\[[28](https://arxiv.org/html/2606.06687#bib.bib28),[44](https://arxiv.org/html/2606.06687#bib.bib29)\], edge/fog networks are characterized by regions of high and low density devices and D2D connections, such as earthquake hotspots interspersed between rural plains or UAVs/UGVs with relay devices covering their communication limitations\. SSD\-FL, via careful cluster formation, can enable decentralized edge/fog networks to leverage periodic inter\-cluster communications, rather than frequent and higher total latency global synchronizations, and thus improve ML training convergence rates overall\.

![Refer to caption](https://arxiv.org/html/2606.06687v1/x1.png)Figure 1:FL architectures with respect to the degree of network decentralization\. From left to right, FL shifts from control by a centralized, global server to fully decentralized devices\. SSD\-FL introduces clusters in decentralized networks, offering heterogeneous D2D cooperation density in decentralized edge/fog networks\.To support these sample applications and beyond, we seek to answer how and when to form clusters in decentralized edge/fog networks\. In this regard, cluster formation involves understanding two deeply coupled trade\-offs: \(i\) global\-level network structure, which influences the optimal number of clusters and \(ii\) local\-level cluster composition, which determines the specific devices within each cluster\. The number of clusters directly controls the rate of local convergence but at the cost of global consensus, e\.g\., more clusters means faster local training but requires many rounds of multi\-hop D2D communications to attain global consensus\. Conversely, device selection within each cluster defines the local communication topology, data distributions \(degree of non\-i\.i\.d\.\), and set of local ML model optimizers, all of which influence intra\-cluster convergence properties\. Thus, to achieve effective cluster formation, we must consider both the number of clusters and their composition jointly\.

Our proposed SSD\-FL methodology addresses these coupled trade\-offs without relying on persistent server infrastructure\. Here, serverless refers specifically to model training, where all coordination occurs entirely via D2D communications\. While SSD\-FL requires a lightweight, one\-time coordination of network devices prior to training, this is in fundamental contrast to traditional centralized as well as SD\-FL methodologies, which require continuous server management \(i\.e\., the server is core to the distributed training process\)\. Therefore, by formalizing this serverless cluster formation, SSD\-FL bridges a core gap towards fully decentralized, serverless FL across large\-scale edge/fog networks\.

### I\-AOutline and Summary of Contributions

In the following, we begin by reviewing relevant literature in Sec\.[II](https://arxiv.org/html/2606.06687#S2)and present SSD\-FL’s system model as well as theoretical background in Sec\.[III](https://arxiv.org/html/2606.06687#S3)\. Then, we derive the convergence and consensus properties of our proposed SSD\-FL methodology in Sec\.[IV](https://arxiv.org/html/2606.06687#S4)followed by the cluster algorithm of SSD\-FL in Sec\.[V](https://arxiv.org/html/2606.06687#S5)\. Subsequently, we validate SSD\-FL relative to baselines experimentally in Sec\.[VI](https://arxiv.org/html/2606.06687#S6)before summarizing the key takeaways in Sec\.[VII](https://arxiv.org/html/2606.06687#S7)\. We summarize our key contributions as follows:

- •Cluster\-driven approach to decentralized FL:We introduce SSD\-FL, a methodology that decomposes the structure of FL in serverless edge/fog networks, via cluster formation, into intra\-cluster and inter\-cluster regimes\. Towards principled cluster formation, SSD\-FL proposes “effective loss functions” with explicit terms for \(i\) network structure heterogeneity via regularization with cluster and global Laplacian matrices and \(ii\) different device ML optimizers \(i\.e\., SGD, SGD with momentum, and proximal SGD\)\.
- •Integrated intra\-cluster and inter\-cluster regime convergence:We characterize the theoretical convergence rate and consensus gaps for intra\-cluster and inter\-cluster regimes, demonstrating \(i\) non\-convex first\-order stationary points with heterogeneous optimizers and \(ii\) connectivity\-driven convergence as a result of regularization via graph Laplacian matrices\. These results follow from our effective loss functions, whose simultaneous treatment of momentum and proximal terms as well as graph regularization requires extending standard smoothness arguments\. Finally, we show integrated \(combined intra\-cluster and inter\-cluster\) convergence for SSD\-FL, in which the ML processes as well as network/clusters’ graph structure are explicit\.
- •Consensus\-convergence guided cluster formation:Our proposed SSD\-FL methodology determines both the optimal number of clusters and their constituents via a one\-time, pre\-deployment initialization step using network graph and device properties\. Leveraging our derived theoretical consensus conditions, we map these system characteristics to explicit cluster and graph conductance thresholds via Cheeger’s inequality, which are then applied to partition the network and refine clusters\.
- •Experimental validation of SSD\-FL:We evaluate SSD\-FL in terms of ML training speed and quality in networks of varying architecture, size, connectivity, and heterogeneity \(i\.e\., uniform and unique local ML optimizers\)\. These experiments demonstrate that SSD\-FL offers both improved final accuracies as well as faster convergence relative to three families of decentralized FL baselines on FMNIST and CIFAR10 datasets\.

## IIRelated Work

We contextualize SSD\-FL with respect to clustering methodologies for centralized FL and relevant advances in decentralized FL\. In particular, we want to emphasize that existing literature has yet to develop methodologies for exact cluster formation \(i\.e\., number of clusters and their devices\) in FL, even in centralized edge/fog networks\. Therefore, our research aims to understand effective clustering and subsequently bridge the gap between deliberate network structure manipulation in centralized FL and fully decentralized edge/fog scenarios\.

### II\-AClustering for centralized FL

The motivation for clustering in centralized FL stems from large\-scale edge/fog networks, in which edge devices may be far away from the central server\. Rather than incur high latency from mandating device\-to\-server transmissions, existing literature proposed semi\-decentralized FL\[[18](https://arxiv.org/html/2606.06687#bib.bib1),[1](https://arxiv.org/html/2606.06687#bib.bib3),[52](https://arxiv.org/html/2606.06687#bib.bib6),[47](https://arxiv.org/html/2606.06687#bib.bib4)\]in which devices are grouped into clusters\. Within these clusters, devices follow gossip\-based protocols \(similar to decentralized FL methodologies\[[32](https://arxiv.org/html/2606.06687#bib.bib32),[15](https://arxiv.org/html/2606.06687#bib.bib36)\]\) in order to achieve intra\-cluster consensus, after which, a single device in every cluster would communicate with the server to complete global aggregations\. In effect, these techniques extend the reach of centralized FL, connecting the “edge” of large\-scale networks while lowering latency for the FL process overall\.

There is a similar line of research in hierarchical FL\[[20](https://arxiv.org/html/2606.06687#bib.bib33),[4](https://arxiv.org/html/2606.06687#bib.bib34),[42](https://arxiv.org/html/2606.06687#bib.bib22),[11](https://arxiv.org/html/2606.06687#bib.bib35)\]\. While these methodologies also involve cluster formation, their clusters locally function as a star topology, with one device managing and synchronizing other devices, and thereby reduce the total network device\-to\-server communication constraints\. However, the underlying scalability issues of large\-scale edge/fog networks remain, especially if devices are distant to the “central” device of their assigned cluster\. Moreover, only a limited set of possible D2D connections are used, i\.e\., only those D2D connections involving the “central” device of each cluster, and, therefore, there is an opportunity for further performance/latency gains by integrating D2D cooperation throughout clusters\.

More broadly, existing methodologies on semi\-decentralized and hierarchical FL depend on restrictive assumptions for clusters\. Typically, clusters are either pre\-determined\[[18](https://arxiv.org/html/2606.06687#bib.bib1),[33](https://arxiv.org/html/2606.06687#bib.bib2),[47](https://arxiv.org/html/2606.06687#bib.bib4)\]or derived from purely statistical properties \(e\.g\., cosine similarity\[[1](https://arxiv.org/html/2606.06687#bib.bib3)\]or training progression\[[45](https://arxiv.org/html/2606.06687#bib.bib38),[10](https://arxiv.org/html/2606.06687#bib.bib39)\]\)\. Even though such approaches do yield improvements to latency and convergence relative to standard, centralized FL, they nonetheless neglect the structural heterogeneity aspects of large\-scale edge/fog networks, i\.e\., the number and quality of their available D2D connections\. Clustering solely based on devices’ computational and statistical characteristics overlooks these underlying network properties, which could otherwise be leveraged for performance and scalability improvements\.

In light of these limitations, our proposed SSD\-FL methodology aims for cluster formation that integrates both network structure and devices’ statistical heterogeneity, including choice of local ML optimizer, via its introduction of effective loss functions\. Moreover, as a further distinction from the above lines of research, SSD\-FL is designed for fully decentralized edge/fog networks, for which global synchronization is not possible\. Our approach of interspersed intra\-cluster and inter\-cluster regimes also allows SSD\-FL to leverage the advantages of clustering \(i\.e\., faster local convergences and intermediate consensus\) while maintaining both the flexibility and scalability of fully decentralized edge/fog networks\. To better highlight these distinctions, we next describe SSD\-FL in the context of decentralized FL methodologies\.

### II\-BCurrent advances in decentralized FL

In decentralized FL research, existing literature can be categorized broadly based on directed or undirected D2D links\. While directed networks for FL\[[24](https://arxiv.org/html/2606.06687#bib.bib26),[22](https://arxiv.org/html/2606.06687#bib.bib27),[35](https://arxiv.org/html/2606.06687#bib.bib40)\]are an important line of research, we focus on the intersection of decentralized FL and undirected networks, which capture the two\-way nature of wireless communications and naturally enable cluster\-based network reorganization as the two sample applications in Sec\.[I](https://arxiv.org/html/2606.06687#S1)suggest\. For such undirected edge/fog networks, existing methodologies\[[39](https://arxiv.org/html/2606.06687#bib.bib7),[21](https://arxiv.org/html/2606.06687#bib.bib13),[13](https://arxiv.org/html/2606.06687#bib.bib41)\]view their underlying network as a single cluster, where performance improvements are achieved primarily through the design of D2D communication sequencing, e\.g\., gossip protocol manipulation\[[36](https://arxiv.org/html/2606.06687#bib.bib25),[23](https://arxiv.org/html/2606.06687#bib.bib42)\], periodic D2D communication\[[13](https://arxiv.org/html/2606.06687#bib.bib41),[32](https://arxiv.org/html/2606.06687#bib.bib32)\], or irregular D2D communication\[[15](https://arxiv.org/html/2606.06687#bib.bib36),[54](https://arxiv.org/html/2606.06687#bib.bib14)\]after devices’ perform local ML model training\. In this regard, existing approaches can be organized into three main segments: \(i\) synchronous, \(ii\) periodic, and \(iii\) stochastic decentralized FL\.

In synchronous decentralized FL\[[24](https://arxiv.org/html/2606.06687#bib.bib26),[31](https://arxiv.org/html/2606.06687#bib.bib43)\], D2D communication happens at every iteration to synchronize local ML models\. While these methodologies leverage frequent mixing to produce convergence guarantees, they incur substantial D2D communication overhead, limiting scalability in large\-scale edge/fog networks\. Periodic decentralized FL\[[32](https://arxiv.org/html/2606.06687#bib.bib32),[13](https://arxiv.org/html/2606.06687#bib.bib41)\]reduces D2D communication overhead by propagating updates only after several rounds of local ML model training\. Such approaches maintain convergence under standard smoothness assumptions and offer communication cost savings\[[32](https://arxiv.org/html/2606.06687#bib.bib32),[21](https://arxiv.org/html/2606.06687#bib.bib13)\], but introduce greater drift across devices, which can overfit locally and require more training time overall\[[53](https://arxiv.org/html/2606.06687#bib.bib8)\]\. By contrast, stochastic decentralized FL methodologies\[[15](https://arxiv.org/html/2606.06687#bib.bib36),[54](https://arxiv.org/html/2606.06687#bib.bib14),[3](https://arxiv.org/html/2606.06687#bib.bib44)\]rely on arbitrary, random, or asynchronous operations, where the timing of local device training and/or D2D communications are dictated by randomness or hardware constraints\. As such, these methodologies enable more functionality and integration in large\-scale edge/fog networks, at the cost of predictability, leading to cases of inefficient resource use and inconsistent training overall\.

SSD\-FL aims to provide a complementary perspective to these existing lines of research via restructuring the underlying edge/fog network\. By partitioning devices into clusters and managing clusters via interspersed intra\-cluster and inter\-cluster regimes, SSD\-FL not only reduces D2D communication overhead, similar to periodic decentralized FL approaches, but also provides a more intuitive/natural way to manage heterogeneity in large\-scale edge/fog networks, rather than the more general and unpredictable frameworks underlying stochastic methodologies\. Thus, SSD\-FL introduces network structure control as a core component of effective decentralized FL design\.

## IIISystem Model

In the following, we first describe our network model in Sec\.[III\-A](https://arxiv.org/html/2606.06687#S3.SS1), the ML model training components in Sec\.[III\-B](https://arxiv.org/html/2606.06687#S3.SS2), and theoretical background in Sec\.[III\-C](https://arxiv.org/html/2606.06687#S3.SS3)\.

### III\-ANetwork model

We model the edge/fog network as a graphG=\{𝒩,ℰ\}G=\\\{\\mathcal\{N\},\\mathcal\{E\}\\\}, where𝒩=\{1,⋯,N\}\\mathcal\{N\}=\\\{1,\\cdots,N\\\}denotes the set of devices/nodes andℰ\\mathcal\{E\}represents the set of weighted active D2D edges/links, with\(i,j\)∈ℰ\(i,j\)\\in\\mathcal\{E\}if deviceiiis able and willing to share ML model parameters with devicejjand vice versa\. Given anyi,j∈𝒩i,j\\in\\mathcal\{N\}, we assume that if the D2D link\(i,j\)\(i,j\)exists, then so does\(j,i\)\(j,i\)\. Since SSD\-FL follows different D2D communication structures within and across clusters, we use separate graphs:G~=\{𝒩,ℰ~\}\\tilde\{G\}=\\\{\\mathcal\{N\},\\tilde\{\\mathcal\{E\}\}\\\}for intra\-cluster regimes and the full graphGGfor inter\-cluster regimes\. For the rest of this paper, non\-calligraphic font represents the size of the corresponding set, e\.g\.,N=\|𝒩\|N=\|\\mathcal\{N\}\|\.

SSD\-FL aims to partition the network graphGGinto a set of clusters or subgraphs𝒮=\{1,⋯,S\}\\mathcal\{S\}=\\\{1,\\cdots,S\\\}, with the subgraph for clusterss∈𝒮s\\in\\mathcal\{S\}defined asG~s=\{𝒩s,ℰ~s\}\\tilde\{G\}\_\{s\}=\\\{\\mathcal\{N\}\_\{s\},\\tilde\{\\mathcal\{E\}\}\_\{s\}\\\}and their union denoted byG~=\{𝒩,ℰ~\}≡\{∪s∈𝒮Ns,∪s∈𝒮ℰ~s\}\\tilde\{G\}=\\\{\\mathcal\{N\},\\tilde\{\\mathcal\{E\}\}\\\}\\equiv\\\{\\cup\_\{s\\in\\mathcal\{S\}\}N\_\{s\},\\cup\_\{s\\in\\mathcal\{S\}\}\\tilde\{\\mathcal\{E\}\}\_\{s\}\\\}\. Here,𝒩s⊂𝒩\\mathcal\{N\}\_\{s\}\\subset\\mathcal\{N\}, represents a subset of the network’s nodes, whileℰs⊂ℰ\\mathcal\{E\}\_\{s\}\\subset\\mathcal\{E\}represents the weighted set of edges\(i,j\),∀i,j∈𝒩s\(i,j\),\\forall i,j\\in\\mathcal\{N\}\_\{s\}\. Moreover, the set of clusters𝒮\\mathcal\{S\}is connected such that, given any two clusterss,s′∈𝒮s,s^\{\{\}^\{\\prime\}\}\\in\\mathcal\{S\},s≠s′s\\neq s^\{\{\}^\{\\prime\}\}, there is a path from at least one devicei∈𝒩si\\in\\mathcal\{N\}\_\{s\}to another devicek∈𝒩s′k\\in\\mathcal\{N\}\_\{s^\{\{\}^\{\\prime\}\}\}through other clusterss^∈𝒮∖\{s,s′\}\\hat\{s\}\\in\\mathcal\{S\}\\setminus\\\{s,s^\{\{\}^\{\\prime\}\}\\\}if necessary\.

Within each clusters∈𝒮s\\in\\mathcal\{S\}, the set of D2D linksℰ~s\\tilde\{\\mathcal\{E\}\}\_\{s\}is represented by adjacency matrix𝑨~s∈ℝNs×Ns\\tilde\{\\bm\{A\}\}\_\{s\}\\in\\mathbb\{R\}^\{N\_\{s\}\\times N\_\{s\}\}, where𝑨~s=\[a~i,j\]1≤i,j≤N\\tilde\{\\bm\{A\}\}\_\{s\}=\[\\tilde\{a\}\_\{i,j\}\]\_\{1\\leq i,j\\leq N\}witha~i,j=0\\tilde\{a\}\_\{i,j\}=0if\(i,j\)≠ℰs\(i,j\)\\neq\\mathcal\{E\}\_\{s\}and0<a~i,j≤10<\\tilde\{a\}\_\{i,j\}\\leq 1otherwise\. As in existing literature\[[14](https://arxiv.org/html/2606.06687#bib.bib45),[24](https://arxiv.org/html/2606.06687#bib.bib26)\], we consider these adjacency matrices to be doubly stochastic, i\.e\.,A~s​𝟏=A~sT​𝟏=𝟏\\tilde\{A\}\_\{s\}\\bm\{1\}=\\tilde\{A\}\_\{s\}^\{T\}\\bm\{1\}=\\bm\{1\}, with symmetry, i\.e\.,a~i,j=a~j,i\\tilde\{a\}\_\{i,j\}=\\tilde\{a\}\_\{j,i\}, being the result of undirected graphs\. We stack these cluster adjacency matrices𝑨~s\\tilde\{\\bm\{A\}\}\_\{s\}∀s∈𝒮\\forall s\\in\\mathcal\{S\}diagonally, leading to a block diagonal adjacency matrix𝑨~∈ℝN×N\\tilde\{\\bm\{A\}\}\\in\\mathbb\{R\}^\{N\\times N\}such that

𝑨~=\[𝑨~1⋯𝟎⋮⋱⋮𝟎⋯𝑨~S\]\\tilde\{\\bm\{A\}\}=\\begin\{bmatrix\}\\tilde\{\\bm\{A\}\}\_\{1\}&\\cdots&\\mathbf\{0\}\\\\ \\vdots&\\ddots&\\vdots\\\\ \\mathbf\{0\}&\\cdots&\\tilde\{\\bm\{A\}\}\_\{S\}\\end\{bmatrix\}\(1\)for the full graphG~\\tilde\{G\}during intra\-cluster regimes\. Moreover, as each block𝑨~s\\tilde\{\\bm\{A\}\}\_\{s\}is doubly stochastic,𝑨~\\tilde\{\\bm\{A\}\}is also doubly stochastic and symmetric\. On the other hand, for inter\-cluster regimes, the weighted set of D2D edgesℰ\\mathcal\{E\}induces a separate doubly stochastic adjacency matrix𝑨=\[ai,j\]1≤i,j≤N\\bm\{A\}=\[a\_\{i,j\}\]\_\{1\\leq i,j\\leq N\}withai,j≠a~i,ja\_\{i,j\}\\neq\\tilde\{a\}\_\{i,j\},ai,j=0a\_\{i,j\}=0if\(i,j\)∉ℰ\(i,j\)\\notin\\mathcal\{E\}, and0<ai,j≤10<a\_\{i,j\}\\leq 1otherwise\. With this structure, we next analyze the conductance of each cluster via the graph conductanceΦ​\(G~s\)\\Phi\(\\tilde\{G\}\_\{s\}\)defined as

Φ​\(G~s\)=min𝒱⊆𝒩s0<vol​\(𝒱\)≤12​vol​\(𝒩s\)⁡ϕ​\(𝒱\),\\Phi\(\\tilde\{G\}\_\{s\}\)=\\min\_\{\\begin\{subarray\}\{c\}\\mathcal\{V\}\\subseteq\\mathcal\{N\}\_\{s\}\\\\ 0<\\text\{vol\}\(\\mathcal\{V\}\)\\leq\\frac\{1\}\{2\}\\text\{vol\}\(\\mathcal\{N\}\_\{s\}\)\\end\{subarray\}\}\\phi\(\\mathcal\{V\}\),\(2\)where we define the volume of𝒱\\mathcal\{V\}asvol​\(𝒱\)=∑i∈𝒱di\\text\{vol\}\(\\mathcal\{V\}\)=\\sum\_\{i\\in\\mathcal\{V\}\}d\_\{i\}, the degree of nodeiiasdi=∑j∈𝒩sAi,jd\_\{i\}=\\sum\_\{j\\in\\mathcal\{N\}\_\{s\}\}A\_\{i,j\}, and the cut conductance of𝒱\\mathcal\{V\}with respect to𝒩s\\mathcal\{N\}\_\{s\}asϕ​\(𝒱\)\\phi\(\\mathcal\{V\}\)\. Formally, thisϕ​\(𝒱\)\\phi\(\\mathcal\{V\}\)is defined as

ϕ​\(𝒱\)=cut​\(𝒱,𝒱¯\)min⁡\{vol​\(𝒱\),vol​\(𝒱¯\)\},\\phi\(\\mathcal\{V\}\)=\\frac\{\\text\{cut\}\(\\mathcal\{V\},\\overline\{\\mathcal\{V\}\}\)\}\{\\min\\\{\\text\{vol\}\(\\mathcal\{V\}\),\\text\{vol\}\(\\overline\{\\mathcal\{V\}\}\)\\\}\},\(3\)wherecut​\(𝒱,𝒱¯\)=∑i∈𝒱,j∈𝒱¯Ai,j\\text\{cut\}\(\\mathcal\{V\},\\overline\{\\mathcal\{V\}\}\)=\\sum\_\{i\\in\\mathcal\{V\},j\\in\\overline\{\\mathcal\{V\}\}\}A\_\{i,j\}\. In other words, the graph conductanceΦ​\(⋅\)\\Phi\(\\cdot\)measures the smallest cut conductance, and thereby the strength of bottlenecks within a graph or cluster\. This property is leveraged by SSD\-FL for effective cluster formation, as discussed in Sec\.[V](https://arxiv.org/html/2606.06687#S5)\. For brevity, we will refer to graph conductance simply as conductance throughout the rest of the manuscript\.

Within this structure, we assume a total ofTToperational instances, so that𝒯=\{1,⋯,T\}\\mathcal\{T\}=\\\{1,\\cdots,T\\\}, and organize𝒯\\mathcal\{T\}into a series of intra\-cluster regimes of durationτa\>0\\tau\_\{a\}\>0followed by inter\-cluster regimes of durationτr\>0\\tau\_\{r\}\>0\. Together, we combine intra\-cluster and inter\-cluster regimes into overarching global cycles of lengthτg=τa\+τr\\tau\_\{g\}=\\tau\_\{a\}\+\\tau\_\{r\}, thus leading to a total ofK=⌊T/τg⌋K=\\lfloor T/\\tau\_\{g\}\\rfloorglobal cycles with𝒦=\{0,⋯,K−1\}\\mathcal\{K\}=\\\{0,\\cdots,K\-1\\\}\. Given any global cyclek∈𝒦k\\in\\mathcal\{K\}, we denote the intra\-cluster regime ask~\\tilde\{k\}witht∈k~=\{k​τg,⋯,k​τg\+\(τa−1\)\}t\\in\\tilde\{k\}=\\\{k\\tau\_\{g\},\\cdots,k\\tau\_\{g\}\+\(\\tau\_\{a\}\-1\)\\\}and represent the inter\-cluster regime usingk^\\hat\{k\}such thatt∈k^=\{k​τg\+τa,⋯,k​τg\+τa\+\(τr−1\)\}t\\in\\hat\{k\}=\\\{k\\tau\_\{g\}\+\\tau\_\{a\},\\cdots,k\\tau\_\{g\}\+\\tau\_\{a\}\+\(\\tau\_\{r\}\-1\)\\\}\. Similarly, we denote the set of all intra\-cluster and inter\-cluster regimes as𝒦~\\tilde\{\\mathcal\{K\}\}and𝒦^\\hat\{\\mathcal\{K\}\}respectively\. This form enables referencing theqq\-th step for both intra\-cluster and inter\-cluster regimes, e\.g\.,\(k~,q\)=k​τg\+q\(\\tilde\{k\},q\)=k\\tau\_\{g\}\+qforq∈\{0,⋯,τa−1\}q\\in\\\{0,\\cdots,\\tau\_\{a\}\-1\\\}, which we employ as superscripts within the ML mechanisms explained next\.

### III\-BML model training mechanisms

We first explain the ML model training and D2D communications for intra\-cluster regimesk~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}, then summarize the network\-wide consensus process under inter\-cluster regimesk^∈𝒦^\\hat\{k\}\\in\\hat\{\\mathcal\{K\}\}\. During an intra\-cluster regimek~\\tilde\{k\}and iterationqq, all network devicesi∈𝒩i\\in\\mathcal\{N\}locally train a set of ML model parameters𝜽ik~,q∈ℝd\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\\in\\mathbb\{R\}^\{d\}with the goal of minimizing its local loss functionLi​\(𝜽ik~,q\|𝒟i\)L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\|\\mathcal\{D\}\_\{i\}\)defined as

Li​\(𝜽ik~,q\|𝒟i\)=1Di​∑h=1Diℓh​\(𝜽ik~,q\|\(xh,yh\)\),L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\|\\mathcal\{D\}\_\{i\}\)=\\frac\{1\}\{D\_\{i\}\}\\sum\_\{h=1\}^\{D\_\{i\}\}\\ell\_\{h\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\|\(x\_\{h\},y\_\{h\}\)\),\(4\)whereℓh:ℝd→ℝ\\ell\_\{h\}:\\mathbb\{R\}^\{d\}\\rightarrow\\mathbb\{R\}is the loss function for thehh\-th datum with featuresxh∈ℝw×zx\_\{h\}\\in\\mathbb\{R\}^\{w\\times z\}and labelyh∈ℝy\_\{h\}\\in\\mathbb\{R\},𝒟i\\mathcal\{D\}\_\{i\}denotes the dataset at deviceii, andDiD\_\{i\}denotes the dataset size\. For future expressions, we will omit theDiD\_\{i\}dependence within the expression ofLi​\(⋅\)L\_\{i\}\(\\cdot\)as well as the\(xh,yh\)\(x\_\{h\},y\_\{h\}\)dependence for expressions involvingℓh\\ell\_\{h\}\. Moreover, similar to existing literature\[[14](https://arxiv.org/html/2606.06687#bib.bib45),[5](https://arxiv.org/html/2606.06687#bib.bib46)\],ddis set to11to clarify analysis through vector variables\. To minimize their local loss functions in \([4](https://arxiv.org/html/2606.06687#S3.E4)\), each devicei∈𝒩i\\in\\mathcal\{N\}updates its local ML model parameters𝜽ik~,q\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}using the gradient of \([4](https://arxiv.org/html/2606.06687#S3.E4)\), expressed as

∇Li​\(𝜽ik~,q\)=1Di​∑h=1Di∇ℓh​\(𝜽ik~,q\)\.\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)=\\frac\{1\}\{D\_\{i\}\}\\sum\_\{h=1\}^\{D\_\{i\}\}\\nabla\\ell\_\{h\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)\.\(5\)In practice, the full gradient in \([5](https://arxiv.org/html/2606.06687#S3.E5)\) is often approximated by a stochastic gradient,

gi​\(𝜽ik~,q\)=1M​∑h∈𝒟i𝖡,k~,q∇ℓh​\(𝜽ik~,q\),g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)=\\frac\{1\}\{M\}\\sum\_\{h\\in\\mathcal\{D\}\_\{i\}^\{\\mathsf\{B\},\\tilde\{k\},q\}\}\\nabla\\ell\_\{h\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\),\(6\)where𝒟i𝖡,k~,q\\mathcal\{D\}\_\{i\}^\{\\mathsf\{B\},\\tilde\{k\},q\}denotes a randomly sampled mini\-batch ofMMdata from𝒟i\\mathcal\{D\}\_\{i\}at theqq\-th instance during thek~\\tilde\{k\}intra\-cluster regime\. Using \([6](https://arxiv.org/html/2606.06687#S3.E6)\), devicesi∈𝒩i\\in\\mathcal\{N\}then leverage stochastic gradient descent \(SGD\) approaches with heterogeneous optimizers, resulting in standard SGD, proximal SGD, or SGD with momentum\. Formally, these optimizers have the following structures:

- •Standard SGD: g~i​\(𝜽ik~,q\)=gi​\(𝜽ik~,q\),∀q,i\.\\tilde\{g\}\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)=g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\),\\forall q,i\.\(7\)
- •Proximal SGD with0≤μi<10\\leq\\mu\_\{i\}<1being the proximal parameter\[[50](https://arxiv.org/html/2606.06687#bib.bib47)\]: g~i​\(𝜽ik~,q\)=gi​\(𝜽ik~,q\)\+μi​\(𝜽ik~,q−𝜽ik~,0\),∀q,i\.\\tilde\{g\}\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)=g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)\+\\mu\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},0\}\_\{i\}\),\\forall q,i\.\(8\)
- •SGD with momentum where0≤ρi<10\\leq\\rho\_\{i\}<1is the momentum parameter\[[34](https://arxiv.org/html/2606.06687#bib.bib48)\]: g~i​\(𝜽ik~,q\)=gi​\(𝜽ik~,q\)\+∑p=0q−1ρiq−p​gi​\(𝜽ik~,p\),∀q,i\.\\tilde\{g\}\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)=g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)\+\\sum\_\{p=0\}^\{q\-1\}\\rho\_\{i\}^\{q\-p\}g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},p\}\_\{i\}\),\\forall q,i\.\(9\)

Combined, \([7](https://arxiv.org/html/2606.06687#S3.E7)\)\-\([9](https://arxiv.org/html/2606.06687#S3.E9)\) yields an aggregate expression for the local stochastic gradients:

g~i​\(𝜽ik~,q\)=gi​\(𝜽ik~,q\)\+∑p=0q−1ρiq−p​gi​\(𝜽ik~,p\)\+μi​\(𝜽ik~,q−𝜽ik~,0\),\\tilde\{g\}\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)=g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)\+\\sum\_\{p=0\}^\{q\-1\}\\rho\_\{i\}^\{q\-p\}g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},p\}\_\{i\}\)\+\\mu\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},0\}\_\{i\}\),\(10\)which enables devicesi∈𝒩i\\in\\mathcal\{N\}to choose their specific optimizer, e\.g\.,μi=ρi=0\\mu\_\{i\}=\\rho\_\{i\}=0indicates standard SGD whileμi\>0\\mu\_\{i\}\>0andρi=0\\rho\_\{i\}=0indicates SGD with momentum\.

Thus, given an intra\-cluster regimek~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}and clusters∈𝒮s\\in\\mathcal\{S\}, each devicei∈𝒩si\\in\\mathcal\{N\}\_\{s\}would simultaneously update and share their local ML model among neighbors with active D2D links via

𝜽ik~,q\+1=∑j∈𝒩sa~j,is​𝜽jk~,q−η​g~i​\(𝜽ik~,q\),\\bm\{\\theta\}^\{\\tilde\{k\},q\+1\}\_\{i\}=\\sum\_\{\\begin\{subarray\}\{c\}j\\in\\mathcal\{N\}\_\{s\}\\end\{subarray\}\}\\tilde\{a\}^\{s\}\_\{j,i\}\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{j\}\-\\eta\\tilde\{g\}\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\),\(11\)wherea~j,is\\tilde\{a\}^\{s\}\_\{j,i\}is the\(j,i\)\(j,i\)\-th entry of thess\-th cluster’s adjacency matrix𝑨~s\\tilde\{\\bm\{A\}\}\_\{s\},∑j∈𝒩sa~j,is​𝜽jk~,q\\sum\_\{j\\in\\mathcal\{N\}\_\{s\}\}\\tilde\{a\}^\{s\}\_\{j,i\}\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{j\}represents the weighted sum of deviceii’s neighboring ML models from theqq\-th iteration andη\>0\\eta\>0is the learning rate\. Combining the individual device update rule in \([11](https://arxiv.org/html/2606.06687#S3.E11)\) for a clusterss, we then obtain

𝜽^sk~,q\+1=𝑨~s​𝜽^sk~,q−η​𝑮~s​\(𝜽^sk~,q\),\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\+1\}\_\{s\}=\\tilde\{\\bm\{A\}\}\_\{s\}\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\-\\eta\\tilde\{\\bm\{G\}\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\),\(12\)where

𝑮~s​\(𝜽^sk~,q\)=𝑮s​\(𝜽^sk~,q\)\+∑p=0q−1𝝆sq−p⊙𝑮s​\(𝜽^sk~,p\)\\displaystyle\\tilde\{\\bm\{G\}\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)=\\bm\{G\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\+\\sum\_\{p=0\}^\{q\-1\}\\bm\{\\rho\}\_\{s\}^\{q\-p\}\\odot\\bm\{G\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\(13\)\+𝝁s⊙\(𝜽^sk~,q−𝜽^sk~,0\),\\displaystyle\+\\bm\{\\mu\}\_\{s\}\\odot\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\\right\),𝑮s​\(𝜽^sk~,q\)=\[gi​\(𝜽ik~,q\)\]i∈𝒩s\\bm\{G\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)=\\left\[g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)\\right\]\_\{i\\in\\mathcal\{N\}\_\{s\}\},𝝆sq=\[ρiq\]i∈𝒩s\\bm\{\\rho\}^\{q\}\_\{s\}=\[\\rho^\{q\}\_\{i\}\]\_\{i\\in\\mathcal\{N\}\_\{s\}\},𝝁s=\[μi\]i∈𝒩s\\bm\{\\mu\}\_\{s\}=\[\\mu\_\{i\}\]\_\{i\\in\\mathcal\{N\}\_\{s\}\}, and⊙\\odotdenotes the Hadamard product\.

In \([12](https://arxiv.org/html/2606.06687#S3.E12)\), both the active intra\-cluster D2D links and local gradient induce changes to local ML model parameters, which can be better highlighted after the introduction of±𝜽^sk~,q\\pm\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}as follows:

𝜽^sk~,q\+1=𝜽^sk~,q−η​\(𝑮~s​\(𝜽^sk~,q\)\+1η​\(𝐈s−𝑨s\)​𝜽^sk~,q\)⏟≜∇F~s​\(𝜽^sk~,q\),\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\+1\}\_\{s\}=\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\-\\eta\\underbrace\{\\left\(\\tilde\{\\bm\{G\}\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\+\\frac\{1\}\{\\eta\}\\left\(\\mathbf\{I\}\_\{s\}\-\\bm\{A\}\_\{s\}\\right\)\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\\right\)\}\_\{\\triangleq\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\},\(14\)where we use𝐈s\\mathbf\{I\}\_\{s\}to denote the identity matrix of identical dimension to𝑨s\\bm\{A\}\_\{s\}\. From \([14](https://arxiv.org/html/2606.06687#S3.E14)\), the stochastic gradient update is consequently∇F~s​\(𝜽^sk~,q\)\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\), which indicates that SSD\-FL minimizes the stochastic gradient of an “effective” intra\-cluster loss function\. By reversing this gradient,∇F~s​\(⋅\)\\nabla\\tilde\{F\}\_\{s\}\(\\cdot\), we formally define the effective intra\-cluster loss function as follows:

L~s​\(𝜽^sk~,q\)=∑i∈𝒩sLi​\(𝜽ik~,q\)⏟\(a\)\+∑i∈𝒩s𝜽ik~,q​∑p=0q−1ρiq−p​gi​\(𝜽ik~,p\)⏟\(b\)\\displaystyle\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)=\\underbrace\{\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)\}\_\{\(a\)\}\+\\underbrace\{\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\\sum\_\{p=0\}^\{q\-1\}\\rho^\{q\-p\}\_\{i\}g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},p\}\_\{i\}\)\}\_\{\(b\)\}\(15\)\+∑i∈𝒩sμi2​‖𝜽ik~,q−𝜽ik~,0‖2⏟\(c\)\+12​η​‖𝜽^sk~,q‖𝐈s−𝑨s2⏟\(d\),\\displaystyle\+\\underbrace\{\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\frac\{\\mu\_\{i\}\}\{2\}\\\|\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},0\}\_\{i\}\\\|^\{2\}\}\_\{\(c\)\}\+\\underbrace\{\\frac\{1\}\{2\\eta\}\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\\\|^\{2\}\_\{\\mathbf\{I\}\_\{s\}\-\\bm\{A\}\_\{s\}\}\}\_\{\(d\)\},where terms\(a\)\(a\)and\(b\)\(b\)assess the ML model qualities via functions of loss \(with term\(b\)\(b\)active only for devicesi∈𝒩si\\in\\mathcal\{N\}\_\{s\}withρi\>0\\rho\_\{i\}\>0\), term\(c\)\(c\)minimizes sudden or dynamic changes to local ML model parameters \(i\.e\., smoother training for devicesi∈𝒩si\\in\\mathcal\{N\}\_\{s\}withμi\>0\\mu\_\{i\}\>0\), and term\(d\)\(d\)integrates active D2D interaction via a graph regularization term:

‖𝜽^sk~,q‖𝐈s−𝑨~s2=\(𝜽^sk~,q\)T​\(𝐈s−𝑨~s\)​𝜽^sk~,q\\displaystyle\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\\\|^\{2\}\_\{\\mathbf\{I\}\_\{s\}\-\\tilde\{\\bm\{A\}\}\_\{s\}\}=\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\\right\)^\{T\}\(\\mathbf\{I\}\_\{s\}\-\\tilde\{\\bm\{A\}\}\_\{s\}\)\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\(16\)=∑i,j∈𝒩sa~j,i​\(𝜽ik~,q−𝜽jk~,q\)2\.\\displaystyle=\\sum\_\{i,j\\in\\mathcal\{N\}\_\{s\}\}\\tilde\{a\}\_\{j,i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{j\}\)^\{2\}\.The form of \([16](https://arxiv.org/html/2606.06687#S3.E16)\) thus encourages consensus among devicesi∈𝒩si\\in\\mathcal\{N\}\_\{s\}belonging to the same clusterssand with active D2D linksa~j,i\>0\\tilde\{a\}\_\{j,i\}\>0\. Moreover, since𝔼​\[∇F~s​\(𝜽^sk~,q\)\]=∇L^s​\(𝜽^sk~,q\)\\mathbb\{E\}\\left\[\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\]=\\nabla\\hat\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\), we can confirm that, in \([14](https://arxiv.org/html/2606.06687#S3.E14)\), clusterss∈𝒮s\\in\\mathcal\{S\}are performing forms of gradient descent with respect to the effective loss function in \([15](https://arxiv.org/html/2606.06687#S3.E15)\)\.

These properties forL~s\\tilde\{L\}\_\{s\}also hold at the global level, across the sum for all clusters\. Since𝑨~\\tilde\{\\bm\{A\}\}consists of blocks𝑨~s\\tilde\{\\bm\{A\}\}\_\{s\}with alls∈𝒮s\\in\\mathcal\{S\}, the effective global loss function can be expressed as the sum of \([15](https://arxiv.org/html/2606.06687#S3.E15)\) over all clusterss∈𝒮s\\in\\mathcal\{S\}as follows:

L~​\(𝜽k~,q\)=∑s∈𝒮∑i∈𝒩sLi​\(𝜽ik~,q\)\\displaystyle\\tilde\{L\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\)=\\sum\_\{s\\in\\mathcal\{S\}\}\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)\(17\)\+∑i∈𝒩𝜽ik~,q​∑p=0q−1ρiq−p​∇Li​\(𝜽ik~,p\)\\displaystyle\+\\sum\_\{i\\in\\mathcal\{N\}\}\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\\sum\_\{p=0\}^\{q\-1\}\\rho^\{q\-p\}\_\{i\}\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},p\}\_\{i\}\)\+∑i∈𝒩μi2​‖𝜽ik~,q−𝜽ik~,0‖2\+12​η​‖𝜽^sk~,q‖𝐈−𝑨~2,\\displaystyle\+\\sum\_\{i\\in\\mathcal\{N\}\}\\frac\{\\mu\_\{i\}\}\{2\}\\\|\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},0\}\_\{i\}\\\|^\{2\}\+\\frac\{1\}\{2\\eta\}\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\\\|^\{2\}\_\{\\mathbf\{I\}\-\\tilde\{\\bm\{A\}\}\},where𝐈\\mathbf\{I\}is the identity matrix of similar dimension to𝑨~\\tilde\{\\bm\{A\}\}\. Thus, across all clusterss∈𝒮s\\in\\mathcal\{S\}, network devicesi∈𝒩i\\in\\mathcal\{N\}collectively aim to minimize their local loss \(and local proximal terms ifρi\>0\\rho\_\{i\}\>0\) while improving cluster\-wide consensus, during intra\-cluster regimesk~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}\.

On the other hand, during inter\-cluster regimesk^∈𝒦^\\hat\{k\}\\in\\hat\{\\mathcal\{K\}\}, all network devicesi∈𝒩i\\in\\mathcal\{N\}undergo simulated global \(i\.e\., across all clusters\) synchronizations by iterative D2D communications\. Since the goal during inter\-cluster regimes extends beyond singular clusters, the update rule follows the full graphGGand thus adjacency matrix𝑨\\bm\{A\}, yielding

𝜽k^,q\+1=𝑨T​𝜽k^,q,\\bm\{\\theta\}^\{\\hat\{k\},q\+1\}=\\bm\{A\}^\{T\}\\bm\{\\theta\}^\{\\hat\{k\},q\},\(18\)for a total ofτr\\tau\_\{r\}iterations\. These inter\-cluster updates represent a diffusion process over the global network graphGG, whose efficiency depends on the connectivity within𝑨\\bm\{A\}\. In highly connected edge/fog networks, such as dense or fully connected networks \(i\.e\., those with complete graphs\), D2D ML model parameter propagation happens fast, and the network acts as a single cluster\. By contrast, for sparse or weakly connected𝑨\\bm\{A\}\(i\.e\., edge/fog networks with highly heterogeneous link density\), some devices may be poorly synchronized\. As such, careful clustering, followed by intra\-cluster consensus before inter\-cluster communications, provides a structural remedy\. We examine these scenarios within our experiments in Sec\.[VI](https://arxiv.org/html/2606.06687#S6)\.

### III\-CTheoretical Background

We next define theoretical properties underpinning SSD\-FL’s convergence and consensus properties, which we present in Sec\.[IV](https://arxiv.org/html/2606.06687#S4)\. To this end, we first explain assumptions on the device\-level loss functions from \([4](https://arxiv.org/html/2606.06687#S3.E4)\), beginning with smoothness and bounded gradients\.

###### Assumption 1\(Smoothness\)\.

The loss functionsLi​\(⋅\)L\_\{i\}\(\\cdot\)areγi\\gamma\_\{i\}\-Lipschitz smooth, whereγi\>0\\gamma\_\{i\}\>0and∀i∈𝒩\\forall i\\in\\mathcal\{N\}\. Formally,

‖∇Li​\(𝜽1\)−∇Li​\(𝜽2\)‖≤γi​‖𝜽1−𝜽2‖,\\\|\\nabla L\_\{i\}\(\\bm\{\\theta\}\_\{1\}\)\-\\nabla L\_\{i\}\(\\bm\{\\theta\}\_\{2\}\)\\\|\\leq\\gamma\_\{i\}\\\|\\bm\{\\theta\}\_\{1\}\-\\bm\{\\theta\}\_\{2\}\\\|,\(19\)where𝛉1,𝛉2∈ℝd\\bm\{\\theta\}\_\{1\},\\bm\{\\theta\}\_\{2\}\\in\\mathbb\{R\}^\{d\}\.

###### Assumption 2\(Bounded Gradients\)\.

The gradients of loss functions∇Li​\(⋅\)\\nabla L\_\{i\}\(\\cdot\)are bounded∀i∈𝒩\\forall i\\in\\mathcal\{N\}and∀𝛉i\\forall\\bm\{\\theta\}\_\{i\}as follows:

‖∇Li​\(𝜽i\)‖≤B,\\\|\\nabla L\_\{i\}\(\\bm\{\\theta\}\_\{i\}\)\\\|\\leq B,\(20\)where0<B<∞0<B<\\infty\.

We will leverage Assumptions[1](https://arxiv.org/html/2606.06687#Thmassumption1)and[2](https://arxiv.org/html/2606.06687#Thmassumption2)together to simplify the effective global loss of \([17](https://arxiv.org/html/2606.06687#S3.E17)\) and subsequently prove convergence of SSD\-FL\. As such, we also need to formalize properties for the adjacency matrices𝑨~\\tilde\{\\bm\{A\}\}and𝑨\\bm\{A\}as follows:

###### Assumption 3\(Adjacency Matrix Properties\)\.

The adjacency matrices𝐀~\\tilde\{\\bm\{A\}\}and𝐀\\bm\{A\}are both assumed to have the following properties: \(i\) doubly stochastic such that𝐀~​𝟏=𝐀​𝟏=𝟏\\tilde\{\\bm\{A\}\}\\bm\{1\}=\{\\bm\{A\}\}\\bm\{1\}=\\bm\{1\}and𝐀~T​𝟏=𝐀T​𝟏=𝟏\\tilde\{\\bm\{A\}\}^\{T\}\\bm\{1\}=\{\\bm\{A\}\}^\{T\}\\bm\{1\}=\\bm\{1\}, \(ii\)𝐈⪰𝐀~≻0\\mathbf\{I\}\\succeq\\tilde\{\\bm\{A\}\}\\succ 0and𝐈⪰𝐀≻0\\mathbf\{I\}\\succeq\{\\bm\{A\}\}\\succ 0, where⪰\\succeqand≻\\succdenote positive semi\-definite and positive definite respectively, and \(iii\) symmetric such that𝐀~=𝐀~T\\tilde\{\\bm\{A\}\}=\\tilde\{\\bm\{A\}\}^\{T\}and𝐀=𝐀T\{\\bm\{A\}\}=\{\\bm\{A\}\}^\{T\}\.

As a consequence of Assumption[3](https://arxiv.org/html/2606.06687#Thmassumption3), we have that, via the doubly stochastic condition and the Perron\-Frobenius Theorem\[[27](https://arxiv.org/html/2606.06687#bib.bib49)\], the largest eigenvalue of both𝑨~\\tilde\{\\bm\{A\}\}and𝑨\{\\bm\{A\}\}are11, and that, via the positive definite property, the eigenvalues of𝑨~\\tilde\{\\bm\{A\}\}and𝑨\\bm\{A\}are real and strictly positive, i\.e\.,λ1​\(𝑨\)=1≥λ2​\(𝑨\)≥⋯≥λi​\(𝑨\)\>0\\lambda\_\{1\}\(\\bm\{A\}\)=1\\geq\\lambda\_\{2\}\(\\bm\{A\}\)\\geq\\cdots\\geq\\lambda\_\{i\}\(\\bm\{A\}\)\>0whereλm​\(𝑨\)\\lambda\_\{m\}\(\\bm\{A\}\)denotes themm\-th largest eigenvalue of𝑨\\bm\{A\}\. The final assumption relates to variability in the effective intra\-cluster loss functions defined in \([15](https://arxiv.org/html/2606.06687#S3.E15)\)\.

###### Assumption 4\(Bounded Gradient Variances\)\.

For any intra\-cluster regimek~\\tilde\{k\},k∈𝒦k\\in\\mathcal\{K\}, clusters∈𝒮s\\in\\mathcal\{S\}, and instance0≤q<τa−10\\leq q<\\tau\_\{a\}\-1, there exist scalarsα,αs≥0\\alpha,\\alpha\_\{s\}\\geq 0such that

Var⁡\[∇F~s​\(𝜽^sk~,q\)\]≤α\+αs​‖∇L~s​\(𝜽^sk~,q\)‖2\.\\operatorname\{Var\}\\left\[\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\]\\leq\\alpha\+\\alpha\_\{s\}\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\\|^\{2\}\.\(21\)

Since∇F~s​\(𝜽^sk~,q\)\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)is the unbiased estimate of the effective intra\-cluster gradient∇L~s​\(𝜽^sk~,q\)\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\), Assumption[4](https://arxiv.org/html/2606.06687#Thmassumption4)follows naturally\. Finally, as a result of Assumption[4](https://arxiv.org/html/2606.06687#Thmassumption4), we have that

𝔼​\[‖∇F~s​\(𝜽^sk~,q\)‖2\]≤α\+α^s​‖∇L~s​\(𝜽^sk~,q\)‖2,\\mathbb\{E\}\\left\[\\left\\\|\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\\right\]\\leq\\alpha\+\\hat\{\\alpha\}\_\{s\}\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\},\(22\)whereα^s=αs\+1\\hat\{\\alpha\}\_\{s\}=\\alpha\_\{s\}\+1\. In both \([21](https://arxiv.org/html/2606.06687#S3.E21)\) and \([22](https://arxiv.org/html/2606.06687#S3.E22)\), the constantα\\alphadepicts baseline variance, i\.e\., variance floor when‖∇L~s​\(𝜽^sk~,q\)‖2≈0\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\\|^\{2\}\\approx 0, and thereby describes the gradient noise of the stochastic effective gradient∇F~s​\(𝜽^sk~,q\)\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)independent of other variables such as specific intra\-cluster regimek~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}\. Meanwhile,αs\\alpha\_\{s\}and, by extension,α^s\\hat\{\\alpha\}\_\{s\}estimate relative gradient norm amplification, specifically how the variance of effective intra\-cluster stochastic gradient grows with full intra\-cluster gradient norm‖∇L~s​\(𝜽^sk~,q\)‖2\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\\|^\{2\}\. In practice, bothαs\\alpha\_\{s\}and thusα^s\\hat\{\\alpha\}\_\{s\}are influenced by dataset and optimizer heterogeneity within each clusters∈𝒮s\\in\\mathcal\{S\}, and we develop a methodology for their estimation in Sec\.[V](https://arxiv.org/html/2606.06687#S5)\.

## IVTheoretical Results

In the following, we prove integrated \(joint intra\- and inter\-cluster\) convergence across global roundsk∈𝒦k\\in\\mathcal\{K\}for SSD\-FL\. This analysis presents several non\-trivial challenges relative to existing decentralized FL convergence results\. The heterogeneous optimizer structure in \([10](https://arxiv.org/html/2606.06687#S3.E10)\) requires construction of an effective loss function in \([15](https://arxiv.org/html/2606.06687#S3.E15)\), whose smoothness properties require new treatment of gradient gaps across momentum, proximal, and graph regularization terms simultaneously in Sec\.[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1)\. Subsequently, in Sec\.[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2), we explain the integrated convergence of SSD\-FL across intra\- and inter\-cluster regimes in Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2), which leverages the results in Sec\.[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1)and cannot be obtained by direct application or extension of single regime \(intra\- or inter\-cluster\) analysis\.

### IV\-AEffective loss function properties

Given any intra\-cluster regimek~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}, we bound the gradient gap for effective intra\-cluster loss functions, considering the option for heterogeneous optimizers therein\.\{restatable\}propositionreglsmooth \(Gradient Gap of Effective Intra\-cluster Loss\) Given two instancesq1q\_\{1\}andq2q\_\{2\}such thatq1≠q2q\_\{1\}\\neq q\_\{2\}andq1,q2<τaq\_\{1\},q\_\{2\}<\\tau\_\{a\}within any intra\-cluster regimek~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}, the cluster\-level regularized loss functionsL~s​\(𝜽^sk~,q1\)\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)andL~s​\(𝜽^sk~,q2\)\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\),∀s∈𝒮\\forall s\\in\\mathcal\{S\}have bounded gradient gap as follows:

‖∇L~s​\(𝜽^sk~,q1\)−∇L~s​\(𝜽^sk~,q2\)‖≤γs𝖾𝖿𝖿​‖𝜽^sk~,q1−𝜽^sk~,q2‖\+τa​B​Ns\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)\-\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\right\\\|\\leq\\gamma\_\{s\}^\{\\mathsf\{eff\}\}\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\\|\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\(23\)where

γs𝖾𝖿𝖿=\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\),\\gamma\_\{s\}^\{\\mathsf\{eff\}\}=\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\)\\right\),\(24\)andγ^s=maxi∈𝒩s⁡γi\\hat\{\\gamma\}\_\{s\}=\\max\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\gamma\_\{i\}\. Similarly, for global\-level regularized loss functionsL~​\(𝜽k~,q1\)\\tilde\{L\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\)andL~​\(𝜽k~,q2\)\\tilde\{L\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\), the gradient gap is

‖∇L~​\(𝜽k~,q1\)−∇L~​\(𝜽k~,q2\)‖≤γ𝖾𝖿𝖿​‖𝜽k~,q1−𝜽k~,q2‖\+τa​B​N,\\left\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\)\-\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\)\\right\\\|\\leq\{\\gamma\}^\{\\mathsf\{eff\}\}\\left\\\|\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\-\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\\right\\\|\+\\tau\_\{a\}B\\sqrt\{N\},\(25\)where

γ𝖾𝖿𝖿=\(γ^\+1\+1η​\(1−λN​\(𝑨~\)\)\),\{\\gamma\}^\{\\mathsf\{eff\}\}=\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\}\(\\tilde\{\\bm\{A\}\}\)\\right\)\\right\),\(26\)andγ^=maxi∈𝒩⁡γi\\hat\{\\gamma\}=\\max\_\{i\\in\\mathcal\{N\}\}\\gamma\_\{i\}\.

The gradient gap in Proposition[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1)extends the smoothness assumption with standard loss functions in \([4](https://arxiv.org/html/2606.06687#S3.E4)\) to effective intra\-cluster loss functions from \([15](https://arxiv.org/html/2606.06687#S3.E15)\)\. With it, we subsequently establish a corresponding loss gap between any two iterationsq1,q2∈k~q\_\{1\},q\_\{2\}\\in\\tilde\{k\}, for allk~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}as follows:\{restatable\}corollaryresmooth\(Effective Intra\-cluster Loss Gap\) Given two instancesq1q\_\{1\}andq2q\_\{2\}such thatq1≠q2q\_\{1\}\\neq q\_\{2\}andq1,q2<τaq\_\{1\},q\_\{2\}<\\tau\_\{a\}within any intra\-cluster regimek~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}, the cluster\-level effective loss functionsL~s​\(𝜽^sk~,q1\)\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)andL~s​\(𝜽^sk~,q2\)\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\),∀s∈𝒮\\forall s\\in\\mathcal\{S\}have bounded gap as follows:

L~s​\(𝜽^sk~,q1\)≤L~s​\(𝜽^sk~,q2\)\+\(∇L~s​\(𝜽^sk~,q2\)\)T​\(𝜽^sk~,q1−𝜽^sk~,q2\)\\displaystyle\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)\\leq\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\+\\left\(\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\right\)^\{T\}\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)\(27\)\+\(12​γs𝖾𝖿𝖿\+τa​B​Ns\)​‖𝜽^sk~,q1−𝜽^sk~,q2‖2\.\\displaystyle\+\\left\(\\frac\{1\}\{2\}\\gamma^\{\\mathsf\{eff\}\}\_\{s\}\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\\|^\{2\}\.
Together, Proposition[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1)and Corollary[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1)generalize conventional smoothness property of local loss functions to their effective intra\-cluster loss function counterparts\. In this regard, from \([23](https://arxiv.org/html/2606.06687#S4.E23)\), \([25](https://arxiv.org/html/2606.06687#S4.E25)\), and \([27](https://arxiv.org/html/2606.06687#S4.E27)\), we see that the smoothness ofL~s​\(⋅\)\\tilde\{L\}\_\{s\}\(\\cdot\)is preserved, with additive terms determined by the size of the cluster/network \(Ns\\sqrt\{N\_\{s\}\}orN\\sqrt\{N\}\) and the intra\-cluster regime duration,τa\\tau\_\{a\}\.

### IV\-BSSD\-FL convergence and consensus

Towards proving SSD\-FL’s integrated global round convergence \(i\.e\., across both intra\- and inter\-cluster regimes\), we begin by leveraging effective intra\-cluster loss function properties to demonstrate intra\-cluster convergence as follows:\{restatable\}theoremintraConv \(Intra\-cluster Convergence\) Ifη<2α^s​Γs\\eta<\\frac\{2\}\{\\hat\{\\alpha\}\_\{s\}\\Gamma\_\{s\}\}, then, given any intra\-cluster regimek~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}and clusters∈𝒮s\\in\\mathcal\{S\}, we bound the first\-order stationary point as follows:

∑q=0τa−1‖∇L~s​\(𝜽^sk~,q\)‖2≤L~s​\(𝜽^sk~,0\)\+α​τa​η22​Γsη−α^s​η22​Γs\\displaystyle\\sum\_\{q=0\}^\{\\tau\_\{a\}\-1\}\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\\leq\\frac\{\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\)\+\\frac\{\\alpha\\tau\_\{a\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\(28\)where

Γs=\(γs𝖾𝖿𝖿\+τa​B​Ns\)\.\\Gamma\_\{s\}=\\left\(\\gamma^\{\\mathsf\{eff\}\}\_\{s\}\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\.\(29\)
When the baseline variance of the effective intra\-cluster stochastic gradient is near zero, i\.e\.,α≈0\\alpha\\approx 0, such as when batches are the size of the full dataset per the discussion in Assumption[4](https://arxiv.org/html/2606.06687#Thmassumption4), then Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)implies that∑q=0τa−1‖∇L~s​\(𝜽^sk~,q\)‖2≤L~s​\(𝜽^sk~,0\)η−α^s​η22​Γs\\sum\_\{q=0\}^\{\\tau\_\{a\}\-1\}\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\\leq\\frac\{\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\)\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\. In other words, the first\-order stationary point becomes bounded by a constant independent of the intra\-cluster regime durationτa\\tau\_\{a\}\. Consequently, for largeτa→∞\\tau\_\{a\}\\rightarrow\\infty, the average first\-order stationary point is bounded above by zero

limτa→∞1τa​∑q=0τa−1‖∇L~s​\(𝜽^sk~,q\)‖2≤limτa→∞1τa​L~s​\(𝜽^sk~,0\)η−α^s​η22​Γs→0,\\lim\_\{\\tau\_\{a\}\\rightarrow\\infty\}\\frac\{1\}\{\\tau\_\{a\}\}\\sum\_\{q=0\}^\{\\tau\_\{a\}\-1\}\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\\leq\\lim\_\{\\tau\_\{a\}\\rightarrow\\infty\}\\frac\{1\}\{\\tau\_\{a\}\}\\frac\{\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\)\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\\rightarrow 0,\(30\)and therefore∇L~s​\(𝜽^sk~,q\)→0\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\rightarrow 0for allq∈k~q\\in\\tilde\{k\}\. By contrast, for stochastic gradients with non\-trivial batches,α\>0\\alpha\>0and thus the average first\-order stationary point asτa→∞\\tau\_\{a\}\\rightarrow\\inftyis bounded by a constant, specificallyα​η22​Γsη−α^s​η22​Γs\\frac\{\\frac\{\\alpha\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\. As such, SSD\-FL is able to yield bounded average first\-order stationary points\. With this characterization of intra\-cluster regime convergence, we next examine the corresponding intra\-cluster consensus gap properties\.\{restatable\}lemmaintraCons\(Intra\-cluster consensus gap\) For any intra\-cluster regimek~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}and assuming thatΔsk~,q⟂𝟏s\\Delta^\{\\tilde\{k\},q\}\_\{s\}\\perp\\bm\{1\}\_\{s\}andη<1−λ2​\(𝑨s\)\\eta<1\-\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\), the intra\-cluster cluster consensus gap can be bounded above as follows:

‖Δsk~,τa‖≤\(λ2​\(𝑨s\)\+η\)τa−1​‖Δsk~,0‖⏟\(a\)\+2​η​τa​B​Ns1−η−λ2​\(𝑨s\)⏟\(b\),\\left\\\|\\Delta^\{\\tilde\{k\},\\tau\_\{a\}\}\_\{s\}\\right\\\|\\leq\\underbrace\{\(\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\+\\eta\)^\{\\tau\_\{a\}\-1\}\\left\\\|\\Delta^\{\\tilde\{k\},0\}\_\{s\}\\right\\\|\}\_\{\(a\)\}\+\\underbrace\{\\frac\{2\\eta\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\}\{1\-\\eta\-\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\}\}\_\{\(b\)\},\(31\)whereΔsk~,τa=𝜽¯sk~,τa​𝟏s−𝜽^sk~,τa\\Delta^\{\\tilde\{k\},\\tau\_\{a\}\}\_\{s\}=\\overline\{\\bm\{\\theta\}\}^\{\\tilde\{k\},\\tau\_\{a\}\}\_\{s\}\\bm\{1\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},\\tau\_\{a\}\}\_\{s\}, and𝜽¯sk~,τa=1Ns​∑i∈𝒩s𝜽sk~,τa\\overline\{\\bm\{\\theta\}\}^\{\\tilde\{k\},\\tau\_\{a\}\}\_\{s\}=\\frac\{1\}\{N\_\{s\}\}\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\bm\{\\theta\}^\{\\tilde\{k\},\\tau\_\{a\}\}\_\{s\}\.

For individual clusterss∈𝒮s\\in\\mathcal\{S\}, the two terms in Lemma[30](https://arxiv.org/html/2606.06687#S4.E30)highlight competing effects in intra\-cluster regimes\. While the initial intra\-cluster disagreement decreases exponentially in term \([31](https://arxiv.org/html/2606.06687#S4.E31)\)\(a\)\(a\)as a result ofλ2​\(𝑨s\)\+η<1\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\+\\eta<1, the2​η​τa​B​Ns2\\eta\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}component of \([31](https://arxiv.org/html/2606.06687#S4.E31)\)\(b\)\(b\)grows linearly with respect to the duration of the intra\-cluster regimeτa\\tau\_\{a\}\. Specifically, we refer to2​η​τa​B​Ns2\\eta\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}as a cumulative gradient noise from bounding the gradient of the effective intra\-cluster loss functionL~s​\(𝜽^sk~,q\)\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)and therein the heterogeneous optimizer choices embedded via𝝆\\bm\{\\rho\}and𝝁\\bm\{\\mu\}\. As a result, Lemma[30](https://arxiv.org/html/2606.06687#S4.E30)implies that consensus is not assured within individual clusterss∈𝒮s\\in\\mathcal\{S\}even though they demonstrate convergence in Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)\. This motivates inter\-cluster regimesk^∈𝒦^\\hat\{k\}\\in\\hat\{\\mathcal\{K\}\}in SSD\-FL, as the network can thus synchronize all devicesi∈𝒩i\\in\\mathcal\{N\}as well as re\-balance the cumulative gradient noise within clusterss∈𝒮s\\in\\mathcal\{S\}\. In this regard, we next show the inter\-cluster consensus:\{restatable\}lemmainterCons\(Inter\-cluster consensus\) Given any instanceqqwithin an inter\-cluster regimek^∈𝒦^\\hat\{k\}\\in\\hat\{\\mathcal\{K\}\}and assuming thatΔ^k^,q⟂𝟏s\\hat\{\\Delta\}^\{\\hat\{k\},q\}\\perp\\bm\{1\}\_\{s\}, we bound the inter\-cluster consensus gap as

‖Δ^k^,τr‖≤λ2​\(𝑨\)τr−1​‖Δ^k^,0‖,\\left\\\|\\hat\{\\Delta\}^\{\\hat\{k\},\\tau\_\{r\}\}\\right\\\|\\leq\\lambda\_\{2\}\(\\bm\{A\}\)^\{\\tau\_\{r\}\-1\}\\left\\\|\\hat\{\\Delta\}^\{\\hat\{k\},0\}\\right\\\|,\(32\)whereΔ^k^,q=𝜽¯k^,q​𝟏−𝜽k~,q\\hat\{\\Delta\}^\{\\hat\{k\},q\}=\\overline\{\\bm\{\\theta\}\}^\{\\hat\{k\},q\}\\bm\{1\}\-\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}, and𝜽¯k^,q=1N​∑i∈𝒩𝜽k^,q\\overline\{\\bm\{\\theta\}\}^\{\\hat\{k\},q\}=\\frac\{1\}\{N\}\\sum\_\{i\\in\\mathcal\{N\}\}\\bm\{\\theta\}^\{\\hat\{k\},q\}\.

From \([32](https://arxiv.org/html/2606.06687#S4.E32)\), it is immediate that all devicesi∈𝒩i\\in\\mathcal\{N\}reach consensus in exponential fashion, as Assumption[3](https://arxiv.org/html/2606.06687#Thmassumption3)impliesλ2​\(𝑨\)<1\\lambda\_\{2\}\(\\bm\{A\}\)<1\. Thus, inter\-cluster regimesk^∈𝒦^\\hat\{k\}\\in\\hat\{\\mathcal\{K\}\}integrate the intra\-cluster regime convergences from Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)across all clusterss∈𝒮s\\in\\mathcal\{S\}\. Formally, we prove integrated convergence across full global roundsk∈𝒦k\\in\\mathcal\{K\}, obtaining the following result\.\{restatable\}theoremcombConv \(Integrated Convergence\) Letη≤mins∈𝒮⁡\{1−λ2​\(𝑨~s\),2α^s​Γs\}\\eta\\leq\\min\_\{s\\in\\mathcal\{S\}\}\\\{1\-\\lambda\_\{2\}\(\\tilde\{\\bm\{A\}\}\_\{s\}\),\\frac\{2\}\{\\hat\{\\alpha\}\_\{s\}\\Gamma\_\{s\}\}\\\}, then, for all global cyclesk∈𝒦k\\in\\mathcal\{K\}, we have bounded first\-order stationary point as follows:

∑q=0τr\+τa−1‖∇L~​\(𝜽k,q\)‖2≤\(2​τr−1\)​L~​\(𝜽k,0\)\+α​C1​∑s∈𝒮Γsη−α^​η22​Γ\\displaystyle\\sum\_\{q=0\}^\{\\tau\_\{r\}\+\\tau\_\{a\}\-1\}\\left\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\right\\\|^\{2\}\\leq\\frac\{\(2\\tau\_\{r\}\-1\)\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\)\+\\alpha C\_\{1\}\\sum\_\{s\\in\\mathcal\{S\}\}\\Gamma\_\{s\}\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\\eta^\{2\}\}\{2\}\\Gamma\}\(33\)\+4​\(τr−1\)​\(γ𝖾𝖿𝖿​\(1−λN​\(𝑨\)\)1−λ2​\(𝑨\)\)2​‖Δ^k,0‖2\+4​C2\\displaystyle\+4\(\\tau\_\{r\}\-1\)\\left\(\\frac\{\\gamma^\{\\mathsf\{eff\}\}\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)\}\{1\-\\lambda\_\{2\}\(\{\\bm\{A\}\}\)\}\\right\)^\{2\}\\\|\\hat\{\\Delta\}^\{k,0\}\\\|^\{2\}\+4C\_\{2\}whereΓ=γ𝖾𝖿𝖿\+τa​B​N\\Gamma=\\gamma^\{\\mathsf\{eff\}\}\+\\tau\_\{a\}B\\sqrt\{N\},C1=\(τa\+2​τr−2\)​η22C\_\{1\}=\\frac\{\\left\(\\tau\_\{a\}\+2\\tau\_\{r\}\-2\\right\)\\eta^\{2\}\}\{2\},C2=τa2​B2​N​τr​\(τa\+τr−1\)2C\_\{2\}=\\tau\_\{a\}^\{2\}B^\{2\}N\\tau\_\{r\}\(\\tau\_\{a\}\+\\tau\_\{r\}\-1\)^\{2\}, andα^=maxs∈𝒮⁡α^s\\hat\{\\alpha\}=\\max\_\{s\\in\\mathcal\{S\}\}\\hat\{\\alpha\}\_\{s\}\.

Aside fromL~​\(𝜽k,0\)\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\), all other terms on the right hand side of[33](https://arxiv.org/html/2606.06687#S4.E33)remain constants independent of the global roundk∈𝒦k\\in\\mathcal\{K\}\. As such, since effective global loss from \([17](https://arxiv.org/html/2606.06687#S3.E17)\) can be bounded byL~max\\tilde\{L\}^\{\\max\}for allk∈𝒦k\\in\\mathcal\{K\}, we have that, asK→∞K\\rightarrow\\infty,

limK→∞1K​∑k∈𝒦∑q=0τa\+τr−1‖∇L​\(𝜽k,q\)‖2\\displaystyle\\lim\_\{K\\rightarrow\\infty\}\\frac\{1\}\{K\}\\sum\_\{k\\in\\mathcal\{K\}\}\\sum\_\{q=0\}^\{\\tau\_\{a\}\+\\tau\_\{r\}\-1\}\\left\\\|\\nabla L\(\\bm\{\\theta\}^\{k,q\}\)\\right\\\|^\{2\}\(34\)≤\(2​τr−1\)​L​\(𝜽k,0\)\+α​C1​∑s∈𝒮Γsη−α^​η22​Γ\\displaystyle\\leq\\frac\{\(2\\tau\_\{r\}\-1\)L\(\\bm\{\\theta\}^\{k,0\}\)\+\\alpha C\_\{1\}\\sum\_\{s\\in\\mathcal\{S\}\}\\Gamma\_\{s\}\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\\eta^\{2\}\}\{2\}\\Gamma\}\+4​\(τr−1\)​\(γ𝖾𝖿𝖿​\(1−λN​\(𝑨\)\)1−λ2​\(𝑨\)\)2​‖Δ^k,0‖2\+4​C2\.\\displaystyle\+4\(\\tau\_\{r\}\-1\)\\left\(\\frac\{\\gamma^\{\\mathsf\{eff\}\}\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)\}\{1\-\\lambda\_\{2\}\(\{\\bm\{A\}\}\)\}\\right\)^\{2\}\\\|\\hat\{\\Delta\}^\{k,0\}\\\|^\{2\}\+4C\_\{2\}\.In other words, the average global first\-order stationary point, integrated across intra\-cluster regimesk~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}and inter\-cluster regimesk^∈𝒦^\\hat\{k\}\\in\\hat\{\\mathcal\{K\}\}, is bounded above by a constant independent of the global roundkk\. Therefore, Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)indicates that SSD\-FL yields bounded global convergence, with finite effective global loss function gradients\.

## VCluster Formation

The theoretical results on convergence and consensus of SSD\-FL in Sec\.[IV](https://arxiv.org/html/2606.06687#S4)assumed a general case with1≤S≤N1\\leq S\\leq Ntotal clusters to partition the network ofNNdevices\. Now, we leverage those results to develop SSD\-FL’s cluster formation algorithm, determining both an optimal number of clustersS=\|𝒮\|S=\|\\mathcal\{S\}\|and the constituent devices therein, i\.e\.,𝒩s,∀s∈𝒮\\mathcal\{N\}\_\{s\},\\forall s\\in\\mathcal\{S\}\. The key cluster formation steps are summarized in Algorithm[1](https://arxiv.org/html/2606.06687#alg1)\.

### V\-AConductance criteria

To develop a conductance criteria for cluster formation, we revisit Lemma[30](https://arxiv.org/html/2606.06687#S4.E30)\. For the first global roundk=0k=0, the intra\-cluster consensus gap‖Δsk~,0‖=0\\\|\\Delta^\{\\tilde\{k\},0\}\_\{s\}\\\|=0for any and all possible clusterss∈𝒮s\\in\\mathcal\{S\}andS∈\{1,⋯,N\}S\\in\\\{1,\\cdots,N\\\}\(as the optimal number of clustersSSis unknown\), specifically because network devices are initialized with the same local ML model parameters so thatθi0,0=θj0,0\\theta^\{0,0\}\_\{i\}=\\theta^\{0,0\}\_\{j\}∀i,j∈𝒩\\forall i,j\\in\\mathcal\{N\}\. Setting‖Δ𝗍𝗈𝗅‖\\\|\\Delta^\{\\mathsf\{tol\}\}\\\|as the limit on the tolerable consensus gap across allk~∈𝒦~\\tilde\{k\}\\in\\tilde\{\\mathcal\{K\}\}, we can then obtain the following by rearranging Lemma[30](https://arxiv.org/html/2606.06687#S4.E30)for any clusters∈𝒮s\\in\\mathcal\{S\}andS∈\{1,⋯,N\}S\\in\\\{1,\\cdots,N\\\}

η\+2​η​B​⌊N/S⌋‖Δ𝗍𝗈𝗅‖≤1−λ2​\(𝑨~s\)\.\\eta\+\\frac\{2\\eta B\\sqrt\{\\lfloor N/S\\rfloor\}\}\{\\\|\\Delta^\{\\mathsf\{tol\}\}\\\|\}\\leq 1\-\\lambda\_\{2\}\(\\tilde\{\\bm\{A\}\}\_\{s\}\)\.\(35\)Noting thatI−𝑨~sI\-\\tilde\{\\bm\{A\}\}\_\{s\}is equivalent to the normalized Laplacian for any clusters∈𝒮s\\in\\mathcal\{S\}as a result of Assumption[3](https://arxiv.org/html/2606.06687#Thmassumption3), we can then leverage Cheeger’s inequality\[[6](https://arxiv.org/html/2606.06687#bib.bib56)\], which states that

\(ΦSmin\)22≤1−λ2​\(𝑨~s\)\\frac\{\(\\Phi^\{\\min\}\_\{S\}\)^\{2\}\}\{2\}\\leq 1\-\\lambda\_\{2\}\(\\tilde\{\\bm\{A\}\}\_\{s\}\)\(36\)whereΦSmin\\Phi^\{\\min\}\_\{S\}denotes the minimum conductance threshold forS∈\{1,⋯,N\}S\\in\\\{1,\\cdots,N\\\}\. By inspection of \([35](https://arxiv.org/html/2606.06687#S5.E35)\) and \([36](https://arxiv.org/html/2606.06687#S5.E36)\), we have that

ΦSmin=2​η\+4​η​B​⌊N/S⌋‖Δ𝗍𝗈𝗅‖\.\\Phi^\{\\min\}\_\{S\}=\\sqrt\{2\\eta\+\\frac\{4\\eta B\\sqrt\{\\lfloor N/S\\rfloor\}\}\{\\\|\\Delta^\{\\mathsf\{tol\}\}\\\|\}\}\.\(37\)To summarize, given some set of clusters𝒮\\mathcal\{S\}, \([37](https://arxiv.org/html/2606.06687#S5.E37)\) adapts a minimum conductance thresholdΦSmin\\Phi^\{\\min\}\_\{S\}inversely proportional to the maximum tolerable intra\-cluster consensus gapΔS𝗍𝗈𝗅\\Delta^\{\\mathsf\{tol\}\}\_\{S\}\. Moreover,ΦSmin\\Phi^\{\\min\}\_\{S\}changes with the number of clusters, as largerSSin \([37](https://arxiv.org/html/2606.06687#S5.E37)\) reduces the conductance requirement for each clusters∈𝒮s\\in\\mathcal\{S\}\. This is intended because more clusters results in fewer devices per cluster \(on average\), which in turn reduces the likelihood of more divergent datasets \(as compared to clusters with more devices\)\.

Algorithm 1Cluster Formation in SSD\-FL1:Input:Network graph

G=\(𝒩,𝑨\)G=\(\\mathcal\{N\},\\bm\{A\}\), intra\-cluster duration

τa\\tau\_\{a\}, inter\-cluster duration

τr\\tau\_\{r\}, learning rate

η\\eta, bound

BB, maximum tolerable consensus gap

‖ΔS𝗍𝗈𝗅‖\\\|\\Delta^\{\\mathsf\{tol\}\}\_\{S\}\\\|, and effective smoothness coefficients

γs𝖾𝖿𝖿\\gamma^\{\\mathsf\{eff\}\}\_\{s\}and

γ𝖾𝖿𝖿\\gamma^\{\\mathsf\{eff\}\}\.

2:Output:Optimal set of clusters

𝒮∗\\mathcal\{S\}^\{\*\}\.

3:Initialize sets of candidate partitions

𝒮~=\{\{G\}\}\\tilde\{\\mathcal\{S\}\}=\\\{\\\{G\\\}\\\}, estimated average first\-order stationary points

ℋ~=\{\}\\tilde\{\\mathcal\{H\}\}=\\\{\\\}, and minimum conductance thresholds

𝚽min=\{\}\\bm\{\\Phi\}^\{\\min\}=\\\{\\\}\.

4:Initialize

𝒮^=\{G\}\\hat\{\\mathcal\{S\}\}=\\\{G\\\}as the starting partition of the original network

GG\.

5:while

\|𝒮^\|≤N\|\\hat\{\\mathcal\{S\}\}\|\\leq Ndo

6:Determine conductance threshold

Φ\|𝒮^\|min\\Phi^\{\\min\}\_\{\|\\hat\{\\mathcal\{S\}\}\|\}via \([37](https://arxiv.org/html/2606.06687#S5.E37)\)\.

7:Track the average \(over clusters

𝒮^\\hat\{\\mathcal\{S\}\}\) intra\-cluster first\-order stationary point from Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)in \([28](https://arxiv.org/html/2606.06687#S4.E28)\), i\.e\.,

ℋ~←ℋ~∪\{1S^​∑s∈𝒮^L~s​\(𝜽^sk~,0\)\+α​τa​η22​Γsη−α^s​η22​Γs\}\\tilde\{\\mathcal\{H\}\}\\leftarrow\\tilde\{\\mathcal\{H\}\}\\cup\\left\\\{\\frac\{1\}\{\\hat\{S\}\}\\sum\_\{s\\in\\hat\{\\mathcal\{S\}\}\}\\frac\{\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\)\+\\frac\{\\alpha\\tau\_\{a\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\\right\\\}\. This average relies on

αso\\alpha\_\{s\}^\{o\}and

αsd\\alpha\_\{s\}^\{d\},

∀s∈𝒮^\\forall s\\in\\hat\{\\mathcal\{S\}\}, estimates via the processes in \([38](https://arxiv.org/html/2606.06687#S5.E38)\)\-\([41](https://arxiv.org/html/2606.06687#S5.E41)\) to obtain

αs\\alpha\_\{s\}\.

8:Sort clusters

s∈𝒮^s\\in\\hat\{\\mathcal\{S\}\}in ascending conductance, i\.e\., let

𝒬=\{s\(1\),…,s\(\|𝒮\|\)\}←sorts∈𝒮^⁡\(Φ​\(G~s\)\)\\mathcal\{Q\}=\\\{s^\{\(1\)\},\\dots,s^\{\(\|\\mathcal\{S\}\|\)\}\\\}\\leftarrow\\operatorname\{sort\}\_\{s\\in\\hat\{\\mathcal\{S\}\}\}\(\\Phi\(\\tilde\{G\}\_\{s\}\)\)\.

9:

𝒮^←SpectralPartitioning​\(ΦSmin,𝒬\)\\hat\{\\mathcal\{S\}\}\\leftarrow\\textsc\{SpectralPartitioning\}\(\\Phi^\{\\min\}\_\{S\},\\mathcal\{Q\}\)\.

10:Update set of all candidate partitions,

𝒮~←𝒮~∪\{𝒮^\}\\tilde\{\\mathcal\{S\}\}\\leftarrow\\tilde\{\\mathcal\{S\}\}\\cup\\\{\\hat\{\\mathcal\{S\}\}\\\}\.

11:endwhile

12:Find the optimal cluster

𝒮∗\\mathcal\{S\}^\{\*\}that satisfies the conductance requirements in

ΦSmin\\Phi^\{\\min\}\_\{S\}with minimum average first\-order stationary point, i\.e\.,

𝒮∗=arg⁡min𝒮∈𝒮~⁡ℋ~\\mathcal\{S\}^\{\*\}=\\arg\\min\_\{\\mathcal\{S\}\\in\\tilde\{\\mathcal\{S\}\}\}\\tilde\{\\mathcal\{H\}\}subject to

mins∈𝒮⁡Φ​\(G~s\)≥ΦSmin\\min\_\{s\\in\\mathcal\{S\}\}\\Phi\(\\tilde\{G\}\_\{s\}\)\\geq\\Phi^\{\\min\}\_\{S\}\.

13:Return

𝒮∗\\mathcal\{S\}^\{\*\}\.

### V\-BIntegration of heterogeneous optimizers

Within any clusters∈𝒮s\\in\\mathcal\{S\}, the internal cluster heterogeneity influences relative gradient norm amplificationαs\{\\alpha\}\_\{s\}andα^s\\hat\{\\alpha\}\_\{s\}as per Assumption[4](https://arxiv.org/html/2606.06687#Thmassumption4), and, in turn,α^s\\hat\{\\alpha\}\_\{s\}greatly influences the resulting convergence results in Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)and[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)\. As the two primary forms of D2D heterogeneity are at the data\-level and optimizer\-level, we defineαs=αso\+αsd\\alpha\_\{s\}=\\alpha\_\{s\}^\{o\}\+\\alpha\_\{s\}^\{d\}whereαso\\alpha\_\{s\}^\{o\}andαsd\\alpha\_\{s\}^\{d\}are the optimizer\-induced and data\-induced gradient norm amplification coefficients respectively\.

Since bothαso\\alpha\_\{s\}^\{o\}andαsd\\alpha\_\{s\}^\{d\}measure internal cluster differences, we obtain them via D2D pairwise comparisons\. Towards optimizer\-induced heterogeneity, we first obtain

βso=1Ns2​∑i∈𝒩s∑j∈𝒩sζ1​𝟏\[opti≠optj\]\+ζ2​‖μi−μj‖\+ζ3​‖ρi−ρj‖,\\beta\_\{s\}^\{o\}=\\frac\{1\}\{N\_\{s\}^\{2\}\}\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\sum\_\{j\\in\\mathcal\{N\}\_\{s\}\}\\zeta\_\{1\}\\mathbf\{1\}\_\{\[\\text\{opt\}\_\{i\}\\neq\\text\{opt\}\_\{j\}\]\}\+\\zeta\_\{2\}\\\|\\mu\_\{i\}\-\\mu\_\{j\}\\\|\+\\zeta\_\{3\}\\\|\\rho\_\{i\}\-\\rho\_\{j\}\\\|,\(38\)whereζ1\\zeta\_\{1\},ζ2\\zeta\_\{2\}, andζ3\\zeta\_\{3\}are scaling coefficients for differentials in optimizer, proximal parametersμi\\mu\_\{i\}andμj\\mu\_\{j\}, and momentum parametersρi\\rho\_\{i\}andρj\\rho\_\{j\}\. Subsequently, we linearly scaleβso\\beta^\{o\}\_\{s\}to obtainαso\\alpha^\{o\}\_\{s\}as follows

αso=βsoζ1\+ζ2\+ζ3​\(αo,max−αo,min\)\+αo,min,\\alpha\_\{s\}^\{o\}=\\frac\{\\beta^\{o\}\_\{s\}\}\{\\zeta\_\{1\}\+\\zeta\_\{2\}\+\\zeta\_\{3\}\}\(\\alpha^\{o,\\max\}\-\\alpha^\{o,\\min\}\)\+\\alpha^\{o,\\min\},\(39\)whereαo,max\\alpha^\{o,\\max\}andαo,min\\alpha^\{o,\\min\}denote the max and min contributions to optimizer heterogeneity scaling inαso\\alpha^\{o\}\_\{s\}, respectively\. On the other hand, the data heterogeneity estimation relies on a combination of empirical average Jensen\-Shannon divergence \(JSD\)\[[8](https://arxiv.org/html/2606.06687#bib.bib58)\]of relative frequencies and empirical energy distance \(EED\)\[[30](https://arxiv.org/html/2606.06687#bib.bib57)\]of a sample of raw data from device\-level datasets\. We express this as

βsd=1\|ℰ~s\|​∑i,j∈𝒩s\(i,j\)∈ℰ~s\(JSD​\(𝒴i∥𝒴j\)\+1w​z​EED​\(𝒟^i,𝒟^j\)\),\\beta\_\{s\}^\{d\}=\\frac\{1\}\{\|\\tilde\{\\mathcal\{E\}\}\_\{s\}\|\}\\sum\_\{\\begin\{subarray\}\{c\}i,j\\in\\mathcal\{N\}\_\{s\}\\\\ \(i,j\)\\in\\tilde\{\\mathcal\{E\}\}\_\{s\}\\end\{subarray\}\}\\left\(\\text\{JSD\}\(\\mathcal\{Y\}\_\{i\}\\\|\\mathcal\{Y\}\_\{j\}\)\+\\frac\{1\}\{wz\}\\text\{EED\}\(\\hat\{\\mathcal\{D\}\}\_\{i\},\\hat\{\\mathcal\{D\}\}\_\{j\}\)\\right\),\(40\)where\|ℰ~s\|\|\\tilde\{\\mathcal\{E\}\}\_\{s\}\|denotes the cardinality ofℰ~s\\tilde\{\\mathcal\{E\}\}\_\{s\},JSDrepresents the Jensen\-Shannon divergence,𝒴i\\mathcal\{Y\}\_\{i\}is the relative frequency of labels within deviceii’s dataset𝒟i\\mathcal\{D\}\_\{i\},w​zwzrepresents the total data features,EED​\(𝒟^i,𝒟^j\)=2D^i​D^j​∑h∈𝒟^i,m∈𝒟j^‖xh−xm‖−1D^i2​∑h,m∈D^i‖xh−xm‖−1D^j2​∑h,m∈D^j‖xh−xm‖\\text\{EED\}\(\\hat\{\\mathcal\{D\}\}\_\{i\},\\hat\{\\mathcal\{D\}\}\_\{j\}\)=\\frac\{2\}\{\\hat\{D\}\_\{i\}\\hat\{D\}\_\{j\}\}\\sum\_\{h\\in\\hat\{\\mathcal\{D\}\}\_\{i\},m\\in\\hat\{\\mathcal\{D\}\_\{j\}\}\}\\\|x\_\{h\}\-x\_\{m\}\\\|\-\\frac\{1\}\{\\hat\{D\}\_\{i\}^\{2\}\}\\sum\_\{h,m\\in\\hat\{D\}\_\{i\}\}\\\|x\_\{h\}\-x\_\{m\}\\\|\-\\frac\{1\}\{\\hat\{D\}\_\{j\}^\{2\}\}\\sum\_\{h,m\\in\\hat\{D\}\_\{j\}\}\\\|x\_\{h\}\-x\_\{m\}\\\|as the squared empirical energy distance from\[[30](https://arxiv.org/html/2606.06687#bib.bib57)\], and𝒟^i\\hat\{\\mathcal\{D\}\}\_\{i\}denotes a randomly chosen batch of data of sizeD^i\\hat\{D\}\_\{i\}from deviceii\. Note that\|𝒟^i\|=\|𝒟^j\|\|\\hat\{\\mathcal\{D\}\}\_\{i\}\|=\|\\hat\{\\mathcal\{D\}\}\_\{j\}\|, for any\(i,j\)∈ℰ~s\(i,j\)\\in\\tilde\{\\mathcal\{E\}\}\_\{s\}\.

The structure of \([40](https://arxiv.org/html/2606.06687#S5.E40)\) in that both JSD and EED are used to estimate pairwise and total cluster similarities is because SSD\-FL aims to avoid wholesale D2D data sharing\. Instead, JSD enables SSD\-FL to measure devices’ differences in distribution, as relative frequency in labels can act as a proxy for empirical dataset distribution\. Simultaneously, EED on a randomly chosen subset of data𝒟^i\\hat\{\\mathcal\{D\}\}\_\{i\}and𝒟^j\\hat\{\\mathcal\{D\}\}\_\{j\}still enables a measure of the nominal differences between devices’ datasets, especially as it subtracts the internal gap in devices’ local datasets\. Next, to obtainαsd\\alpha^\{d\}\_\{s\}, we scaleβsd\\beta^\{d\}\_\{s\}linearly as in \([39](https://arxiv.org/html/2606.06687#S5.E39)\), obtaining

αsd=βsd​\(αd,max−αd,min\)\+αd,min\\alpha\_\{s\}^\{d\}=\\beta^\{d\}\_\{s\}\(\\alpha^\{d,\\max\}\-\\alpha^\{d,\\min\}\)\+\\alpha^\{d,\\min\}\(41\)whereαd,max\\alpha^\{d,\\max\}andαd,min\\alpha^\{d,\\min\}denote the max and min contributions to D2D data heterogeneity scaling inαsd\\alpha^\{d\}\_\{s\}, respectively\.

Algorithm 2Spectral Partitioning1:Input:Conductance threshold

ΦS^min\\Phi^\{\\min\}\_\{\\hat\{S\}\}and sorted clusters

𝑸=\{s\(1\),…,s\(\|𝒮\|\)\}\\bm\{Q\}=\\\{s^\{\(1\)\},\\dots,s^\{\(\|\\mathcal\{S\}\|\)\}\\\}\.

2:Output:Updated and partitioned cluster set

𝑸\\bm\{Q\}\.

3:forEach cluster

s∈𝑸s\\in\\bm\{Q\}do

4:Compute Fiedler eigenvector

ν2​\(s\)\\nu\_\{2\}\(s\)and obtain sorted indices

π=argsort​\(ν2​\(s\)\)\\pi=\\mathrm\{argsort\}\(\\nu\_\{2\}\(s\)\)\.

5:Initialize minimum conductance of possible partitions

Φ~Qmin←0\\tilde\{\\Phi\}^\{\\min\}\_\{Q\}\\leftarrow 0\.

6:forIndex

n=1n=1to

\|s\|\|s\|do

7:Define two candidate subsets:

sna=\{π​\(1\),…,π​\(n\)\}s^\{a\}\_\{n\}=\\\{\\pi\(1\),\\ldots,\\pi\(n\)\\\}and

snb=s∖snas^\{b\}\_\{n\}=s\\setminus s^\{a\}\_\{n\}\.

8:Compute minimum conductance:

Φn=min⁡\{Φ​\(G~sna\),Φ​\(G~snb\)\}\\Phi\_\{n\}=\\min\\\{\\Phi\(\\tilde\{G\}\_\{s^\{a\}\_\{n\}\}\),\\Phi\(\\tilde\{G\}\_\{s^\{b\}\_\{n\}\}\)\\\}\.

9:if

Φn\>Φ~Qmin\\Phi\_\{n\}\>\\tilde\{\\Phi\}^\{\\min\}\_\{Q\}then

10:Update minimum conductance of possible partitions,

Φ^S^min←Φn\\hat\{\\Phi\}^\{\\min\}\_\{\\hat\{S\}\}\\leftarrow\\Phi\_\{n\}\.

11:Update intermediary best candidate partition,

𝒫←\{sna,snb\}\\mathcal\{P\}\\leftarrow\\\{s^\{a\}\_\{n\},s^\{b\}\_\{n\}\\\}\.

12:endif

13:endfor

14:if

Φ^S^min≥ΦS^min\\hat\{\\Phi\}^\{\\min\}\_\{\\hat\{S\}\}\\geq\\Phi^\{\\min\}\_\{\\hat\{S\}\}then

15:Update cluster set:

𝑸←\(𝑸∖\{s\}\)∪𝒫\\bm\{Q\}\\leftarrow\(\\bm\{Q\}\\setminus\\\{s\\\}\)\\cup\\mathcal\{P\}\.

16:return

𝑸\\bm\{Q\}\.

17:elseif

Φ^S^min<ΦS^min\\hat\{\\Phi\}^\{\\min\}\_\{\\hat\{S\}\}<\\Phi^\{\\min\}\_\{\\hat\{S\}\}and

ssis

s\(1\)s^\{\(1\)\}then

18:Save the best candidate partition,

𝒫~←𝒫\\tilde\{\\mathcal\{P\}\}\\leftarrow\\mathcal\{P\}\.

19:endif

20:endfor

21:Update cluster set:

𝑸←\(𝑸∖\{s\(1\)\}\)∪𝒫~\\bm\{Q\}\\leftarrow\(\\bm\{Q\}\\setminus\\\{s^\{\(1\)\}\\\}\)\\cup\\tilde\{\\mathcal\{P\}\}\.

22:return

𝑸\\bm\{Q\}\.

### V\-CCombined cluster formation

At a high level, SSD\-FL’s cluster formation, summarized in Algorithm[1](https://arxiv.org/html/2606.06687#alg1), iteratively partitions the network based on spectral structure and expected ML model training convergence \(i\.e\., Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)\)\. Specifically, SSD\-FL iteratively increases the number of clusters\|S\|\|S\|from11toNN, the size of the network\. Starting with the original network graphG=\(𝒩,𝑨\)G=\(\\mathcal\{N\},\\bm\{A\}\), we denote the current partition of the network as𝒮^\\hat\{\\mathcal\{S\}\}, and thus start with𝒮^=\{G\}\\hat\{\\mathcal\{S\}\}=\\\{G\\\}\(and single cluster as\|𝒮^\|=1\|\\hat\{\\mathcal\{S\}\}\|=1\)\. SSD\-FL then computes the conductanceΦ​\(G~s\)\\Phi\(\\tilde\{G\}\_\{s\}\)of each subgraphs∈𝒮^s\\in\\hat\{\\mathcal\{S\}\}using \([2](https://arxiv.org/html/2606.06687#S3.E2)\), and simultaneously determines the minimum conductance thresholdΦSmin\\Phi^\{\\min\}\_\{S\}from the Cheeger\-based bound in \([37](https://arxiv.org/html/2606.06687#S5.E37)\)\.

For each iteration, SSD\-FL evaluates the current cluster set𝒮^\\hat\{\\mathcal\{S\}\}via Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)\(and theαs\\alpha\_\{s\}estimation process from Sec\.[V\-B](https://arxiv.org/html/2606.06687#S5.SS2)\) to obtain an average effective intra\-cluster first\-order stationary point, stored inℋ~\\tilde\{\\mathcal\{H\}\}\. Simultaneously, SSD\-FL ranks the clusters within the current cluster set, i\.e\.,s∈𝒮^s\\in\\hat\{\\mathcal\{S\}\}, in ascending order of their conductance, forming a sorted set𝒬=\{s\(1\),…,s\(\|𝒮^\|\)\}\\mathcal\{Q\}=\\\{s^\{\(1\)\},\\dots,s^\{\(\|\\hat\{\\mathcal\{S\}\}\|\)\}\\\}\. In this way, the least\-connected \(and hence most separable as well as weakest internal consensus\) clusters are examined first\. We next apply the spectral partitioning process, detailed in Algorithm[2](https://arxiv.org/html/2606.06687#alg2)\. In this process, each clusters∈𝒬s\\in\\mathcal\{Q\}, starting withs\(1\)s^\{\(1\)\}, is partitioned by analyzing the Fiedler eigenvectorν2​\(s\)\\nu\_\{2\}\(s\)of its normalized Laplacian matrix, which corresponds to𝐈s−𝐀~s\\mathbf\{I\}\_\{s\}\-\\tilde\{\\mathbf\{A\}\}\_\{s\}as a result of Assumption[3](https://arxiv.org/html/2606.06687#Thmassumption3)\. Within the Fiedler vectorν2​\(s\)\\nu\_\{2\}\(s\), devices with similar eigenvector values are more connected, while those with large gaps indicate weaker connectivity\[[6](https://arxiv.org/html/2606.06687#bib.bib56)\]\. SSD\-FL sweeps throughν2​\(s\)\\nu\_\{2\}\(s\), identifying the partition𝒫=\{sa,sb\}\\mathcal\{P\}=\\\{s^\{a\},s^\{b\}\\\}ofsswith the largest minimum conductance\. If partition𝒫\\mathcal\{P\}has conductance over thresholdΦSmin\\Phi^\{\\min\}\_\{S\}, then the set𝒬\\mathcal\{Q\}is updated as𝒬=\(𝒮^∖\{s\}\)∪\{sa,sb\}\\mathcal\{Q\}=\(\\hat\{\\mathcal\{S\}\}\\setminus\\\{s\\\}\)\\cup\\\{s^\{a\},s^\{b\}\\\}\. Otherwise, SSD\-FL proceeds to the next smallest conductance clusters\(n\)s^\{\(n\)\}in𝒬\\mathcal\{Q\}\. However, if no partition satisfies the threshold, then the original cluster with the smallest conductance, i\.e\.,s\(1\)s^\{\(1\)\}, will be partitioned following the above rules\. This post\-partition cluster candidate is then stored as the new𝒮^\\hat\{\\mathcal\{S\}\}and in the candidate set𝒮~\\tilde\{\\mathcal\{S\}\}\.

SSD\-FL continues the above process iteratively, until\|𝒮^\|=N\|\\hat\{\\mathcal\{S\}\}\|=N, or, in other words, there is a candidate partition of every feasible size for a network withNNdevices\. Among these possible partitions𝒮∈𝒮~\\mathcal\{S\}\\in\\tilde\{\\mathcal\{S\}\}, SSD\-FL determines𝒮∗=arg⁡min𝒮∈𝒮~⁡ℋ~​s\.t\.​Φ​\(𝒮\)≥ΦSmin\\mathcal\{S\}^\{\*\}=\\arg\\min\_\{\\mathcal\{S\}\\in\\tilde\{\\mathcal\{S\}\}\}\\tilde\{\\mathcal\{H\}\}\\text\{ s\.t\. \}\\Phi\(\\mathcal\{S\}\)\\geq\\Phi^\{\\min\}\_\{S\}\. As such,𝒮∗\\mathcal\{S\}^\{\*\}corresponds to the set of clusters that \(i\) maintains sufficient intra\-cluster connectivity and \(ii\) yields the lowest average effective first\-order gradient\. Therefore, SSD\-FL’s cluster formation is based on both graph topology and estimated ML performance\.

## VIExperimental Evaluation

In the following, we evaluate the performance of the proposed SSD\-FL methodology across four dimensions, organized to highlight its core advantages, progressively\. To this end, we present the experimental setup in Sec\.[VI\-A](https://arxiv.org/html/2606.06687#S6.SS1)\. Then, we first examine the impact of inter\-cluster periodτr\\tau\_\{r\}in Sec\.[VI\-C](https://arxiv.org/html/2606.06687#S6.SS3)and intra\-cluster periodτa\\tau\_\{a\}in Sec\.[VI\-B](https://arxiv.org/html/2606.06687#S6.SS2), as these results most directly demonstrate the impact of careful and deliberate cluster formation, which is our central contribution\. Subsequently, we evaluate the scalability of SSD\-FL relative to baselines via varying network size in Sec\.[VI\-D](https://arxiv.org/html/2606.06687#S6.SS4), before concluding with performance across various network graph architectures in Sec\.[VI\-E](https://arxiv.org/html/2606.06687#S6.SS5)in order to establish SSD\-FL’s general robustness\. These experiments are performed for with and without heterogeneous optimizers, though the homogeneous SGD optimizer experiments are left to Appendix[G](https://arxiv.org/html/2606.06687#A7)for conciseness\. Similarly, additional experiments on link formation probabilities and on SSD\-FL’s intra\-cluster convergence bound are also available in Appendix[G](https://arxiv.org/html/2606.06687#A7)\.

![Refer to caption](https://arxiv.org/html/2606.06687v1/x2.png)Figure 2:Varying intra\-cluster periodτa\\tau\_\{a\}for FMNIST\. SSD\-FL’s advantage over baselines grows withτa\\tau\_\{a\}, and remains consistent across both mild and extreme heterogeneity settings\.### VI\-AExperimental setup

The experiments are performed on FMNIST\[[48](https://arxiv.org/html/2606.06687#bib.bib50)\]and CIFAR10\[[16](https://arxiv.org/html/2606.06687#bib.bib51)\], with their respective training datasets of size6000060000and5000050000samples evenly partitioned across the network devices\. The exact partition depends on the notion of data heterogeneity across the network, and, here, we consider mild and extreme non\-i\.i\.d\. scenarios, which correspond to cases where each device has data drawn from33or11label of the full dataset\. Moreover, as experiments involve heterogeneous ML optimizers at devices, we randomly assign each device an optimizer and, for proximal and momentum optimizers, we further assign a proximal parameterμi\\mu\_\{i\}drawn uniformly at random from\{5×10−5,1×10−4\}\\\{5\\times 10^\{\-5\},1\\times 10^\{\-4\}\\\}or a momentum parameterρi\\rho\_\{i\}drawn uniformly at random from\{0\.8,0\.85\}\\\{0\.8,0\.85\\\}\. Finally, the ML models used are five layer CNNs, with output channel dimension3232,6464,128128,128128, and256256sequentially, followed by a single linear layer\. These more traditional neural networks are used because our goal is primarily the proof\-of\-concept of SSD\-FL for further exploration of clustering \(and network structure manipulation more generally\) in decentralized FL settings and, as such, obtaining state\-of\-the\-art \(SOTA\) or near SOTA accuracies are not our intention\.

Unless otherwise stated, the underlying networks are based on Erdős–Rényi random graphs\[[9](https://arxiv.org/html/2606.06687#bib.bib52)\]with link formation probability10%10\\%and size3030devices\. Additionally, all experiments are run for2020total global cycles, with intra\-cluster periodτa=3\\tau\_\{a\}=3and inter\-cluster period ofτr=1\\tau\_\{r\}=1\. For all experiments, networks’ adjacency matrices, including the inter\-cluster and intra\-cluster graph matrices𝑨\\bm\{A\}and𝑨~\\tilde\{\\bm\{A\}\}, are based off of Metropolis\-Hastings weights\[[49](https://arxiv.org/html/2606.06687#bib.bib15)\]\. To contextualize performance, we examine SSD\-FL relative to four classes of baseline decentralized FL methodologies: \(i\) synchronous \(sDFL\)\[[21](https://arxiv.org/html/2606.06687#bib.bib13)\], \(ii\) periodic \(pDFL\)\[[32](https://arxiv.org/html/2606.06687#bib.bib32)\], \(iii\) stochastic \(STC\)\[[15](https://arxiv.org/html/2606.06687#bib.bib36)\], and \(iv\) clustered stochastic \(cSTC\), which determines the total number of clusters randomly and thereafter follows stochastic\[[15](https://arxiv.org/html/2606.06687#bib.bib36)\]\. Moreover, for fairness, these baseline decentralized FL methodologies will have dedicated training rounds and additional D2D network communications adhering toτa\\tau\_\{a\}andτr\\tau\_\{r\}respectively\. Finally, regarding SSD\-FL’s cluster formation parameters, we useΔS𝗍𝗈𝗅=10\\Delta^\{\\mathsf\{tol\}\}\_\{S\}=10forS∈\{1,⋯,N\}S\\in\\\{1,\\cdots,N\\\}, andα=0\.1\\alpha=0\.1\. To deriveαs\\alpha\_\{s\}, we use an equal weighting in \([38](https://arxiv.org/html/2606.06687#S5.E38)\) withζ1\\zeta\_\{1\},ζ2\\zeta\_\{2\}, andζ3=1\\zeta\_\{3\}=1, while, for the min\-max scalings in \([39](https://arxiv.org/html/2606.06687#S5.E39)\) and \([41](https://arxiv.org/html/2606.06687#S5.E41)\), we useαo,max=0\.2\\alpha^\{o,\\max\}=0\.2andαo,min=0\\alpha^\{o,\\min\}=0as well asαd,max=0\.2\\alpha^\{d,\\max\}=0\.2andαd,min=0\\alpha^\{d,\\min\}=0, respectively\.

![Refer to caption](https://arxiv.org/html/2606.06687v1/x3.png)Figure 3:Varying intra\-cluster periodτa\\tau\_\{a\}for CIFAR10\. The performance gap between SSD\-FL and baselines is more pronounced under extreme heterogeneity\.Table I:Examining the average global cycles needed to reach various accuracy threshold on FMNIST and for networks with heterogeneous ML optimizers at devices\. SSD\-FL’s advantage accumulates for higher accuracy thresholds\. Dashes indicate thresholds that were not reached\.Table II:Average global cycles that decentralized FL methodologies need to reach or exceed accuracy thresholds on CIFAR10 when devices employ heterogeneous ML optimizers\. SSD\-FL, similar to the case in Table[I](https://arxiv.org/html/2606.06687#S6.T1), continues to demonstrate faster convergence for higher thresholds\.
### VI\-BIntra\-cluster durationτa\\tau\_\{a\}

First, we examine the impact of intra\-cluster periodτa\\tau\_\{a\}on SSD\-FL and the various decentralized FL baselines in Fig\.[2](https://arxiv.org/html/2606.06687#S6.F2)\-[3](https://arxiv.org/html/2606.06687#S6.F3), withτr=1\\tau\_\{r\}=1to isolate the effects ofτa\\tau\_\{a\}and a network ofN=10N=10devices\. The intra\-cluster period enables us to assess whether cluster formation offers value, specifically as longer local training periods within clusters \(i\.e\., largerτa\\tau\_\{a\}\) should benefit methods with more careful and deliberate cluster formation, while highlighting the drift and instability that result from random or no clustering\.

This intuition is confirmed across both datasets and heterogeneity levels\. Atτa\\tau\_\{a\}= 1, all methods perform comparably, with SSD\-FL holding only a modest edge over the best baseline\. However, asτa\\tau\_\{a\}grows larger, SSD\-FL pulls progressively further ahead\. For example whenτa=5\\tau\_\{a\}=5in extreme non\-i\.i\.d\. scenarios, SSD\-FL leads the best baseline STC by roughly4%4\\%on FMNIST \(46%46\\%vs42%42\\%\) and roughly2%2\\%on CIFAR10 \(35%35\\%vs33%33\\%\), with the separation visible not just in final accuracy but throughout the convergence trajectory\. The fact that this gap emerges and widens withτa\\tau\_\{a\}rather than remaining constant suggests that SSD\-FL’s cluster formation is translating longer intra\-cluster training periods into more useful model updates than the baselines\.

Beyond final accuracies, SSD\-FL also offers notably smoother and faster convergence curves relative to STC and cSTC across both datasets\. Unlike STC and cSTC, both of which exhibit more erratic/noisy convergence behavior, SSD\-FL converges steadily throughout, reflecting the intra\-cluster stability induced by Algorithm[1](https://arxiv.org/html/2606.06687#alg1)\. Moreover, while sDFL and pDFL do offer smooth convergence curves, their accuracies are far lower than those obtained by SSD\-FL, for example by roughly9%9\\%and4%4\\%on FMNIST and CIFAR10 in extreme non\-i\.i\.d\. settings atτa=5\\tau\_\{a\}=5\. Taken together, these points suggest that SSD\-FL, via careful cluster formation, is able to effectively lead to intra\-cluster stability \(i\.e\., reduced intra\-cluster differences\), which in turn produces more useful local ML model updates and easier inter\-cluster propagation across global rounds\.

### VI\-CInter\-cluster periodτr\\tau\_\{r\}

Next, we examine the impact of inter\-cluster periodτr\\tau\_\{r\}on convergence speed in Tables[I](https://arxiv.org/html/2606.06687#S6.T1)and[II](https://arxiv.org/html/2606.06687#S6.T2), by measuring the average number of global cycles needed to reach various accuracy thresholds on random graphs withN=10N=10devices andτa=1\\tau\_\{a\}=1\. Rather than final accuracy alone, convergence speed highlights the practical importance of both communication efficiency and training effectiveness, especially in large\-scale edge/fog networks\. Moreover, these experiments also examine the impact of changingτr∈\[1,3,5\]\\tau\_\{r\}\\in\[1,3,5\], though the tables forτr=1\\tau\_\{r\}=1are left to Appendix[G](https://arxiv.org/html/2606.06687#A7)as their takeaways are similar to those in Tables[I](https://arxiv.org/html/2606.06687#S6.T1)and[II](https://arxiv.org/html/2606.06687#S6.T2)\.

For FMNIST in Table[I](https://arxiv.org/html/2606.06687#S6.T1), we see that SSD\-FL nearly always requires fewer global rounds to reach the accuracy thresholds than the decentralized FL baselines\. Moreover, the gap in global rounds needed between SSD\-FL and the baselines increases with higher accuracy thresholds\. On FMNIST under mild non\-i\.i\.d\. withτr=3\\tau\_\{r\}=3, SSD\-FL requires12%12\\%fewer global rounds than the best performing baseline pDFL to reach65%65\\%accuracy \(6\.566\.56vs7\.517\.51\), a gap that widens to15%15\\%saving fewer rounds at72%72\\%accuracy \(11\.7511\.75vs13\.8013\.80\)\. Meanwhile, under extreme non\-i\.i\.d\. settings withτr=3\\tau\_\{r\}=3, SSD\-FL’s advantage becomes more pronounced, requiring18%18\\%fewer rounds than pDFL to reach40%40\\%accuracy \(8\.988\.98vs11\.0111\.01\), and, alongside cSTC, is the only one of two methods to reach the45%45\\%threshold\. Similarly, these trends continue to hold on CIFAR10 withτr=3\\tau\_\{r\}=3in Table[II](https://arxiv.org/html/2606.06687#S6.T2)\. Under mild non\-i\.i\.d\. settings, SSD\-FL reaches72%72\\%accuracy in17\.7317\.73rounds vs18\.6418\.64for the best performing baseline sDFL\. These savings become more pronounced in extreme non\-i\.i\.d\. settings, where SSD\-FL requires14%14\\%fewer rounds than pDFL \(best performing baseline\) to reach40%40\\%accuracy \(11\.2111\.21vs12\.6012\.60\)\.

Asτr\\tau\_\{r\}increases to55, the absolute gap between SSD\-FL and the best performing baselines become smaller\. For example, on FMNIST and mild non\-i\.i\.d\. settings, SSD\-FL’s lead over pDFL at72%72\\%accuracy decreases from2\.052\.05to0\.670\.67global rounds\. This is expected, however, as largerτr\\tau\_\{r\}means more inter\-cluster synchronization steps, which gives all methods more opportunities for global synchronization\.

While these previous experiments established SSD\-FL’s advantages in terms of controllable training hyper\-parameters, we next evaluate its adaptability to various fixed network properties, such as network size, architecture, and link formation probabilities \(in Appendix[G\-A](https://arxiv.org/html/2606.06687#A7.SS1)\), which are defined by the network environments rather than something controlled by network operators\.

### VI\-DNetwork size

We next examine the impact of network size fromN=10N=10toN=50N=50for random graphs using both FMNIST in Fig\.[4](https://arxiv.org/html/2606.06687#S6.F4), and CIFAR10 in Fig\.[5](https://arxiv.org/html/2606.06687#S6.F5)\. This experiment assesses the scalability benefits offered by SSD\-FL, specifically that careful and deliberate cluster formation yields consistent advantages as edge/fog networks grow larger\.

![Refer to caption](https://arxiv.org/html/2606.06687v1/x4.png)Figure 4:Varying network size fromN=10N=10to5050with Erdős–Rényi random graphs on FMNIST\. SSD\-FL consistently yields better or equal performance relative to decentralized FL baselines\.Across both datasets and heterogeneity levels, SSD\-FL consistently outperforms all baselines and maintains a stable performance gap as networks grow in size\. While these gains appears modest, this stable final accuracy advantage across network sizes compounds with the results from Sec\.[VI\-B](https://arxiv.org/html/2606.06687#S6.SS2)and[VI\-C](https://arxiv.org/html/2606.06687#S6.SS3), the latter of which demonstratesmuchfaster convergence in settings with the more practically relevant case ofτr\>1\\tau\_\{r\}\>1\. Thus, SSD\-FL allows network operators to save on communication rounds while achieving higher final accuracies relative to existing methodologies in larger edge/fog settings\.

Among the baselines, cSTC is the only one that also employs clustering, making it a particularly valuable point of comparison\. While it starts comparably to SSD\-FL atN=10N=10in the mild non\-i\.i\.d\. scenario of Fig\.[4](https://arxiv.org/html/2606.06687#S6.F4)\(both near74\.5%74\.5\\%\), its performance stalls asNNgrows, falling roughly7%7\\%behind SSD\-FL byN=50N=50\(73%73\\%vs80%80\\%\)\. In extreme non\-i\.i\.d\. settings, this gap grows, with cSTC trailing SSD\-FL by approximately10%10\\%on FMNIST and4%4\\%on CIFAR10 atN=50N=50\. This shows that careless or random cluster formation can actually compound the difficulties of large\-scale decentralized FL rather than helping them\. By contrast, SSD\-FL’s stable scaling behavior shows that principled cluster formation \(per Algorithm[1](https://arxiv.org/html/2606.06687#alg1)\) offers value in larger and more complex network graphs\. Interestingly, when networks employ homogeneous SGD optimizers at devices, cSTC performs at a comparable level to the STC baseline, with further details provided in Appendix[G](https://arxiv.org/html/2606.06687#A7)\.

![Refer to caption](https://arxiv.org/html/2606.06687v1/x5.png)Figure 5:Varying network size fromN=10N=10to5050with Erdős–Rényi random graphs on CIFAR10\. SSD\-FL maintains a consistent performance gap across various network sizes\.
### VI\-EGlobal network architectures

We compare SSD\-FL with these decentralized FL baselines over multiple global network architectures, each with a unique underlying rule guiding its set of D2D links\. In particular, we evaluate over \(i\) Erdős–Rényi random graph \(RNG\)\[[9](https://arxiv.org/html/2606.06687#bib.bib52)\], in which any two devicesi,j∈𝒩i,j\\in\\mathcal\{N\}have a fixed probability,10%10\\%, to have link between them, \(ii\) Barabási–Albert preferential attachment \(PrefA\)\[[2](https://arxiv.org/html/2606.06687#bib.bib53)\], where we set each device to iteratively connect to one other devices with probability proportional to their current degree, \(iii\) random geometric graph \(RGeo\)\[[26](https://arxiv.org/html/2606.06687#bib.bib55)\], where devices are placed uniformly at random in a unit\-sized Euclidean space and links are established between those within a0\.20\.2radius, \(iv\) Watts\-Strogatz small world\[[46](https://arxiv.org/html/2606.06687#bib.bib54)\], for which we choose to have each device with33links to neighboring devices and a20%20\\%chance to reconnect these links randomly, and \(iv\) complete graphs \(Comp\)\[[7](https://arxiv.org/html/2606.06687#bib.bib60)\], in which all devicesi∈𝒩i\\in\\mathcal\{N\}are connected\.

![Refer to caption](https://arxiv.org/html/2606.06687v1/x6.png)Figure 6:Evaluation of decentralized FL baselines for various network architectures on FMNIST\. SSD\-FL yields the best performances with the exception of complete networks, for which it identifies a single cluster as optimal, reducing to sDFL\.![Refer to caption](https://arxiv.org/html/2606.06687v1/x7.png)Figure 7:Evaluation of decentralized FL baselines for various network architectures on CIFAR10\. Results mirror the FMNIST findings in Fig\.[6](https://arxiv.org/html/2606.06687#S6.F6), including the special case of complete networks\.Across all non\-trivial topologies, SSD\-FL consistently outperforms the baselines on both FMNIST in Fig\.[6](https://arxiv.org/html/2606.06687#S6.F6)and CIFAR10 in Fig\.[7](https://arxiv.org/html/2606.06687#S6.F7)\. The advantages are most pronounced on preferential attachment and small world graphs, where SSD\-FL leads the best performing baseline STC by roughly7%7\\%on FMNIST in mild non\-i\.i\.d\. settings \(73\.5%73\.5\\%vs67\.7%67\.7\\%on PrefA\), and, similarly, by roughly7%7\\%in extreme non\-i\.i\.d\. scenarios \(44\.8%44\.8\\%vs37\.6%37\.6\\%on PrefA\)\. Meanwhile, on random graphs, SSD\-FL maintains a more modest but consistent advantage of roughly3%3\\%over STC under mild non\-i\.i\.d\. \(81\.1%81\.1\\%vs78\.2%78\.2\\%\), with a larger gap of roughly2%2\\%under extreme non\-i\.i\.d\. \(52\.5%52\.5\\%vs50\.6%50\.6\\%\)\. Since these takeaways on FMNIST are similar to those for CIFAR10 in Fig\.[7](https://arxiv.org/html/2606.06687#S6.F7), these results collectively suggest that SSD\-FL’s cluster formation is able to exploit the underlying structure of diverse network topologies, yielding consistent improvements regardless of how the deployment network is formed\.

For the special case of complete graphs, SSD\-FL and sDFL achieve near identical performance on both datasets and heterogeneity levels \(88\.3%88\.3\\%vs88\.2%88\.2\\%on FMNIST mild non\-i\.i\.d\.,80\.9%80\.9\\%vs81\.0%81\.0\\%on FMNIST extreme non\-i\.i\.d\.\), with SSD\-FL forming a single cluster as Algorithm[1](https://arxiv.org/html/2606.06687#alg1)correctly identifies that partitioning is unnecessary\. In sparse networks, clustering trades global connectivity for local density, accelerating intra\-cluster convergence enough to justify the reduction in active links\. In a complete graph however, this trade\-off breaks down as the network is already maximally connected, and so partitioning offers no local convergence benefit while incurring consensus delays/costs\. Rather than being a limitation, this result highlights that SSD\-FL demonstrates nuance in its cluster formation by clustering only when helpful\.

## VIIConclusion

In this paper, we have introduced SSD\-FL, a serverless, semi\-decentralized framework for FL, bridging the gap among centralized, semi\-decentralized, and decentralized FL\. To do so, our methodology introduces intra\-cluster and inter\-cluster regimes, which together form global rounds, and subsequently showed the convergence and consensus properties for such a framework with general clusters\. Thereafter, we leveraged these theoretical bounds to optimize cluster formation via spectral properties of the network\. Meanwhile, experiments across various graph topologies as well as different levels of device data and ML optimizer heterogeneity showed that SSD\-FL would consistently outperform baseline decentralized FL methodologies\. Future work can explore time\-varying clusters and theoretical extensions for directed topologies, in which asymmetric D2D communications can further complicate convergence, consensus, and overall decision making\.

## References

- \[1\]\(2025\)Sdflmq: a semi\-decentralized federated learning framework over mqtt\.InProceedings of the 2025 IEEE International Parallel and Distributed Processing Symposium Workshops,pp\. 1100–1107\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p2.1),[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p1.1),[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p3.1)\.
- \[2\]A\. Barabási and R\. Albert\(1999\)Emergence of scaling in random networks\.Science286\(5439\),pp\. 509–512\.Cited by:[§VI\-E](https://arxiv.org/html/2606.06687#S6.SS5.p1.6)\.
- \[3\]M\. Bornstein, T\. Rabbani, E\. Z\. Wang, A\. Bedi, and F\. Huang\(2023\)SWIFT: rapid decentralized federated learning via wait\-free model communication\.InProceedings of the Eleventh International Conference on Learning Representations,pp\. 1–30\.Cited by:[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p2.1)\.
- \[4\]Z\. Chen, W\. Chen, J\. Li, Q\. Wu, M\. Ding, X\. Han, X\. Deng, and L\. Wang\(2025\)Hierarchical federated learning for social network with mobility\.IEEE Transactions on Cognitive Communications and Networking\.Note:to appearCited by:[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p2.1)\.
- \[5\]S\. Chewi, S\. Bubeck, and A\. Salim\(2023\)On the complexity of finding stationary points of smooth functions in one dimension\.InProceedings of the 34th International Conference on Algorithmic Learning Theory,pp\. 358–374\.Cited by:[§III\-B](https://arxiv.org/html/2606.06687#S3.SS2.p1.22)\.
- \[6\]F\. R\. K\. Chung\(1997\)Spectral graph theory\.CBMS Regional Conference Series in Mathematics, Vol\.92,American Mathematical Society,Providence, RI\.External Links:ISBN 978\-0\-8218\-0315\-8Cited by:[§V\-A](https://arxiv.org/html/2606.06687#S5.SS1.p1.13),[§V\-C](https://arxiv.org/html/2606.06687#S5.SS3.p2.22)\.
- \[7\]P\. Erdős\(1947\)Some remarks on the theory of graphs\.Bulletin of the American Mathematical Society53\(4\),pp\. 292–294\.Cited by:[§VI\-E](https://arxiv.org/html/2606.06687#S6.SS5.p1.6)\.
- \[8\]B\. Fuglede and F\. Topsøe\(2004\)Jensen–shannon divergence and hilbert space embedding\.InProceedings of the 2004 IEEE International Symposium on Information Theory,pp\. 31\.External Links:[Document](https://dx.doi.org/10.1109/ISIT.2004.1365067)Cited by:[§V\-B](https://arxiv.org/html/2606.06687#S5.SS2.p2.14)\.
- \[9\]E\. N\. Gilbert\(1959\)Random graphs\.The Annals of Mathematical Statistics30\(4\),pp\. 1141–1144\.Cited by:[Appendix G](https://arxiv.org/html/2606.06687#A7.p1.1),[§VI\-A](https://arxiv.org/html/2606.06687#S6.SS1.p2.20),[§VI\-E](https://arxiv.org/html/2606.06687#S6.SS5.p1.6)\.
- \[10\]B\. Gong, T\. Xing, Z\. Liu, W\. Xi, and X\. Chen\(2023\)Towards hierarchical clustered federated learning with model stability on mobile devices\.IEEE Transactions on Mobile Computing23\(6\),pp\. 7148–7164\.Cited by:[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p3.1)\.
- \[11\]M\. S\. HaghighiFard and S\. Coleri\(2025\)Hierarchical federated learning in multi\-hop cluster\-based vanets\.IEEE Transactions on Vehicular Technology\.Note:to appearCited by:[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p2.1)\.
- \[12\]E\. Hallaji, R\. Razavi\-Far, M\. Saif, B\. Wang, and Q\. Yang\(2024\)Decentralized federated learning: a survey on security and privacy\.IEEE Transactions on Big Data10\(2\),pp\. 194–213\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p1.1)\.
- \[13\]A\. Hashemi, A\. Acharya, R\. Das, H\. Vikalo, S\. Sanghavi, and I\. Dhillon\(2021\)On the benefits of multiple gossip steps in communication\-constrained decentralized federated learning\.IEEE Transactions on Parallel and Distributed Systems33\(11\),pp\. 2727–2739\.Cited by:[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p2.1)\.
- \[14\]Z\. Jiang, A\. Balu, C\. Hegde, and S\. Sarkar\(2017\)Collaborative deep learning in fixed topology networks\.Advances in Neural Information Processing Systems30,pp\. 3322–3330\.Cited by:[§III\-A](https://arxiv.org/html/2606.06687#S3.SS1.p3.12),[§III\-B](https://arxiv.org/html/2606.06687#S3.SS2.p1.22)\.
- \[15\]A\. Koloskova, N\. Loizou, S\. Boreiri, M\. Jaggi, and S\. Stich\(2020\)A unified theory of decentralized sgd with changing topology and local updates\.InProceedings of the 2020 International conference on machine learning,pp\. 5381–5393\.Cited by:[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p1.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p2.1),[§VI\-A](https://arxiv.org/html/2606.06687#S6.SS1.p2.20)\.
- \[16\]A\. Krizhevsky\(2009\)Learning multiple layers of features from tiny images\.Technical reportUniversity of Toronto\.Note:Technical ReportCited by:[§VI\-A](https://arxiv.org/html/2606.06687#S6.SS1.p1.13)\.
- \[17\]Q\. Li and D\. Chen\(2023\)Peer to peer distributed solar energy trading\.ACM SIGMETRICS Performance Evaluation Review50\(4\),pp\. 44–46\.Cited by:[1st item](https://arxiv.org/html/2606.06687#S1.I1.i1.p1.1)\.
- \[18\]F\. P\. Lin, S\. Hosseinalipour, S\. S\. Azam, C\. G\. Brinton, and N\. Michelusi\(2021\)Semi\-decentralized federated learning with cooperative d2d local model aggregations\.IEEE Journal on Selected Areas in Communications39\(12\),pp\. 3851–3869\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p2.1),[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p1.1),[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p3.1)\.
- \[19\]J\. Liu, J\. Yan, H\. Xu, L\. Wang, Z\. Wang, J\. Huang, and C\. Qiao\(2025\)Accelerating decentralized federated learning with probabilistic communication in heterogeneous edge computing\.IEEE Transactions on Networking\.Note:to appearCited by:[§I](https://arxiv.org/html/2606.06687#S1.p3.1)\.
- \[20\]L\. Liu, J\. Zhang, S\. Song, and K\. B\. Letaief\(2022\)Hierarchical federated learning with quantization: convergence analysis and system design\.IEEE Transactions on Wireless Communications22\(1\),pp\. 2–18\.Cited by:[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p2.1)\.
- \[21\]W\. Liu, L\. Chen, and W\. Zhang\(2022\)Decentralized federated learning: balancing communication and computing costs\.IEEE Transactions on Signal and Information Processing over Networks8,pp\. 131–143\.Cited by:[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p2.1),[§VI\-A](https://arxiv.org/html/2606.06687#S6.SS1.p2.20)\.
- \[22\]A\. Nedić and A\. Olshevsky\(2014\)Distributed optimization over time\-varying directed graphs\.IEEE Transactions on Automatic Control60\(3\),pp\. 601–615\.Cited by:[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1)\.
- \[23\]A\. Nedic and A\. Ozdaglar\(2009\)Distributed subgradient methods for multi\-agent optimization\.IEEE Transactions on Automatic Control54\(1\),pp\. 48–61\.Cited by:[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1)\.
- \[24\]D\. T\. A\. Nguyen, S\. Wang, D\. T\. Nguyen, A\. Nedich, and H\. V\. Poor\(2024\)Decentralized federated learning with gradient tracking over time\-varying directed networks\.arXiv:2409\.17189\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p3.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p2.1),[§III\-A](https://arxiv.org/html/2606.06687#S3.SS1.p3.12)\.
- \[25\]J\. Pei, W\. Liu, J\. Li, L\. Wang, and C\. Liu\(2024\)A review of federated learning methods in heterogeneous scenarios\.IEEE Transactions on Consumer Electronics70\(3\),pp\. 5983–5999\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p1.1)\.
- \[26\]M\. D\. Penrose\(2003\)Random geometric graphs\.Oxford Studies in Probability, Vol\.5,Oxford University Press,Oxford, UK\.External Links:ISBN 978\-0\-19\-850626\-3Cited by:[§VI\-E](https://arxiv.org/html/2606.06687#S6.SS5.p1.6)\.
- \[27\]S\. U\. Pillai, T\. Suel, and S\. Cha\(2005\)The perron\-frobenius theorem: some of its applications\.IEEE Signal Processing Magazine22\(2\),pp\. 62–75\.Cited by:[§III\-C](https://arxiv.org/html/2606.06687#S3.SS3.p3.9)\.
- \[28\]N\. Pogkas, G\. Karastergios, C\. Antonopoulos, S\. Koubias, and G\. Papadopoulos\(2005\)An ad\-hoc sensor network for disaster relief operations\.InProceedings of the 2005 IEEE Conference on Emerging Technologies and Factory Automation,pp\. 131–139\.Cited by:[2nd item](https://arxiv.org/html/2606.06687#S1.I1.i2.p1.1)\.
- \[29\]L\. P\. Qian, H\. Zhang, Q\. Wang, Y\. Wu, and B\. Lin\(2022\)Joint multi\-domain resource allocation and trajectory optimization in uav\-assisted maritime iot networks\.IEEE Internet of Things Journal10\(1\),pp\. 539–552\.Cited by:[2nd item](https://arxiv.org/html/2606.06687#S1.I1.i2.p1.1)\.
- \[30\]M\. L\. Rizzo and G\. J\. Székely\(2016\)Energy distance\.Wiley Interdisciplinary Reviews: Computational Statistics8\(1\),pp\. 27–38\.External Links:[Document](https://dx.doi.org/10.1002/wics.1375)Cited by:[§V\-B](https://arxiv.org/html/2606.06687#S5.SS2.p2.14),[§V\-B](https://arxiv.org/html/2606.06687#S5.SS2.p2.27)\.
- \[31\]W\. Shi, Q\. Ling, G\. Wu, and W\. Yin\(2015\)Extra: an exact first\-order algorithm for decentralized consensus optimization\.SIAM Journal on Optimization25\(2\),pp\. 944–966\.Cited by:[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p2.1)\.
- \[32\]T\. Sun, D\. Li, and B\. Wang\(2022\)Decentralized federated averaging\.IEEE Transactions on Pattern Analysis and Machine Intelligence45\(4\),pp\. 4289–4301\.Cited by:[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p1.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p2.1),[§VI\-A](https://arxiv.org/html/2606.06687#S6.SS1.p2.20)\.
- \[33\]Y\. Sun, J\. Shao, Y\. Mao, J\. H\. Wang, and J\. Zhang\(2022\)Semi\-decentralized federated edge learning for fast convergence on non\-iid data\.InProceedings of the 2022 IEEE Wireless Communications and Networking Conference \(WCNC\),pp\. 1898–1903\.Cited by:[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p3.1)\.
- \[34\]I\. Sutskever, J\. Martens, G\. Dahl, and G\. Hinton\(2013\)On the importance of initialization and momentum in deep learning\.InProceedings of the 30th International Conference on Machine Learning,pp\. 1139–1147\.Cited by:[3rd item](https://arxiv.org/html/2606.06687#S3.I1.i3.p1.1)\.
- \[35\]H\. Taheri, A\. Mokhtari, H\. Hassani, and R\. Pedarsani\(2020\)Quantized decentralized stochastic learning over directed graphs\.InProceedings of the 2020 International Conference on Machine Learning,pp\. 9324–9333\.Cited by:[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1)\.
- \[36\]Z\. Tang, S\. Shi, B\. Li, and X\. Chu\(2022\)GossipFL: a decentralized federated learning framework with sparsified and adaptive communication\.IEEE Transactions on Parallel and Distributed Systems34\(3\),pp\. 909–922\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p3.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1)\.
- \[37\]W\. Tushar, T\. K\. Saha, C\. Yuen, D\. Smith, and H\. V\. Poor\(2020\)Peer\-to\-peer trading in electricity networks: an overview\.IEEE Transactions on Smart Grid11\(4\),pp\. 3185–3200\.Cited by:[1st item](https://arxiv.org/html/2606.06687#S1.I1.i1.p1.1)\.
- \[38\]J\. Wang, Q\. Liu, H\. Liang, G\. Joshi, and H\. V\. Poor\(2021\)A novel framework for the analysis and design of heterogeneous federated learning\.IEEE Transactions on Signal Processing69,pp\. 5234–5249\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p3.1)\.
- \[39\]J\. Wang, A\. K\. Sahu, G\. Joshi, and S\. Kar\(2022\)Matcha: a matching\-based link scheduling strategy to speed up distributed optimization\.IEEE Transactions on Signal Processing70,pp\. 5208–5221\.Cited by:[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1)\.
- \[40\]S\. Wang, T\. Tuor, T\. Salonidis, K\. K\. Leung, C\. Makaya, T\. He, and K\. Chan\(2019\)Adaptive federated learning in resource constrained edge computing systems\.IEEE Journal on Selected Areas in Communications37\(6\),pp\. 1205–1221\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p1.1)\.
- \[41\]S\. Wang, S\. Hosseinalipour, V\. Aggarwal, C\. G\. Brinton, D\. J\. Love, W\. Su, and M\. Chiang\(2023\)Toward cooperative federated learning over heterogeneous edge/fog networks\.IEEE Communications Magazine61\(12\),pp\. 54–60\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p1.1),[§I](https://arxiv.org/html/2606.06687#S1.p3.1)\.
- \[42\]S\. Wang, S\. Hosseinalipour, M\. Gorlatova, C\. G\. Brinton, and M\. Chiang\(2022\)UAV\-assisted online machine learning over multi\-tiered networks: a hierarchical nested personalized federated learning approach\.IEEE Transactions on Network and Service Management20\(2\),pp\. 1847–1865\.Cited by:[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p2.1)\.
- \[43\]S\. Wang, R\. Morabito, S\. Hosseinalipour, M\. Chiang, and C\. G\. Brinton\(2024\)Device sampling and resource optimization for federated learning in cooperative edge networks\.IEEE/ACM Transactions on Networking32\(5\),pp\. 4365 – 4381\.External Links:[Document](https://dx.doi.org/10.1109/TNET.2024.3423673)Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p1.1)\.
- \[44\]X\. Wang and Y\. Lu\(2024\)Information\-centric robotic ad hoc networking based continuous data routing and delivery for disaster scenes\.IEEE Transactions on Green Communications and Networking9\(3\),pp\. 768–777\.Cited by:[2nd item](https://arxiv.org/html/2606.06687#S1.I1.i2.p1.1)\.
- \[45\]Z\. Wang, H\. Xu, J\. Liu, Y\. Xu, H\. Huang, and Y\. Zhao\(2022\)Accelerating federated learning with cluster construction and hierarchical aggregation\.IEEE Transactions on Mobile Computing22\(7\),pp\. 3805–3822\.Cited by:[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p3.1)\.
- \[46\]D\. J\. Watts and S\. H\. Strogatz\(1998\)Collective dynamics of ‘small\-world’networks\.Nature393\(6684\),pp\. 440–442\.Cited by:[§VI\-E](https://arxiv.org/html/2606.06687#S6.SS5.p1.6)\.
- \[47\]S\. Weng, M\. Xiao, C\. Ren, and M\. Skoglund\(2024\)Coded cooperative networks for semi\-decentralized federated learning\.IEEE Wireless Communications Letters14\(3\),pp\. 626–630\.Cited by:[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p1.1),[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p3.1)\.
- \[48\]H\. Xiao, K\. Rasul, and R\. Vollgraf\(2017\)Fashion\-mnist: a novel image dataset for benchmarking machine learning algorithms\.arXiv:1708\.07747\.Cited by:[§VI\-A](https://arxiv.org/html/2606.06687#S6.SS1.p1.13)\.
- \[49\]L\. Xiao, S\. Boyd, and S\. Lall\(2005\)Distributed average consensus with time\-varying metropolis weights\.Automatica41\(12\),pp\. 1895–1906\.External Links:[Document](https://dx.doi.org/10.1016/j.automatica.2005.07.008)Cited by:[§VI\-A](https://arxiv.org/html/2606.06687#S6.SS1.p2.20)\.
- \[50\]L\. Xiao and T\. Zhang\(2014\)A proximal stochastic gradient method with progressive variance reduction\.SIAM Journal on Optimization24\(4\),pp\. 2057–2075\.Cited by:[2nd item](https://arxiv.org/html/2606.06687#S3.I1.i2.p1.1)\.
- \[51\]A\. Yazdinejad, A\. Dehghantanha, H\. Karimipour, G\. Srivastava, and R\. M\. Parizi\(2024\)A robust privacy\-preserving federated learning model against model poisoning attacks\.IEEE Transactions on Information Forensics and Security19\(1\),pp\. 6693–6708\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p1.1)\.
- \[52\]M\. Yemini, R\. Saha, E\. Ozfatura, D\. Gündüz, and A\. J\. Goldsmith\(2022\)Semi\-decentralized federated learning with collaborative relaying\.InProceedings of the 2022 IEEE International Symposium on Information Theory,pp\. 1471–1476\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p2.1),[§II\-A](https://arxiv.org/html/2606.06687#S2.SS1.p1.1)\.
- \[53\]L\. Yuan, Z\. Wang, L\. Sun, S\. Y\. Philip, and C\. G\. Brinton\(2024\)Decentralized federated learning: a survey and perspective\.IEEE Internet of Things Journal11\(21\),pp\. 34617 – 34638\.Cited by:[§I](https://arxiv.org/html/2606.06687#S1.p1.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p2.1)\.
- \[54\]S\. Zehtabi, D\. Han, R\. Parasnis, S\. Hosseinalipour, and C\. G\. Brinton\(2024\)Decentralized sporadic federated learning: a unified algorithmic framework with convergence guarantees\.arXiv:2402\.03448\.Cited by:[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p1.1),[§II\-B](https://arxiv.org/html/2606.06687#S2.SS2.p2.1)\.
- \[55\]C\. Zhang, G\. Shan, and B\. Roh\(2025\)Fmd\-iov: security and robust enhancement for federated multi\-domain learning–based iov\.IEEE Transactions on Intelligent Transportation Systems26\(9\),pp\. 14225–14236\.Cited by:[2nd item](https://arxiv.org/html/2606.06687#S1.I1.i2.p1.1)\.

## Appendix

## Table of Contents

Appendix[A](https://arxiv.org/html/2606.06687#A1): Proof of Proposition[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1)[A](https://arxiv.org/html/2606.06687#A1)Appendix[B](https://arxiv.org/html/2606.06687#A2): Proof of Corollary[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1)[B](https://arxiv.org/html/2606.06687#A2)Appendix[C](https://arxiv.org/html/2606.06687#A3): Proof of Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)[C](https://arxiv.org/html/2606.06687#A3)Appendix[D](https://arxiv.org/html/2606.06687#A4): Proof of Lemma[30](https://arxiv.org/html/2606.06687#S4.E30)[D](https://arxiv.org/html/2606.06687#A4)Appendix[E](https://arxiv.org/html/2606.06687#A5): Proof of Lemma[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)[E](https://arxiv.org/html/2606.06687#A5)Appendix[F](https://arxiv.org/html/2606.06687#A6): Proof of Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)[F](https://arxiv.org/html/2606.06687#A6)Appendix[G](https://arxiv.org/html/2606.06687#A7): Additional Experiments[G](https://arxiv.org/html/2606.06687#A7)[G\-A](https://arxiv.org/html/2606.06687#A7.SS1)Varying Link Probabilities\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[G\-A](https://arxiv.org/html/2606.06687#A7.SS1)[G\-B](https://arxiv.org/html/2606.06687#A7.SS2)Homogeneous SGD Optimizers\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[G\-B](https://arxiv.org/html/2606.06687#A7.SS2)[G\-C](https://arxiv.org/html/2606.06687#A7.SS3)Normalized Intra\-Cluster Gradients\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[G\-C](https://arxiv.org/html/2606.06687#A7.SS3)

## Appendix AProof of Proposition[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1)

###### Proof\.

Recall that, via the definition of regularized cluster loss functions, we can expand‖∇L~s​\(𝜽^sk~,q1\)−∇L~s​\(𝜽^sk~,q2\)‖\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)\-\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\\|as follows:

‖∇L~s​\(𝜽^sk~,q1\)−∇L~s​\(𝜽^sk~,q2\)‖\\displaystyle\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)\-\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\\|\(42\)=\(a\)∥∇\(∑i∈𝒩sLi​\(𝜽ik~,q1\)−Li​\(𝜽ik~,q2\)\)\+∇\(𝜽ik~,q1​∑p=0q1−1ρiq1−p​∇Li​\(𝜽ik~,p\)−𝜽ik~,q2​∑p=0q2−1ρiq2−p​∇Li​\(𝜽ik~,p\)\)\\displaystyle\\overset\{\(a\)\}\{=\}\\Bigg\\\|\\nabla\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\)\-L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\_\{i\}\)\\right\)\+\\nabla\\left\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\\sum\_\{p=0\}^\{q\_\{1\}\-1\}\\rho^\{q\_\{1\}\-p\}\_\{i\}\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},p\}\_\{i\}\)\-\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\_\{i\}\\sum\_\{p=0\}^\{q\_\{2\}\-1\}\\rho^\{q\_\{2\}\-p\}\_\{i\}\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},p\}\_\{i\}\)\\right\)\(43\)\+∇\(∑i∈𝒩sμi2\(∥𝜽ik~,q1−𝜽ik~,0∥2−∥𝜽ik~,q2−𝜽ik~,0∥2\)\)\+∇12​η\(∥𝜽^sk~,q1∥𝑰s−𝑨s2−∥𝜽^sk~,q2∥𝑰s−𝑨s2\)∥\\displaystyle\+\\nabla\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\frac\{\\mu\_\{i\}\}\{2\}\\left\(\\\|\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},0\}\_\{i\}\\\|^\{2\}\-\\\|\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},0\}\_\{i\}\\\|^\{2\}\\right\)\\right\)\+\\nabla\\frac\{1\}\{2\\eta\}\\left\(\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\\\|^\{2\}\_\{\\bm\{I\}\_\{s\}\-\\bm\{A\}\_\{s\}\}\-\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\\|^\{2\}\_\{\\bm\{I\}\_\{s\}\-\\bm\{A\}\_\{s\}\}\\right\)\\Bigg\\\|≤\(b\)​‖∇ℒs​\(𝜽^sk~,q1\)−∇ℒs​\(𝜽^sk~,q2\)‖⏟\(i\)\+‖∑p=0q1−1𝝆sq1−p⊙∇ℒs​\(𝜽^sk~,p\)−∑p=0q2−1𝝆sq2−p⊙∇ℒs​\(𝜽^sk~,p\)‖⏟\(i​i\)\\displaystyle\\overset\{\(b\)\}\{\\leq\}\\underbrace\{\\left\\\|\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)\-\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\right\\\|\}\_\{\(i\)\}\+\\underbrace\{\\left\\\|\\sum\_\{p=0\}^\{q\_\{1\}\-1\}\\bm\{\\rho\}\_\{s\}^\{q\_\{1\}\-p\}\\odot\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\-\\sum\_\{p=0\}^\{q\_\{2\}\-1\}\\bm\{\\rho\}\_\{s\}^\{q\_\{2\}\-p\}\\odot\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\\right\\\|\}\_\{\(ii\)\}\(44\)\+‖𝝁s⊙\(𝜽^sk~,q1−𝜽^sk~,0\)−𝝁s⊙\(𝜽^sk~,q2−𝜽^sk~,0\)‖⏟\(i​i​i\)\+‖1η​\(𝑰s−𝑨s\)​\(𝜽^sk~,q1−𝜽^sk~,q2\)‖⏟\(i​v\),\\displaystyle\+\\underbrace\{\\left\\\|\\bm\{\\mu\}\_\{s\}\\odot\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\\right\)\-\\bm\{\\mu\}\_\{s\}\\odot\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\\right\)\\right\\\|\}\_\{\(iii\)\}\+\\underbrace\{\\left\\\|\\frac\{1\}\{\\eta\}\\left\(\\bm\{I\}\_\{s\}\-\\bm\{A\}\_\{s\}\\right\)\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)\\right\\\|\}\_\{\(iv\)\},where∇ℒs​\(𝜽^sk~,q\)=\[∇Li​\(𝜽ik~,q\)\]i∈𝒩s\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)=\[\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)\]\_\{i\\in\\mathcal\{N\}\_\{s\}\},\(a\)\(a\)is from the expanded definition of the regularized effective cluster loss functions, and\(b\)\(b\)applies the gradient to the scalars and then uses the triangle inequality\. We next bound each of the four terms\(i\),\(i​i\),\(i​i​i\),\(i\),\(ii\),\(iii\),and\(i​v\)\(iv\)in \([44](https://arxiv.org/html/2606.06687#A1.E44)\), starting with term\(i\)\(i\)as follows:

‖∇ℒs​\(𝜽^sk~,q1\)−∇ℒs​\(𝜽^sk~,q2\)‖​=\(c\)​\(∑i∈𝒩s\(∇Li​\(𝜽ik~,q1\)−∇Li​\(𝜽ik~,q2\)\)2\)1/2\\displaystyle\\left\\\|\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)\-\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\right\\\|\\overset\{\(c\)\}\{=\}\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\left\(\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\)\-\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\_\{i\}\)\\right\)^\{2\}\\right\)^\{1/2\}\(45\)≤\(d\)​\(∑i∈𝒩sγi2​\(𝜽ik~,q1−𝜽ik~,q2\)2\)1/2\\displaystyle\\overset\{\(d\)\}\{\\leq\}\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\gamma\_\{i\}^\{2\}\\left\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\_\{i\}\\right\)^\{2\}\\right\)^\{1/2\}\(46\)≤\(e\)​\(maxi∈𝒩s⁡γi\)​\(∑i∈𝒩s\(𝜽ik~,q1−𝜽ik~,q2\)2\)1/2\\displaystyle\\overset\{\(e\)\}\{\\leq\}\\left\(\\max\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\gamma\_\{i\}\\right\)\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\left\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\_\{i\}\\right\)^\{2\}\\right\)^\{1/2\}\(47\)=\(f\)​γ^s​‖𝜽^sk~,q1−𝜽^sk~,q2‖,\\displaystyle\\overset\{\(f\)\}\{=\}\\hat\{\\gamma\}\_\{s\}\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|,\(48\)where\(c\)\(c\)follows from the definition of the Euclidean norm,\(d\)\(d\)leverages the smoothness assumption in Assumption[1](https://arxiv.org/html/2606.06687#Thmassumption1),\(e\)\(e\)extracts the largest smoothness coefficientγ^s=maxi∈𝒩s⁡γi\\hat\{\\gamma\}\_\{s\}=\\max\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\gamma\_\{i\}, and\(f\)\(f\)re\-applies the equivalent form of the Euclidean norm\. Next, for term\(i​i\)\(ii\)in \([44](https://arxiv.org/html/2606.06687#A1.E44)\), we have that

‖∑p=0q1−1𝝆sq1−p⊙∇ℒs​\(𝜽^sk~,p\)−∑p=0q2−1𝝆sq2−p⊙∇ℒs​\(𝜽^sk~,p\)‖\\displaystyle\\left\\\|\\sum\_\{p=0\}^\{q\_\{1\}\-1\}\\bm\{\\rho\}\_\{s\}^\{q\_\{1\}\-p\}\\odot\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\-\\sum\_\{p=0\}^\{q\_\{2\}\-1\}\\bm\{\\rho\}\_\{s\}^\{q\_\{2\}\-p\}\\odot\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\\right\\\|\(49\)=\(g\)​‖∑p=q2q1−1𝝆sq1−p⊙∇ℒs​\(𝜽^sk~,p\)\+∑p=0q2−1\(𝝆sq1−p−𝝆sq2−p\)⊙∇ℒs​\(𝜽^sk~,p\)‖\\displaystyle\\overset\{\(g\)\}\{=\}\\left\\\|\\sum\_\{p=q\_\{2\}\}^\{q\_\{1\}\-1\}\\bm\{\\rho\}\_\{s\}^\{q\_\{1\}\-p\}\\odot\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\+\\sum\_\{p=0\}^\{q\_\{2\}\-1\}\\left\(\\bm\{\\rho\}\_\{s\}^\{q\_\{1\}\-p\}\-\\bm\{\\rho\}\_\{s\}^\{q\_\{2\}\-p\}\\right\)\\odot\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\\right\\\|\(50\)≤\(h\)​∑p=q2q1−1‖𝝆sq1−p⊙∇ℒs​\(𝜽^sk~,p\)‖\+∑p=0q2−1‖\(𝝆sq1−p−𝝆sq2−p\)⊙∇ℒs​\(𝜽^sk~,p\)‖\\displaystyle\\overset\{\(h\)\}\{\\leq\}\\sum\_\{p=q\_\{2\}\}^\{q\_\{1\}\-1\}\\left\\\|\\bm\{\\rho\}\_\{s\}^\{q\_\{1\}\-p\}\\odot\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\\right\\\|\+\\sum\_\{p=0\}^\{q\_\{2\}\-1\}\\left\\\|\\left\(\\bm\{\\rho\}\_\{s\}^\{q\_\{1\}\-p\}\-\\bm\{\\rho\}\_\{s\}^\{q\_\{2\}\-p\}\\right\)\\odot\\nabla\\mathcal\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\\right\\\|\(51\)≤\(i\)​∑p=q2q1−1\(∑i∈𝒩s\(ρiq1−p​∇Li​\(𝜽ik~,q1\)\)2\)1/2\+∑p=0q2−1\(∑i∈𝒩s\(\(ρiq1−p−ρiq2−p\)​∇Li​\(𝜽ik~,q1\)\)2\)1/2\\displaystyle\\overset\{\(i\)\}\{\\leq\}\\sum\_\{p=q\_\{2\}\}^\{q\_\{1\}\-1\}\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\left\(\\rho\_\{i\}^\{q\_\{1\}\-p\}\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\)\\right\)^\{2\}\\right\)^\{1/2\}\+\\sum\_\{p=0\}^\{q\_\{2\}\-1\}\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\left\(\\left\(\\rho\_\{i\}^\{q\_\{1\}\-p\}\-\\rho\_\{i\}^\{q\_\{2\}\-p\}\\right\)\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\)\\right\)^\{2\}\\right\)^\{1/2\}\(52\)≤\(j\)​∑p=q2q1−1\(∑i∈𝒩s\(∇Li​\(𝜽ik~,q1\)\)2\)1/2\+∑p=0q2−1\(∑i∈𝒩s\(∇Li​\(𝜽ik~,q1\)\)2\)1/2\\displaystyle\\overset\{\(j\)\}\{\\leq\}\\sum\_\{p=q\_\{2\}\}^\{q\_\{1\}\-1\}\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\left\(\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\)\\right\)^\{2\}\\right\)^\{1/2\}\+\\sum\_\{p=0\}^\{q\_\{2\}\-1\}\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\left\(\\nabla L\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\)\\right\)^\{2\}\\right\)^\{1/2\}\(53\)≤\(k\)​∑p=0τa−1\(Ns​B2\)1/2=τa​B​Ns,\\displaystyle\\overset\{\(k\)\}\{\\leq\}\\sum\_\{p=0\}^\{\\tau\_\{a\}\-1\}\\left\(N\_\{s\}B^\{2\}\\right\)^\{1/2\}=\\tau\_\{a\}B\\sqrt\{N\_\{s\}\},\(54\)where\(g\)\(g\)aligns the summations over the iterations,\(h\)\(h\)results from the triangle inequality,\(i\)\(i\)expands the Euclidean distance,\(j\)\(j\)uses the fact thatρiq1−p\\rho\_\{i\}^\{q\_\{1\}\-p\}andρiq1−p−ρiq2−p≤1\\rho^\{q\_\{1\}\-p\}\_\{i\}\-\\rho^\{q\_\{2\}\-p\}\_\{i\}\\leq 1, and\(k\)\(k\)uses the fact thatq1≤τaq\_\{1\}\\leq\\tau\_\{a\}and subsequently leverages Assumption[2](https://arxiv.org/html/2606.06687#Thmassumption2)to obtain‖∇Li​\(𝜽i\)‖<B\\\|\\nabla L\_\{i\}\(\\bm\{\\theta\}\_\{i\}\)\\\|<B\. Next, we bound the difference of proximal terms \(i\.e\., term\(i​i​i\)\(iii\)in \([44](https://arxiv.org/html/2606.06687#A1.E44)\)\) as follows:

‖𝝁s⊙\(𝜽^sk~,q1−𝜽^sk~,0\)−𝝁s⊙\(𝜽^sk~,q2−𝜽^sk~,0\)‖​=\(l\)​‖𝝁s⊙\(𝜽^sk~,q1−𝜽^sk~,q2\)‖\\displaystyle\\left\\\|\\bm\{\\mu\}\_\{s\}\\odot\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\\right\)\-\\bm\{\\mu\}\_\{s\}\\odot\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\\right\)\\right\\\|\\overset\{\(l\)\}\{=\}\\left\\\|\\bm\{\\mu\}\_\{s\}\\odot\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)\\right\\\|\(55\)≤\(m\)​\(∑i∈𝒩s\(μi​\(𝜽ik~,q1−𝜽ik~,q2\)\)2\)1/2\\displaystyle\\overset\{\(m\)\}\{\\leq\}\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\left\(\\mu\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\_\{i\}\)\\right\)^\{2\}\\right\)^\{1/2\}\(56\)≤\(n\)​\(∑i∈𝒩s\(\(𝜽ik~,q1−𝜽ik~,q2\)\)2\)1/2\\displaystyle\\overset\{\(n\)\}\{\\leq\}\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\left\(\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\_\{i\}\-\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\_\{i\}\)\\right\)^\{2\}\\right\)^\{1/2\}\(57\)≤\(o\)​‖𝜽^sk~,q1−𝜽^sk~,q2‖\\displaystyle\\overset\{\(o\)\}\{\\leq\}\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\(58\)where\(l\)\(l\)cancels out±𝜽^sk~,0\\pm\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\},\(m\)\(m\)expands the definition of Euclidean distance,\(n\)\(n\)uses the fact thatμi≤1\\mu\_\{i\}\\leq 1so thatmaxi⁡μi≤1\\max\_\{i\}\\mu\_\{i\}\\leq 1, and\(o\)\(o\)is the definition of Euclidean distance\. Finally, for term\(i​v\)\(iv\)in \([44](https://arxiv.org/html/2606.06687#A1.E44)\), we have that

‖1η​\(𝑰s−𝑨s\)​\(𝜽^sk~,q1−𝜽^sk~,q2\)‖​≤\(q\)​1η​‖𝑰s−𝑨s‖​‖𝜽^sk~,q1−𝜽^sk~,q2‖\\displaystyle\\left\\\|\\frac\{1\}\{\\eta\}\\left\(\\bm\{I\}\_\{s\}\-\\bm\{A\}\_\{s\}\\right\)\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)\\right\\\|\\overset\{\(q\)\}\{\\leq\}\\frac\{1\}\{\\eta\}\\\|\\bm\{I\}\_\{s\}\-\\bm\{A\}\_\{s\}\\\|\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\(59\)≤\(p\)​1η​λmax​\(𝑰s−𝑨s\)​‖𝜽^sk~,q1−𝜽^sk~,q2‖\\displaystyle\\overset\{\(p\)\}\{\\leq\}\\frac\{1\}\{\\eta\}\\lambda\_\{\\max\}\(\\bm\{I\}\_\{s\}\-\\bm\{A\}\_\{s\}\)\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\(60\)=\(r\)​1η​\(1−λNs​\(𝑨s\)\)​‖𝜽^sk~,q1−𝜽^sk~,q2‖,\\displaystyle\\overset\{\(r\)\}\{=\}\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|,\(61\)where\(q\)\(q\)converts the expression into two terms,\(p\)\(p\)uses the fact that the 2\-norm of a matrix \(spectral norm\) is the largest eigenvalue of said matrix,\(r\)\(r\)simplifies the expression ofλmax\\lambda\_\{\\max\}\.

Finally, combining the bounds for terms\(i\)\(i\),\(i​i\)\(ii\),\(i​i​i\)\(iii\), and\(i​v\)\(iv\)in \([44](https://arxiv.org/html/2606.06687#A1.E44)\) yields

‖∇L~s​\(𝜽^sk~,q1\)−∇L~s​\(𝜽^sk~,q2\)‖≤γ^s​‖𝜽^sk~,q1−𝜽^sk~,q2‖\+τa​B​Ns\+‖𝜽^sk~,q1−𝜽^sk~,q2‖\\displaystyle\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)\-\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\right\\\|\\leq\\hat\{\\gamma\}\_\{s\}\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\+\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\+1η​\(1−λNs​\(𝑨s\)\)​‖𝜽^sk~,q1−𝜽^sk~,q2‖\\displaystyle\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\(62\)=\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\)​‖𝜽^sk~,q1−𝜽^sk~,q2‖\+τa​B​Ns,\\displaystyle=\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\\right\)\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\},\(63\)which completes the proof for the gap between intra\-cluster full gradients\.

Leveraging the same logic for the gap between full gradients across the entire network \(i\.e\., at the global level\), we can obtain

‖∇L~​\(𝜽k~,q1\)−∇L~​\(𝜽k~,q2\)‖≤γ^​‖𝜽k~,q1−𝜽k~,q2‖\+τa​B​N\+‖𝜽k~,q1−𝜽k~,q2‖\\displaystyle\\left\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{1\}\}\)\-\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\_\{2\}\}\)\\right\\\|\\leq\\hat\{\\gamma\}\\left\\\|\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\-\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\\right\\\|\+\\tau\_\{a\}B\\sqrt\{N\}\+\\left\\\|\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\-\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\\right\\\|\+1η​\(1−λN​\(𝑨~\)\)​‖𝜽k~,q1−𝜽k~,q2‖\\displaystyle\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\}\(\\tilde\{\\bm\{A\}\}\)\\right\)\\left\\\|\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\-\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\\right\\\|\(64\)=\(γ^\+1\+1η​\(1−λN​\(𝑨~\)\)\)​‖𝜽k~,q1−𝜽k~,q2‖\+τa​B​N,\\displaystyle=\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\}\(\\tilde\{\\bm\{A\}\}\)\\right\)\\right\)\\left\\\|\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\-\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\\right\\\|\+\\tau\_\{a\}B\\sqrt\{N\},\(65\)whereγ^=maxi∈𝒩⁡γi\\hat\{\\gamma\}=\\max\_\{i\\in\\mathcal\{N\}\}\\gamma\_\{i\}\. ∎

## Appendix BProof of Corollary[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1)

###### Proof\.

Define a variablet~∈\[0,1\]\\tilde\{t\}\\in\[0,1\]so that we can parameterize a line segment from𝜽^sk~,q2\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}to𝜽^sk~,q1\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}as follows:

𝜽^s​\(t~\)=𝜽^sk~,q2\+t~​\(𝜽^sk~,q1−𝜽^sk~,q2\)\.\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)=\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\+\\tilde\{t\}\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)\.\(66\)Exploiting \([66](https://arxiv.org/html/2606.06687#A2.E66)\), we can express intra\-cluster regularized loss functions as functions oft~\\tilde\{t\}, obtaining arithmetic of intra\-cluster regularized loss functions as follows:

L~s​\(𝜽^sk~,q1\)−L~s​\(𝜽^sk~,q2\)≡L~s​\(𝜽^s​\(1\)\)−L~s​\(𝜽^s​\(0\)\)\.\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)\-\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\equiv\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(1\)\)\-\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(0\)\)\.\(67\)Using the fundamental theorem of calculus, we further convert the right hand side of \([67](https://arxiv.org/html/2606.06687#A2.E67)\) as follows:

L~s​\(𝜽^s​\(1\)\)−L~s​\(𝜽^s​\(0\)\)\\displaystyle\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(1\)\)\-\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(0\)\)\(68\)=\(a\)​∫01dd​t~​L~s​\(𝜽^s​\(t~\)\)​𝑑t~\\displaystyle\\overset\{\(a\)\}\{=\}\\int^\{1\}\_\{0\}\\frac\{d\}\{d\\tilde\{t\}\}\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)\)d\\tilde\{t\}\(69\)=\(b\)​∫01∇L~s​\(𝜽^s​\(t~\)\)T​\(𝜽^s​\(1\)−𝜽^s​\(0\)\)​𝑑t~≡∫01∇L~s​\(𝜽^s​\(t~\)\)T​\(𝜽^sk~,q1−𝜽^sk~,q2\)​𝑑t~\\displaystyle\\overset\{\(b\)\}\{=\}\\int^\{1\}\_\{0\}\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)\)^\{T\}\\left\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(1\)\-\\hat\{\\bm\{\\theta\}\}\_\{s\}\(0\)\\right\)d\\tilde\{t\}\\equiv\\int^\{1\}\_\{0\}\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)\)^\{T\}\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)d\\tilde\{t\}\(70\)where\(a\)\(a\)results from the fundamental theorem of calculus, and\(b\)\(b\)follows from the chain rule applied ontoL~s​\(𝜽^s​\(t~\)\)\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)\)and subsequently \([66](https://arxiv.org/html/2606.06687#A2.E66)\)\. Combining \([67](https://arxiv.org/html/2606.06687#A2.E67)\) and \([70](https://arxiv.org/html/2606.06687#A2.E70)\) yields

L~s​\(𝜽^sk~,q1\)​=\(c\)​L~s​\(𝜽^sk~,q2\)\+∫01∇L~s​\(𝜽^s​\(t~\)\)T​\(𝜽^s​\(1\)−𝜽^s​\(0\)\)​𝑑t~\\displaystyle\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)\\overset\{\(c\)\}\{=\}\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\+\\int^\{1\}\_\{0\}\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)\)^\{T\}\\left\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(1\)\-\\hat\{\\bm\{\\theta\}\}\_\{s\}\(0\)\\right\)d\\tilde\{t\}\(71\)=\(d\)​L~s​\(𝜽^sk~,q2\)\+∇L~s​\(𝜽^sk~,q2\)T​\(𝜽^sk~,q1−𝜽^sk~,q2\)\+∫01\(∇L~s​\(𝜽^s​\(t~\)\)−∇L~s​\(𝜽^sk~,q2\)\)T​\(𝜽^sk~,q1−𝜽^sk~,q2\)​𝑑t~,\\displaystyle\\overset\{\(d\)\}\{=\}\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\+\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)^\{T\}\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)\+\\int^\{1\}\_\{0\}\\left\(\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)\)\-\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\right\)^\{T\}\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)d\\tilde\{t\},\(72\)where\(c\)\(c\)re\-arranges the combination of \([67](https://arxiv.org/html/2606.06687#A2.E67)\) and \([70](https://arxiv.org/html/2606.06687#A2.E70)\), and\(d\)\(d\)introduces±∇L~s​\(𝜽^sk~,q2\)​\(𝜽^sk~,q1−𝜽^sk~,q2\)\\pm\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)\. Next, we focus on bounding the integral in \([72](https://arxiv.org/html/2606.06687#A2.E72)\) as follows:

∫01\(∇L~s​\(𝜽^s​\(t~\)\)−∇L~s​\(𝜽^sk~,q2\)\)T​\(𝜽^sk~,q1−𝜽^sk~,q2\)​𝑑t~​≤\(e\)​∫01‖∇L~s​\(𝜽^s​\(t~\)\)−∇L~s​\(𝜽^sk~,q2\)‖​‖𝜽^sk~,q1−𝜽^sk~,q2‖​𝑑t~\\displaystyle\\int^\{1\}\_\{0\}\\left\(\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)\)\-\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\right\)^\{T\}\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)d\\tilde\{t\}\\overset\{\(e\)\}\{\\leq\}\\int^\{1\}\_\{0\}\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)\)\-\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\\right\\\|\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|d\\tilde\{t\}\(73\)≤\(f\)​∫01\[\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\)​‖𝜽^s​\(t~\)−𝜽^sk~,q2‖\+τa​B​Ns\]​‖𝜽^sk~,q1−𝜽^sk~,q2‖​𝑑t~\\displaystyle\\overset\{\(f\)\}\{\\leq\}\\int\_\{0\}^\{1\}\\left\[\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\\right\)\\left\\\|\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\]\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|d\\tilde\{t\}\(74\)=\(g\)​∫01\[\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\)​‖t~​\(𝜽^sk~,q1−𝜽^sk~,q2\)‖\]​‖𝜽^sk~,q1−𝜽^sk~,q2‖​𝑑t~\+τa​B​Ns​‖𝜽^sk~,q1−𝜽^sk~,q2‖\\displaystyle\\overset\{\(g\)\}\{=\}\\int\_\{0\}^\{1\}\\left\[\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\\right\)\\left\\\|\\tilde\{t\}\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)\\right\\\|\\right\]\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|d\\tilde\{t\}\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\(75\)=\(h\)​12​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\)​‖𝜽^sk~,q1−𝜽^sk~,q2‖2\+τa​B​Ns​‖𝜽^sk~,q1−𝜽^sk~,q2‖\\displaystyle\\overset\{\(h\)\}\{=\}\\frac\{1\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\\right\)\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|^\{2\}\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\(76\)where\(e\)\(e\)is from the Cauchy\-Schwarz inequality,\(f\)\(f\)uses the regularized cluster loss gradient gap derived in Theorem[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1),\(g\)\(g\)substitutes the definition of𝜽^s​\(t~\)\\hat\{\\bm\{\\theta\}\}\_\{s\}\(\\tilde\{t\}\)from \([66](https://arxiv.org/html/2606.06687#A2.E66)\), and\(h\)\(h\)expands the integral\. Finally, combining \([72](https://arxiv.org/html/2606.06687#A2.E72)\) and \([76](https://arxiv.org/html/2606.06687#A2.E76)\) yields the result as follows:

L~s​\(𝜽^sk~,q1\)≤L~s​\(𝜽^sk~,q2\)\+∇L~s​\(𝜽^sk~,q2\)T​\(𝜽^sk~,q1−𝜽^sk~,q2\)\\displaystyle\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\)\\leq\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)\+\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\)^\{T\}\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\)\(77\)\+12​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\)​‖𝜽^sk~,q1−𝜽^sk~,q2‖2\+τa​B​Ns​‖𝜽^sk~,q1−𝜽^sk~,q2‖\.\\displaystyle\+\\frac\{1\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\\right\)\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|^\{2\}\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\left\\\|\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{1\}\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\\right\\\|\.
∎

## Appendix CProof of Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)

###### Proof\.

Leveraging the result of Corollary[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1)and combining with the intra\-cluster ML model update rule from \([14](https://arxiv.org/html/2606.06687#S3.E14)\) yields

L~s​\(𝜽^sk~,q\+1\)≤L~s​\(𝜽^sk~,q\)\+∇L~s​\(𝜽^sk~,q\)T​\(−η​∇F~s​\(𝜽^sk~,q\)\)\\displaystyle\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\+1\}\_\{s\}\)\\leq\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\+\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)^\{T\}\\left\(\-\\eta\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\)\(78\)\+12​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\)​‖−η​∇F~s​\(𝜽^sk~,q\)‖2\+τa​B​Ns​‖−η​∇F~s​\(𝜽^sk~,q\)‖\\displaystyle\+\\frac\{1\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\\right\)\\left\\\|\-\\eta\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\left\\\|\-\\eta\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|≤\(a\)​L~s​\(𝜽^sk~,q\)\+∇L~s​\(𝜽^sk~,q\)T​\(−η​∇F~s​\(𝜽^sk~,q\)\)\+12​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)​‖−η​∇F~s​\(𝜽^sk~,q\)‖2,\\displaystyle\\overset\{\(a\)\}\{\\leq\}\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\+\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)^\{T\}\\left\(\-\\eta\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\)\+\\frac\{1\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\\left\\\|\-\\eta\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\},\(79\)where\(a\)\(a\)follows immediately since‖−η​∇F~s​\(𝜽^sk~,q\)‖2\>‖−η​∇F~s​\(𝜽^sk~,q\)‖\\\|\-\\eta\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\\|^\{2\}\>\\\|\-\\eta\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\\|\. Re\-arranging \([79](https://arxiv.org/html/2606.06687#A3.E79)\) and taking the expectation yields

L~s​\(𝜽^sk~,q\+1\)−L~s​\(𝜽^sk~,q\)​≤\(b\)−η​∇L~s​\(𝜽^sk~,q\)T​𝔼​\[∇F~s​\(𝜽^sk~,q\)\]\\displaystyle\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\+1\}\_\{s\}\)\-\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\overset\{\(b\)\}\{\\leq\}\-\\eta\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)^\{T\}\\mathbb\{E\}\\left\[\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\]\+η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)​𝔼​\[‖∇F~s​\(𝜽^sk~,q\)‖2\]\\displaystyle\+\\frac\{\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\\mathbb\{E\}\\left\[\\left\\\|\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\\right\]\(80\)≤\(c\)−η​‖∇L~s​\(𝜽^sk~,q\)‖2\+η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)​\(α\+α^s​‖∇L~s​\(𝜽^sk~,q\)‖2\)\\displaystyle\\overset\{\(c\)\}\{\\leq\}\-\\eta\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\+\\frac\{\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\\left\(\\alpha\+\\hat\{\\alpha\}\_\{s\}\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\\right\)\(81\)=\(d\)​\(−η\+α^s​η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)\)​‖∇L~s​\(𝜽^sk~,q\)‖2\\displaystyle\\overset\{\(d\)\}\{=\}\\left\(\-\\eta\+\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\\right\)\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\+α​η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\),\\displaystyle\+\\frac\{\\alpha\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\),\(82\)where\(b\)\(b\)is the result of re\-arrangement,\(c\)\(c\)leverages Assumption[4](https://arxiv.org/html/2606.06687#Thmassumption4)and the fact that∇F~s​\(𝜽^sk~,q\)\\nabla\\tilde\{F\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)is the unbiased estimate of∇L~s​\(𝜽^sk~,q2\)\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\_\{2\}\}\_\{s\}\), and\(d\)\(d\)simplifies the algebra\. Further re\-arrangement of \([C](https://arxiv.org/html/2606.06687#A3.Ex7)\) yields

\(η−α^s​η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)\)​‖∇L~s​\(𝜽^sk~,q\)‖2≤L~s​\(𝜽^sk~,q\)−L~s​\(𝜽^sk~,q\+1\)\\displaystyle\\left\(\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\\right\)\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\\leq\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\-\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\+1\}\_\{s\}\)\(83\)\+α​η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)\.\\displaystyle\+\\frac\{\\alpha\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\.Finally, dividing both sides of \(LABEL:eq:prf\_intraconv\_3\) by the coefficient on‖∇L~s​\(𝜽^sk~,q\)‖2\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}and summing over all instancesq∈k~q\\in\\tilde\{k\}yields the result as follows:

∑q=0τa−1‖∇L~s​\(𝜽^sk~,q\)‖2​≤\(e\)​L~s​\(𝜽^sk~,0\)−L~s​\(𝜽^sk~,τa\)\(η−α^s​η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)\)\\displaystyle\\sum\_\{q=0\}^\{\\tau\_\{a\}\-1\}\\left\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\\\|^\{2\}\\overset\{\(e\)\}\{\\leq\}\\frac\{\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\)\-\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},\\tau\_\{a\}\}\_\{s\}\)\}\{\\left\(\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\\right\)\}\(84\)\+α​τa​η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)\(η−α^s​η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)\)\\displaystyle\+\\frac\{\\frac\{\\alpha\\tau\_\{a\}\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\}\{\\left\(\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\\right\)\}≤\(f\)​L~s​\(𝜽^sk~,0\)\+α​τa​η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)\(η−α^s​η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\)\),\\displaystyle\\overset\{\(f\)\}\{\\leq\}\\frac\{\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\)\+\\frac\{\\alpha\\tau\_\{a\}\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\}\{\\left\(\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\\right\)\},where\(f\)\(f\)is from the fact thatL~s​\(⋅\)≥0\\tilde\{L\}\_\{s\}\(\\cdot\)\\geq 0\. Finally, note that the\(e\)\(e\)step in \(LABEL:eq:prf\_intraconv\_4\) requires that

η\>α^s​η22​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\+τa​B​Ns\)\)→η<2α^s​\(γ^s\+1\+1η​\(1−λNs​\(𝑨s\)\)\+τa​B​Ns\),\\displaystyle\\eta\>\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\\right\)\\rightarrow\\eta<\\frac\{2\}\{\\hat\{\\alpha\}\_\{s\}\\left\(\\hat\{\\gamma\}\_\{s\}\+1\+\\frac\{1\}\{\\eta\}\\left\(1\-\\lambda\_\{N\_\{s\}\}\(\\bm\{A\}\_\{s\}\)\\right\)\+\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\right\)\},\(85\)after re\-arranging\.

∎

## Appendix DProof of Lemma[30](https://arxiv.org/html/2606.06687#S4.E30)

###### Proof\.

Combining the intra\-cluster ML model parameters update rule in \([14](https://arxiv.org/html/2606.06687#S3.E14)\) and the full form ofF~s​\(⋅\)\\tilde\{F\}\_\{s\}\(\\cdot\)via \([13](https://arxiv.org/html/2606.06687#S3.E13)\) and \([12](https://arxiv.org/html/2606.06687#S3.E12)\) yields

𝜽^sk~,q\+1=𝑨s​𝜽^sk~,q−η​\(𝑮s​\(𝜽^sk~,q\)\+∑p=0q−1𝝆sq−p⊙𝑮s​\(𝜽^sk~,p\)\+𝝁s⊙\(𝜽^sk~,q−𝜽^sk~,0\)\)\.\\displaystyle\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\+1\}\_\{s\}=\\bm\{A\}\_\{s\}\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\-\\eta\\left\(\\bm\{G\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\+\\sum\_\{p=0\}^\{q\-1\}\\bm\{\\rho\}\_\{s\}^\{q\-p\}\\odot\\bm\{G\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\+\\bm\{\\mu\}\_\{s\}\\odot\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\\right\)\\right\)\.\(86\)To analyzeΔsk~,q\+1\\Delta^\{\\tilde\{k\},q\+1\}\_\{s\}, we first express it in an equivalent form

Δsk~,q\+1=𝜽¯sk~,q\+1​𝟏s−𝜽^sk~,q\+1=𝑷s​𝜽^sk~,q\+1,\\displaystyle\\Delta^\{\\tilde\{k\},q\+1\}\_\{s\}=\\overline\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\+1\}\_\{s\}\\bm\{1\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\+1\}\_\{s\}=\\bm\{P\}\_\{s\}\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\+1\}\_\{s\},\(87\)where𝑷s=1Ns​𝟏s​𝟏sT−𝑰s\\bm\{P\}\_\{s\}=\\frac\{1\}\{N\_\{s\}\}\\bm\{1\}\_\{s\}\\bm\{1\}\_\{s\}^\{T\}\-\\bm\{I\}\_\{s\}\. Combining \([86](https://arxiv.org/html/2606.06687#A4.E86)\) and \([87](https://arxiv.org/html/2606.06687#A4.E87)\) then applying the triangle inequality enables the following expansion of‖Δsk~,q\+1‖\\\|\\Delta^\{\\tilde\{k\},q\+1\}\_\{s\}\\\|

‖Δsk~,q\+1‖≤‖𝑷s​\(𝑨s​𝜽^sk~,q\)‖⏟\(i\)\+‖𝑷s​\(η​𝑮s​\(𝜽^sk~,q\)\)‖⏟\(i​i\)\\displaystyle\\left\\\|\\Delta^\{\\tilde\{k\},q\+1\}\_\{s\}\\right\\\|\\leq\\underbrace\{\\left\\\|\\bm\{P\}\_\{s\}\\left\(\\bm\{A\}\_\{s\}\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\\right\)\\right\\\|\}\_\{\(i\)\}\+\\underbrace\{\\left\\\|\\bm\{P\}\_\{s\}\\left\(\\eta\\bm\{G\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\)\\right\\\|\}\_\{\(ii\)\}\+‖𝑷s​\(η​∑p=0q−1𝝆sq−p⊙𝑮s​\(𝜽^sk~,p\)\)‖⏟\(i​i​i\)\+‖𝑷s​\(η​𝝁s⊙\(𝜽^sk~,q−𝜽^sk~,0\)\)‖⏟\(i​v\)\.\\displaystyle\+\\underbrace\{\\left\\\|\\bm\{P\}\_\{s\}\\left\(\\eta\\sum\_\{p=0\}^\{q\-1\}\\bm\{\\rho\}\_\{s\}^\{q\-p\}\\odot\\bm\{G\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\\right\)\\right\\\|\}\_\{\(iii\)\}\+\\underbrace\{\\left\\\|\\bm\{P\}\_\{s\}\\left\(\\eta\\bm\{\\mu\}\_\{s\}\\odot\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\\right\)\\right\)\\right\\\|\}\_\{\(iv\)\}\.\(88\)As𝑨s\\bm\{A\}\_\{s\}is doubly stochastic per Assumption[3](https://arxiv.org/html/2606.06687#Thmassumption3), we exploit commutativity of the constituents of term\(i\)\(i\)in \([D](https://arxiv.org/html/2606.06687#A4.Ex8)\) as follows:

‖𝑷s​\(𝑨s​𝜽^sk~,q\)‖=‖𝑨s​\(𝑷s​𝜽^sk~,q\)‖\\displaystyle\\left\\\|\\bm\{P\}\_\{s\}\\left\(\\bm\{A\}\_\{s\}\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\\right\)\\right\\\|=\\left\\\|\\bm\{A\}\_\{s\}\\left\(\\bm\{P\}\_\{s\}\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\\right\)\\right\\\|\(89\)≤\(a\)​‖𝑨s​Δsk~,q‖\\displaystyle\\overset\{\(a\)\}\{\\leq\}\\left\\\|\\bm\{A\}\_\{s\}\\Delta^\{\\tilde\{k\},q\}\_\{s\}\\right\\\|\(90\)≤\(b\)​λ2​\(𝑨s\)​‖Δsk~,q‖,\\displaystyle\\overset\{\(b\)\}\{\\leq\}\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\\left\\\|\\Delta^\{\\tilde\{k\},q\}\_\{s\}\\right\\\|,\(91\)where\(a\)\(a\)uses the definition ofΔsk~,q\\Delta^\{\\tilde\{k\},q\}\_\{s\}, and\(b\)\(b\)bounds the spectral norm of𝑨s\\bm\{A\}\_\{s\}by its largest feasible eigenvalue, assumingΔsk~,q⟂1\\Delta^\{\\tilde\{k\},q\}\_\{s\}\\perp 1\. Next, for term\(i​i\)\(ii\), we bound as follows:

‖𝑷s​\(η​𝑮s​\(𝜽^sk~,q\)\)‖\\displaystyle\\left\\\|\\bm\{P\}\_\{s\}\\left\(\\eta\\bm\{G\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\)\\right\)\\right\\\|\(92\)=\(c\)​η​\(∑j∈𝒩s\(∑i∈𝒩s1Ns​gi​\(𝜽ik~,q\)−gj​\(𝜽jk~,q\)\)2\)1/2\\displaystyle\\overset\{\(c\)\}\{=\}\\eta\\left\(\\sum\_\{j\\in\\mathcal\{N\}\_\{s\}\}\\left\(\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\frac\{1\}\{N\_\{s\}\}g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)\-g\_\{j\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{j\}\)\\right\)^\{2\}\\right\)^\{1/2\}\(93\)≤\(d\)​η​\(∑j∈𝒩s\(‖∑i∈𝒩s1Ns​gi​\(𝜽ik~,q\)‖\+‖gj​\(𝜽jk~,q\)‖\)2\)1/2\\displaystyle\\overset\{\(d\)\}\{\\leq\}\\eta\\left\(\\sum\_\{j\\in\\mathcal\{N\}\_\{s\}\}\\left\(\\left\\\|\\sum\_\{i\\in\\mathcal\{N\}\_\{s\}\}\\frac\{1\}\{N\_\{s\}\}g\_\{i\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{i\}\)\\right\\\|\+\\left\\\|g\_\{j\}\(\\bm\{\\theta\}^\{\\tilde\{k\},q\}\_\{j\}\)\\right\\\|\\right\)^\{2\}\\right\)^\{1/2\}\(94\)≤\(e\)​η​\(∑j∈𝒩s\(2​B\)2\)1/2\\displaystyle\\overset\{\(e\)\}\{\\leq\}\\eta\\left\(\\sum\_\{j\\in\\mathcal\{N\}\_\{s\}\}\(2B\)^\{2\}\\right\)^\{1/2\}\(95\)=\(f\)​2​η​B​Ns,\\displaystyle\\overset\{\(f\)\}\{=\}2\\eta B\\sqrt\{N\_\{s\}\},\(96\)where\(c\)\(c\)uses the definition of the Euclidean distance,\(d\)\(d\)follows from a triangle inequality,\(e\)\(e\)relies on triangle inequality and Assumption[2](https://arxiv.org/html/2606.06687#Thmassumption2), and\(f\)\(f\)simplifies the result of\(e\)\(e\)\. Similarly, for term\(i​i​i\)\(iii\), we have that

‖𝑷s​\(η​∑p=0q−1𝝆sq−p⊙𝑮s​\(𝜽^sk~,p\)\)‖\\displaystyle\\left\\\|\\bm\{P\}\_\{s\}\\left\(\\eta\\sum\_\{p=0\}^\{q\-1\}\\bm\{\\rho\}\_\{s\}^\{q\-p\}\\odot\\bm\{G\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\\right\)\\right\\\|\(97\)≤\(g\)​η​q​‖𝑷s​𝑮s​\(𝜽^sk~,p\)‖\\displaystyle\\overset\{\(g\)\}\{\\leq\}\\eta q\\left\\\|\\bm\{P\}\_\{s\}\\bm\{G\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},p\}\_\{s\}\)\\right\\\|\(98\)≤\(h\)​2​η​\(τa−1\)​B​Ns,\\displaystyle\\overset\{\(h\)\}\{\\leq\}2\\eta\(\\tau\_\{a\}\-1\)B\\sqrt\{N\_\{s\}\},\(99\)where\(g\)\(g\)follows from triangle inequalities,ρi<1\\rho\_\{i\}<1, and the properties of the Hadamard product, and\(h\)\(h\)is from similar steps as that of\(c\)−\(f\)\(c\)\-\(f\)above in \([96](https://arxiv.org/html/2606.06687#A4.E96)\) andq≤τa−1q\\leq\\tau\_\{a\}\-1\. Finally, for term\(i​v\)\(iv\)in \([D](https://arxiv.org/html/2606.06687#A4.Ex8)\), we bound via the following:

‖𝑷s​\(η​𝝁s⊙\(𝜽^sk~,q−𝜽^sk~,0\)\)‖\\displaystyle\\left\\\|\\bm\{P\}\_\{s\}\\left\(\\eta\\bm\{\\mu\}\_\{s\}\\odot\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\\right\)\\right\)\\right\\\|\(100\)≤\(i\)​η​‖𝑷s​\(𝜽^sk~,q−𝜽^sk~,0\)‖\\displaystyle\\overset\{\(i\)\}\{\\leq\}\\eta\\left\\\|\\bm\{P\}\_\{s\}\\left\(\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\_\{s\}\-\\hat\{\\bm\{\\theta\}\}^\{\\tilde\{k\},0\}\_\{s\}\\right\)\\right\\\|\(101\)=\(j\)​η​‖Δsk~,q−Δsk~,0‖\\displaystyle\\overset\{\(j\)\}\{=\}\\eta\\left\\\|\\Delta^\{\\tilde\{k\},q\}\_\{s\}\-\\Delta^\{\\tilde\{k\},0\}\_\{s\}\\right\\\|\(102\)≤\(k\)​η​‖Δsk~,q‖,\\displaystyle\\overset\{\(k\)\}\{\\leq\}\\eta\\left\\\|\\Delta^\{\\tilde\{k\},q\}\_\{s\}\\right\\\|,\(103\)where\(i\)\(i\)is fromμi≤1\\mu\_\{i\}\\leq 1,\(j\)\(j\)leverages the definition ofΔsk~,q\\Delta^\{\\tilde\{k\},q\}\_\{s\}, and\(k\)\(k\)exploits the fact thatΔsk~,0=0\\Delta^\{\\tilde\{k\},0\}\_\{s\}=0\. Finally, combining \([91](https://arxiv.org/html/2606.06687#A4.E91)\)\-\([103](https://arxiv.org/html/2606.06687#A4.E103)\) into \([D](https://arxiv.org/html/2606.06687#A4.Ex8)\) yields

‖Δsk~,q\+1‖≤\(λ2​\(𝑨s\)\+η\)​‖Δsk~,q‖\+2​η​τa​B​Ns\.\\displaystyle\\left\\\|\\Delta^\{\\tilde\{k\},q\+1\}\_\{s\}\\right\\\|\\leq\(\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\+\\eta\)\\left\\\|\\Delta^\{\\tilde\{k\},q\}\_\{s\}\\right\\\|\+2\\eta\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\.\(104\)Expanding \([104](https://arxiv.org/html/2606.06687#A4.E104)\) recursively yields:

‖Δsk~,q\+1‖​≤\(l\)​\(λ2​\(𝑨s\)\+η\)q​‖Δsk~,0‖\+2​η​τa​B​Ns​∑p=0q\(λ2​\(𝑨s\)\+η\)p\\displaystyle\\left\\\|\\Delta^\{\\tilde\{k\},q\+1\}\_\{s\}\\right\\\|\\overset\{\(l\)\}\{\\leq\}\(\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\+\\eta\)^\{q\}\\left\\\|\\Delta^\{\\tilde\{k\},0\}\_\{s\}\\right\\\|\+2\\eta\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\\sum\_\{p=0\}^\{q\}\(\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\+\\eta\)^\{p\}\(105\)=\(m\)​\(λ2​\(𝑨s\)\+η\)q​‖Δsk~,0‖\+2​η​τa​B​Ns1−η−λ2​\(𝑨s\),\\displaystyle\\overset\{\(m\)\}\{=\}\(\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\+\\eta\)^\{q\}\\left\\\|\\Delta^\{\\tilde\{k\},0\}\_\{s\}\\right\\\|\+\\frac\{2\\eta\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\}\{1\-\\eta\-\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\},\(106\)where\(l\)\(l\)expands the recursion in \([103](https://arxiv.org/html/2606.06687#A4.E103)\), and\(m\)\(m\)bounds the finite geometric sum by the infinite geometric sum and requires thatη<1−λ2​\(𝑨s\)\\eta<1\-\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\. Finally, noting thatq≤τa−1q\\leq\\tau\_\{a\}\-1then yields

‖Δsk~,τa‖≤\(λ2​\(𝑨s\)\+η\)τa−1​‖Δsk~,0‖\+2​η​τa​B​Ns1−η−λ2​\(𝑨s\)\.\\displaystyle\\left\\\|\\Delta^\{\\tilde\{k\},\\tau\_\{a\}\}\_\{s\}\\right\\\|\\leq\(\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\+\\eta\)^\{\\tau\_\{a\}\-1\}\\left\\\|\\Delta^\{\\tilde\{k\},0\}\_\{s\}\\right\\\|\+\\frac\{2\\eta\\tau\_\{a\}B\\sqrt\{N\_\{s\}\}\}\{1\-\\eta\-\\lambda\_\{2\}\(\\bm\{A\}\_\{s\}\)\}\.\(107\)
∎

## Appendix EProof of Lemma[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)

###### Proof\.

Via the global update rule \([12](https://arxiv.org/html/2606.06687#S3.E12)\), we have that

‖Δ^k^,q\+1‖​=\(a\)​‖𝑨​\(𝜽¯k^,q​𝟏−𝜽k~,q\)‖​≤\(b\)​λ2​\(𝑨\)​‖Δ^k^,q‖​≤\(c\)​λ2​\(𝑨\)q​‖Δ^k^,0‖,\\displaystyle\\left\\\|\\hat\{\\Delta\}^\{\\hat\{k\},q\+1\}\\right\\\|\\overset\{\(a\)\}\{=\}\\left\\\|\\bm\{A\}\\left\(\\overline\{\\bm\{\\theta\}\}^\{\\hat\{k\},q\}\\bm\{1\}\-\{\\bm\{\\theta\}\}^\{\\tilde\{k\},q\}\\right\)\\right\\\|\\overset\{\(b\)\}\{\\leq\}\\lambda\_\{2\}\(\\bm\{A\}\)\\left\\\|\\hat\{\\Delta\}^\{\\hat\{k\},q\}\\right\\\|\\overset\{\(c\)\}\{\\leq\}\\lambda\_\{2\}\(\\bm\{A\}\)^\{q\}\\left\\\|\\hat\{\\Delta\}^\{\\hat\{k\},0\}\\right\\\|,\(108\)where\(a\)\(a\)is the result of \([12](https://arxiv.org/html/2606.06687#S3.E12)\),\(b\)\(b\)bounds the spectral norm of𝑨s\\bm\{A\}\_\{s\}by its largest feasible eigenvalue, assumingΔ^k^,q⟂1\\hat\{\\Delta\}^\{\\hat\{k\},q\}\\perp 1, and\(c\)\(c\)expands the recursion\.

∎

## Appendix FProof of Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)

###### Proof\.

Given any global roundk∈𝒦k\\in\\mathcal\{K\}, we sum over the global gradients as follows:

∑q=0τa\+τr−1‖∇L~​\(𝜽k,q\)‖2=∑q=0τa−1‖∇L~​\(𝜽k,q\)‖2⏟\(i\)\+∑q=τaτr\+τa−1‖∇L~​\(𝜽k,q\)‖2⏟\(i​i\),\\sum\_\{q=0\}^\{\\tau\_\{a\}\+\\tau\_\{r\}\-1\}\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|^\{2\}=\\underbrace\{\\sum\_\{q=0\}^\{\\tau\_\{a\}\-1\}\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|^\{2\}\}\_\{\(i\)\}\+\\underbrace\{\\sum\_\{q=\\tau\_\{a\}\}^\{\\tau\_\{r\}\+\\tau\_\{a\}\-1\}\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|^\{2\}\}\_\{\(ii\)\},\(109\)where\(i\)\(i\)is the intra\-cluster regimek~\\tilde\{k\}withq∈\{0,⋯,τa−1\}q\\in\\\{0,\\cdots,\\tau\_\{a\}\-1\\\}, and\(i​i\)\(ii\)is the inter\-cluster regimek^\\hat\{k\}withq∈\{τa,⋯,τr\+τa−1\}q\\in\\\{\\tau\_\{a\},\\cdots,\\tau\_\{r\}\+\\tau\_\{a\}\-1\\\}\. We bound the two components of \([109](https://arxiv.org/html/2606.06687#A6.E109)\) separately, starting with the intra\-cluster regime component in \([109](https://arxiv.org/html/2606.06687#A6.E109)\)\(i\)\(i\)

∑q=0τa−1‖∇L~​\(𝜽k,q\)‖2​=\(a\)​∑s∈𝒮∑q=0τa−1‖∇L~s​\(𝜽^sk,q\)‖2\\displaystyle\\sum\_\{q=0\}^\{\\tau\_\{a\}\-1\}\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|^\{2\}\\overset\{\(a\)\}\{=\}\\sum\_\{s\\in\\mathcal\{S\}\}\\sum\_\{q=0\}^\{\\tau\_\{a\}\-1\}\\\|\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{k,q\}\_\{s\}\)\\\|^\{2\}\(110\)≤\(b\)​∑s∈𝒮L~s​\(𝜽^sk,0\)\+α​τa​η22​Γsη−α^s​η22​Γs\\displaystyle\\overset\{\(b\)\}\{\\leq\}\\sum\_\{s\\in\\mathcal\{S\}\}\\frac\{\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{k,0\}\_\{s\}\)\+\\frac\{\\alpha\\tau\_\{a\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\(111\)≤\(c\)​∑s∈𝒮\(L~s​\(𝜽^sk,0\)\+α​τa​η22​Γs\)η−α^​η22​Γ\\displaystyle\\overset\{\(c\)\}\{\\leq\}\\frac\{\\sum\_\{s\\in\\mathcal\{S\}\}\\left\(\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{k,0\}\_\{s\}\)\+\\frac\{\\alpha\\tau\_\{a\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\\right\)\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\\eta^\{2\}\}\{2\}\\Gamma\}\(112\)≤\(d\)​L~​\(𝜽k,0\)\+∑s∈𝒮α​τa​η22​Γsη−α^​η22​Γ\\displaystyle\\overset\{\(d\)\}\{\\leq\}\\frac\{\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\)\+\\sum\_\{s\\in\\mathcal\{S\}\}\\frac\{\\alpha\\tau\_\{a\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\\eta^\{2\}\}\{2\}\\Gamma\}\(113\)where\(a\)\(a\)is from‖∇L~​\(𝜽k,q\)‖2=\(∇L~​\(𝜽k,q\)\)T​∇L~​\(𝜽k,q\)=∑s∈𝒮\(∇L~s​\(𝜽^sk,q\)\)T​∇L~s​\(𝜽^sk,q\)\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|^\{2\}=\\left\(\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\right\)^\{T\}\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)=\\sum\_\{s\\in\\mathcal\{S\}\}\\left\(\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{k,q\}\_\{s\}\)\\right\)^\{T\}\\nabla\\tilde\{L\}\_\{s\}\(\\hat\{\\bm\{\\theta\}\}^\{k,q\}\_\{s\}\),\(b\)\(b\)follows from Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2),\(c\)\(c\)uses the fact thatΓ≥Γs\\Gamma\\geq\\Gamma\_\{s\}andα^s≥α^\\hat\{\\alpha\}\_\{s\}\\geq\\hat\{\\alpha\}so thatη−α^s​η22​Γs≥η−α^​η22​Γ\\eta\-\\frac\{\\hat\{\\alpha\}\_\{s\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\\geq\\eta\-\\frac\{\\hat\{\\alpha\}\\eta^\{2\}\}\{2\}\\Gamma, and\(d\)\(d\)uses the definition ofL~​\(⋅\)\\tilde\{L\}\(\\cdot\)from \([17](https://arxiv.org/html/2606.06687#S3.E17)\)\. Next, for term\(i​i\)\(ii\)in \([109](https://arxiv.org/html/2606.06687#A6.E109)\), we start by leveraging Proposition[IV\-A](https://arxiv.org/html/2606.06687#S4.SS1), as follows:

‖∇L~​\(𝜽k,q\)−∇L~​\(𝜽k,q−1\)‖≤\(γ^\+1\+1η​\(1−λN​\(𝑨\)\)\)​‖𝜽k,q−𝜽k,q−1‖\+τa​B​N\.\\displaystyle\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\-\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\-1\}\)\\\|\\leq\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\)\\right\)\\\|\\bm\{\\theta\}^\{k,q\}\-\\bm\{\\theta\}^\{k,q\-1\}\\\|\+\\tau\_\{a\}B\\sqrt\{N\}\.\(114\)Applying the triangle inequality to the left hand side of \([114](https://arxiv.org/html/2606.06687#A6.E114)\) and rearranging yields

‖∇L~​\(𝜽k,q\)‖≤‖∇L~​\(𝜽k,q−1\)‖\+\(γ^\+1\+1η​\(1−λN​\(𝑨\)\)\)​‖𝜽k,q−𝜽k,q−1‖\+τa​B​N\\displaystyle\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|\\leq\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\-1\}\)\\\|\+\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\)\\right\)\\\|\\bm\{\\theta\}^\{k,q\}\-\\bm\{\\theta\}^\{k,q\-1\}\\\|\+\\tau\_\{a\}B\\sqrt\{N\}\(115\)Next, we exploit the definition ofΔ^k,q\\hat\{\\Delta\}^\{k,q\}in Lemma[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)to obtain

𝜽k,q=𝜽¯k,q​𝟏−Δ^k,q\\bm\{\\theta\}^\{k,q\}=\\overline\{\\bm\{\\theta\}\}^\{k,q\}\\bm\{1\}\-\\hat\{\\Delta\}^\{k,q\}\(116\)and

𝑨~​Δ^k,q=𝑨~​𝜽¯k,q​𝟏−𝑨~​𝜽k,q​=\(e\)​𝜽¯k,q​𝟏−𝜽k,q\+1,\\tilde\{\\bm\{A\}\}\\hat\{\\Delta\}^\{k,q\}=\\tilde\{\\bm\{A\}\}\\overline\{\\bm\{\\theta\}\}^\{k,q\}\\bm\{1\}\-\\tilde\{\\bm\{A\}\}\\bm\{\\theta\}^\{k,q\}\\overset\{\(e\)\}\{=\}\\overline\{\\bm\{\\theta\}\}^\{k,q\}\\bm\{1\}\-\\bm\{\\theta\}^\{k,q\+1\},\(117\)where \([117](https://arxiv.org/html/2606.06687#A6.E117)\) holds only forq∈\{τa,⋯,τa\+τr−1\}q\\in\\\{\\tau\_\{a\},\\cdots,\\tau\_\{a\}\+\\tau\_\{r\}\-1\\\}and\(e\)\(e\)is from the fact that𝑨\{\\bm\{A\}\}is doubly stochastic\. Taking the difference between \([116](https://arxiv.org/html/2606.06687#A6.E116)\) and \([117](https://arxiv.org/html/2606.06687#A6.E117)\) gives

𝜽k,q\+1−𝜽k,q=Δ^k,q−𝑨​Δ^k,q=\(𝑰−𝑨\)​Δ^k,q,\\bm\{\\theta\}^\{k,q\+1\}\-\\bm\{\\theta\}^\{k,q\}=\\hat\{\\Delta\}^\{k,q\}\-\{\\bm\{A\}\}\\hat\{\\Delta\}^\{k,q\}=\(\\bm\{I\}\-\{\\bm\{A\}\}\)\\hat\{\\Delta\}^\{k,q\},\(118\)which can be bounded above by

‖𝜽k,q\+1−𝜽k,q‖​≤\(f\)​‖𝑰−𝑨‖​‖Δ^k,q‖\\displaystyle\\\|\\bm\{\\theta\}^\{k,q\+1\}\-\\bm\{\\theta\}^\{k,q\}\\\|\\overset\{\(f\)\}\{\\leq\}\\\|\\bm\{I\}\-\{\\bm\{A\}\}\\\|\\\|\\hat\{\\Delta\}^\{k,q\}\\\|\(119\)≤\(g\)​\(1−λN​\(𝑨\)\)​λ2​\(𝑨\)q−1​‖Δ^k,0‖,\\displaystyle\\overset\{\(g\)\}\{\\leq\}\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)\\lambda\_\{2\}\(\{\\bm\{A\}\}\)^\{q\-1\}\\\|\\hat\{\\Delta\}^\{k,0\}\\\|,\(120\)where\(f\)\(f\)is from norm of the right hand side of \([118](https://arxiv.org/html/2606.06687#A6.E118)\), and\(g\)\(g\)takes the largest eigenvalue of𝑰−𝑨\\bm\{I\}\-\{\\bm\{A\}\}and leverages Lemma[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)\. Substituting \([120](https://arxiv.org/html/2606.06687#A6.E120)\) into \([115](https://arxiv.org/html/2606.06687#A6.E115)\) enables the following:

‖∇L~​\(𝜽k,q\)‖≤‖∇L~​\(𝜽k,q−1\)‖\+\(γ^\+1\+1η​\(1−λN​\(𝑨\)\)\)​\(1−λN​\(𝑨\)\)​λ2​\(𝑨\)q−1​‖Δ^k,0‖\+τa​B​N,\\displaystyle\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|\\leq\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\-1\}\)\\\|\+\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\)\\right\)\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)\\lambda\_\{2\}\(\{\\bm\{A\}\}\)^\{q\-1\}\\\|\\hat\{\\Delta\}^\{k,0\}\\\|\+\\tau\_\{a\}B\\sqrt\{N\},\(121\)Expanding the recursive relationship in \([121](https://arxiv.org/html/2606.06687#A6.E121)\) then yields

‖∇L~​\(𝜽k,q\)‖≤‖∇L~​\(𝜽k,0\)‖\+\(γ^\+1\+1η​\(1−λN​\(𝑨\)\)\)​\(1−λN​\(𝑨\)\)​∑p=0q−1λ2​\(𝑨\)p​‖Δ^k,0‖\+\(q−1\)​τa​B​N,\\displaystyle\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|\\leq\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\)\\\|\+\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\)\\right\)\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)\\sum\_\{p=0\}^\{q\-1\}\\lambda\_\{2\}\(\{\\bm\{A\}\}\)^\{p\}\\\|\\hat\{\\Delta\}^\{k,0\}\\\|\+\(q\-1\)\\tau\_\{a\}B\\sqrt\{N\},\(122\)and, after squaring both sides,

‖∇L~​\(𝜽k,q\)‖2≤\{‖∇L~​\(𝜽k,0\)‖\+\(γ^\+1\+1η​\(1−λN​\(𝑨\)\)\)​\(1−λN​\(𝑨\)\)​∑p=0q−1λ2​\(𝑨\)p​‖Δ^k,0‖\+\(q−1\)​τa​B​N\}2\\displaystyle\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|^\{2\}\\leq\\left\\\{\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\)\\\|\+\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\)\\right\)\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)\\sum\_\{p=0\}^\{q\-1\}\\lambda\_\{2\}\(\{\\bm\{A\}\}\)^\{p\}\\\|\\hat\{\\Delta\}^\{k,0\}\\\|\+\(q\-1\)\\tau\_\{a\}B\\sqrt\{N\}\\right\\\}^\{2\}\(123\)≤\(h\)​2​‖∇L~​\(𝜽k,0\)‖2\+4​\(γ^\+1\+1η​\(1−λN​\(𝑨\)\)\)2​\(1−λN​\(𝑨\)\)2​\(11−λ2​\(𝑨\)​‖Δ^k,0‖\)2\+4​τa2​B2​N​\(q−1\)2,\\displaystyle\\overset\{\(h\)\}\{\\leq\}2\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\)\\\|^\{2\}\+4\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\)\\right\)^\{2\}\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)^\{2\}\\left\(\\frac\{1\}\{1\-\\lambda\_\{2\}\(\{\\bm\{A\}\}\)\}\\\|\\hat\{\\Delta\}^\{k,0\}\\\|\\right\)^\{2\}\+4\\tau\_\{a\}^\{2\}B^\{2\}N\(q\-1\)^\{2\},\(124\)where\(h\)\(h\)follows from\(a\+b\)2≤2​a2\+2​b2\(a\+b\)^\{2\}\\leq 2a^\{2\}\+2b^\{2\}applied twice and the fact that∑p=0q−1λ2​\(𝑨\)p≤∑p=0∞λ2​\(𝑨\)p=11−λ2​\(𝑨\)\\sum\_\{p=0\}^\{q\-1\}\\lambda\_\{2\}\(\{\\bm\{A\}\}\)^\{p\}\\leq\\sum\_\{p=0\}^\{\\infty\}\\lambda\_\{2\}\(\{\\bm\{A\}\}\)^\{p\}=\\frac\{1\}\{1\-\\lambda\_\{2\}\(\{\\bm\{A\}\}\)\}\. Summing \([124](https://arxiv.org/html/2606.06687#A6.E124)\) overq∈\{τa,⋯,τa\+τr−1\}q\\in\\\{\\tau\_\{a\},\\cdots,\\tau\_\{a\}\+\\tau\_\{r\}\-1\\\}yields

∑q=τaτa\+τr−1‖∇L~​\(𝜽k,q\)‖2​≤\(i\)​2​\(τr−1\)​‖∇L~​\(𝜽k,0\)‖2\\displaystyle\\sum\_\{q=\\tau\_\{a\}\}^\{\\tau\_\{a\}\+\\tau\_\{r\}\-1\}\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|^\{2\}\\overset\{\(i\)\}\{\\leq\}2\(\\tau\_\{r\}\-1\)\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\)\\\|^\{2\}\+4​\(τr−1\)​\(γ^\+1\+1η​\(1−λN​\(𝑨\)\)\)2​\(1−λN​\(𝑨\)\)2​\(‖Δ^k,0‖1−λ2​\(𝑨\)\)2\+4​τa2​B2​N​∑q=τaτa\+τr−1\(q−1\)2,\\displaystyle\+4\(\\tau\_\{r\}\-1\)\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\)\\right\)^\{2\}\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)^\{2\}\\left\(\\frac\{\\\|\\hat\{\\Delta\}^\{k,0\}\\\|\}\{1\-\\lambda\_\{2\}\(\{\\bm\{A\}\}\)\}\\right\)^\{2\}\+4\\tau\_\{a\}^\{2\}B^\{2\}N\\sum\_\{q=\\tau\_\{a\}\}^\{\\tau\_\{a\}\+\\tau\_\{r\}\-1\}\(q\-1\)^\{2\},\(125\)≤\(j\)​2​\(τr−1\)​‖∇L~​\(𝜽k,0\)‖2\+4​\(τr−1\)​\(γ^\+1\+1η​\(1−λN​\(𝑨\)\)\)2​\(1−λN​\(𝑨\)\)2​\(‖Δ^k,0‖1−λ2​\(𝑨\)\)2\\displaystyle\\overset\{\(j\)\}\{\\leq\}2\(\\tau\_\{r\}\-1\)\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\)\\\|^\{2\}\+4\(\\tau\_\{r\}\-1\)\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\)\\right\)^\{2\}\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)^\{2\}\\left\(\\frac\{\\\|\\hat\{\\Delta\}^\{k,0\}\\\|\}\{1\-\\lambda\_\{2\}\(\{\\bm\{A\}\}\)\}\\right\)^\{2\}\+4​τa2​B2​N​τr​\(τa\+τr−1\)2,\\displaystyle\+4\\tau\_\{a\}^\{2\}B^\{2\}N\\tau\_\{r\}\(\\tau\_\{a\}\+\\tau\_\{r\}\-1\)^\{2\},\(126\)where\(i\)\(i\)expands the summation overqqfor non\-qqdependent terms, and\(j\)\(j\)results from∑q=τaτa\+τr−1\(q−1\)2≤∑q=τaτa\+τr−1q2≤τr​\(τa\+τr−1\)2\\sum\_\{q=\\tau\_\{a\}\}^\{\\tau\_\{a\}\+\\tau\_\{r\}\-1\}\(q\-1\)^\{2\}\\leq\\sum\_\{q=\\tau\_\{a\}\}^\{\\tau\_\{a\}\+\\tau\_\{r\}\-1\}q^\{2\}\\leq\\tau\_\{r\}\(\\tau\_\{a\}\+\\tau\_\{r\}\-1\)^\{2\}\. Returning to \([109](https://arxiv.org/html/2606.06687#A6.E109)\), we combine the bounds for the intra\-cluster and the inter\-cluster terms as follows:

∑q=0τa\+τr−1‖∇L~​\(𝜽k,q\)‖2≤L~​\(𝜽k,0\)\+∑s∈𝒮α​τa​η22​Γsη−α^​η22​Γ\+2​\(τr−1\)​‖∇L~​\(𝜽k,0\)‖2\\displaystyle\\sum\_\{q=0\}^\{\\tau\_\{a\}\+\\tau\_\{r\}\-1\}\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,q\}\)\\\|^\{2\}\\leq\\frac\{\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\)\+\\sum\_\{s\\in\\mathcal\{S\}\}\\frac\{\\alpha\\tau\_\{a\}\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\\eta^\{2\}\}\{2\}\\Gamma\}\+2\(\\tau\_\{r\}\-1\)\\\|\\nabla\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\)\\\|^\{2\}\+4​\(τr−1\)​\(γ^\+1\+1η​\(1−λN​\(𝑨\)\)\)2​\(1−λN​\(𝑨\)\)2​\(‖Δ^k,0‖1−λ2​\(𝑨\)\)2\+4​τa2​B2​N​τr​\(τa\+τr−1\)2\\displaystyle\+4\(\\tau\_\{r\}\-1\)\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\)\\right\)^\{2\}\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)^\{2\}\\left\(\\frac\{\\\|\\hat\{\\Delta\}^\{k,0\}\\\|\}\{1\-\\lambda\_\{2\}\(\{\\bm\{A\}\}\)\}\\right\)^\{2\}\+4\\tau\_\{a\}^\{2\}B^\{2\}N\\tau\_\{r\}\(\\tau\_\{a\}\+\\tau\_\{r\}\-1\)^\{2\}\(127\)≤\(k\)​2​τr​L~​\(𝜽k,0\)\+\(τa\+2​\(τr−1\)\)​∑s∈𝒮α​η22​Γsη−α^​η22​Γ\\displaystyle\\overset\{\(k\)\}\{\\leq\}\\frac\{2\\tau\_\{r\}\\tilde\{L\}\(\\bm\{\\theta\}^\{k,0\}\)\+\(\\tau\_\{a\}\+2\(\\tau\_\{r\}\-1\)\)\\sum\_\{s\\in\\mathcal\{S\}\}\\frac\{\\alpha\\eta^\{2\}\}\{2\}\\Gamma\_\{s\}\}\{\\eta\-\\frac\{\\hat\{\\alpha\}\\eta^\{2\}\}\{2\}\\Gamma\}\+4​\(τr−1\)​\(γ^\+1\+1η​\(1−λN​\(𝑨\)\)\)2​\(1−λN​\(𝑨\)\)2​\(‖Δ^k,0‖1−λ2​\(𝑨\)\)2\+4​τa2​B2​N​τr​\(τa\+τr−1\)2,\\displaystyle\+4\(\\tau\_\{r\}\-1\)\\left\(\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\)\\right\)^\{2\}\\left\(1\-\\lambda\_\{N\}\(\{\\bm\{A\}\}\)\\right\)^\{2\}\\left\(\\frac\{\\\|\\hat\{\\Delta\}^\{k,0\}\\\|\}\{1\-\\lambda\_\{2\}\(\{\\bm\{A\}\}\)\}\\right\)^\{2\}\+4\\tau\_\{a\}^\{2\}B^\{2\}N\\tau\_\{r\}\(\\tau\_\{a\}\+\\tau\_\{r\}\-1\)^\{2\},\(128\)where\(k\)\(k\)leverages Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)withτa=1\\tau\_\{a\}=1and\. Finally, noting thatγ𝖾𝖿𝖿=γ^\+1\+1η​\(1−λN​\(𝑨~\)\)\\gamma^\{\\mathsf\{eff\}\}=\\hat\{\\gamma\}\+1\+\\frac\{1\}\{\\eta\}\(1\-\\lambda\_\{N\}\(\\tilde\{\\bm\{A\}\}\)\)and re\-arranging \([F](https://arxiv.org/html/2606.06687#A6.Ex12)\) completes the proof\.

∎

## Appendix GAdditional Experiments

As indicated within the main manuscript, we further evaluate SSD\-FL by varying link probabilities when the underlying network graph is an Erdős–Rényi random graph\[[9](https://arxiv.org/html/2606.06687#bib.bib52)\]for both heterogeneous and homogeneous device ML optimizers in Appendix[G\-A](https://arxiv.org/html/2606.06687#A7.SS1)\. Subsequently, we examine SSD\-FL when network devices have homogeneous SGD optimizers in appendix[G\-B](https://arxiv.org/html/2606.06687#A7.SS2)and further examine the properties of the bound in Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)via investigating the variation in normalized intra\-cluster gradients across datasets and local device ML optimizers in Appendix[G\-C](https://arxiv.org/html/2606.06687#A7.SS3)\.

### G\-AVarying Link Probabilities

We examine the impact of increasing link formation probabilities from10%10\\%to50%50\\%in random graphs in Fig\.[8](https://arxiv.org/html/2606.06687#A7.F8)and[9](https://arxiv.org/html/2606.06687#A7.F9)\. We do want to emphasize that, when link formation probability is100%100\\%, the random graph has equivalent structure to the complete graphs shown in Sec\.[VI\-E](https://arxiv.org/html/2606.06687#S6.SS5)\.

For the case with heterogeneous ML optimizers at devices in Fig\.[8](https://arxiv.org/html/2606.06687#A7.F8), we see that SSD\-FL either outperforms or matches the final accuracies of the baseline decentralized FL methodologies\. Moreover, relative to the sDFL and pDFL methodologies, SSD\-FL maintains a similar sized performance gap, roughly4%4\\%and13%13\\%respectively, regardless of the link formation probability and dataset\. Experiments with homogeneous ML optimizers in Fig\.[9](https://arxiv.org/html/2606.06687#A7.F9)yield the similar takeaways\.

![Refer to caption](https://arxiv.org/html/2606.06687v1/x8.png)A\)Experiments on the FMNIST dataset\.
![Refer to caption](https://arxiv.org/html/2606.06687v1/x9.png)B\)Experiments on the CIFAR10 dataset\.

Figure 8:Varying link formation probabilities from10%10\\%to50%50\\%for Erdős–Rényi random graphs\. We evaluate both \(a\) FMNIST and \(b\) CIFAR10 datasets for networks with3030devices,τa=3\\tau\_\{a\}=3,τr=1\\tau\_\{r\}=1, and heterogeneous ML optimizers at devices\.![Refer to caption](https://arxiv.org/html/2606.06687v1/x10.png)A\)Experiments on the FMNIST dataset\.
![Refer to caption](https://arxiv.org/html/2606.06687v1/x11.png)B\)Experiments on the CIFAR10 dataset\.

Figure 9:Varying link formation probabilities from10%10\\%to50%50\\%for Erdős–Rényi random graphs with homogeneous SGD optimizers at devices\. The experimental setup is the same as that in Fig\.[8](https://arxiv.org/html/2606.06687#A7.F8)aside from the choice of ML optimizers and, while the accuracies are lower, especially for CIFAR10 in Fig\.[9B\)](https://arxiv.org/html/2606.06687#A7.F9.sf2), the key takeaways remain identical\.
### G\-BHomogeneous SGD Optimizers

We list the experimental results for experiments varying intra\-cluster durationτa\\tau\_\{a\}in Fig\.[10](https://arxiv.org/html/2606.06687#A7.F10), inter\-cluster periodτr\\tau\_\{r\}in Tables[III](https://arxiv.org/html/2606.06687#A7.T3)\-[VI](https://arxiv.org/html/2606.06687#A7.T6), underlying network graph architectures in Fig\.[12](https://arxiv.org/html/2606.06687#A7.F12), and network size in Fig\.[11](https://arxiv.org/html/2606.06687#A7.F11)\. In particular, regarding the inter\-cluster period experiments, Tables[III](https://arxiv.org/html/2606.06687#A7.T3)and[V](https://arxiv.org/html/2606.06687#A7.T5)show results for networks with homogeneous SGD and heterogeneous optimizers across their devices, but only forτr=1\\tau\_\{r\}=1\. While the exact numerical results and convergence curves may differ, the core takeaways remain the same as those from heterogeneous local ML optimizers\.

![Refer to caption](https://arxiv.org/html/2606.06687v1/x12.png)A\)Experiments on the FMNIST dataset\.
![Refer to caption](https://arxiv.org/html/2606.06687v1/x13.png)B\)Experiments on the CIFAR10 dataset\.

Figure 10:Varying intra\-cluster periodτa\\tau\_\{a\}for random networks with of sizeN=10N=10with homogeneous SGD optimizers at devices\. Both FMNIST, in Fig\.[10A\)](https://arxiv.org/html/2606.06687#A7.F10.sf1), and CIFAR10, in Fig\.[10B\)](https://arxiv.org/html/2606.06687#A7.F10.sf2), are investigated for mild and extreme non\-i\.i\.d\. scenarios\.Table III:The average global cycles for methods to reach accuracy thresholds on FMNIST withτr=1\\tau\_\{r\}=1\. Networks with both SGD and heterogeneous optimizers are investigated\. Dashes indicate thresholds that were not reached\.Table IV:Average global cycles when methods reach or exceed accuracy points on FMNIST when networks have homogeneous SGD optimizers at devices\. Dashes indicate thresholds that were not reached\.Table V:The average global cycles for methods to reach accuracy thresholds on CIFAR10 withτr=1\\tau\_\{r\}=1\. Networks with both SGD and heterogeneous optimizers are investigated\. Dashes indicate thresholds that were not reached\.Table VI:Average global cycles required for methods to reach or exceed target accuracies on CIFAR\-10 with homogeneous SGD optimizers at devices\. Dashes indicate thresholds that were not reached\.![Refer to caption](https://arxiv.org/html/2606.06687v1/x14.png)A\)Experiments on the FMNIST dataset\.
![Refer to caption](https://arxiv.org/html/2606.06687v1/x15.png)B\)Experiments on the CIFAR10 dataset\.

Figure 11:Varying network size fromN=10N=10toN=50N=50with Erdős–Rényi random graph architecture and homogeneous SGD optimizers at devices\. While nominal final accuracies are lower than the case for heterogeneous ML optimizers at devices in Fig\.[4](https://arxiv.org/html/2606.06687#S6.F4)and[5](https://arxiv.org/html/2606.06687#S6.F5), the main takeaways remain the same\.![Refer to caption](https://arxiv.org/html/2606.06687v1/x16.png)A\)Experiments on the FMNIST dataset\.
![Refer to caption](https://arxiv.org/html/2606.06687v1/x17.png)B\)Experiments on the CIFAR10 dataset\.

Figure 12:Evaluation of SSD\-FL relative to decentralized FL baselines for various network architectures with homogeneous SGD optimizers at all devices\. Similar to the experiment involving heterogeneous ML optimizers at devices in Fig\.[6](https://arxiv.org/html/2606.06687#S6.F6)and[7](https://arxiv.org/html/2606.06687#S6.F7), SSD\-FL consistently demonstrates superior performance with complete networks being the exception\.
### G\-CNormalized Intra\-Cluster Gradients

We also investigate the impact of heterogeneous/homogeneous ML optimizers and intra\-cluster periodτa\\tau\_\{a\}on the average effective intra\-cluster first order stationary point from Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)\. While the nominal differences across datasets and optimizers are small in Fig\.[13](https://arxiv.org/html/2606.06687#A7.F13)and[14](https://arxiv.org/html/2606.06687#A7.F14), there is an important point\. Asτa\\tau\_\{a\}grows, the almost parabolic nature of average gradients shifts, yielding a different optimal number of clusters\. For instance, in Fig\.[13A\)](https://arxiv.org/html/2606.06687#A7.F13.sf1), we can see the optimal or minimum point shift fromS=4S=4toS=2S=2asτa\\tau\_\{a\}grows from11to55\. Moreover, we see similar takeaways when comparing heterogeneous and homogeneous ML optimizers or mild vs extreme non\-i\.i\.d\. data distributions \- these factors lead to minor differences in estimated average effective gradient but they shift the minima and scaling of estimated gradient with respect to the number of clusters\.

![Refer to caption](https://arxiv.org/html/2606.06687v1/x18.png)A\)Experiments with mild non\-i\.i\.d\. datasets at devices\.
![Refer to caption](https://arxiv.org/html/2606.06687v1/x19.png)B\)Experiments with extreme non\-i\.i\.d\. datasets at devices\.

Figure 13:Average intra\-cluster effective gradients from Theorem[IV\-B](https://arxiv.org/html/2606.06687#S4.SS2)for networks with heterogeneous ML optimizers at devices\. As the intra\-cluster periodτa\\tau\_\{a\}increases, the average intra\-cluster effective gradients decrease in relative magnitude\.![Refer to caption](https://arxiv.org/html/2606.06687v1/x20.png)A\)Experiments with mild non\-i\.i\.d\. datasets at devices\.
![Refer to caption](https://arxiv.org/html/2606.06687v1/x21.png)B\)Experiments with extreme non\-i\.i\.d\. datasets at devices\.

Figure 14:The influence of intra\-cluster periodτa\\tau\_\{a\}on the average intra\-cluster effective gradients for networks with homogeneous SGD optimizers at devices\.