PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Stage Hybrid Federated Learning over Large-Scale D2D-Enabled Fog Networks

Seyyedali Hosseinalipour, Sheikh Shams Azam, Christopher G. Brinton, Nicolo Michelusi, Vaneet Aggarwal, David J. Love, Huaiyu Dai

arXiv:2007.09511v5cs.NIcs.LG

TL;DR

Conventional federated learning relies on device–server communication, which is limiting in multi-layer networks. MH-FL combines D2D consensus within clusters with multi-stage aggregation across layers. Its analysis establishes finite-round convergence conditions, and real-world experiments report improved resource utilization with negligible impact on training convergence speed and accuracy.

  • Problem

    Conventional federated learning’s device–server communication is limiting in multi-layer networks, where aggregation can involve long delays, high bandwidth use, and high power consumption.

    Source: §I · p. 1

  • Method

    MH-FL relays local updates through a multi-layer cluster hierarchy, combining D2D consensus within clusters with inter-layer aggregation.

    Source: C. Summary of Contributions · p. 3, C. Hybrid Learning via Intra- and… · p. 4

  • Results

    Unlimited-D2D MH-FL matches federated-learning loss, while finite rounds can yield a constant asymptotic gap or linear convergence; real-world tests report improved resource utilization.

    Source: C. Summary of Contributions · p. 3

  • Takeaways & Limitations

    Real-world experiments report improved network resource utilization with negligible impact on model convergence speed and accuracy.

    Source: C. Summary of Contributions · p. 3

    Communication imperfections, interference management, stragglers, and device scheduling in the multi-stage fog setting remain future-work directions.

    Source: §V · p. 13

Abstract

from arXiv · show

Federated learning has generated significant interest, with nearly all works focused on a "star" topology where nodes/devices are each connected to a central server. We migrate away from this architecture and extend it through the network dimension to the case where there are multiple layers of nodes between the end devices and the server. Specifically, we develop multi-stage hybrid federated learning (MH-FL), a hybrid of intra- and inter-layer model learning that considers the network as a multi-layer cluster-based structure. MH-FL considers the topology structures among the nodes in the clusters, including local networks formed via device-to-device (D2D) communications, and presumes a semi-decentralized architecture for federated learning. It orchestrates the devices at different network layers in a collaborative/cooperative manner (i.e., using D2D interactions) to form local consensus on the model parameters and combines it with multi-stage parameter relaying between layers of the tree-shaped hierarchy. We derive the upper bound of convergence for MH-FL with respect to parameters of the network topology (e.g., the spectral radius) and the learning algorithm (e.g., the number of D2D rounds in different clusters). We obtain a set of policies for the D2D rounds at different clusters to guarantee either a finite optimality gap or convergence to the global optimum. We then develop a distributed control algorithm for MH-FL to tune the D2D rounds in each cluster over time to meet specific convergence criteria. Our experiments on real-world datasets verify our analytical results and demonstrate the advantages of MH-FL in terms of resource utilization metrics.

I. INTRODUCTION

MH-FL extends federated learning to layered fog networks by combining local D2D consensus with multi-stage parameter aggregation. The paper analyzes convergence and reports real-world resource-utilization gains.

I. INTRODUCTION

  • Conventional federated learning’s direct device–server exchanges can cause long delays, high bandwidth use, and high aggregation power consumption in multi-layer networks.The paper motivates extending its star topology to account for multiple network layers and device topology.Source: §I · p. 1

A. Fog Learning: Federated Learning in Fog Environments

  • FogL extends federated learning across multi-layer clusters, combining inter-layer communication with intra-layer D2D and cooperative consensus.The paper calls this semi-decentralized hybrid learning MH-FL and considers time-varying local network topologies.Source: A. Fog Learning: Federated Learning in… · pp. 1–2

B. Related Work

  • Prior hierarchical federated-learning work mainly considers specific two-tier settings, while MH-FL supports arbitrary-height clusters and explicitly models D2D topology.The paper also distinguishes its hybrid learning analysis from prior consensus and ML literature.Source: B. Related Work · pp. 2–3

