PaperlayerView exact revision on arXiv

Source-linked AI summary

Hierarchical Federated Learning with Quantization: Convergence Analysis and System Design

Lumin Liu, Jun Zhang, Shenghui Song, Khaled B. Letaief

arXiv:2103.14272v2cs.LG

TL;DR

Hierarchical federated learning with quantization lacks a sufficiently tight convergence analysis to guide communication-efficient system design. This paper proposes Hier-Local-QSGD and derives a tighter convergence bound, yielding adaptive aggregation-interval guidelines validated by simulations.

  • Problem

    Existing convergence analyses for hierarchical federated learning are loose and do not account for model quantization, limiting theoretical support for system design.

  • Method

    The paper proposes Hier-Local-QSGD with quantized client-edge and edge-cloud aggregation, then derives a tighter convergence bound for system design.

  • Results

    The analysis improves the local-update error term from quadratic to linear and supports adaptive selection of the two aggregation intervals, whose effectiveness simulations verify.

  • Takeaways & Limitations

    The client-edge aggregation interval should slowly decay, while the edge-cloud interval should adapt to the ratio of client-edge and edge-cloud propagation delays.

  • Takeaways & Limitations

    The analysis assumes IID data, so its conclusion that edge-client association does not affect convergence speed does not directly extend to non-IID settings.

Abstract

from arXiv · show

Federated learning (FL) is a powerful distributed machine learning framework where a server aggregates models trained by different clients without accessing their private data. Hierarchical FL, with a client-edge-cloud aggregation hierarchy, can effectively leverage both the cloud server's access to many clients' data and the edge servers' closeness to the clients to achieve a high communication efficiency. Neural network quantization can further reduce the communication overhead during model uploading. To fully exploit the advantages of hierarchical FL, an accurate convergence analysis with respect to the key system parameters is needed. Unfortunately, existing analysis is loose and does not consider model quantization. In this paper, we derive a tighter convergence bound for hierarchical FL with quantization. The convergence result leads to practical guidelines for important design problems such as the client-edge aggregation and edge-client association strategies. Based on the obtained analytical results, we optimize the two aggregation intervals and show that the client-edge aggregation interval should slowly decay while the edge-cloud aggregation interval needs to adapt to the ratio of the client-edge and edge-cloud propagation delay. Simulation results shall verify the design guidelines and demonstrate the effectiveness of the proposed aggregation strategy.

I. INTRODUCTION … A. FL Problem

The paper motivates communication-efficient hierarchical federated learning and develops a quantized two-level training framework with tighter convergence analysis. It connects the analysis to aggregation-interval control, edge-client association, and the federated learning objective.

  • I. INTRODUCTION: Hierarchical federated learning combines client-edge and edge-cloud aggregation to reduce communication latency, while quantization reduces model-update communication at an accuracy cost.The motivation is especially relevant for large models and wireless client-server links.
  • I. INTRODUCTION: The paper targets accurate convergence analysis because aggregation-interval variance determines practical communication-cost optimization under a fixed training-time budget.The analysis is intended to support system design rather than only theoretical understanding.
  • B. Contributions: An adaptive interval-control algorithm makes τ1 decay according to training loss and selects τ2 using propagation-delay and client-edge-server ratios.The framework is designed to optimize the two aggregation intervals using the derived convergence upper bound.
  • A. Related Works: Prior work established convergence for two-layer FL and quantized FedAvg, but hierarchical-FL analyses largely considered full-precision updates or obtained looser bounds.Existing hierarchical analyses included quadratic aggregation-interval error and, in one case, impractical full-batch client optimization.
  • B. Contributions: The proposed Hier-Local-QSGD algorithm uses client quantized uploads after τ1 local steps and edge quantized uploads after τ2 edge-aggregation steps.The system contains one cloud server, s edge servers, and n clients.
  • B. Contributions: Hier-Local-QSGD reduces aggregation-interval variance from quadratic to linear and reaches a first-order stationary point at O(1/√Kτ1τ2) after K cloud rounds.The stated iteration count is Kτ1τ2 local update iterations.
  • B. Contributions: The analysis recommends infrequent client-edge aggregation when quantization variance exceeds a threshold, while edge-client association does not affect convergence for fixed client and edge-server counts.These guidelines directly connect convergence behavior to hierarchical system design.
  • A. FL Problem: The federated learning problem defines each client’s empirical loss from its local dataset and minimizes a global loss over the joint dataset D = ⋃_{i=1}^n D_i.The training goal is a global model that performs well on the joint data distributions.

