1
Towards Serverless Semi-Decentralized Federated Learning with Heterogeneous Optimizers
arXiv:2606.06687v1 [cs.LG] 4 Jun 2026
Su Wang Member, IEEE, Mung Chiang, Fellow, IEEE, and H. Vincent Poor, Life Fellow, IEEE
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 semidecentralized 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, SSDFL 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, SSDFL 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.
I. I NTRODUCTION Based on the edge/fog network, FL methodologies [1], [2], [3] are partitioned into centralized and decentralized FL [4], as shown in Fig. 1. While centralized FL relies on a server to coordinate ML model training processes [5], [6], decentralized FL [7] 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 [8], [9], [10] 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 semidecentralized FL (SD-FL), these methodologies demonstrate Su 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: [email protected].
faster convergence and improved efficiency by leveraging predefined 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 [5], [11], [12]). 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 [13], [14], 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 Grids rely on D2D communications without global/central control, such as those involving D2D solar energy trading [15], [16]. 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 Networks for disaster recovery communications [17], [18] or multi-domain unmanned vehicle networks [19], [20] are similarly massively distributed and reliant on highly heterogeneous D2D communication links. In the case of natural disaster communications [17], [18], 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. •
2
Local ML Training
Semi-Decentralized FL
Centralized FL
Degree of Decentralization SSD-FL (Ours)
Fully Decentralized FL
Server
Regular D2D or D2S
D2D intra-cluster
D2D inter-cluster
ML model parameters
Clusters
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. A. Outline and Summary of Contributions In the following, we begin by reviewing relevant literature in Sec. II and present SSD-FL’s system model as well as theoretical background in Sec. III. Then, we derive the convergence and consensus properties of our proposed SSD-FL methodology in Sec. IV followed by the cluster algorithm of SSD-FL in Sec. V. Subsequently, we validate SSD-FL relative to baselines experimentally in Sec. VI before summarizing the key takeaways in Sec. VII. 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 onetime, 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 SSDFL 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. II. R ELATED W ORK 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. A. Clustering 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 [9], [10], [8], [21] in which devices are grouped into clusters. Within these clusters, devices follow gossip-based protocols (similar to decentralized FL methodologies [22], [23]) in order to achieve intra-cluster
3
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 [24], [25], [26], [27]. 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 [9], [28], [21] or derived from purely statistical properties (e.g., cosine similarity [10] or training progression [29], [30]). 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. B. Current 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 [14], [31], [32] 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 suggest. For such undirected edge/fog networks, existing methodologies [33], [34], [35] 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 [13], [36], periodic D2D communication [35], [22], or irregular D2D communication [23], [37] 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 [14], [38], 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 largescale edge/fog networks. Periodic decentralized FL [22], [35] 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 [22], [34], but introduce greater drift across devices, which can overfit locally and require more training time overall [7]. By contrast, stochastic decentralized FL methodologies [23], [37], [39] 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 intercluster 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. III. S YSTEM M ODEL In the following, we first describe our network model in Sec. III-A, the ML model training components in Sec. III-B, and theoretical background in Sec. III-C. A. Network model We model the edge/fog network as a graph G = {N , E}, where N = {1, · · · , N } denotes the set of devices/nodes and E represents the set of weighted active D2D edges/links, with (i, j) ∈ E if device i is able and willing to share ML model parameters with device j and vice versa. Given any i, j ∈ N , we assume that if the D2D link (i, j) exists, then so does (j, i). Since SSD-FL follows different D2D communication structures within and across clusters, we use separate graphs: G̃ = {N , Ẽ} for intra-cluster regimes and the full graph G for inter-cluster regimes. For the rest of this paper, noncalligraphic font represents the size of the corresponding set, e.g., N = |N |.
4
SSD-FL aims to partition the network graph G into a set of clusters or subgraphs S = {1, · · · , S}, with the subgraph for clusters s ∈ S defined as G̃s = {Ns , Ẽs } and their union denoted by G̃ = {N , Ẽ} ≡ {∪s∈S Ns , ∪s∈S Ẽs }. Here, Ns ⊂ N , represents a subset of the network’s nodes, while Es ⊂ E represents the weighted set of edges (i, j), ∀i, j ∈ Ns . Moreover, the set of clusters S is connected such that, given ′ ′ any two clusters s, s ∈ S, s ̸= s , there is a path from at least one device i ∈ Ns to another device k ∈ Ns′ through other ′ clusters ŝ ∈ S \ {s, s } if necessary. Within each cluster s ∈ S, the set of D2D links Ẽs is represented by adjacency matrix Ãs ∈ RNs ×Ns , where Ãs = [ãi,j ]1≤i,j≤N with ãi,j = 0 if (i, j) ̸= Es and 0 < ãi,j ≤ 1 otherwise. As in existing literature [40], [14], we consider these adjacency matrices to be doubly stochastic, i.e., Ãs 1 = ÃTs 1 = 1, with symmetry, i.e., ãi,j = ãj,i , being the result of undirected graphs. We stack these cluster adjacency matrices Ãs ∀s ∈ S diagonally, leading to a block diagonal adjacency matrix à ∈ RN ×N such that Ã1 · · · 0 .. .. à = ... (1) . . 0
· · · ÃS
for the full graph G̃ during intra-cluster regimes. Moreover, as each block Ãs is doubly stochastic, Ã is also doubly stochastic and symmetric. On the other hand, for inter-cluster regimes, the weighted set of D2D edges E induces a separate doubly stochastic adjacency matrix A = [ai,j ]1≤i,j≤N with ai,j ̸= ãi,j , ai,j = 0 if (i, j) ∈ / E, and 0 < ai,j ≤ 1 otherwise. With this structure, we next analyze the conductance of each cluster via the graph conductance Φ(G̃s ) defined as Φ(G̃s ) =
min
V⊆Ns 0<vol(V)≤ 12 vol(Ns )
ϕ(V),
the inter-cluster regime using k̂ such that t ∈ k̂ = {kτg + τa , · · · , kτg +τa +(τr −1)}. Similarly, we denote the set of all intra-cluster and inter-cluster regimes as K̃ and K̂ respectively. This form enables referencing the q-th step for both intracluster and inter-cluster regimes, e.g., (k̃, q) = kτg + q for q ∈ {0, · · · , τa − 1}, which we employ as superscripts within the ML mechanisms explained next. B. ML model training mechanisms We first explain the ML model training and D2D communications for intra-cluster regimes k̃ ∈ K̃, then summarize the network-wide consensus process under inter-cluster regimes k̂ ∈ K̂. During an intra-cluster regime k̃ and iteration q, all network devices i ∈ N locally train a set of ML model parameters θik̃,q ∈ Rd with the goal of minimizing its local loss function Li (θik̃,q |Di ) defined as D
Li (θik̃,q |Di ) =
where we define the volume P of V as vol(V) = i∈V di , the degree of node i as di = j∈Ns Ai,j , and the cut conductance of V with respect to Ns as ϕ(V). Formally, this ϕ(V) is defined as cut(V, V) , (3) ϕ(V) = min{vol(V), vol(V)} P where cut(V, V) = i∈V,j∈V Ai,j . In other words, the graph conductance Φ(·) 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. For brevity, we will refer to graph conductance simply as conductance throughout the rest of the manuscript. Within this structure, we assume a total of T operational instances, so that T = {1, · · · , T }, and organize T into a series of intra-cluster regimes of duration τa > 0 followed by inter-cluster regimes of duration τr > 0. Together, we combine intra-cluster and inter-cluster regimes into overarching global cycles of length τg = τa + τr , thus leading to a total of K = ⌊T /τg ⌋ global cycles with K = {0, · · · , K − 1}. Given any global cycle k ∈ K, we denote the intra-cluster regime as k̃ with t ∈ k̃ = {kτg , · · · , kτg + (τa − 1)} and represent
(4)
h=1
where ℓh : Rd → R is the loss function for the h-th datum with features xh ∈ Rw×z and label yh ∈ R, Di denotes the dataset at device i, and Di denotes the dataset size. For future expressions, we will omit the Di dependence within the expression of Li (·) as well as the (xh , yh ) dependence for expressions involving ℓh . Moreover, similar to existing literature [40], [41], d is set to 1 to clarify analysis through vector variables. To minimize their local loss functions in (4), each device i ∈ N updates its local ML model parameters θik̃,q using the gradient of (4), expressed as D
∇Li (θik̃,q ) =
i 1 X ∇ℓh (θik̃,q ). Di
(5)
h=1
(2) P
i 1 X ℓh (θik̃,q |(xh , yh )), Di
In practice, the full gradient in (5) is often approximated by a stochastic gradient, 1 X gi (θik̃,q ) = ∇ℓh (θik̃,q ), (6) M h∈DiB,k̃,q
where DiB,k̃,q denotes a randomly sampled mini-batch of M data from Di at the q-th instance during the k̃ intra-cluster regime. Using (6), devices i ∈ 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. •
Proximal SGD with 0 ≤ µi < 1 being the proximal parameter [42]: g̃i (θik̃,q ) = gi (θik̃,q ) + µi (θik̃,q − θik̃,0 ), ∀q, i.
•
(7)
(8)
SGD with momentum where 0 ≤ ρi < 1 is the momentum parameter [43]: g̃i (θik̃,q ) = gi (θik̃,q ) +
q−1 X ρq−p gi (θik̃,p ), ∀q, i. i p=0
(9)
5
Combined, (7)-(9) yields an aggregate expression for the local stochastic gradients: g̃i (θik̃,q ) = gi (θik̃,q ) +
q−1 X ρq−p gi (θik̃,p ) + µi (θik̃,q − θik̃,0 ), i p=0
(10) which enables devices i ∈ N to choose their specific optimizer, e.g., µi = ρi = 0 indicates standard SGD while µi > 0 and ρi = 0 indicates SGD with momentum. Thus, given an intra-cluster regime k̃ ∈ K̃ and cluster s ∈ S, each device i ∈ Ns would simultaneously update and share their local ML model among neighbors with active D2D links via X ãsj,i θjk̃,q − ηg̃i (θik̃,q ), (11) θik̃,q+1 = j∈Ns
where ãsj,i is the (j, i)-th entry of the s-th cluster’s adjacency P k̃,q s matrix Ãs , represents the weighted sum of j∈Ns ãj,i θj device i’s neighboring ML models from the q-th iteration and η > 0 is the learning rate. Combining the individual device update rule in (11) for a cluster s, we then obtain θ̂sk̃,q+1 = Ãs θ̂sk̃,q − η G̃s (θ̂sk̃,q ),
(12)
to local ML model parameters (i.e., smoother training for devices i ∈ Ns with µi > 0), and term (d) integrates active D2D interaction via a graph regularization term: T ∥θ̂sk̃,q ∥2Is −Ãs = θ̂sk̃,q (Is − Ãs )θ̂sk̃,q X (16) ãj,i (θik̃,q − θjk̃,q )2 . = i,j∈Ns
The form of (16) thus encourages consensus among devices i ∈ Ns belonging to the same cluster h s and with i active D2D links ãj,i > 0. Moreover, since E ∇F̃s (θ̂sk̃,q ) = ∇L̂s (θ̂sk̃,q ), we can confirm that, in (14), clusters s ∈ S are performing forms of gradient descent with respect to the effective loss function in (15). These properties for L̃s also hold at the global level, across the sum for all clusters. Since à consists of blocks Ãs with all s ∈ S, the effective global loss function can be expressed as the sum of (15) over all clusters s ∈ S as follows: XX L̃(θ k̃,q ) = Li (θik̃,q ) s∈S i∈Ns
+
where
X
θik̃,q
G̃s (θ̂sk̃,q ) = Gs (θ̂sk̃,q ) +
+
ρq−p ⊙ Gs (θ̂sk̃,p ) s (13)
p=0
X µi i∈N
(17)
p=0
i∈N q−1 X
q−1 X ρq−p ∇Li (θik̃,p ) i
2
∥θik̃,q − θik̃,0 ∥2 +
1 k̃,q 2 ∥θ̂ ∥ , 2η s I−Ã
+ µs ⊙ θ̂sk̃,q − θ̂sk̃,0 , h i , ρqs = [ρqi ]i∈Ns , µs = [µi ]i∈Ns , Gs (θ̂sk̃,q ) = gi (θik̃,q ) i∈Ns and ⊙ denotes the Hadamard product. In (12), 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 as follows: 1 θ̂sk̃,q+1 = θ̂sk̃,q − η G̃s (θ̂sk̃,q ) + (Is − As ) θ̂sk̃,q , (14) η | {z }
where I is the identity matrix of similar dimension to Ã. Thus, across all clusters s ∈ S, network devices i ∈ N collectively aim to minimize their local loss (and local proximal terms if ρi > 0) while improving cluster-wide consensus, during intracluster regimes k̃ ∈ K̃. On the other hand, during inter-cluster regimes k̂ ∈ K̂, all network devices i ∈ 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 graph G and thus adjacency matrix A, yielding
where we use Is to denote the identity matrix of identical dimension to As . From (14), the stochastic gradient update is consequently ∇F̃s (θ̂sk̃,q ), which indicates that SSD-FL minimizes the stochastic gradient of an “effective” intra-cluster loss function. By reversing this gradient, ∇F̃s (·), we formally define the effective intra-cluster loss function as follows:
for a total of τr iterations. These inter-cluster updates represent a diffusion process over the global network graph G, whose efficiency depends on the connectivity within 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 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.
≜∇F̃s (θ̂sk̃,q )
L̃s (θ̂sk̃,q ) =
X
Li (θik̃,q ) +
+
X µi i∈Ns
|
2
{z
(a)
}
∥θik̃,q − θik̃,0 ∥2 + {z
(c)
θik̃,q
}
q−1 X ρq−p gi (θik̃,p ) i p=0
i∈Ns
i∈Ns
|
X
{z
|
(b)
1 k̃,q 2 ∥θ̂ ∥ , 2η s Is −As | {z }
} (15)
(d)
where terms (a) and (b) assess the ML model qualities via functions of loss (with term (b) active only for devices i ∈ Ns with ρi > 0), term (c) minimizes sudden or dynamic changes
θ k̂,q+1 = AT θ k̂,q ,
(18)
C. Theoretical Background We next define theoretical properties underpinning SSDFL’s convergence and consensus properties, which we present in Sec. IV. To this end, we first explain assumptions on the
6
device-level loss functions from (4), beginning with smoothness and bounded gradients. Assumption 1 (Smoothness). The loss functions Li (·) are γi Lipschitz smooth, where γi > 0 and ∀i ∈ N . Formally, ∥∇Li (θ1 ) − ∇Li (θ2 )∥ ≤ γi ∥θ1 − θ2 ∥,
(19)
where θ1 , θ2 ∈ Rd . Assumption 2 (Bounded Gradients). The gradients of loss functions ∇Li (·) are bounded ∀i ∈ N and ∀θi as follows: ∥∇Li (θi )∥ ≤ B,
(20)
where 0 < B < ∞. We will leverage Assumptions 1 and 2 together to simplify the effective global loss of (17) and subsequently prove convergence of SSD-FL. As such, we also need to formalize properties for the adjacency matrices à and A as follows: Assumption 3 (Adjacency Matrix Properties). The adjacency matrices à and A are both assumed to have the following properties: (i) doubly stochastic such that Ã1 = A1 = 1 and ÃT 1 = AT 1 = 1, (ii) I ⪰ à ≻ 0 and I ⪰ A ≻ 0, where ⪰ and ≻ denote positive semi-definite and positive definite respectively, and (iii) symmetric such that à = ÃT and A = AT . As a consequence of Assumption 3, we have that, via the doubly stochastic condition and the Perron-Frobenius Theorem [44], the largest eigenvalue of both à and A are 1, and that, via the positive definite property, the eigenvalues of à and A are real and strictly positive, i.e., λ1 (A) = 1 ≥ λ2 (A) ≥ · · · ≥ λi (A) > 0 where λm (A) denotes the mth largest eigenvalue of A. The final assumption relates to variability in the effective intra-cluster loss functions defined in (15). Assumption 4 (Bounded Gradient Variances). For any intracluster regime k̃, k ∈ K, cluster s ∈ S, and instance 0 ≤ q < τa − 1, there exist scalars α, αs ≥ 0 such that h i Var ∇F̃s (θ̂sk̃,q ) ≤ α + αs ∥∇L̃s (θ̂sk̃,q )∥2 . (21) Since ∇F̃s (θ̂sk̃,q ) is the unbiased estimate of the effective intra-cluster gradient ∇L̃s (θ̂sk̃,q ), Assumption 4 follows naturally. Finally, as a result of Assumption 4, we have that 2 2 E ∇F̃s (θ̂sk̃,q ) ≤ α + α̂s ∇L̃s (θ̂sk̃,q ) , (22) where α̂s = αs + 1. In both (21) and (22), the constant α depicts baseline variance, i.e., variance floor when ∥∇L̃s (θ̂sk̃,q )∥2 ≈ 0, and thereby describes the gradient noise of the stochastic effective gradient ∇F̃s (θ̂sk̃,q ) independent of other variables such as specific intra-cluster regime k̃ ∈ K̃. Meanwhile, αs and, by extension, α̂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 . In practice, both αs and thus α̂s are influenced by dataset and optimizer heterogeneity within each cluster s ∈ S, and we develop a methodology for their estimation in Sec. V.
IV. T HEORETICAL R ESULTS In the following, we prove integrated (joint intra- and intercluster) convergence across global rounds k ∈ K for SSD-FL. This analysis presents several non-trivial challenges relative to existing decentralized FL convergence results. The heterogeneous optimizer structure in (10) requires construction of an effective loss function in (15), whose smoothness properties require new treatment of gradient gaps across momentum, proximal, and graph regularization terms simultaneously in Sec. IV-A. Subsequently, in Sec. IV-B, we explain the integrated convergence of SSD-FL across intra- and inter-cluster regimes in Theorem 2, which leverages the results in Sec. IV-A and cannot be obtained by direct application or extension of single regime (intra- or inter-cluster) analysis. A. Effective loss function properties Given any intra-cluster regime k̃ ∈ K̃, we bound the gradient gap for effective intra-cluster loss functions, considering the option for heterogeneous optimizers therein. Proposition 1. (Gradient Gap of Effective Intra-cluster Loss) Given two instances q1 and q2 such that q1 ̸= q2 and q1 , q2 < τa within any intra-cluster regime k̃ ∈ K̃, the cluster-level regularized loss functions L̃s (θ̂sk̃,q1 ) and L̃s (θ̂sk̃,q2 ) , ∀s ∈ S have bounded gradient gap as follows: p ∇L̃s (θ̂sk̃,q1 ) − ∇L̃s (θ̂sk̃,q2 ) ≤ γseff ∥θ̂sk̃,q1 −θ̂sk̃,q2 ∥+τa B Ns (23) where 1 (24) γseff = γ̂s + 1 + (1 − λNs (As )) , η and γ̂s = maxi∈Ns γi . Similarly, for global-level regularized loss functions L̃(θ k̃,q1 ) and L̃(θ k̃,q2 ), the gradient gap is √ ∇L̃(θ k̃,q1 ) − ∇L̃(θ k̃,q2 ) ≤ γ eff θ k̃,q1 − θ k̃,q2 +τa B N , (25) where 1 γ eff = γ̂ + 1 + 1 − λN (Ã) , (26) η and γ̂ = maxi∈N γi . Proof. See Appendix A.
■
The gradient gap in Proposition 1 extends the smoothness assumption with standard loss functions in (4) to effective intra-cluster loss functions from (15). With it, we subsequently establish a corresponding loss gap between any two iterations q1 , q2 ∈ k̃, for all k̃ ∈ K̃ as follows: Corollary 1. (Effective Intra-cluster Loss Gap) Given two instances q1 and q2 such that q1 ̸= q2 and q1 , q2 < τa within any intra-cluster regime k̃ ∈ K̃, the cluster-level effective loss functions L̃s (θ̂sk̃,q1 ) and L̃s (θ̂sk̃,q2 ) , ∀s ∈ S have bounded gap as follows: T L̃s (θ̂sk̃,q1 ) ≤ L̃s (θ̂sk̃,q2 ) + ∇L̃s (θ̂sk̃,q2 ) θ̂sk̃,q1 − θ̂sk̃,q2 p 1 eff γ + τa B Ns ∥θ̂sk̃,q1 − θ̂sk̃,q2 ∥2 . + 2 s (27)
7
■
Proof. See Appendix B.
Together, Proposition 1 and Corollary 1 generalize conventional smoothness property of local loss functions to their effective intra-cluster loss function counterparts. In this regard, from (23), (25), and (27), we see that the smoothness of L̃s (·) is preserved, with√additive √ terms determined by the size of the cluster/network ( Ns or N ) and the intra-cluster regime duration, τa . B. SSD-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: Theorem 1. (Intra-cluster Convergence) If η < α̂s2Γs , then, given any intra-cluster regime k̃ ∈ K̃ and cluster s ∈ S, we bound the first-order stationary point as follows: τX a −1
∇L̃s (θ̂sk̃,q )
2
2
≤
L̃s (θ̂sk̃,0 ) + ατ2a η Γs 2
η − α̂s2η Γs
q=0
where
p Γs = γseff + τa B Ns .
(28)
(29)
k̃,τa
a where ∆k̃,τ = θs s
When the baseline variance of the effective intra-cluster stochastic gradient is near zero, i.e., α ≈ 0, such as when batches are the size of the full dataset per the discussion in Assumption 4, then Theorem 1 implies that 2 Pτa −1 L̃ (θ̂ k̃,0 ) ∇L̃s (θ̂sk̃,q ) ≤ sα̂s ηs2 . In other words, the firstq=0 η−
2
τ −1
a 2 1 L̃s (θ̂sk̃,0 ) 1 X ∇L̃s (θ̂sk̃,q ) ≤ lim → 0, 2 τa →∞ τa τa →∞ τa η − α̂s η Γ s q=0 2 (30) and therefore ∇L̃s (θ̂sk̃,q ) → 0 for all q ∈ k̃. By contrast, for stochastic gradients with non-trivial batches, α > 0 and thus the average first-order stationary point as τa → ∞ is bounded
lim
αη 2 2 Γs 2 η− α̂s2η Γs
■
For individual clusters s ∈ S, the two terms in Lemma 1 highlight competing effects in intra-cluster regimes. While the initial intra-cluster disagreement decreases exponentially √ in term (31)(a) as a result of λ2 (As ) + η < 1, the 2ητa B Ns component of (31)(b) grows linearly with respect to the duration √of the intra-cluster regime τa . Specifically, we refer to 2ητa B Ns as a cumulative gradient noise from bounding the gradient of the effective intra-cluster loss function L̃s (θ̂sk̃,q ) and therein the heterogeneous optimizer choices embedded via ρ and µ. As a result, Lemma 1 implies that consensus is not assured within individual clusters s ∈ S even though they demonstrate convergence in Theorem 1. This motivates inter-cluster regimes k̂ ∈ K̂ in SSD-FL, as the network can thus synchronize all devices i ∈ N as well as re-balance the cumulative gradient noise within clusters s ∈ S. In this regard, we next show the inter-cluster consensus: Lemma 2. (Inter-cluster consensus) Given any instance q within an inter-cluster regime k̂ ∈ K̂ and assuming that ˆ k̂,q ⊥ 1s , we bound the inter-cluster consensus gap as ∆ ˆ k̂,τr ≤ λ2 (A)τr −1 ∆ ˆ k̂,0 , ∆ ˆ k̂,q = θ where ∆
k̂,q
1 − θ k̃,q , and θ
k̂,q
= N1
P
(32)
i∈N θ
k̂,q
. ■
Proof. See Appendix E.
From (32), it is immediate that all devices i ∈ N reach consensus in exponential fashion, as Assumption 3 implies λ2 (A) < 1. Thus, inter-cluster regimes k̂ ∈ K̂ integrate the intra-cluster regime convergences from Theorem 1 across all clusters s ∈ S. Formally, we prove integrated convergence across full global rounds k ∈ K, obtaining the following result. Theorem 2. (Integrated Convergence) Let η ≤ mins∈S {1 − λ2 (Ãs ), α̂s2Γs }, then, for all global cycles k ∈ K, we have bounded first-order stationary point as follows:
. 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. Lemma 1. (Intra-cluster consensus gap) For any intra-cluster regime k̃ ∈ K̃ and assuming that ∆k̃,q ⊥ 1s and η < s 1 − λ2 (As ), the intra-cluster cluster consensus gap can be bounded above as follows: √ 2ητa B Ns k̃,τa τa −1 k̃,0 ∆s ≤ (λ2 (As ) + η) ∆s + , | {z } |1 − η −{zλ2 (As )} (a)
k̃,τa . i∈Ns θs
P
Γs
order stationary point becomes bounded by a constant independent of the intra-cluster regime duration τa . Consequently, for large τa → ∞, the average first-order stationary point is bounded above by zero
by a constant, specifically
= N1s
Proof. See Appendix D.
■
Proof. See Appendix C.
k̃,τa
1s − θ̂sk̃,τa , and θ s
(b)
(31)
τr +τ a −1 X
∇L̃(θ
k,q
2
)
≤
q=0
(2τr − 1)L̃(θ k,0 ) + αC1
P
s∈S Γs
2 η − α̂η2 Γ
eff 2 γ (1 − λN (A)) ˆ k,0 ∥2 + 4C2 + 4(τr − 1) ∥∆ 1 − λ2 (A) (33) √ 2 where Γ = γ eff + τa B N , C1 = (τa +2τ2r −2)η , C2 = τa2 B 2 N τr (τa + τr − 1)2 , and α̂ = maxs∈S α̂s . Proof. See Appendix F.
■
Aside from L̃(θ k,0 ), all other terms on the right hand side of 33 remain constants independent of the global round k ∈ K.
8
As such, since effective global loss from (17) can be bounded by L̃max for all k ∈ K, we have that, as K → ∞, 1 K→∞ K lim
≤
r −1 X τa +τ X
k∈K
q=0 k,0
(2τr − 1)L(θ
+ 4(τr − 1)
∇L(θ k,q )
) + αC1
2
P
s∈S Γs α̂η 2 η− 2 Γ eff 2 γ (1 − λN (A)) ˆ k,0 2
1 − λ2 (A)
∥∆
(34)
∥ + 4C2 .
In other words, the average global first-order stationary point, integrated across intra-cluster regimes k̃ ∈ K̃ and inter-cluster regimes k̂ ∈ K̂, is bounded above by a constant independent of the global round k. Therefore, Theorem 2 indicates that SSDFL yields bounded global convergence, with finite effective global loss function gradients.
Algorithm 1 C LUSTER F ORMATION IN SSD-FL 1: Input: Network graph G = (N , A), intra-cluster duration
τa , inter-cluster duration τr , learning rate η, bound B, maximum tolerable consensus gap ∥∆tol S ∥, and effective smoothness coefficients γseff and γ eff . 2: Output: Optimal set of clusters S ∗ . 3: Initialize sets of candidate partitions S̃ = {{G}}, estimated average first-order stationary points H̃ = {}, and minimum conductance thresholds Φmin = {}. 4: Initialize Ŝ = {G} as the starting partition of the original network G. 5: while |Ŝ| ≤ N do 6: Determine conductance threshold Φmin via (37). |Ŝ| 7:
η− 2 Γs o d relies on αs and αs , ∀s ∈ Ŝ, estimates via the processes
V. C LUSTER F ORMATION The theoretical results on convergence and consensus of SSD-FL in Sec. IV assumed a general case with 1 ≤ S ≤ N total clusters to partition the network of N devices. Now, we leverage those results to develop SSD-FL’s cluster formation algorithm, determining both an optimal number of clusters S = |S| and the constituent devices therein, i.e., Ns , ∀s ∈ S. The key cluster formation steps are summarized in Algorithm 1. A. Conductance criteria To develop a conductance criteria for cluster formation, we revisit Lemma 1. For the first global round k = 0, the intracluster consensus gap ∥∆k̃,0 s ∥ = 0 for any and all possible clusters s ∈ S and S ∈ {1, · · · , N } (as the optimal number of clusters S is unknown), specifically because network devices are initialized with the same local ML model parameters so that θi0,0 = θj0,0 ∀i, j ∈ N . Setting ∥∆tol ∥ as the limit on the tolerable consensus gap across all k̃ ∈ K̃, we can then obtain the following by rearranging Lemma 1 for any cluster s ∈ S and S ∈ {1, · · · , N } p 2ηB ⌊N/S⌋ ≤ 1 − λ2 (Ãs ). (35) η+ ∥∆tol ∥ Noting that I − Ãs is equivalent to the normalized Laplacian for any cluster s ∈ S as a result of Assumption 3, we can then leverage Cheeger’s inequality [45], which states that 2 (Φmin S ) ≤ 1 − λ2 (Ãs ) (36) 2 where Φmin denotes the minimum conductance threshold for S S ∈ {1, · · · , N }. By inspection of (35) and (36), we have that s p 4ηB ⌊N/S⌋ min ΦS = 2η + . (37) ∥∆tol ∥
To summarize, given some set of clusters S, (37) adapts a minimum conductance threshold Φmin inversely proportional S to the maximum tolerable intra-cluster consensus gap ∆tol S . Moreover, Φmin changes with the number of clusters, as larger S
Track the average (over clusters Ŝ) intra-cluster firstorder stationary point from Theorem 1 in (28), i.e., 2 P L̃ (θ̂ k̃,0 )+ ατa η Γ 1 H̃ ← H̃ ∪ Ŝ s∈Ŝ s s α̂s η2 2 s . This average
in (38)-(41) to obtain αs . Sort clusters s ∈ Ŝ in ascending conductance, i.e., let Q = {s(1) , . . . , s(|S|) } ← sorts∈Ŝ (Φ(G̃s )). 9: Ŝ ← S PECTRAL PARTITIONING(Φmin S , Q). 10: Update set of all candidate partitions, S̃ ← S̃ ∪ {Ŝ}. 11: end while 12: Find the optimal cluster S ∗ that satisfies the conductance with minimum average first-order requirements in Φmin S stationary point, i.e., S ∗ = arg minS∈S̃ H̃ subject to mins∈S Φ(G̃s ) ≥ Φmin S . 13: Return S ∗ . 8:
S in (37) reduces the conductance requirement for each cluster s ∈ 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).
B. Integration of heterogeneous optimizers Within any cluster s ∈ S, the internal cluster heterogeneity influences relative gradient norm amplification αs and α̂s as per Assumption 4, and, in turn, α̂s greatly influences the resulting convergence results in Theorem 1 and 2. As the two primary forms of D2D heterogeneity are at the data-level and optimizer-level, we define αs = αso + αsd where αso and αsd are the optimizer-induced and data-induced gradient norm amplification coefficients respectively. Since both αso and αsd measure internal cluster differences, we obtain them via D2D pairwise comparisons. Towards optimizer-induced heterogeneity, we first obtain 1 X X ζ1 1[opti ̸=optj ] + ζ2 ∥µi − µj ∥ + ζ3 ∥ρi − ρj ∥, Ns2 i∈Ns j∈Ns (38) where ζ1 , ζ2 , and ζ3 are scaling coefficients for differentials in optimizer, proximal parameters µi and µj , and momentum βso =
9
parameters ρi and ρj . Subsequently, we linearly scale βso to obtain αso as follows αso =
βso (αo,max − αo,min ) + αo,min , ζ1 + ζ2 + ζ3
(39)
where αo,max and αo,min denote the max and min contributions to optimizer heterogeneity scaling in αso , respectively. On the other hand, the data heterogeneity estimation relies on a combination of empirical average Jensen-Shannon divergence (JSD) [46] of relative frequencies and empirical energy distance (EED) [47] of a sample of raw data from device-level datasets. We express this as X 1 1 d JSD(Yi ∥Yj ) + EED(D̂i , D̂j ) , (40) βs = wz |Ẽs | i,j∈Ns (i,j)∈Ẽs
where |Ẽs | denotes the cardinality of Ẽs , JSD represents the Jensen-Shannon divergence, Yi is the relative frequency of labels within device i’s dataset DiP , wz represents the total data features, EED(D̂i , D̂j ) = D̂ 2D̂ h∈D̂i ,m∈Dˆj ∥xh − xm ∥ − i jP P 1 1 h,m∈D̂i ∥xh − xm ∥ − D̂ 2 h,m∈D̂j ∥xh − xm ∥ as the D̂ 2 i
j
squared empirical energy distance from [47], and D̂i denotes a randomly chosen batch of data of size D̂i from device i. Note that |D̂i | = |D̂j |, for any (i, j) ∈ Ẽs . The structure of (40) 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 D̂i and 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 , we scale βsd linearly as in (39), obtaining αsd = βsd (αd,max − αd,min ) + αd,min d,max
(41)
d,min
where α and α denote the max and min contributions to D2D data heterogeneity scaling in αsd , respectively. C. Combined cluster formation At a high level, SSD-FL’s cluster formation, summarized in Algorithm 1, iteratively partitions the network based on spectral structure and expected ML model training convergence (i.e., Theorem 1). Specifically, SSD-FL iteratively increases the number of clusters |S| from 1 to N , the size of the network. Starting with the original network graph G = (N , A), we denote the current partition of the network as Ŝ, and thus start with Ŝ = {G} (and single cluster as |Ŝ| = 1). SSDFL then computes the conductance Φ(G̃s ) of each subgraph s ∈ Ŝ using (2), and simultaneously determines the minimum conductance threshold Φmin from the Cheeger-based bound S in (37). For each iteration, SSD-FL evaluates the current cluster set Ŝ via Theorem 1 (and the αs estimation process from Sec. V-B) to obtain an average effective intra-cluster firstorder stationary point, stored in H̃. Simultaneously, SSD-FL
Algorithm 2 S PECTRAL PARTITIONING 1: Input: Conductance threshold Φmin and sorted clusters Ŝ
Q = {s(1) , . . . , s(|S|) }. 2: Output: Updated and partitioned cluster set Q. 3: for Each cluster s ∈ Q do 4: Compute Fiedler eigenvector ν2 (s) and obtain sorted indices π = argsort(ν2 (s)). 5: Initialize minimum conductance of possible partitions Φ̃min Q ← 0. 6: for Index n = 1 to |s| do 7: Define two candidate subsets: san = {π(1), . . . , π(n)} and sbn = s \ san . 8: Compute minimum conductance: Φn = min{Φ(G̃san ), Φ(G̃sbn )}. 9: if Φn > Φ̃min then Q 10: Update minimum conductance of possible partitions, Φ̂min ← Φn . Ŝ 11: Update intermediary best candidate partition, P ← {san , sbn }. 12: end if 13: end for 14: if Φ̂min ≥ Φmin then Ŝ Ŝ 15: Update cluster set: Q ← (Q \ {s}) ∪ P. 16: return Q. 17: else if Φ̂min < Φmin and s is s(1) then Ŝ Ŝ 18: Save the best candidate partition, P̃ ← P. 19: end if 20: end for 21: Update cluster set: Q ← (Q \ {s(1) }) ∪ P̃. 22: return Q.
ranks the clusters within the current cluster set, i.e., s ∈ Ŝ, in ascending order of their conductance, forming a sorted set Q = {s(1) , . . . , 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. In this process, each cluster s ∈ Q, starting with s(1) , is partitioned by analyzing the Fiedler eigenvector ν2 (s) of its normalized Laplacian matrix, which corresponds to Is − Ãs as a result of Assumption 3. Within the Fiedler vector ν2 (s), devices with similar eigenvector values are more connected, while those with large gaps indicate weaker connectivity [45]. SSD-FL sweeps through ν2 (s), identifying the partition P = {sa , sb } of s with the largest minimum conductance. If partition P has conductance over threshold Φmin S , then the set Q is updated as Q = (Ŝ \ {s}) ∪ {sa , sb }. Otherwise, SSD-FL proceeds to the next smallest conductance cluster s(n) in Q. However, if no partition satisfies the threshold, then the original cluster with the smallest conductance, i.e., s(1) , will be partitioned following the above rules. This post-partition cluster candidate is then stored as the new Ŝ and in the candidate set S̃. SSD-FL continues the above process iteratively, until |Ŝ| = N , or, in other words, there is a candidate partition of every feasible size for a network with N devices. Among these possible partitions S ∈ S̃, SSD-FL determines S ∗ =
10
pDFL pDFL pDFL
66
iii) Mild a = 5 75 70
65
65
v) Extreme a = 3 44
47
40
42
35
36
37
0
5
10 15 20
32
Global Cycle
0
5
10 15 20
Global Cycle
a=5 a=3 a=1
48
vi) Extreme a = 5
38
32
cSTC cSTC cSTC
80
70
iv) Extreme a = 1
41
STC STC STC
ii) Mild a = 3
80 75
70
62
Accuracy (%)
i) Mild a = 1
sDFL sDFL sDFL
Accuracy (%)
Accuracy (%)
74
SSD-FL (Ours) SSD-FL (Ours) SSD-FL (Ours)
32
Accuracy (%)
a=5 a=3 a=1
0
5
10 15 20
Global Cycle
SSD-FL (Ours) SSD-FL (Ours) SSD-FL (Ours)
i) Mild a = 1
sDFL sDFL sDFL
58
pDFL pDFL pDFL
ii) Mild a = 3
STC STC STC
61
46
54
56
44
50
51
cSTC cSTC cSTC
iii) Mild a = 5
42 46 46 v) Extreme a = 3 iv) Extreme a = 1 vi) Extreme a = 5 30 37 33 28 33 30 26 29 27 24 24 25 0 5 10 15 20 0 5 10 15 20 0 5 10 15 20
Global Cycle
Global Cycle
Global Cycle
FIGURE 2: Varying intra-cluster period τa for FMNIST. SSD-FL’s advantage over baselines grows with τa , and remains consistent across both mild and extreme heterogeneity settings.
FIGURE 3: Varying intra-cluster period τa for CIFAR10. The performance gap between SSD-FL and baselines is more pronounced under extreme heterogeneity.
∗ arg minS∈S̃ H̃ s.t. Φ(S) ≥ Φmin S . As such, S corresponds to the set of clusters that (i) maintains sufficient intra-cluster connectivity and (ii) yields the lowest average effective firstorder gradient. Therefore, SSD-FL’s cluster formation is based on both graph topology and estimated ML performance.
further assign a proximal parameter µi drawn uniformly at random from {5 × 10−5 , 1 × 10−4 } or a momentum parameter ρi drawn uniformly at random from {0.8, 0.85}. Finally, the ML models used are five layer CNNs, with output channel dimension 32, 64, 128, 128, and 256 sequentially, 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 [50] with link formation probability 10% and size 30 devices. Additionally, all experiments are run for 20 total global cycles, with intracluster period τa = 3 and inter-cluster period of τr = 1. For all experiments, networks’ adjacency matrices, including the inter-cluster and intra-cluster graph matrices A and Ã, are based off of Metropolis-Hastings weights [51]. To contextualize performance, we examine SSD-FL relative to four classes of baseline decentralized FL methodologies: (i) synchronous (sDFL) [34], (ii) periodic (pDFL) [22], (iii) stochastic (STC) [23], and (iv) clustered stochastic (cSTC), which determines the total number of clusters randomly and thereafter follows stochastic [23]. Moreover, for fairness, these baseline decentralized FL methodologies will have dedicated training rounds and additional D2D network communications adhering to τa and τr respectively. Finally, regarding SSDFL’s cluster formation parameters, we use ∆tol S = 10 for S ∈ {1, · · · , N }, and α = 0.1. To derive αs , we use an equal weighting in (38) with ζ1 , ζ2 , and ζ3 = 1, while, for the min-max scalings in (39) and (41), we use αo,max = 0.2 and αo,min = 0 as well as αd,max = 0.2 and αd,min = 0, respectively.
VI. E XPERIMENTAL E VALUATION 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. Then, we first examine the impact of inter-cluster period τr in Sec. VI-C and intra-cluster period τa in Sec. VI-B, 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, before concluding with performance across various network graph architectures in Sec. VI-E 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 for conciseness. Similarly, additional experiments on link formation probabilities and on SSD-FL’s intra-cluster convergence bound are also available in Appendix G. A. Experimental setup The experiments are performed on FMNIST [48] and CIFAR10 [49], with their respective training datasets of size 60000 and 50000 samples 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 from 3 or 1 label 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
B. Intra-cluster duration τa First, we examine the impact of intra-cluster period τa on SSD-FL and the various decentralized FL baselines in
11
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.
τr = 3 Method
SSD-FL sDFL pDFL STC cSTC
Mild non-i.i.d. acc
τr = 5 Extreme non-i.i.d. acc
Mild non-i.i.d. acc
Extreme non-i.i.d. acc
51%
58%
65%
72%
30%
35%
40%
45%
51%
58%
65%
72%
30%
35%
40%
45%
2.89 3.07 3.06 3.21 3.15
4.16 4.61 4.58 4.93 4.66
6.56 7.40 7.43 7.51 7.51
11.75 14.70 13.80 16.06 14.30
2.63 2.77 2.73 2.94 2.92
4.93 5.55 5.32 5.78 5.84
8.98 11.08 11.01 13.86 12.15
17.75 – – – 19.12
2.64 2.72 2.70 3.02 2.95
3.68 3.83 3.83 4.75 4.23
5.59 5.87 5.88 6.65 6.29
9.84 10.66 10.51 13.96 12.11
2.44 2.45 2.44 2.67 2.80
4.35 4.34 4.35 5.55 5.51
7.42 7.90 7.78 13.78 10.36
13.52 15.22 15.36 – 17.55
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, continues to demonstrate faster convergence for higher thresholds.
τr = 3 Method
SSD-FL sDFL pDFL STC cSTC
Mild non-i.i.d. acc
τr = 5 Extreme non-i.i.d. acc
Mild non-i.i.d. acc
Extreme non-i.i.d. acc
51%
58%
65%
72%
30%
35%
40%
45%
51%
58%
65%
72%
30%
35%
40%
45%
6.41 6.68 6.61 6.98 6.55
9.26 9.71 9.57 11.10 10.36
12.87 13.79 13.62 15.14 14.52
17.73 18.64 18.99 – 19.37
2.86 2.91 3.00 3.40 3.06
5.88 6.42 6.47 8.47 7.64
11.21 12.42 12.60 17.38 14.06
– – – – –
5.90 6.20 5.99 6.62 6.25
8.57 8.90 8.66 10.87 9.89
11.63 12.11 11.79 15.07 13.85
15.88 16.61 16.16 19.86 17.92
2.60 2.63 2.46 3.37 2.92
4.84 5.13 5.02 6.67 7.52
8.91 9.91 9.42 15.31 13.28
15.38 16.98 17.31 – –
Fig. 2-3, with τr = 1 to isolate the effects of τa and a network of N = 10 devices. 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 ) 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 = 1, all methods perform comparably, with SSD-FL holding only a modest edge over the best baseline. However, as τa grows larger, SSD-FL pulls progressively further ahead. For example when τa = 5 in extreme non-i.i.d. scenarios, SSD-FL leads the best baseline STC by roughly 4% on FMNIST (46% vs 42%) and roughly 2% on CIFAR10 (35% vs 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 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, SSDFL converges steadily throughout, reflecting the intra-cluster stability induced by Algorithm 1. Moreover, while sDFL and pDFL do offer smooth convergence curves, their accuracies are far lower than those obtained by SSD-FL, for example by roughly 9% and 4% on FMNIST and CIFAR10 in extreme non-i.i.d. settings at τ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 intracluster differences), which in turn produces more useful local ML model updates and easier inter-cluster propagation across
global rounds. C. Inter-cluster period τr Next, we examine the impact of inter-cluster period τr on convergence speed in Tables I and II, by measuring the average number of global cycles needed to reach various accuracy thresholds on random graphs with N = 10 devices and τ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], though the tables for τr = 1 are left to Appendix G as their takeaways are similar to those in Tables I and II. For FMNIST in Table I, 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, SSD-FL requires 12% fewer global rounds than the best performing baseline pDFL to reach 65% accuracy (6.56 vs 7.51), a gap that widens to 15% saving fewer rounds at 72% accuracy (11.75 vs 13.80). Meanwhile, under extreme non-i.i.d. settings with τr = 3, SSD-FL’s advantage becomes more pronounced, requiring 18% fewer rounds than pDFL to reach 40% accuracy (8.98 vs 11.01), and, alongside cSTC, is the only one of two methods to reach the 45% threshold. Similarly, these trends continue to hold on CIFAR10 with τr = 3 in Table II. Under mild non-i.i.d. settings, SSD-FL reaches 72% accuracy in 17.73 rounds vs 18.64 for the best performing baseline sDFL. These savings become more pronounced in extreme non-i.i.d. settings, where SSDFL requires 14% fewer rounds than pDFL (best performing baseline) to reach 40% accuracy (11.21 vs 12.60).
12
86
Accuracy (%)
sDFL
a) Mild non-i.i.d.
pDFL 56
82
52
78
48
74
44
70
40
66
36
62
10
20 30 40 Network Size N
50
32
STC
cSTC
SSD-FL (Ours)
b) Extreme non-i.i.d.
sDFL
a) Mild non-i.i.d.
20 30 40 Network Size N
50
STC
cSTC
10
20 30 40 Network Size N
50
b) Extreme non-i.i.d.
33
50 30
46
27
42 10
pDFL 36
54 Accuracy (%)
SSD-FL (Ours)
38
10
20 30 40 Network Size N
50
24
FIGURE 4: Varying network size from N = 10 to 50 with Erdős–Rényi random graphs on FMNIST. SSD-FL consistently yields better or equal performance relative to decentralized FL baselines.
FIGURE 5: Varying network size from N = 10 to 50 with Erdős–Rényi random graphs on CIFAR10. SSD-FL maintains a consistent performance gap across various network sizes.
As τr increases to 5, 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 at 72% accuracy decreases from 2.05 to 0.67 global rounds. This is expected, however, as larger τ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), which are defined by the network environments rather than something controlled by network operators.
formation can actually compound the difficulties of largescale decentralized FL rather than helping them. By contrast, SSD-FL’s stable scaling behavior shows that principled cluster formation (per Algorithm 1) 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.
D. Network size We next examine the impact of network size from N = 10 to N = 50 for random graphs using both FMNIST in Fig. 4, and CIFAR10 in Fig. 5. 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. 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 and VI-C, the latter of which demonstrates much faster convergence in settings with the more practically relevant case of τ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 at N = 10 in the mild non-i.i.d. scenario of Fig. 4 (both near 74.5%), its performance stalls as N grows, falling roughly 7% behind SSD-FL by N = 50 (73% vs 80%). In extreme non-i.i.d. settings, this gap grows, with cSTC trailing SSDFL by approximately 10% on FMNIST and 4% on CIFAR10 at N = 50. This shows that careless or random cluster
E. Global 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) [50], in which any two devices i, j ∈ N have a fixed probability, 10%, to have link between them, (ii) Barabási–Albert preferential attachment (PrefA) [52], where we set each device to iteratively connect to one other devices with probability proportional to their current degree, (iii) random geometric graph (RGeo) [53], where devices are placed uniformly at random in a unit-sized Euclidean space and links are established between those within a 0.2 radius, (iv) Watts-Strogatz small world [54], for which we choose to have each device with 3 links to neighboring devices and a 20% chance to reconnect these links randomly, and (iv) complete graphs (Comp) [55], in which all devices i ∈ N are connected. Across all non-trivial topologies, SSD-FL consistently outperforms the baselines on both FMNIST in Fig. 6 and CIFAR10 in Fig. 7. The advantages are most pronounced on preferential attachment and small world graphs, where SSDFL leads the best performing baseline STC by roughly 7% on FMNIST in mild non-i.i.d. settings (73.5% vs 67.7% on PrefA), and, similarly, by roughly 7% in extreme non-i.i.d. scenarios (44.8% vs 37.6% on PrefA). Meanwhile, on random graphs, SSD-FL maintains a more modest but consistent advantage of roughly 3% over STC under mild non-i.i.d. (81.1% vs 78.2%), with a larger gap of roughly 2% under extreme non-i.i.d. (52.5% vs 50.6%). Since these takeaways on FMNIST are similar to those for CIFAR10 in Fig. 7, these results collectively suggest that SSD-FL’s cluster formation is able to exploit the underlying structure of diverse network
13
SSD-FL (Ours)
sDFL
pDFL
STC
cSTC
b) Extreme non-i.i.d.
RNG
Graph architecture
PrefA RGeo SWorld Comp
a) Mild non-i.i.d.
60
70
80
90
Accuracy (%)
30
40
50
60
Accuracy (%)
70
80
FIGURE 6: Evaluation of decentralized FL baselines for various net-
work 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.
SSD-FL (Ours)
sDFL
pDFL
STC
cSTC
b) Extreme non-i.i.d.
RNG
Graph architecture
PrefA RGeo SWorld Comp
a) Mild non-i.i.d.
40
45
50
55
Accuracy (%)
60
65 20
25
30
35
40
Accuracy (%)
45
50
FIGURE 7: Evaluation of decentralized FL baselines for various network architectures on CIFAR10. Results mirror the FMNIST findings in Fig. 6, including the special case of complete networks.
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% vs 88.2% on FMNIST mild non-i.i.d., 80.9% vs 81.0% on FMNIST extreme non-i.i.d.), with SSDFL forming a single cluster as Algorithm 1 correctly identifies that partitioning is unnecessary. In sparse networks, clustering trades global connectivity for local density, accelerating intracluster 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. VII. C ONCLUSION 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 SSDFL 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. R EFERENCES [1] A. Yazdinejad, A. Dehghantanha, H. Karimipour, G. Srivastava, and R. M. Parizi, “A robust privacy-preserving federated learning model against model poisoning attacks,” IEEE Transactions on Information Forensics and Security, vol. 19, no. 1, pp. 6693–6708, 2024. [2] E. Hallaji, R. Razavi-Far, M. Saif, B. Wang, and Q. Yang, “Decentralized federated learning: A survey on security and privacy,” IEEE Transactions on Big Data, vol. 10, no. 2, pp. 194–213, 2024. [3] S. Wang, R. Morabito, S. Hosseinalipour, M. Chiang, and C. G. Brinton, “Device sampling and resource optimization for federated learning in cooperative edge networks,” IEEE/ACM Transactions on Networking, vol. 32, no. 5, pp. 4365 – 4381, 2024. [4] J. Pei, W. Liu, J. Li, L. Wang, and C. Liu, “A review of federated learning methods in heterogeneous scenarios,” IEEE Transactions on Consumer Electronics, vol. 70, no. 3, pp. 5983–5999, 2024. [5] S. Wang, S. Hosseinalipour, V. Aggarwal, C. G. Brinton, D. J. Love, W. Su, and M. Chiang, “Toward cooperative federated learning over heterogeneous edge/fog networks,” IEEE Communications Magazine, vol. 61, no. 12, pp. 54–60, 2023. [6] S. Wang, T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan, “Adaptive federated learning in resource constrained edge computing systems,” IEEE Journal on Selected Areas in Communications, vol. 37, no. 6, pp. 1205–1221, 2019. [7] L. Yuan, Z. Wang, L. Sun, S. Y. Philip, and C. G. Brinton, “Decentralized federated learning: A survey and perspective,” IEEE Internet of Things Journal, vol. 11, no. 21, pp. 34 617 – 34 638, 2024. [8] M. Yemini, R. Saha, E. Ozfatura, D. Gündüz, and A. J. Goldsmith, “Semi-decentralized federated learning with collaborative relaying,” in Proceedings of the 2022 IEEE International Symposium on Information Theory. IEEE, 2022, pp. 1471–1476. [9] F. P.-C. Lin, S. Hosseinalipour, S. S. Azam, C. G. Brinton, and N. Michelusi, “Semi-decentralized federated learning with cooperative d2d local model aggregations,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 12, pp. 3851–3869, 2021. [10] A. Ali-Pour and J. Gascon-Samson, “Sdflmq: A semi-decentralized federated learning framework over mqtt,” in Proceedings of the 2025 IEEE International Parallel and Distributed Processing Symposium Workshops. IEEE, 2025, pp. 1100–1107. [11] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, “A novel framework for the analysis and design of heterogeneous federated learning,” IEEE Transactions on Signal Processing, vol. 69, pp. 5234–5249, 2021. [12] J. Liu, J. Yan, H. Xu, L. Wang, Z. Wang, J. Huang, and C. Qiao, “Accelerating decentralized federated learning with probabilistic communication in heterogeneous edge computing,” IEEE Transactions on Networking, 2025, to appear. [13] Z. Tang, S. Shi, B. Li, and X. Chu, “Gossipfl: A decentralized federated learning framework with sparsified and adaptive communication,” IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 3, pp. 909–922, 2022. [14] D. T. A. Nguyen, S. Wang, D. T. Nguyen, A. Nedich, and H. V. Poor, “Decentralized federated learning with gradient tracking over timevarying directed networks,” arXiv:2409.17189, 2024. [15] W. Tushar, T. K. Saha, C. Yuen, D. Smith, and H. V. Poor, “Peer-topeer trading in electricity networks: An overview,” IEEE Transactions on Smart Grid, vol. 11, no. 4, pp. 3185–3200, 2020. [16] Q. Li and D. Chen, “Peer to peer distributed solar energy trading,” ACM SIGMETRICS Performance Evaluation Review, vol. 50, no. 4, pp. 44– 46, 2023.
14
[17] N. Pogkas, G. Karastergios, C. Antonopoulos, S. Koubias, and G. Papadopoulos, “An ad-hoc sensor network for disaster relief operations,” in Proceedings of the 2005 IEEE Conference on Emerging Technologies and Factory Automation. IEEE, 2005, pp. 131–139. [18] X. Wang and Y. Lu, “Information-centric robotic ad hoc networking based continuous data routing and delivery for disaster scenes,” IEEE Transactions on Green Communications and Networking, vol. 9, no. 3, pp. 768–777, 2024. [19] L. P. Qian, H. Zhang, Q. Wang, Y. Wu, and B. Lin, “Joint multi-domain resource allocation and trajectory optimization in uav-assisted maritime iot networks,” IEEE Internet of Things Journal, vol. 10, no. 1, pp. 539– 552, 2022. [20] C. Zhang, G. Shan, and B.-H. Roh, “Fmd-iov: Security and robust enhancement for federated multi-domain learning–based iov,” IEEE Transactions on Intelligent Transportation Systems, vol. 26, no. 9, pp. 14 225–14 236, 2025. [21] S. Weng, M. Xiao, C. Ren, and M. Skoglund, “Coded cooperative networks for semi-decentralized federated learning,” IEEE Wireless Communications Letters, vol. 14, no. 3, pp. 626–630, 2024. [22] T. Sun, D. Li, and B. Wang, “Decentralized federated averaging,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 4, pp. 4289–4301, 2022. [23] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, “A unified theory of decentralized sgd with changing topology and local updates,” in Proceedings of the 2020 International conference on machine learning. PMLR, 2020, pp. 5381–5393. [24] L. Liu, J. Zhang, S. Song, and K. B. Letaief, “Hierarchical federated learning with quantization: Convergence analysis and system design,” IEEE Transactions on Wireless Communications, vol. 22, no. 1, pp. 2– 18, 2022. [25] Z. Chen, W. Chen, J. Li, Q. Wu, M. Ding, X. Han, X. Deng, and L. Wang, “Hierarchical federated learning for social network with mobility,” IEEE Transactions on Cognitive Communications and Networking, 2025, to appear. [26] S. Wang, S. Hosseinalipour, M. Gorlatova, C. G. Brinton, and M. Chiang, “Uav-assisted online machine learning over multi-tiered networks: A hierarchical nested personalized federated learning approach,” IEEE Transactions on Network and Service Management, vol. 20, no. 2, pp. 1847–1865, 2022. [27] M. S. HaghighiFard and S. Coleri, “Hierarchical federated learning in multi-hop cluster-based vanets,” IEEE Transactions on Vehicular Technology, 2025, to appear. [28] Y. Sun, J. Shao, Y. Mao, J. H. Wang, and J. Zhang, “Semi-decentralized federated edge learning for fast convergence on non-iid data,” in Proceedings of the 2022 IEEE Wireless Communications and Networking Conference (WCNC). IEEE, 2022, pp. 1898–1903. [29] Z. Wang, H. Xu, J. Liu, Y. Xu, H. Huang, and Y. Zhao, “Accelerating federated learning with cluster construction and hierarchical aggregation,” IEEE Transactions on Mobile Computing, vol. 22, no. 7, pp. 3805–3822, 2022. [30] B. Gong, T. Xing, Z. Liu, W. Xi, and X. Chen, “Towards hierarchical clustered federated learning with model stability on mobile devices,” IEEE Transactions on Mobile Computing, vol. 23, no. 6, pp. 7148–7164, 2023. [31] A. Nedić and A. Olshevsky, “Distributed optimization over time-varying directed graphs,” IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 601–615, 2014. [32] H. Taheri, A. Mokhtari, H. Hassani, and R. Pedarsani, “Quantized decentralized stochastic learning over directed graphs,” in Proceedings of the 2020 International Conference on Machine Learning. PMLR, 2020, pp. 9324–9333. [33] J. Wang, A. K. Sahu, G. Joshi, and S. Kar, “Matcha: A matching-based link scheduling strategy to speed up distributed optimization,” IEEE Transactions on Signal Processing, vol. 70, pp. 5208–5221, 2022. [34] W. Liu, L. Chen, and W. Zhang, “Decentralized federated learning: Balancing communication and computing costs,” IEEE Transactions on Signal and Information Processing over Networks, vol. 8, pp. 131–143, 2022. [35] A. Hashemi, A. Acharya, R. Das, H. Vikalo, S. Sanghavi, and I. Dhillon, “On the benefits of multiple gossip steps in communication-constrained decentralized federated learning,” IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 11, pp. 2727–2739, 2021. [36] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multiagent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009.
[37] S. Zehtabi, D.-J. Han, R. Parasnis, S. Hosseinalipour, and C. G. Brinton, “Decentralized sporadic federated learning: A unified algorithmic framework with convergence guarantees,” arXiv:2402.03448, 2024. [38] W. Shi, Q. Ling, G. Wu, and W. Yin, “Extra: An exact first-order algorithm for decentralized consensus optimization,” SIAM Journal on Optimization, vol. 25, no. 2, pp. 944–966, 2015. [39] M. Bornstein, T. Rabbani, E. Z. Wang, A. Bedi, and F. Huang, “Swift: Rapid decentralized federated learning via wait-free model communication,” in Proceedings of the Eleventh International Conference on Learning Representations, 2023, pp. 1–30. [40] Z. Jiang, A. Balu, C. Hegde, and S. Sarkar, “Collaborative deep learning in fixed topology networks,” Advances in Neural Information Processing Systems, vol. 30, pp. 3322–3330, 2017. [41] S. Chewi, S. Bubeck, and A. Salim, “On the complexity of finding stationary points of smooth functions in one dimension,” in Proceedings of the 34th International Conference on Algorithmic Learning Theory. PMLR, 2023, pp. 358–374. [42] L. Xiao and T. Zhang, “A proximal stochastic gradient method with progressive variance reduction,” SIAM Journal on Optimization, vol. 24, no. 4, pp. 2057–2075, 2014. [43] I. Sutskever, J. Martens, G. Dahl, and G. Hinton, “On the importance of initialization and momentum in deep learning,” in Proceedings of the 30th International Conference on Machine Learning. PMLR, 2013, pp. 1139–1147. [44] S. U. Pillai, T. Suel, and S. Cha, “The perron-frobenius theorem: some of its applications,” IEEE Signal Processing Magazine, vol. 22, no. 2, pp. 62–75, 2005. [45] F. R. K. Chung, Spectral Graph Theory, ser. CBMS Regional Conference Series in Mathematics. Providence, RI: American Mathematical Society, 1997, vol. 92. [46] B. Fuglede and F. Topsøe, “Jensen–shannon divergence and hilbert space embedding,” in Proceedings of the 2004 IEEE International Symposium on Information Theory. IEEE, 2004, p. 31. [47] M. L. Rizzo and G. J. Székely, “Energy distance,” Wiley Interdisciplinary Reviews: Computational Statistics, vol. 8, no. 1, pp. 27–38, 2016. [48] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” arXiv:1708.07747, 2017. [49] A. Krizhevsky, “Learning multiple layers of features from tiny images,” University of Toronto, Tech. Rep., 2009, technical Report. [50] E. N. Gilbert, “Random graphs,” The Annals of Mathematical Statistics, vol. 30, no. 4, pp. 1141–1144, 1959. [51] L. Xiao, S. Boyd, and S. Lall, “Distributed average consensus with time-varying metropolis weights,” Automatica, vol. 41, no. 12, pp. 1895– 1906, 2005. [52] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. [53] M. D. Penrose, Random Geometric Graphs, ser. Oxford Studies in Probability. Oxford, UK: Oxford University Press, 2003, vol. 5. [54] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘smallworld’networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998. [55] P. Erdős, “Some remarks on the theory of graphs,” Bulletin of the American Mathematical Society, vol. 53, no. 4, pp. 292–294, 1947.
15
A PPENDIX TABLE OF C ONTENTS Appendix A: Proof of Proposition 1
16
Appendix B: Proof of Corollary 1
18
Appendix C: Proof of Theorem 1
19
Appendix D: Proof of Lemma 1
20
Appendix E: Proof of Lemma 2
21
Appendix F: Proof of Theorem 2
22
Appendix G: Additional Experiments G-A Varying Link Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G-B Homogeneous SGD Optimizers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G-C Normalized Intra-Cluster Gradients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24 24 24 27
16
A PPENDIX A P ROOF OF P ROPOSITION 1 Proposition 1. (Gradient Gap of Effective Intra-cluster Loss) Given two instances q1 and q2 such that q1 ̸= q2 and q1 , q2 < τa within any intra-cluster regime k̃ ∈ K̃, the cluster-level regularized loss functions L̃s (θ̂sk̃,q1 ) and L̃s (θ̂sk̃,q2 ) , ∀s ∈ S have bounded gradient gap as follows: p ∇L̃s (θ̂sk̃,q1 ) − ∇L̃s (θ̂sk̃,q2 ) ≤ γseff ∥θ̂sk̃,q1 − θ̂sk̃,q2 ∥ + τa B Ns (23) where
1 γ̂s + 1 + (1 − λNs (As )) , η
γseff =
(24)
and γ̂s = maxi∈Ns γi . Similarly, for global-level regularized loss functions L̃(θ k̃,q1 ) and L̃(θ k̃,q2 ), the gradient gap is √ ∇L̃(θ k̃,q1 ) − ∇L̃(θ k̃,q2 ) ≤ γ eff θ k̃,q1 − θ k̃,q2 + τa B N , where γ eff =
1 γ̂ + 1 + 1 − λN (Ã) , η
(25)
(26)
and γ̂ = maxi∈N γi . Proof. Recall that, via the definition of regularized cluster loss functions, we can expand ∥∇L̃s (θ̂sk̃,q1 ) − ∇L̃s (θ̂sk̃,q2 )∥ as follows: ∥∇L̃s (θ̂sk̃,q1 ) − ∇L̃s (θ̂sk̃,q2 )∥ (a)
(42) !
= ∇
X
Li (θik̃,q1 ) − Li (θik̃,q2 )
+ ∇ θik̃,q1
qX 1 −1
X µi i∈Ns
2
∥θik̃,q1 − θik̃,0 ∥2 − ∥θik̃,q2 − θik̃,0 ∥2 qX 1 −1
(b)
≤ ∇Ls (θ̂sk̃,q1 ) − ∇Ls (θ̂sk̃,q2 ) + | {z } (i)
! ρiq2 −p ∇Li (θik̃,p )
(43)
p=0
p=0
i∈Ns
+∇
ρiq1 −p ∇Li (θik̃,p ) − θik̃,q2
qX 2 −1
! +∇
1 k̃,q1 2 ∥θ̂s ∥Is −As − ∥θ̂sk̃,q2 ∥2Is −As 2η
ρqs1 −p ⊙ ∇Ls (θ̂sk̃,p ) −
p=0
qX 2 −1
ρsq2 −p ⊙ ∇Ls (θ̂sk̃,p )
(44)
p=0
|
{z
}
(ii)
1 (Is − As ) θ̂sk̃,q1 − θ̂sk̃,q2 , + µs ⊙ θ̂sk̃,q1 − θ̂sk̃,0 − µs ⊙ θ̂sk̃,q2 − θ̂sk̃,0 + | {z } |η {z } (iii)
(iv)
where ∇Ls (θ̂sk̃,q ) = [∇Li (θik̃,q )]i∈Ns , (a) is from the expanded definition of the regularized effective cluster loss functions, and (b) applies the gradient to the scalars and then uses the triangle inequality. We next bound each of the four terms (i), (ii), (iii), and (iv) in (44), starting with term (i) as follows: ! 2 1/2 X (c) k̃,q1 k̃,q2 k̃,q1 k̃,q2 ∇Ls (θ̂s ) − ∇Ls (θ̂s ) = ∇Li (θi ) − ∇Li (θi ) (45) i∈Ns (d)
X
≤
2 γi2 θik̃,q1 − θik̃,q2
!1/2 (46)
i∈Ns (e)
≤
max γi
i∈Ns
2 X k̃,q θi 1 − θik̃,q2
!1/2 (47)
i∈Ns
(f )
= γ̂s θ̂sk̃,q1 − θ̂sk̃,q2 ,
(48)
where (c) follows from the definition of the Euclidean norm, (d) leverages the smoothness assumption in Assumption 1, (e) extracts the largest smoothness coefficient γ̂s = maxi∈Ns γi , and (f ) re-applies the equivalent form of the Euclidean norm. Next, for term (ii) in (44), we have that qX 1 −1 p=0
ρqs1 −p ⊙ ∇Ls (θ̂sk̃,p ) −
qX 2 −1 p=0
ρsq2 −p ⊙ ∇Ls (θ̂sk̃,p )
(49)
17
(g)
=
qX 1 −1
ρqs1 −p ⊙ ∇Ls (θ̂sk̃,p ) +
p=q2 q1 −1 (h) X
≤
qX 2 −1
≤
p=q2 q1 −1 (j) X
≤
p=q2 a −1 (k) τX
≤
(50)
p=0
ρqs1 −p ⊙ ∇Ls (θ̂sk̃,p ) +
p=q2 q1 −1 (i) X
ρqs1 −p − ρqs2 −p ⊙ ∇Ls (θ̂sk̃,p )
qX 2 −1
ρsq1 −p − ρqs2 −p ⊙ ∇Ls (θ̂sk̃,p )
(51)
p=0
2 X q −p ρi 1 ∇Li (θik̃,q1 )
!1/2 +
i∈Ns
X
2
!1/2
∇Li (θik̃,q1 )
+
i∈Ns
Ns B 2
1/2
= τa B
p
qX 2 −1
X
p=0
i∈Ns
qX 2 −1
X
p=0
i∈Ns
Ns ,
ρqi 1 −p − ρqi 2 −p ∇Li (θik̃,q1 ) 2
∇Li (θik̃,q1 )
2
!1/2 (52)
!1/2 (53)
(54)
p=0
where (g) aligns the summations over the iterations, (h) results from the triangle inequality, (i) expands the Euclidean distance, (j) uses the fact that ρqi 1 −p and ρqi 1 −p −ρqi 2 −p ≤ 1, and (k) uses the fact that q1 ≤ τa and subsequently leverages Assumption 2 to obtain ∥∇Li (θi )∥ < B. Next, we bound the difference of proximal terms (i.e., term (iii) in (44)) as follows: (l) (55) µs ⊙ θ̂sk̃,q1 − θ̂sk̃,0 − µs ⊙ θ̂sk̃,q2 − θ̂sk̃,0 = µs ⊙ θ̂sk̃,q1 − θ̂sk̃,q2 !1/2 2 X (m) ≤ (56) µi (θik̃,q1 − θik̃,q2 ) i∈Ns (n)
≤
X
2
(θik̃,q1 − θik̃,q2 )
!1/2 (57)
i∈Ns (o)
≤ θ̂sk̃,q1 − θ̂sk̃,q2
(58)
where (l) cancels out ±θ̂sk̃,0 , (m) expands the definition of Euclidean distance, (n) uses the fact that µi ≤ 1 so that maxi µi ≤ 1, and (o) is the definition of Euclidean distance. Finally, for term (iv) in (44), we have that (q) 1 1 ≤ ∥Is − As ∥ θ̂sk̃,q1 − θ̂sk̃,q2 (59) (Is − As ) θ̂sk̃,q1 − θ̂sk̃,q2 η η (p) 1 ≤ λmax (Is − As ) θ̂sk̃,q1 − θ̂sk̃,q2 (60) η (r) 1 = (1 − λNs (As )) θ̂sk̃,q1 − θ̂sk̃,q2 , (61) η where (q) converts the expression into two terms, (p) uses the fact that the 2-norm of a matrix (spectral norm) is the largest eigenvalue of said matrix, (r) simplifies the expression of λmax . Finally, combining the bounds for terms (i), (ii), (iii), and (iv) in (44) yields p ∇L̃s (θ̂sk̃,q1 ) − ∇L̃s (θ̂sk̃,q2 ) ≤ γ̂s θ̂sk̃,q1 − θ̂sk̃,q2 + τa B Ns + θ̂sk̃,q1 − θ̂sk̃,q2 1 (1 − λNs (As )) θ̂sk̃,q1 − θ̂sk̃,q2 (62) η p 1 (63) = γ̂s + 1 + (1 − λNs (As )) θ̂sk̃,q1 − θ̂sk̃,q2 + τa B Ns , η 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 1 + 1 − λN (Ã) θ k̃,q1 − θ k̃,q2 (64) η √ 1 = γ̂ + 1 + 1 − λN (Ã) θ k̃,q1 − θ k̃,q2 + τa B N , (65) η where γ̂ = maxi∈N γi . ■ +
18
A PPENDIX B P ROOF OF C OROLLARY 1 Corollary 1. (Effective Intra-cluster Loss Gap) Given two instances q1 and q2 such that q1 ̸= q2 and q1 , q2 < τa within any intra-cluster regime k̃ ∈ K̃, the cluster-level effective loss functions L̃s (θ̂sk̃,q1 ) and L̃s (θ̂sk̃,q2 ) , ∀s ∈ S have bounded gap as follows: T
L̃s (θ̂sk̃,q1 ) ≤ L̃s (θ̂sk̃,q2 ) + ∇L̃s (θ̂sk̃,q2 ) θ̂sk̃,q1 − θ̂sk̃,q2 p 1 eff γs + τa B Ns ∥θ̂sk̃,q1 − θ̂sk̃,q2 ∥2 . + 2
Proof. Define a variable t̃ ∈ [0, 1] so that we can parameterize a line segment from θ̂sk̃,q2 to θ̂sk̃,q1 as follows: θ̂s (t̃) = θ̂sk̃,q2 + t̃ θ̂sk̃,q1 − θ̂sk̃,q2 .
(27)
(66)
Exploiting (66), we can express intra-cluster regularized loss functions as functions of 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)).
(67)
Using the fundamental theorem of calculus, we further convert the right hand side of (67) as follows: L̃s (θ̂s (1)) − L̃s (θ̂s (0)) Z 1 d (a) L̃s (θ̂s (t̃))dt̃ = d t̃ 0 Z 1 Z 1 (b) = ∇L̃s (θ̂s (t̃))T θ̂s (1) − θ̂s (0) dt̃ ≡ ∇L̃s (θ̂s (t̃))T θ̂sk̃,q1 − θ̂sk̃,q2 dt̃ 0
(68) (69) (70)
0
where (a) results from the fundamental theorem of calculus, and (b) follows from the chain rule applied onto L̃s (θ̂s (t̃)) and subsequently (66). Combining (67) and (70) yields Z 1 k̃,q2 k̃,q1 (c) ∇L̃s (θ̂s (t̃))T θ̂s (1) − θ̂s (0) dt̃ (71) L̃s (θ̂s ) = L̃s (θ̂s ) + 0 Z 1 T (d) (72) θ̂sk̃,q1 − θ̂sk̃,q2 dt̃, ∇L̃s (θ̂s (t̃)) − ∇L̃s (θ̂sk̃,q2 ) = L̃s (θ̂sk̃,q2 ) + ∇L̃s (θ̂sk̃,q2 )T θ̂sk̃,q1 − θ̂sk̃,q2 + 0
where (c) re-arranges the combination of (67) and (70), and (d) introduces ±∇L̃s (θ̂sk̃,q2 ) θ̂sk̃,q1 − θ̂sk̃,q2 . Next, we focus on bounding the integral in (72) as follows: Z 1 (e) Z 1 T k̃,q2 k̃,q1 k̃,q2 (73) dt̃ ≤ ∇L̃s (θ̂s (t̃)) − ∇L̃s (θ̂sk̃,q2 ) θ̂sk̃,q1 − θ̂sk̃,q2 dt̃ θ̂s − θ̂s ∇L̃s (θ̂s (t̃)) − ∇L̃s (θ̂s ) 0 0 Z 1 (f ) p 1 ≤ γ̂s + 1 + (1 − λNs (As )) θ̂s (t̃) − θ̂sk̃,q2 + τa B Ns θ̂sk̃,q1 − θ̂sk̃,q2 dt̃ (74) η 0 Z 1 p 1 (g) = γ̂s + 1 + (1 − λNs (As )) t̃ θ̂sk̃,q1 − θ̂sk̃,q2 (75) θ̂sk̃,q1 − θ̂sk̃,q2 dt̃ + τa B Ns θ̂sk̃,q1 − θ̂sk̃,q2 η 0 p 2 1 (h) 1 γ̂s + 1 + (1 − λNs (As )) θ̂sk̃,q1 − θ̂sk̃,q2 + τa B Ns θ̂sk̃,q1 − θ̂sk̃,q2 = (76) 2 η where (e) is from the Cauchy-Schwarz inequality, (f ) uses the regularized cluster loss gradient gap derived in Theorem 1, (g) substitutes the definition of θ̂s (t̃) from (66), and (h) expands the integral. Finally, combining (72) and (76) yields the result as follows: L̃s (θ̂sk̃,q1 ) ≤ L̃s (θ̂sk̃,q2 ) + ∇L̃s (θ̂sk̃,q2 )T θ̂sk̃,q1 − θ̂sk̃,q2 (77) p 2 1 1 γ̂s + 1 + (1 − λNs (As )) θ̂sk̃,q1 − θ̂sk̃,q2 + τa B Ns θ̂sk̃,q1 − θ̂sk̃,q2 . + 2 η ■
19
A PPENDIX C P ROOF OF T HEOREM 1 Theorem 1. (Intra-cluster Convergence) If η < α̂s2Γs , then, given any intra-cluster regime k̃ ∈ K̃ and cluster s ∈ S, we bound the first-order stationary point as follows: τX a −1 q=0
where
∇L̃s (θ̂sk̃,q )
2
2
≤
L̃s (θ̂sk̃,0 ) + ατ2a η Γs 2
η − α̂s2η Γs
p Γs = γseff + τa B Ns .
(28)
(29)
Proof. Leveraging the result of Corollary 1 and combining with the intra-cluster ML model update rule from (14) yields L̃s (θ̂sk̃,q+1 ) ≤ L̃s (θ̂sk̃,q ) + ∇L̃s (θ̂sk̃,q )T −η∇F̃s (θ̂sk̃,q ) (78) p 2 1 1 γ̂s + 1 + (1 − λNs (As )) −η∇F̃s (θ̂sk̃,q ) + τa B Ns −η∇F̃s (θ̂sk̃,q ) + 2 η 1 (a) p 2 1 k̃,q k̃,q T k̃,q −η∇F̃s (θ̂sk̃,q ) , ≤ L̃s (θ̂s ) + ∇L̃s (θ̂s ) −η∇F̃s (θ̂s ) + γ̂s + 1 + (1 − λNs (As )) + τa B Ns (79) 2 η where (a) follows immediately since ∥ − η∇F̃s (θ̂sk̃,q )∥2 > ∥ − η∇F̃s (θ̂sk̃,q )∥. Re-arranging (79) and taking the expectation yields i h (b) L̃s (θ̂sk̃,q+1 ) − L̃s (θ̂sk̃,q ) ≤ −η∇L̃s (θ̂sk̃,q )T E ∇F̃s (θ̂sk̃,q ) p 2 η2 1 + γ̂s + 1 + (1 − λNs (As )) + τa B Ns E ∇F̃s (θ̂sk̃,q ) (80) 2 η (c) p 2 2 1 η2 γ̂s + 1 + (1 − λNs (As )) + τa B Ns ≤ −η ∇L̃s (θ̂sk̃,q ) + α + α̂s ∇L̃s (θ̂sk̃,q ) (81) 2 η p 2 1 α̂s η 2 (d) γ̂s + 1 + (1 − λNs (As )) + τa B Ns ∇L̃s (θ̂sk̃,q ) = −η + 2 η p 1 αη 2 γ̂s + 1 + (1 − λNs (As )) + τa B Ns , + (82) 2 η where (b) is the result of re-arrangement, (c) leverages Assumption 4 and the fact that ∇F̃s (θ̂sk̃,q ) is the unbiased estimate of ∇L̃s (θ̂sk̃,q2 ), and (d) simplifies the algebra. Further re-arrangement of (82) yields p 2 α̂s η 2 1 η− ∇L̃s (θ̂sk̃,q ) ≤ L̃s (θ̂sk̃,q ) − L̃s (θ̂sk̃,q+1 ) γ̂s + 1 + (1 − λNs (As )) + τa B Ns 2 η (83) p αη 2 1 + γ̂s + 1 + (1 − λNs (As )) + τa B Ns . 2 η 2
Finally, dividing both sides of (83) by the coefficient on ∇L̃s (θ̂sk̃,q ) and summing over all instances q ∈ k̃ yields the result as follows: τX a −1 2 (e) L̃s (θ̂sk̃,0 ) − L̃s (θ̂sk̃,τa ) ∇L̃s (θ̂sk̃,q ) ≤ √ 2 η − α̂s2η γ̂s + 1 + η1 (1 − λNs (As )) + τa B Ns q=0 √ ατa η 2 γ̂s + 1 + η1 (1 − λNs (As )) + τa B Ns 2 + (84) √ 2 η − α̂s2η γ̂s + 1 + η1 (1 − λNs (As )) + τa B Ns √ ατa η 2 1 k̃,0 γ̂ + 1 + (1 − λ (A )) + τ B Ns (f ) L̃s (θ̂s ) + s N s a s 2 η , ≤ √ 2 η − α̂s2η γ̂s + 1 + η1 (1 − λNs (As )) + τa B Ns where (f ) is from the fact that L̃s (·) ≥ 0. Finally, note that the (e) step in (84) requires that p α̂s η 2 1 2 η> γ̂s + 1 + 1 − λNs (As ) + τa B Ns →η< √ , 1 2 η α̂s γ̂s + 1 + η (1 − λNs (As )) + τa B Ns
(85)
after re-arranging. ■
20
A PPENDIX D P ROOF OF L EMMA 1 Lemma 1. (Intra-cluster consensus gap) For any intra-cluster regime k̃ ∈ K̃ and assuming that ∆k̃,q s ⊥ 1s and η < 1−λ2 (As ), the intra-cluster cluster consensus gap can be bounded above as follows: √ 2ητa B Ns k̃,0 k̃,τa τa −1 ∆s + ∆s ≤ (λ2 (As ) + η) , (31) | {z } |1 − η −{zλ2 (As )} (a)
(b)
P k̃,τa k̃,τa a where ∆k̃,τ = θ s 1s − θ̂sk̃,τa , and θ s = N1s i∈Ns θsk̃,τa . s Proof. Combining the intra-cluster ML model parameters update rule in (14) and the full form of F̃s (·) via (13) and (12) yields ! q−1 X q−p k̃,p k̃,q k̃,0 k̃,q+1 k̃,q k̃,q θ̂s = As θ̂s − η Gs (θ̂s ) + ρs ⊙ Gs (θ̂s ) + µs ⊙ θ̂s − θ̂s . (86) p=0
To analyze ∆k̃,q+1 , we first express it in an equivalent form s k̃,q+1
∆k̃,q+1 = θs s
1s − θ̂sk̃,q+1 = Ps θ̂sk̃,q+1 ,
(87)
where Ps = N1s 1s 1Ts − Is . Combining (86) and (87) then applying the triangle inequality enables the following expansion of ∥ ∥∆k̃,q+1 s k̃,q k̃,q ≤ P ∆k̃,q+1 A θ̂ + P ) ηG ( θ̂ s s s s s s s {z } | {z } | (i)
+ Ps
η
q−1 X
(ii)
!
+ Ps ηµs ⊙ θ̂sk̃,q − θ̂sk̃,0 . | {z }
ρq−p ⊙ Gs (θ̂sk̃,p ) s
p=0
|
{z
}
(iii)
(88)
(iv)
As As is doubly stochastic per Assumption 3, we exploit commutativity of the constituents of term (i) in (88) as follows: Ps As θ̂sk̃,q = As Ps θ̂sk̃,q (89) (a)
≤ As ∆k̃,q s
(90)
(b)
≤ λ2 (As ) ∆k̃,q , s
(91)
where (a) uses the definition of ∆k̃,q s , and (b) bounds the spectral norm of As by its largest feasible eigenvalue, assuming k̃,q ∆s ⊥ 1. Next, for term (ii), we bound as follows: Ps ηGs (θ̂sk̃,q ) (92) !2 1/2 X X 1 (c) k̃,q k̃,q = η gi (θi ) − gj (θj ) (93) Ns j∈Ns i∈Ns !2 1/2 X X 1 (d) ≤ η gi (θik̃,q ) + gj (θjk̃,q ) (94) Ns j∈Ns i∈Ns 1/2 X (e) ≤ η (2B)2 (95) j∈Ns (f )
= 2ηB
p
Ns ,
(96)
where (c) uses the definition of the Euclidean distance, (d) follows from a triangle inequality, (e) relies on triangle inequality and Assumption 2, and (f ) simplifies the result of (e). Similarly, for term (iii), we have that ! q−1 X q−p k̃,p Ps η ρs ⊙ Gs (θ̂s ) (97) p=0
21
(g)
≤ ηq Ps Gs (θ̂sk̃,p )
(h)
≤ 2η(τa − 1)B
(98)
p Ns ,
(99)
where (g) follows from triangle inequalities, ρi < 1, and the properties of the Hadamard product, and (h) is from similar steps as that of (c) − (f ) above in (96) and q ≤ τa − 1. Finally, for term (iv) in (88), we bound via the following: Ps ηµs ⊙ θ̂sk̃,q − θ̂sk̃,0 (100) (i) (101) ≤ η Ps θ̂sk̃,q − θ̂sk̃,0 (j)
k̃,0 = η ∆k̃,q s − ∆s
(102)
(k)
, ≤ η ∆k̃,q s
(103)
k̃,0 where (i) is from µi ≤ 1, (j) leverages the definition of ∆k̃,q s , and (k) exploits the fact that ∆s = 0. Finally, combining (91)(103) into (88) yields p + 2ητa B Ns . ∆k̃,q+1 ≤ (λ2 (As ) + η) ∆k̃,q (104) s s
Expanding (104) recursively yields: (l)
∆k̃,q+1 ≤ (λ2 (As ) + η)q ∆k̃,0 + 2ητa B s s (m)
= (λ2 (As ) + η)
q
q p X Ns (λ2 (As ) + η)p
√ 2ητa B Ns + , 1 − η − λ2 (As )
∆k̃,0 s
(105)
p=0
(106)
where (l) expands the recursion in (103), and (m) bounds the finite geometric sum by the infinite geometric sum and requires that η < 1 − λ2 (As ). Finally, noting that q ≤ τa − 1 then yields √ 2ητa B Ns k̃,0 k̃,τa τa −1 + ≤ (λ2 (As ) + η) ∆s ∆s . (107) 1 − η − λ2 (As ) ■ A PPENDIX E P ROOF OF L EMMA 2 ˆ k̂,q ⊥ 1s , Lemma 2. (Inter-cluster consensus) Given any instance q within an inter-cluster regime k̂ ∈ K̂ and assuming that ∆ we bound the inter-cluster consensus gap as ˆ k̂,τr ≤ λ2 (A)τr −1 ∆ ˆ k̂,0 , ∆ ˆ k̂,q = θ where ∆
k̂,q
1 − θ k̃,q , and θ
k̂,q
= N1
P
i∈N θ
k̂,q
(32)
.
Proof. Via the global update rule (12), we have that (b) k̂,q k̂,q+1 (a) k̃,q ˆ ˆ k̂,q ∆ = A θ 1−θ ≤ λ2 (A) ∆
(c)
ˆ k̂,0 , ≤ λ2 (A)q ∆
(108)
ˆ k̂,q ⊥ 1, and where (a) is the result of (12), (b) bounds the spectral norm of As by its largest feasible eigenvalue, assuming ∆ (c) expands the recursion. ■
22
A PPENDIX F P ROOF OF T HEOREM 2 Theorem 2. (Integrated Convergence) Let η ≤ mins∈S {1 − λ2 (Ãs ), α̂s2Γs }, then, for all global cycles k ∈ K, we have bounded first-order stationary point as follows: P τr +τ a −1 X 2 (2τr − 1)L̃(θ k,0 ) + αC1 s∈S Γs k,q ∇L̃(θ ) ≤ 2 η − α̂η2 Γ q=0 (33) 2 eff γ (1 − λN (A)) ˆ k,0 ∥2 + 4C2 ∥∆ + 4(τr − 1) 1 − λ2 (A) √ 2 where Γ = γ eff + τa B N , C1 = (τa +2τ2r −2)η , C2 = τa2 B 2 N τr (τa + τr − 1)2 , and α̂ = maxs∈S α̂s . Proof. Given any global round k ∈ K, we sum over the global gradients as follows: τa +τ r −1 X
∥∇L̃(θ
k,q
2
)∥ =
q=0
τX a −1
∥∇L̃(θ
k,q
2
)∥ +
τr +τ a −1 X
∥∇L̃(θ k,q )∥2 ,
(109)
q=τa
q=0
{z
|
|
}
(i)
{z
(ii)
}
where (i) is the intra-cluster regime k̃ with q ∈ {0, · · · , τa − 1}, and (ii) is the inter-cluster regime k̂ with q ∈ {τa , · · · , τr + τa − 1}. We bound the two components of (109) separately, starting with the intra-cluster regime component in (109)(i) τX a −1
τa −1 (a) X X
∥∇L̃(θ k,q )∥2 =
q=0
≤
(110)
s∈S q=0
(b) X L̃s (θ̂ k,0 ) + ατa η s 2 ≤ α̂s η 2 Γ η − s s∈S 2 (c)
∥∇L̃s (θ̂sk,q )∥2
P
s∈S
2
Γs
(111) 2
L̃s (θ̂sk,0 ) + ατ2a η Γs
(112) 2 η − α̂η2 Γ P ατa η 2 (d) L̃(θ k,0 ) + s∈S 2 Γs ≤ (113) 2 η − α̂η2 Γ T T P where (a) is from ∥∇L̃(θ k,q )∥2 = ∇L̃(θ k,q ) ∇L̃(θ k,q ) = s∈S ∇L̃s (θ̂sk,q ) ∇L̃s (θ̂sk,q ), (b) follows from Theorem 1, 2
2
(c) uses the fact that Γ ≥ Γs and α̂s ≥ α̂ so that η − α̂s2η Γs ≥ η − α̂η2 Γ, and (d) uses the definition of L̃(·) from (17). Next, for term (ii) in (109), we start by leveraging Proposition 1, as follows: √ 1 k,q k,q−1 ∥∇L̃(θ ) − ∇L̃(θ )∥ ≤ γ̂ + 1 + (1 − λN (A)) ∥θ k,q − θ k,q−1 ∥ + τa B N . (114) η Applying the triangle inequality to the left hand side of (114) and rearranging yields √ 1 ∥∇L̃(θ k,q )∥ ≤ ∥∇L̃(θ k,q−1 )∥ + γ̂ + 1 + (1 − λN (A)) ∥θ k,q − θ k,q−1 ∥ + τa B N η
(115)
ˆ k,q in Lemma 2 to obtain Next, we exploit the definition of ∆ θ k,q = θ and ˆ k,q = Ãθ Ã∆
k,q
k,q
ˆ k,q 1−∆ (e)
1 − Ãθ k,q = θ
k,q
(116) 1 − θ k,q+1 ,
(117)
where (117) holds only for q ∈ {τa , · · · , τa + τr − 1} and (e) is from the fact that A is doubly stochastic. Taking the difference between (116) and (117) gives ˆ k,q − A∆ ˆ k,q = (I − A)∆ ˆ k,q , θ k,q+1 − θ k,q = ∆ (118) which can be bounded above by (f )
ˆ k,q ∥ ∥θ k,q+1 − θ k,q ∥ ≤ ∥I − A∥∥∆
(119)
(g)
ˆ k,0 ∥, ≤ (1 − λN (A)) λ2 (A)q−1 ∥∆
(120)
23
where (f ) is from norm of the right hand side of (118), and (g) takes the largest eigenvalue of I − A and leverages Lemma 2. Substituting (120) into (115) enables the following: √ 1 ˆ k,0 ∥ + τa B N , ∥∇L̃(θ k,q )∥ ≤ ∥∇L̃(θ k,q−1 )∥ + γ̂ + 1 + (1 − λN (A)) (1 − λN (A)) λ2 (A)q−1 ∥∆ (121) η Expanding the recursive relationship in (121) then yields q−1 X √ 1 k,q k,0 ˆ k,0 ∥ + (q − 1)τa B N , ∥∇L̃(θ )∥ ≤ ∥∇L̃(θ )∥ + γ̂ + 1 + (1 − λN (A)) (1 − λN (A)) λ2 (A)p ∥∆ η p=0
(122)
and, after squaring both sides, (
)2 q−1 X √ 1 p ˆ k,0 ∥∇L̃(θ )∥ ≤ ∥∇L̃(θ )∥ + γ̂ + 1 + (1 − λN (A)) (1 − λN (A)) λ2 (A) ∥∆ ∥ + (q − 1)τa B N (123) η p=0 2 2 (h) 1 1 2 k,0 2 k,0 ˆ ≤ 2∥∇L̃(θ )∥ + 4 γ̂ + 1 + (1 − λN (A)) (1 − λN (A)) ∥∆ ∥ + 4τa2 B 2 N (q − 1)2 , (124) η 1 − λ2 (A) Pq−1 P∞ where (h) follows from (a + b)2 ≤ 2a2 + 2b2 applied twice and the fact that p=0 λ2 (A)p ≤ p=0 λ2 (A)p = 1−λ12 (A) . Summing (124) over q ∈ {τa , · · · , τa + τr − 1} yields k,q
2
τa +τ r −1 X
k,0
(i)
∥∇L̃(θ k,q )∥2 ≤ 2(τr − 1)∥∇L̃(θ k,0 )∥2
q=τa
2 1 2 + 4(τr − 1) γ̂ + 1 + (1 − λN (A)) (1 − λN (A)) η (j)
≤ 2(τr − 1)∥∇L̃(θ
k,0
ˆ k,0 ∥ ∥∆ 1 − λ2 (A)
!2 + 4τa2 B 2 N
(q − 1)2 ,
(125)
q=τa
2 1 2 )∥ + 4(τr − 1) γ̂ + 1 + (1 − λN (A)) (1 − λN (A)) η 2
τa +τ r −1 X
ˆ k,0 ∥ ∥∆ 1 − λ2 (A)
!2
+ 4τa2 B 2 N τr (τa + τr − 1)2 ,
(126) P τa +τr −1 2 where (i) expands the summation over q for non-q dependent terms, and (j) results from q=τa (q −1)2 ≤ q=τ q ≤ a 2 τr (τa + τr − 1) . Returning to (109), we combine the bounds for the intra-cluster and the inter-cluster terms as follows: P 2 τa +τ r −1 X L̃(θ k,0 ) + s∈S ατ2a η Γs k,q 2 ∥∇L̃(θ )∥ ≤ + 2(τr − 1)∥∇L̃(θ k,0 )∥2 α̂η 2 η − Γ q=0 2 !2 2 ˆ k,0 ∥ ∥∆ 1 2 + 4τa2 B 2 N τr (τa + τr − 1)2 (127) + 4(τr − 1) γ̂ + 1 + (1 − λN (A)) (1 − λN (A)) η 1 − λ2 (A) P αη 2 (k) 2τr L̃(θ k,0 ) + (τa + 2(τr − 1)) s∈S 2 Γs ≤ 2 η − α̂η2 Γ !2 2 ˆ k,0 ∥ 1 ∥∆ 2 + 4(τr − 1) γ̂ + 1 + (1 − λN (A)) (1 − λN (A)) + 4τa2 B 2 N τr (τa + τr − 1)2 , (128) η 1 − λ2 (A) Pτa +τr −1
where (k) leverages Theorem 1 with τa = 1 and. Finally, noting that γ eff = γ̂ + 1 + η1 (1 − λN (Ã)) and re-arranging (128) completes the proof. ■
24
A PPENDIX G A DDITIONAL E XPERIMENTS 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 [50] for both heterogeneous and homogeneous device ML optimizers in Appendix G-A. Subsequently, we examine SSD-FL when network devices have homogeneous SGD optimizers in appendix G-B and further examine the properties of the bound in Theorem 1 via investigating the variation in normalized intra-cluster gradients across datasets and local device ML optimizers in Appendix G-C. A. Varying Link Probabilities We examine the impact of increasing link formation probabilities from 10% to 50% in random graphs in Fig. 8 and 9. We do want to emphasize that, when link formation probability is 100%, the random graph has equivalent structure to the complete graphs shown in Sec. VI-E. For the case with heterogeneous ML optimizers at devices in Fig. 8, 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, SSDFL maintains a similar sized performance gap, roughly 4% and 13% respectively, regardless of the link formation probability and dataset. Experiments with homogeneous ML optimizers in Fig. 9 yield the similar takeaways.
pDFL
a) Mild non-i.i.d.
85
Accuracy (%)
sDFL
50
75
45
70
40
65
35
60
30
10% 20% 30% 40% 50% Link formation probability
cSTC
SSD-FL (Ours)
b) Extreme non-i.i.d.
55
80
STC
sDFL
pDFL
a) Mild non-i.i.d.
cSTC
38
62
35
58 32
54
29
50 46
10% 20% 30% 40% 50% Link formation probability
STC
b) Extreme non-i.i.d.
66
Accuracy (%)
SSD-FL (Ours)
10% 20% 30% 40% 50% Link formation probability
A) Experiments on the FMNIST dataset.
26
10% 20% 30% 40% 50% Link formation probability
B) Experiments on the CIFAR10 dataset.
FIGURE 8: Varying link formation probabilities from 10% to 50% for Erdős–Rényi random graphs. We evaluate both (a) FMNIST and (b) CIFAR10 datasets for networks with 30 devices, τa = 3, τr = 1, and heterogeneous ML optimizers at devices.
B. Homogeneous SGD Optimizers We list the experimental results for experiments varying intra-cluster duration τa in Fig. 10, inter-cluster period τr in Tables III-VI, underlying network graph architectures in Fig. 12, and network size in Fig. 11. In particular, regarding the intercluster period experiments, Tables III and V show results for networks with homogeneous SGD and heterogeneous optimizers across their devices, but only for τ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. TABLE III: The average global cycles for methods to reach accuracy thresholds on FMNIST with τr = 1. Networks with both SGD and heterogeneous optimizers are investigated. Dashes indicate thresholds that were not reached.
SGD optimizers Method
SSD-FL ONE ALL RGW RGP
Mild non-i.i.d. acc
Hybrid optimizers
Extreme non-i.i.d. acc
Mild non-i.i.d. acc
Extreme non-i.i.d. acc
51%
58%
65%
72%
30%
35%
40%
45%
51%
58%
65%
72%
30%
35%
40%
45%
4.02 5.29 5.39 4.39 5.02
6.35 10.16 9.95 7.45 8.59
10.45 18.65 19.30 13.61 17.11
19.71 – – – –
4.16 7.73 7.58 4.67 5.19
8.79 – 19.79 13.07 14.51
17.93 – – 19.94 –
– – – – –
3.50 5.01 5.06 3.64 3.81
5.45 10.77 10.38 5.69 5.90
9.24 – – 11.18 10.29
19.46 – – – –
3.48 8.79 8.91 3.68 3.71
7.11 – – 9.34 8.97
16.71 – – 19.37 18.45
– – – – –
25
85
Accuracy (%)
sDFL
a) Mild non-i.i.d.
pDFL 55
80
50
75
45
70
40
65
35
60
10% 20% 30% 40% 50% Link formation probability
30
STC
cSTC
SSD-FL (Ours)
b) Extreme non-i.i.d.
sDFL
pDFL
a) Mild non-i.i.d.
cSTC
38
62
35
58 32
54
29
50 46
10% 20% 30% 40% 50% Link formation probability
STC
b) Extreme non-i.i.d.
66
Accuracy (%)
SSD-FL (Ours)
10% 20% 30% 40% 50% Link formation probability
A) Experiments on the FMNIST dataset.
26
10% 20% 30% 40% 50% Link formation probability
B) Experiments on the CIFAR10 dataset.
FIGURE 9: Varying link formation probabilities from 10% to 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 aside from the choice of ML optimizers and, while the accuracies are lower, especially for CIFAR10 in Fig. 9B), the key takeaways remain identical.
pDFL pDFL pDFL
66
iii) Mild a = 5
70
65
65
v) Extreme a = 3
vi) Extreme a = 5
44
47
40
42
35
36
37
0
5
10 15 20
Global Cycle
32
48
75
38
32
a=5 a=3 a=1
cSTC cSTC cSTC
80
70
iv) Extreme a = 1
41
STC STC STC
ii) Mild a = 3
80 75
70
62
Accuracy (%)
i) Mild a = 1
sDFL sDFL sDFL
Accuracy (%)
Accuracy (%)
74
SSD-FL (Ours) SSD-FL (Ours) SSD-FL (Ours)
0
5
10 15 20
Accuracy (%)
a=5 a=3 a=1
32
0
Global Cycle
5
10 15 20
Global Cycle
SSD-FL (Ours) SSD-FL (Ours) SSD-FL (Ours)
i) Mild a = 1
sDFL sDFL sDFL
58
pDFL pDFL pDFL
ii) Mild a = 3
STC STC STC
61
46
54
56
44
50
51
cSTC cSTC cSTC
iii) Mild a = 5
42 46 46 v) Extreme a = 3 iv) Extreme a = 1 vi) Extreme a = 5 30 37 33 28 33 30 26 29 27 24 24 25 0 5 10 15 20 0 5 10 15 20 0 5 10 15 20
Global Cycle
A) Experiments on the FMNIST dataset.
Global Cycle
Global Cycle
B) Experiments on the CIFAR10 dataset.
FIGURE 10: Varying intra-cluster period τa for random networks with of size N = 10 with homogeneous SGD optimizers at devices. Both FMNIST, in Fig. 10A), and CIFAR10, in Fig. 10B), are investigated for mild and extreme non-i.i.d. scenarios.
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.
τr = 3 Method
SSD-FL ONE ALL RGW RGP
Mild non-i.i.d. acc
τr = 5 Extreme non-i.i.d. acc
Mild non-i.i.d. acc
Extreme non-i.i.d. acc
51%
58%
65%
72%
30%
35%
40%
45%
51%
58%
65%
72%
30%
35%
40%
45%
3.34 3.57 3.56 3.72 4.12
4.77 5.23 5.27 6.22 5.94
7.29 8.29 8.42 9.05 10.04
12.72 14.79 14.53 18.16 17.87
3.12 3.37 3.40 3.66 4.12
5.64 6.51 6.47 8.20 6.91
9.82 11.91 12.02 14.80 15.44
18.27 – – – –
2.98 3.10 3.08 3.61 3.84
4.14 4.40 4.39 5.86 5.42
6.31 6.68 6.67 8.50 9.23
10.57 11.34 11.37 17.69 15.91
2.72 2.75 2.74 3.65 3.65
4.76 5.06 5.01 7.61 5.87
7.86 8.62 8.32 14.21 11.84
14.07 15.51 15.62 – –
26
TABLE V: The average global cycles for methods to reach accuracy thresholds on CIFAR10 with τr = 1. Networks with both SGD and heterogeneous optimizers are investigated. Dashes indicate thresholds that were not reached.
SGD optimizers Method
SSD-FL ONE ALL RGW RGP
Mild non-i.i.d. acc
Hybrid optimizers
Extreme non-i.i.d. acc
Mild non-i.i.d. acc
Extreme non-i.i.d. acc
36%
40%
44%
48%
22%
25.5%
29%
32.5%
36%
40%
44%
48%
22%
25.5%
29%
32.5%
8.35 8.74 8.50 8.78 8.89
13.12 14.35 14.68 13.51 15.01
18.91 – – 18.99 –
– – – – –
3.98 4.62 4.78 4.33 4.79
9.95 17.77 17.47 9.72 14.44
– – – – –
– – – – –
7.38 7.12 7.29 7.70 7.59
10.96 12.29 12.13 12.32 11.53
16.15 19.92 19.26 16.87 16.39
– – – – –
3.79 4.38 4.51 3.85 3.57
8.29 15.72 15.53 9.82 11.16
16.76 – – – –
– – – – –
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.
τr = 3 Method
58%
65%
72%
30%
35%
40%
45%
51%
58%
65%
72%
30%
35%
40%
45%
10.79 11.31 11.36 11.28 12.38
15.23 16.26 16.26 17.24 17.91
– – – – –
3.26 3.16 3.10 2.97 4.68
7.00 7.01 7.25 8.45 9.52
13.06 14.31 14.65 15.82 19.53
– – – – –
6.89 7.01 6.96 7.88 7.55
9.72 10.12 10.22 11.04 11.08
14.05 14.23 14.35 16.91 16.91
18.94 – – – –
2.96 2.92 2.93 2.98 4.46
5.94 6.08 6.32 8.21 8.62
11.59 11.96 11.94 14.97 17.39
19.59 – – – –
pDFL
STC
cSTC
10
20 30 40 Network Size N
50
Accuracy (%)
sDFL
a) Mild non-i.i.d.
pDFL
78
48
74
44
70
40
66
36 20 30 40 Network Size N
50
32
STC
cSTC
SSD-FL (Ours)
b) Extreme non-i.i.d.
56 52
10
Extreme non-i.i.d. acc
51%
82
62
Mild non-i.i.d. acc
7.49 7.63 7.60 7.96 7.95
SSD-FL (Ours) 86
τr = 5 Extreme non-i.i.d. acc
sDFL
a) Mild non-i.i.d.
33
50 30
46
27
42 10
20 30 40 Network Size N
A) Experiments on the FMNIST dataset.
50
b) Extreme non-i.i.d.
36
54 Accuracy (%)
SSD-FL ONE ALL RGW RGP
Mild non-i.i.d. acc
38
10
20 30 40 Network Size N
50
24
B) Experiments on the CIFAR10 dataset.
FIGURE 11: Varying network size from N = 10 to N = 50 with 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 and 5, the main takeaways remain the same.
27
SSD-FL (Ours)
sDFL
pDFL
STC
cSTC
SSD-FL (Ours)
b) Extreme non-i.i.d.
sDFL
pDFL
a) Mild non-i.i.d.
STC
cSTC
b) Extreme non-i.i.d.
RNG
RNG
Graph architecture
Graph architecture
PrefA RGeo SWorld Comp
PrefA RGeo SWorld Comp
a) Mild non-i.i.d.
60
70
Accuracy (%)
80
30
40
50
60
Accuracy (%)
70
80
35
40
A) Experiments on the FMNIST dataset.
45
50
Accuracy (%)
55
60 20
25
30
35
Accuracy (%)
40
45
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 and 7, SSD-FL consistently demonstrates superior performance with complete networks being the exception.
C. Normalized Intra-Cluster Gradients We also investigate the impact of heterogeneous/homogeneous ML optimizers and intra-cluster period τa on the average effective intra-cluster first order stationary point from Theorem 1. While the nominal differences across datasets and optimizers are small in Fig. 13 and 14, there is an important point. As τa grows, the almost parabolic nature of average gradients shifts, yielding a different optimal number of clusters. For instance, in Fig. 13A), we can see the optimal or minimum point shift from S = 4 to S = 2 as τa grows from 1 to 5. 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. a=1
S*
a=3
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
1 2 3 4 5 6 7 8 9 10
Number of Clusters S
b) CIFAR10
a=5
a=1
1.0
S*
Est Avg Grad
Est Avg Grad
1.0
a) FMNIST
a=3
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
1 2 3 4 5 6 7 8 9 10
S*
a) FMNIST
Number of Clusters S
1 2 3 4 5 6 7 8 9 10
0.0
Number of Clusters S
A) Experiments with mild non-i.i.d. datasets at devices.
b) CIFAR10
a=5
S*
1 2 3 4 5 6 7 8 9 10
Number of Clusters S
B) Experiments with extreme non-i.i.d. datasets at devices.
FIGURE 13: Average intra-cluster effective gradients from Theorem 1 for networks with heterogeneous ML optimizers at devices. As the intra-cluster period τa increases, the average intra-cluster effective gradients decrease in relative magnitude.
a=1
S*
a=3
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
1 2 3 4 5 6 7 8 9 10
Number of Clusters S
b) CIFAR10
a=5
a=1
1.0
S*
Est Avg Grad
Est Avg Grad
1.0
a) FMNIST
1 2 3 4 5 6 7 8 9 10
Number of Clusters S
A) Experiments with mild non-i.i.d. datasets at devices.
S*
a) FMNIST
a=3
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
1 2 3 4 5 6 7 8 9 10
Number of Clusters S
0.0
b) CIFAR10
a=5
S*
1 2 3 4 5 6 7 8 9 10
Number of Clusters S
B) Experiments with extreme non-i.i.d. datasets at devices.
FIGURE 14: The influence of intra-cluster period τa on the average intra-cluster effective gradients for networks with homogeneous SGD optimizers at devices.