C. Summary of Contributions

  • MH-FL relays end-device updates through a hierarchy using multi-stage cluster aggregation, with local aggregations formed through cooperative D2D consensus.The paper develops cluster-level distributed control to adapt D2D rounds over time.Source: C. Summary of Contributions · p. 3
  • Unlimited D2D rounds make MH-FL’s model loss coincide with federated learning; finite rounds can yield a constant asymptotic gap or linear convergence to the optimum.The convergence bound depends on model, topology, and algorithm characteristics, including communication-graph structure and D2D rounds.Source: C. Summary of Contributions · p. 3
  • Real-world experiments verify the theoretical findings and report significantly improved network resource utilization with negligible impact on convergence speed and accuracy.The contribution passage labels the method “MH-MT.”Source: C. Summary of Contributions · p. 3

A. Network Architecture and Graph Model

  • The FogL hierarchy places the main server at the root and devices at the leaves, while an augmented graph adds virtual nodes to establish parent-cluster mappings.Within clusters, nodes form connected graphs for D2D communication, so the network is tree-like at the macro scale but not within clusters.Source: A. Network Architecture and Graph Model · p. 3, Figure 3 · p. 3

B. Machine Learning Task

  • Each device trains on its local dataset toward a global weighted-average model; LUT clusters use D2D consensus and one-child sampling, while EUT clusters upload each child’s model.The architecture reduces to federated learning in the single-layer, single-EUT-cluster case and resembles fully distributed learning with one LUT cluster and no server.Source: B. Machine Learning Task · p. 4, C. Hybrid Learning via Intra- and… · pp. 4–5

D. Parameter Sharing vs. Gradient Sharing

This section distinguishes parameter sharing from gradient sharing and describes distributed average consensus for local aggregation. Cluster D2D communication runs over a time-varying topology, with a finite number of rounds often leaving an imperfect average estimate.

D. Parameter Sharing vs. Gradient Sharing

  • Parameter sharing is the paper’s general case; gradients can yield the same global parameters under a one-step update, while multiple local updates require parameters at each aggregation.The paper also derives one theoretical result based on gradient sharing.Source: D. Parameter Sharing vs. Gradient… · p. 5

A. Distributed Average Consensus within Clusters

  • In each LUT cluster, nodes use D2D consensus rounds to estimate the average of their parameters without collecting a full table of cluster parameters at every node.Each round transfers parameters between neighboring nodes; the number of rounds is a design parameter.Source: D. Parameter Sharing vs. Gradient… · p. 5, A. Distributed Average Consensus… · p. 5
  • The cluster communication graph is undirected, connected, and static within one global iteration, although it may vary between iterations.Consensus convergence requires a connected graph; a disconnected cluster can be partitioned into connected subgraphs with the same parent.Source: A. Distributed Average Consensus… · pp. 5–6
  • Time constraints limit D2D rounds, so nodes often do not obtain a perfect estimate of their cluster’s parameter average.The paper analyzes how this finite-round consensus affects MH-FL performance.Source: A. Distributed Average Consensus… · p. 6

B. Local Aggregations and Parameters Propagation

MH-FL relays scaled parameters through the hierarchy, combining local cluster aggregation with parent-child transfers. The server forms and broadcasts the global model, with additional D2D-round tuning available for convergence control.

B. Local Aggregations and Parameters Propagation

1) Nodes’ parameters in the bottom-most layer:

  • At the bottom layer, devices weight their parameters by their datapoint counts before D2D consensus, encoding those counts in the multi-layer aggregations.The final local parameter after D2D rounds is stored by each device.Source: 1) Nodes’ parameters in the… · p. 6

2) Nodes’ parameters in the middle layers:

  • In middle layers, a parent samples a child’s parameter in LUT clusters, while EUT clusters share child parameters directly; LUT consensus can introduce deviation from the true cluster average.The parent scales the received vector by the number of its children before relaying it upward.Source: 2) Nodes’ parameters in the middle… · p. 6