B. Training Algorithm of Two-Layer FL and Hierarchical FL

The section describes two-layer FedAvg and hierarchical FL training, where local client updates are aggregated centrally or through edge servers and a cloud server. It then introduces Hier-Local-QSGD to exploit the client–edge–cloud hierarchy for communication-efficient training.

  • B. Training Algorithm of Two-Layer FL and Hierarchical FL: In two-layer FL, each client performs τ local SGD steps, uploads its update, and receives the centrally averaged model until accuracy or resource limits are reached.
  • B. Training Algorithm of Two-Layer FL and Hierarchical FL: Cloud aggregation incorporates many clients but has high communication cost, whereas edge aggregation serves fewer clients at lower cost.
  • B. Training Algorithm of Two-Layer FL and Hierarchical FL: Hierarchical FL combines one cloud server with s edge servers and disjoint client groups, leveraging the client–edge–cloud communication hierarchy.
  • B. Training Algorithm of Two-Layer FL and Hierarchical FL: The proposed Hier-Local-QSGD algorithm uses the hierarchical architecture to improve communication efficiency through two algorithmic modules.

1) Frequent Edge Aggregation and Infrequent Cloud Aggregation: · 2) Quantized Model Updates: · III. CONVERGENCE ANALYSIS

The paper analyzes Hier-Local-QSGD, which combines frequent low-latency edge aggregation, infrequent cloud aggregation, and quantized model updates. Its convergence analysis assumes smooth losses, bounded unbiased stochastic-gradient variance, and unbiased quantization noise proportional to update magnitude.

  • 1) Frequent Edge Aggregation and Infrequent Cloud Aggregation:: Larger aggregation intervals reduce communication rounds but can degrade performance by steering local models toward local rather than global loss optima.The tradeoff motivates frequent edge aggregation and less frequent cloud aggregation.
  • 1) Frequent Edge Aggregation and Infrequent Cloud Aggregation:: Hier-Local-QSGD aggregates client models at edge servers every τ1 local updates and aggregates edge models at the cloud every τ2 edge aggregations.This hierarchy exploits lower edge propagation latency while reducing the frequency of cloud communication.
  • 2) Quantized Model Updates:: Quantization reduces transmitted model-update size and communication overhead, but low precision introduces training noise that can degrade the trained model.The analysis therefore investigates quantization effects rather than treating communication reduction independently of optimization performance.
  • 2) Quantized Model Updates:: The method uses Q1 for client-to-edge updates and Q2 for edge-to-cloud updates, with random sparsification and stochastic rounding as representative random quantizers.The quantizers are characterized through unbiasedness and variance behavior, and stochastic rounding uses a tuning parameter s for quantization levels.
  • 2) Quantized Model Updates:: The hierarchical algorithm indexes client models by cloud rounds, edge rounds, and local steps, with total local iterations t = kτ1τ2 + t2τ1 + t1.This indexing tracks the nested progression of local updates, edge aggregations, and cloud aggregations.
  • III. CONVERGENCE ANALYSIS: The convergence analysis targets non-convex loss functions and presents a convergence result with a proof sketch, while detailed key-lemma proofs are provided in the appendix.The section also discusses findings derived from the resulting convergence bound.
  • III. CONVERGENCE ANALYSIS: The analysis assumes L-smooth losses, unbiased stochastic gradients with variance bounded by σ2, and unbiased random quantizers whose variance grows with squared ℓ2 input norm.These assumptions cover smoothness, stochastic-gradient noise, and quantization noise; larger q corresponds intuitively to lower communication cost and lower precision.

A. Convergence Analysis Challenges · B. Main Result and Discussions