3) Main server:

  • The main server computes the global parameter from received parameters and broadcasts it down the hierarchy to begin the next global round.For asymptotic convergence to the optimum, the server may also approximate and broadcast the next-iteration loss gradient.Source: 3) Main server · pp. 6–7
  • The algorithm’s starred and double-hash steps add online tuning of D2D rounds at different clusters.The paper’s control algorithms tune those rounds over time to meet convergence criteria.Source: 3) Main server · p. 7

C. Theoretical Analysis of MH-FL

The theoretical analysis studies how topology and finite D2D consensus affect MH-FL convergence. It relates cluster divergence to data heterogeneity and uses that quantity to guide D2D-round control.

C. Theoretical Analysis of MH-FL

  • The analysis examines MH-FL’s performance under limited D2D rounds, with explicit attention to network topology and consensus.The paper identifies this effect as the main theme of its theoretical analysis.Source: C. Theoretical Analysis of MH-FL · p. 7
  • The convergence analysis assumes a globally µ-strongly convex and η-smooth loss function, with η greater than µ.The paper identifies these as common assumptions in federated learning and machine learning literature.Source: C. Theoretical Analysis of MH-FL · p. 7
  • The consensus update is represented using a matrix of scaled node parameters before consensus and a consensus matrix applied to those parameters.The passage identifies the parameter matrix and consensus matrix in the update representation.Source: C. Theoretical Analysis of MH-FL · p. 7
  • Cluster divergence Υ is an upper bound on differences between nodes’ scaled parameters and reflects data heterogeneity within bottom-layer clusters and subtrees above them.The analysis links divergence to the convergence bound and uses it to determine D2D rounds.Source: C. Theoretical Analysis of MH-FL · p. 7

1) General convergence bound:

The convergence bound links MH-FL’s expected loss to learning and network parameters, including cluster connectivity, D2D rounds, and parameter divergence. The asymptotic results give D2D-round conditions for a finite optimality gap or linear convergence to the optimum.

1) General convergence bound:

  • The bound depends on loss characteristics, cluster sizes, spectral-radius bounds, D2D rounds, and parameter divergence; more rounds or better connectivity lower it, while greater divergence worsens it.Errors from earlier global iterations are dampened, while later errors have a more pronounced effect on the bound.Source: 1) General convergence bound · pp. 7–8

2) Asymptotic optimality:

  • Proposition 1’s D2D-round criteria provide a design guideline for a finite optimality gap, with rounds tapering over time as parameter divergence is expected to decrease.The policy uses fixed layer-specific control parameters; smaller spectral radii are associated with fewer required rounds.Source: 2) Asymptotic optimality · pp. 8–9
  • Under stricter D2D-round tuning, Proposition 2 guarantees linear convergence to the optimum at a rate no faster than 1 − µ/η, with finite rounds while tuning variables remain positive.The policy boosts rounds over time and stops at the optimal point, where the loss gradient is zero.Source: 2) Asymptotic optimality · pp. 8–9
  • The Proposition 2 policy assumes knowledge of the global loss gradient, which is unavailable at the start of an iteration and therefore requires an approximation in practice.The model weight is then sent down through the layers.Source: 2) Asymptotic optimality · p. 9

3) Relationship between global iterations and D2D rounds:

The paper relates D2D-round policies to the global iterations needed for a target accuracy and develops distributed controls for choosing rounds across time and network layers. It also gives a slower convergent gradient-sharing alternative and identifies cluster sampling as a technique for further study.

3) Relationship between global iterations and D2D rounds:

  • The corollaries give sufficient D2D rounds to reach a target accuracy by a chosen iteration, or sufficient global iterations for a target accuracy under a predetermined D2D policy.The conditions include both finite-gap and asymptotic-convergence policies.Source: 3) Relationship between global… · p. 9

4) Varying gradient step size:

  • Under the stated conditions, gradient-sharing MH-FL converges to the optimum: its expected optimality gap tends to zero at O(1/k), slower than Proposition 2’s linear rate but allowing D2D rounds to taper.Source: 4) Varying gradient step size · p. 9

5) Cluster sampling:

  • Cluster sampling activates only a portion of clusters at each global iteration and extends the convergence analysis, but further investigation of the technique is left to future work.It is proposed as a way to reduce upstream communications in networks with millions of nodes.Source: 5) Cluster sampling · p. 9

D. Control Algorithms for Distributed Consensus Tuning

  • Policies A and B distribute real-time D2D-round tuning to cluster parent nodes using cluster-topology estimates; A tapers rounds, while B boosts them to target linear convergence.With increasing ω, the scheme tolerates less consensus error and requires more D2D rounds, trading those rounds against the number of global iterations.Source: 1) Adaptive D2D for loss functions… · pp. 9–10

1) Adaptive D2D for loss functions satisfying Assumption 1:

  • For Policy B, the server estimates the global gradient norm using a tuning parameter ω and broadcasts the estimate; cluster heads use it with δ and network parameters to calculate round counts.The estimate relies on an approximation from the preceding iteration’s gradient norm.Source: 1) Adaptive D2D for loss functions… · p. 10

2) Adaptive D2D tuning for non-convex loss functions:

For non-convex losses outside the stated assumption, the paper proposes a heuristic D2D-round tuning procedure. It bounds aggregation error by a specified tolerance ψ.

2) Adaptive D2D tuning for non-convex loss functions:

  • For non-convex losses, the heuristic procedure uses a maximum tolerable aggregation error ψ at each global iteration and bounds the aggregation-error 2-norm by ψ.Each parent node receives ψ and its layer’s node count before training; the procedure replaces the convex-loss tuning algorithm.Source: 2) Adaptive D2D tuning for non-convex… · pp. 10–11

IV. EXPERIMENTAL EVALUATION

The experiments evaluate MH-FL on MNIST across network configurations, data distributions, and model types. They examine convergence behavior, adaptive D2D tuning, and resource use against the EUT baseline.

A. Experimental Setup; V. CONCLUSION AND FUTURE WORK

  • The evaluation uses a three-layer fog network with 125 bottom-layer devices and MNIST, including i.i.d. and non-i.i.d. data and SVM and NN classifiers.The paper identifies joint optimization of device partitioning and LUT/EUT operation as future work.Source: A. Experimental Setup · p. 11, §V · p. 13

B. MH-FL with Fixed Consensus Rounds

  • With more than 15 fixed D2D rounds per cluster, MH-FL achieves performance comparable to EUT; with 1 or 2 rounds, convergence is not achieved in all cases.Increasing consensus rounds improves accuracy and training stability.Source: 1) MH-FL with fixed step size · p. 11, Figure 5 · p. 12
  • Decreasing the gradient-descent step size can yield convergence to the optimum when a fixed step size cannot, but convergence is slower.The paper reports a trade-off between more constant-rate D2D rounds with faster convergence and fewer decaying-rate rounds with lower power consumption but slower convergence.Source: 2) MH-FL with decaying step size · p. 11, Figure 6 · p. 12

C. MH-FL with Adaptive D2D Round Tuning

4) Analytical vs. experimental bound comparison:

D. Network Resource Utilization

APPENDIX A PROOF OF THEOREM 1

The proof builds the convergence bound in stages, first treating arbitrary local aggregation errors and then bounding the error introduced by D2D consensus. It combines these results into the final bound.

APPENDIX A PROOF OF THEOREM 1

  • The proof proceeds in three parts: bound convergence with arbitrary aggregation errors, bound D2D consensus error, and derive the final convergence bound.This is the stated proof structure for Theorem 1.Source: Appendix A · p. 15

A. PART I: Convergence Bound for General Local Aggregation Error at the Sampled Nodes

C. PART III: Obtaining the Final Convergence Bound

This proof section completes the final convergence-bound derivation and then establishes the stated D2D-round proposition through a limiting argument.