The paper addresses convergence-analysis challenges from hierarchical aggregation, model-upload compression, and loose bounds, then establishes a convergence result for Hier-Local-QSGD. The analysis yields an O(1/√(Kτ1τ2)) rate under sufficiently small learning rates and discusses batch-size and non-IID extensions.

  • A. Convergence Analysis Challenges: Hierarchical convergence analysis must handle gradient divergence from two aggregation levels, model-uploading compression, and the difficulty of deriving tight bounds without uniformly bounded gradients.The proposed analysis tracks local-model evolution and carefully bounds parameter divergence under relaxed assumptions.
  • B. Main Result and Discussions: Theorem 1 establishes a convergence result for Hier-Local-QSGD on non-convex loss functions under the stated assumptions and a lower-bounded loss.The theorem analyzes the cloud-server parameter sequence generated by Algorithm 1.
  • B. Main Result and Discussions: When G≥0, Hier-Local-QSGD satisfies the stated first-order stationary condition for its training iterations.The condition applies to the sequence analyzed in Theorem 1.
  • B. Main Result and Discussions: With η = 1/(L√(Kτ1τ2)), the algorithm achieves an overall convergence rate of O(1/√(Kτ1τ2)).This rate is presented for sufficiently small learning rates.
  • B. Main Result and Discussions: The rate indicates improved communication efficiency while achieving comparable performance to the baseline without partial edge aggregation and model quantization.The comparison is stated for non-convex loss functions.
  • B. Main Result and Discussions: Using a batch of size b reduces the stochastic-gradient variance in Assumption 2 from σ^2 to σ^2/b.The analysis otherwise remains unchanged under this batch-size modification.
  • B. Main Result and Discussions: The proof extension does not handle non-IID data directly, but experiments evaluate whether the analytically derived adaptive interval scheme works in that setting.The passage distinguishes the proof extension from the later experimental evaluation.

C. Examples of System Design Guidelines … D. Proof Outline

The analysis yields system-design guidelines showing when quantization favors infrequent aggregation and when client-edge association does not affect convergence speed. The proof introduces an auxiliary unquantized variable, bounds three evolution terms, and derives the convergence result used for aggregation-interval selection.

  • C. Examples of System Design Guidelines: The examples illustrate how the convergence analysis produces practical system-design guidelines for hierarchical federated learning.The section presents two examples of guidelines obtained from the analysis.
  • 1) Too much quantization suggests infrequent communication:: When quantization is very inaccurate, increasing the client-edge aggregation interval lowers the convergence upper bound, so infrequent local aggregation is preferable.When quantization is not too inaccurate, the opposite holds: smaller intervals yield faster convergence.
  • 1) Too much quantization suggests infrequent communication:: With fixed cloud communication frequency, the effect of the edge-client aggregation interval on convergence depends on the quantization level, unlike existing FedAvg analyses.Existing FedAvg analyses associate smaller local aggregation intervals consistently with faster convergence.
  • 2) Edge-client association strategy has no impact on the convergence:: With a fixed number of edge servers and at least one client per server, convergence speed is independent of the client-edge association strategy.Training should therefore minimize the communication delay of each aggregation to accelerate the overall system.
  • 2) Edge-client association strategy has no impact on the convergence:: Partial edge aggregation adds variance inversely proportional to the aggregated client count, making weighted cloud averaging preferable to uniform averaging.Weighted averaging balances the additional variance introduced by edge servers with fewer clients.
  • D. Proof Outline: The proof introduces an auxiliary variable representing the average of unquantized edge-server updates to analyze the cloud model evolution.This variable supports the subsequent bounds on the cloud update process.
  • D. Proof Outline: Using smoothness, the proof bounds three evolution terms and relates them to aggregation intervals τ1, τ2 and quantization variances q1, q2 before deriving Theorem 1.Lemmas 1–4 provide the component bounds, whose combination yields the main convergence result under a sufficiently small learning rate and a stated condition.
  • D. Proof Outline: The derived convergence result is then applied to aggregation-interval selection to reduce overall training latency in hierarchical federated learning.The analysis is explicitly connected to a system-design problem after establishing convergence with respect to update iterations.

IV. ADAPTIVE AGGREGATION INTERVAL CONTROL

This section uses the convergence bound to optimize hierarchical FL aggregation intervals under a communication–accuracy trade-off. It derives optimal intervals and proposes an adaptive scheme that periodically updates them from observed training loss with negligible communication overhead.

  • IV. ADAPTIVE AGGREGATION INTERVAL CONTROL: The convergence bound exposes an accuracy–latency trade-off, allowing τ1 and τ2 to be selected for a specified training deadline by minimizing the bound.The parameters are obtained by setting derivatives with respect to the corresponding aggregation intervals to zero.
  • IV. ADAPTIVE AGGREGATION INTERVAL CONTROL: Theorem 2 derives aggregation intervals that minimize the Hier-Local-QSGD error bound under the stated assumptions.The solution follows from convexity in τ1 and τ = τ1τ2 when 1 + q1 < n/s, followed by setting partial derivatives to zero.
  • IV. ADAPTIVE AGGREGATION INTERVAL CONTROL: The adaptive scheme divides training into equal wall-clock intervals and estimates the best aggregation interval for the next interval using the convergence bound.At each interval start, the server uses the bound to estimate the optimal local update step for the upcoming T0 period.
  • IV. ADAPTIVE AGGREGATION INTERVAL CONTROL: The server computes interval updates from clients’ training losses, while transmitting one scalar value between clients and server adds negligible communication cost.The computation of τ1 requires only the training loss, and the scalar exchange is negligible relative to model-parameter communication.