C. PART III: Obtaining the Final Convergence Bound

  • Substituting the preceding inequality into the earlier bound and expanding recursively yields the theorem result.The proof adds and subtracts the optimal objective value before the recursive expansion.Source: C. PART III: Obtaining the Final… · p. 19

APPENDIX B PROOF OF PROPOSITION 1

  • The Proposition 1 proof applies the stated D2D-round bound and takes the limit with respect to global iteration k.The supplied proof concludes after that limiting step.Source: Appendix B · pp. 19–20

APPENDIX C PROOF OF PROPOSITION 2

The appendix verifies the D2D-round condition for Proposition 2, derives iteration requirements for two corollaries, and proves Proposition 3 by bounding expected objective error.

APPENDIX C PROOF OF PROPOSITION 2

  • For Proposition 2, the proof combines the proposed D2D-round condition with bounds on the objective decrease to obtain the proposition result.It also invokes smoothness and strong convexity of F.Source: Appendix C · p. 20

APPENDIX D PROOF OF COROLLARY 1

  • The Corollary 1 proof derives sufficient conditions for the requested accuracy and rearranges them into the stated iteration requirements.It treats the corollary's two conditions separately.Source: Appendix D · p. 21

APPENDIX E PROOF OF COROLLARY 2

  • The Corollary 2 proof obtains the iteration count κ by taking logarithms of the two conditions involving the convergence factors.The proof notes that the logarithm bases are positive and less than one.Source: Appendix E · p. 21

APPENDIX F PROOF OF PROPOSITION 3

  • For Proposition 3, induction establishes a bound on expected objective error while the proposed D2D rounds bound the consensus error.The proof uses the consensus-error bound in its induction step.Source: Appendix F · p. 24

APPENDIX G CLUSTER SAMPLING

Cluster sampling engages selected bottom-layer clusters and the paths linking them to the main server, producing active and passive nodes and clusters. The appendix gives a convergence bound for this setting, notes how the bound changes with the number of active clusters, and leaves a full analysis of convergence and D2D-round counts for future work.

APPENDIX G CLUSTER SAMPLING

  • At each global iteration, the server selects bottom-layer clusters; nodes on their paths to the server are active, while the remaining clusters are passive.A middle-layer cluster is active if it contains at least one active node.Source: Appendix G · pp. 25–26
  • The analysis adds a stochastic-optimization assumption bounding each device’s squared gradient norm by a constant plus a multiple of the global squared gradient norm.The passage identifies this as an assumption common in stochastic optimization literature.Source: Appendix G · p. 25
  • The appendix states an upper bound on the objective-function convergence of MH-FL with cluster sampling.The bound uses the number of sampled devices’ data points at iteration k.Source: Appendix G · p. 25
  • The authors leave extending their earlier convergence and D2D-round derivations to cluster sampling for future work.They observe that increasing the number of active clusters often decreases the bound’s right-hand side.Source: Appendix G · p. 27
  • Increasing the number of active clusters often reduces the bound’s right-hand side, implying higher training accuracy and greater similarity to the bound without sampling.When all clusters are active, the bound has a form similar to the earlier bound, but with a larger coefficient.Source: Appendix G · p. 27

APPENDIX H AGGREGATION ERROR UPON USING ALGORITHM 3

This appendix sketches the aggregation-error derivation for Algorithm 3, including a layer-summed expression after applying the D2D-round tuning rule.

APPENDIX H AGGREGATION ERROR UPON USING ALGORITHM 3

  • The appendix begins by giving an expression for aggregation error at the k-th global aggregation.The subsequent passage says the derivation follows a procedure from Appendix A.Source: Appendix H · p. 29
  • The derivation defines Φ as a sum of layer-size terms, then applies the D2D-round tuning rule to obtain a further expression.The displayed expression is described as having |L| terms.Source: Appendix H · p. 29
  • The resulting expression repeats a term involving ψ, Φ, D, and the number of layers |L| across |L| terms.The passage does not state a further interpretation of this expression.Source: Appendix H · p. 29

APPENDIX I DETAILS OF THE SIMULATIONS SETTING AND FURTHER SIMULATIONS

The appendix reports simulation settings for SVM and neural-network classifiers on MNIST and Fashion-MNIST, with i.i.d. and non-i.i.d. data splits. It evaluates fog networks with 125 or 625 devices arranged in groups of five across layers.

1) Setup:

  • Simulations run on one machine using PySyft to emulate distributed learning over PyTorch.The machine has 64 GB RAM and 8 GB GPU memory; virtual nodes use mutually exclusive parameters and datasets.Source: 1) Setup · p. 30

2) Classifiers:

  • Experiments use regularized SVM and fully connected neural-network classifiers initialized from a copy of the global model.The SVM is tuned with µ = 0.1 and η = 10; the one-hidden-layer NN has 7,850 parameters and uses softmax, negative log-likelihood, and L2 regularization.Source: 2) Classifiers · p. 30

3) Datasets and Data Distribution among the Nodes:

  • MNIST and Fashion-MNIST each provide 60,000 training and 10,000 test images, split across devices into i.i.d. or non-i.i.d. class distributions.Each device has approximately the same number of training samples; under non-i.i.d. distribution, each device has samples from only one class.Source: 3) Datasets and Data Distribution… · p. 30

4) Network Formation:

  • The 125-device network has three sublayers and the 625-device network has four, with nodes clustered in groups of five at successive layers.Within-cluster D2D links use random geometric graphs, with distance thresholds increasing toward the server: 40 m at the bottom layers, then 50 m and 60 m at upper layers.Source: 4) Network Formation · p. 30

B. Further Simulation Results

Supplementary simulations examine convergence, D2D-round controls, energy use, and parameter transmissions across MNIST and Fashion-MNIST network configurations. They report trade-offs as control parameters change and compare simulated convergence with the derived upper bound.

Energy and Parameter Transmission Savings under Various D2D Control Parameters and Tolerable Aggregation Errors

  • Increasing σ′ often saves energy by reducing D2D rounds, but too few rounds can slow convergence enough to require considerably more global aggregations.Parameter transmissions may rise slightly as σ′ increases; MH-FL outperforms EUT in both energy consumption and parameter transmissions in the reported cases.Source: C. Energy and Parameter Transmission… · pp. 31–32
  • For moderate-to-high ψ (ψ ≥ 10^3), MH-FL outperforms EUT in energy consumption across the reported scenarios, while increasing ψ often raises parameter transmissions.At small ψ, such as ψ = 10, MH-FL can consume more energy than EUT; increased transmissions often reflect more global aggregations to reach target accuracy.Source: C. Energy and Parameter Transmission… · p. 32

B. Further Simulation Results

  • With fixed D2D rounds per cluster, increasing the round count makes MH-MT more like the EUT baseline and stabilizes learning in non-i.i.d. settings.The figure captions report this pattern for MNIST with 625 devices and Fashion-MNIST with 125 and 625 devices.Source: Figure 16 · p. 33, Figure 27 · p. 34, Figure 38 · p. 36
  • For finite-gap and linear-convergence controls, the simulations vary σ′, δ, and ψ to examine D2D-round tapering across time and network layers.The captions report these patterns for i.i.d. and non-i.i.d. settings across the listed MNIST and Fashion-MNIST configurations.Source: Figure 18 · p. 33, Figure 22 · p. 33, Figure 19 · p. 33
  • In the step-size comparisons, decreasing the gradient-descent step size can enable convergence to the optimum when a fixed step size cannot, but convergence is slower.The figure captions report this comparison for MNIST with 625 devices and Fashion-MNIST with 125 and 625 devices.Source: Figure 17 · p. 33, Figure 28 · p. 34, Figure 39 · p. 36
  • Across the reported simulations, practical convergence is faster than the derived upper bound on global iterations to reach the target accuracy.This comparison is reported for MNIST with 625 devices and Fashion-MNIST with 125 and 625 devices.Source: Figure 24 · p. 34, Figure 35 · p. 35, Figure 46 · p. 37
Loading 2007.09511v5…