V. NUMERICAL RESULTS

This section presents sample simulations of Hier-Local-QSGD to verify convergence-analysis observations and demonstrate the effectiveness of adaptive aggregation-interval selection.

  • V. NUMERICAL RESULTS: Sample simulations evaluate Hier-Local-QSGD against observations from the convergence analysis.
  • V. NUMERICAL RESULTS: The experiments assess the proposed adaptive aggregation-interval selection algorithm.
  • V. NUMERICAL RESULTS: The numerical results illustrate the effectiveness of the adaptive aggregation-interval selection approach.

A. Settings … VI. CONCLUSIONS

The paper evaluates quantized hierarchical FL through controlled simulations, showing that quantization changes the preferred local-update interval, weighted aggregation removes association sensitivity, and adaptive intervals improve performance. These findings support a communication-efficient algorithm and tighter convergence-based design guidelines.

  • A. Settings: The simulations use hierarchical systems with equal client loads, testing IID and non-IID data generated through Dirichlet distributions with α = 100, 1, and 0.1.Experiments include n = 20 clients and s = 4 edge servers, while the association study uses 20 clients and 2 edge servers.
  • A. Settings: The evaluation uses CNN and ResNet18 models with random sparsification or stochastic rounding, under modeled wireless communication and computation latencies.The reported full-precision latencies are T_comp = 2 s and T_comm = 33 s for CIFAR-10, versus 7.2 s and 63.3 s for CIFAR-100.
  • B. Verification of the two obtained design guidelines: The study validates two design guidelines: quantization can favor infrequent local communication, and weighted aggregation makes performance independent of edge-client association.These guidelines are evaluated under IID, minor non-IID, and extreme non-IID settings using the proposed hierarchical algorithm.
  • 2) Edge-client Association:: The proposed Hier-Local-QSGD algorithm makes learning performance insensitive to edge-client association because weighted averaging balances variance.With uniform averaging, association strategies diverge, while the (10, 10) assignment performs best; the proposed method also remains effective under extreme non-IID data.
  • C. Adaptive Aggregation Interval Control: Adaptive aggregation intervals outperform fixed intervals across data distributions, with τ_1 decreasing for α = 100 and α = 1 but increasing later for α = 0.1.For CIFAR-100, τ_1 increases when the learning rate decays at the 60th, 120th, and 160th epochs.
  • VI. CONCLUSIONS: The paper develops a communication-efficient hierarchical FL algorithm with tighter convergence analysis, reducing the local-update error term from quadratic to linear.The analysis supports local-update and association guidelines and motivates adaptive selection of both aggregation intervals.

APPENDIX Proofs of Key Lemmas

The appendix proves four key lemmas using smoothness, unbiased quantization, expectation identities, conditional independence, and variance decompositions. The derivations establish the required bounds through systematic expectation and inner-product expansions.

  • Lemma 1: Lemma 1 follows from L-smoothness, unbiased random quantization, and expectations applied to the update equations.The proof takes expectations of (22) and (23), using E_Q2[x_k+1] = x̄_k+1.
  • Lemma 2: Lemma 2 bounds the relevant terms by reindexing expectations, applying an inner-product identity, and exploiting conditional independence.The proof separately bounds terms A, B1, and B2, with several inner products vanishing in expectation.
  • Lemma 2: Lemma 2’s final upper bound follows after applying Assumption 2 and combining the bounds on the expanded terms.The appendix notes that the relevant relation directly follows from Assumption 2 before assembling the final bound.
  • Lemmas 3 and 4: Lemmas 3 and 4 use the identity E∥x∥2 = ∥Ex∥2 + Var(x)2 to derive their respective bounds from the update equations.Lemma 4 follows the same approach as Lemma 3 while using equations (10) and (11).
Loading 2103.14272v2…