PaperlayerView exact revision on arXiv

Source-linked AI summary

Design and Analysis of Uplink and Downlink Communications for Federated Learning

Sihui Zheng, Cong Shen, Xiang Chen

arXiv:2012.04057v1cs.ITcs.LGeess.SP

TL;DR

Communication is recognized as a primary bottleneck in federated learning, while earlier studies provide only a glimpse of communication optimization's potential. This paper studies quantization and transmission choices for FL, deriving convergence results and evaluating their learning-performance impact; 1-bit quantization reaches 99.8% of floating-point baseline accuracy on MNIST at 3.1% bandwidth and almost the same convergence rate.

  • Problem

    Communication is recognized as one of federated learning's primary bottlenecks, while early studies provide only a glimpse of communication optimization's potential.

  • Method

    The paper designs and analyzes FL-tailored quantization and transmission choices, including layered quantization and weight-versus-differential transmission.

  • Results

    1-bit quantization at 3.1% of floating-point baseline bandwidth achieves 99.8% of floating-point baseline accuracy at almost the same convergence rate on MNIST.

  • Takeaways & Limitations

    To achieve O(1/T) convergence with quantization, transmitting weights requires logarithmically increasing quantization levels, whereas transmitting weight differentials permits a constant level.

Abstract

from arXiv · show

Communication has been known to be one of the primary bottlenecks of federated learning (FL), and yet existing studies have not addressed the efficient communication design, particularly in wireless FL where both uplink and downlink communications have to be considered. In this paper, we focus on the design and analysis of physical layer quantization and transmission methods for wireless FL. We answer the question of what and how to communicate between clients and the parameter server and evaluate the impact of the various quantization and transmission options of the updated model on the learning performance. We provide new convergence analysis of the well-known FedAvg under non-i.i.d. dataset distributions, partial clients participation, and finite-precision quantization in uplink and downlink communications. These analyses reveal that, in order to achieve an O(1/T) convergence rate with quantization, transmitting the weight requires increasing the quantization level at a logarithmic rate, while transmitting the weight differential can keep a constant quantization level. Comprehensive numerical evaluation on various real-world datasets reveals that the benefit of a FL-tailored uplink and downlink communication design is enormous - a carefully designed quantization and transmission achieves more than 98% of the floating-point baseline accuracy with fewer than 10% of the baseline bandwidth, for majority of the experiments on both i.i.d. and non-i.i.d. datasets. In particular, 1-bit quantization (3.1% of the floating-point baseline bandwidth) achieves 99.8% of the floating-point baseline accuracy at almost the same convergence rate on MNIST, representing the best known bandwidth-accuracy tradeoff to the best of the authors' knowledge.

I. INTRODUCTION

The paper argues that wireless FL communication must be tailored to its iterative, non-i.i.d. learning process and jointly designed for uplink and downlink. It develops practical quantization and transmission methods, convergence guarantees, and experiments showing large bandwidth savings with limited accuracy loss.

  • Communication is a primary FL bottleneck, but wireless communication design has received less attention than the learning component.
  • Standard communication techniques can be highly suboptimal because FL updates form a progressive long-term process rather than an i.i.d. source over time.
  • Both uplink local-weight uploads and downlink global-weight downloads must be considered because they jointly determine FL performance across rounds.
  • The paper studies FL-tailored quantization and transmission of model weights or updates to maximize learning accuracy and convergence rate.
  • For O(1/T) convergence, direct weight transmission requires logarithmically increasing quantization precision, whereas weight differentials permit constant precision under non-i.i.d. data and partial participation.
  • Across most experiments, designed communication exceeds 98% of floating-point baseline accuracy with fewer than 10% of baseline bandwidth, including i.i.d. and non-i.i.d. datasets.
  • On MNIST, 1-bit quantization uses 3.1% of floating-point baseline bandwidth while achieving 99.8% of baseline accuracy at almost the same convergence rate.

III. SYSTEM MODEL

The system model describes wireless FL as repeated downlink broadcast, local client training, uplink upload, and server aggregation. It explicitly accommodates non-i.i.d. local datasets and partial client participation.

  • Wireless FL uses a central parameter server and up to N clients that collaboratively train a machine-learning model.
  • Each client stores a disjoint local dataset that remains on the device, and datasets across clients are assumed to be non-i.i.d.
  • The global objective minimizes the average loss over all clients’ data to obtain the optimal model parameter w∗.
  • At each round, the server broadcasts the current global model to K randomly selected clients, which explicitly captures partial participation.
  • Selected clients improve the received model using mini-batch SGD for E local steps on their local data.
  • Clients synchronously upload their local models, after which the server aggregates them into a new global model and begins the next round.

IV. UPLINK COMMUNICATION DESIGN

The uplink design considers whether to transmit weights or weight differentials and how to quantize them for repeated FL communication. The paper emphasizes that this choice affects convergence under quantization, while practical quantizer design balances precision, overflow, and implementation complexity.

  • A. What to Transmit: Weight versus Weight Differential: Uplink communication can transmit either the latest local weight or its weight differential, leveraging correlations across FL rounds.The design questions are what to transmit and how to transmit it.
  • A. What to Transmit: Weight versus Weight Differential: Weight-differential transmission depends on server state for reconstruction and may fail when intermediate models are deleted or decoding errors make the stored global model inaccurate.In these cases, transmitting the weight vector itself is more preferable.
  • A. What to Transmit: Weight versus Weight Differential: The choice between weight and weight differential has a substantial effect on learning performance when quantization causes imperfect reconstruction.This motivates analyzing the two transmission options separately rather than treating them as equivalent communication choices.
  • B. How to Transmit: Quantization Designs: Quantization reduces each floating-point model value to a lower-bit message through scale-up, rounding, limiting, and scale-down operations.The gain G controls the precision–overflow trade-off: larger G preserves more decimal digits but can increase overflow during limiting.
  • B. How to Transmit: Quantization Designs: Native Quantization fixes G at 2^(B−1), whereas Tuned Quantization permits a larger gain but requires receiver-side scaling.The tuned structure provides finer control of the quantization gain at the cost of receiver knowledge of G.
  • B. How to Transmit: Quantization Designs: Stochastic rounding and an enhanced 1-bit quantizer are considered as practical alternatives within the uplink quantization design.The enhanced 1-bit operation rounds the weight to a sign value and lets the receiver scale it down.

1) Analysis for weight transmission:

The analysis characterizes FedAvg with quantized uplink transmission under non-i.i.d. data and partial client participation. Direct weight transmission requires increasing precision for the O(1/T) rate, whereas weight-differential transmission preserves that rate with fixed precision.

  • 1) Analysis for weight transmission: FedAvg with quantized direct weight transmission retains the global-optimum convergence rate O(1/T) when quantization precision increases over time.The result is established under the paper’s smoothness, strong-convexity, variance, and bounded-weight assumptions.
  • 1) Analysis for weight transmission: For direct weight transmission, the required quantization level grows logarithmically with iteration, B_t = O(log(t)).This increasing precision is needed to match the scaling behavior of vanilla FedAvg.
  • 1) Analysis for weight transmission: The convergence bound covers non-i.i.d. local datasets and randomly selected partial clients participating in each round.The analysis assumes equal local dataset sizes in the simplified partial-participation setting.
  • 2) Analysis for weight differential transmission: Weight differentials typically have a smaller range than raw weights near convergence, allowing larger gains without excessive overflow and avoiding bits spent on constant weight components.This improves quantization precision and communication efficiency for differential transmission.
  • 2) Analysis for weight differential transmission: Weight-differential transmission achieves O(1/T) convergence with a fixed quantization level, avoiding the increasing precision required for direct weights.Theorem 2 states the corresponding convergence bound for non-i.i.d. data, partial participation, and uplink quantization.
  • 2) Analysis for weight differential transmission: Theorems 1 and 2 show that carefully designed quantization can largely preserve the convergence rate known without quantization.The analysis controls quantization errors so the overall noise level does not increase beyond the SGD noise level.

V. DOWNLINK COMMUNICATION DESIGN

Downlink communication must broadcast the global model because differential transmission is infeasible with partial participation and newly joining clients. The paper therefore develops layered quantization, which adapts gains to layer-specific weight ranges and analyzes its quantized convergence.

  • V. Downlink Communication Design: Downlink differential transmission is infeasible under partial participation because newly selected clients lack the previous base model needed for reconstruction.The downlink therefore focuses on transmitting the current global model directly.
  • A. Layered Quantization: Layered Quantization assigns each network layer a base gain and a layer-specific gain to match differences in weight dynamic ranges.The layer-specific gain is applied to adjust the retained digits for that layer.
  • A. Layered Quantization: Different CNN layers exhibit substantially different weight dynamic ranges, motivating layer-specific gains instead of one global gain.The paper reports that applying different gains can improve overall performance relative to a single global gain.
  • A. Layered Quantization: The layer-specific gain can be updated dynamically each round from a layer’s empirical CDF, using its 90-percentile value.The server broadcasts the current layer gains with the quantized global model so clients can rescale their outputs.
  • A. Layered Quantization: Static layered quantization fixes layer-specific gains using a pre-trained model, reducing computation and per-round gain communication.This comes at the expense of not tracking weight dynamic ranges in real time.
  • B. Convergence Analysis for FedAvg with Downlink Quantization: Quantized downlink FedAvg admits a convergence bound for non-i.i.d. datasets, partial participation, and stochastic rounding.The downlink analysis indicates that direct weight transmission requires B_t = O(log(t)) quantization precision for the stated convergence scaling.
  • B. Convergence Analysis for FedAvg with Downlink Quantization: Because downlink differential transmission is unavailable, whether the logarithmic precision requirement can be improved remains open in the paper’s analysis.This is identified specifically as an unresolved issue for FL downlink communication.

VI. EXPERIMENTS

The experiments evaluate quantization and transmission designs for uplink and downlink FL across i.i.d. and non-i.i.d. datasets. They show that tailored choices of quantization, rounding, and weight-differential transmission can preserve accuracy while reducing bandwidth.

  • Experimental setup: Experiments cover MNIST, CIFAR-10, Shakespeare, and F-EMNIST under i.i.d. and non-i.i.d. client data distributions.The setup uses partial client participation and compares uplink and downlink communication designs against a floating-point baseline.
  • Uplink design: Tuned quantization accounts for the weight dynamic range, and stochastic rounding generally outperforms nearest rounding in convergence speed and final accuracy.The comparison reports that stochastic rounding remains better even when fewer bits are used; nearest rounding can degrade performance as more clients participate.
  • Uplink design: Logarithmically increasing quantization levels outperform fixed bit-widths at similar average bit-widths when transmitting weights.The logarithmic approach averages 2 bits on CIFAR-10 and 3 bits on Shakespeare while achieving better final convergence accuracy than fixed 2-bit and 3-bit quantization, respectively.
  • Uplink design: Weight differentials have a smaller and increasingly concentrated dynamic range, supporting low-bit transmission and potentially lower late-stage bit-widths.On MNIST, the differential range is an order of magnitude smaller; the share below 9e-5 rises from 35% at round 10 to 90% at round 500.
  • Uplink design: 1-bit differential quantization reaches 99.83% of baseline accuracy with 3.13% of baseline bandwidth for i.i.d. MNIST and 99.41% with the same bandwidth for non-i.i.d. MNIST.The corresponding accuracies are 99.08% and 98.59%, respectively; 2-bit transmission reaches 99.93% and 99.81% of baseline accuracy.

C. Results for Downlink Communication

Downlink quantization is more sensitive to design choices than uplink quantization, but tuned, stochastic, and layered schemes substantially improve its efficiency. The experiments show that low-bit downlink communication can retain accuracy close to the floating-point baseline.

  • Downlink sensitivity: For the same quantization level and method, downlink quantization performs worse than uplink quantization.The paper attributes the broader impact to downloaded-model inaccuracies being used by many clients.
  • Downlink quantization: With tuned quantization and stochastic rounding, 6-bit downlink quantization achieves 78.33% accuracy, or 98% of baseline accuracy, on CIFAR-10.Without differential transmission support, performance decreases noticeably when bit-width falls below 3.
  • Layered quantization: Layered quantization improves 3-bit and 4-bit communication for CIFAR-10 and F-EMNIST in both i.i.d. and non-i.i.d. settings.For CIFAR-10, 3-bit communication rises from 74.48% to 77.15% and 4-bit communication from 76.04% to 78.42%; F-EMNIST rises from 75.23% to 78.29% and from 78.48% to 80.46%.
  • Overall downlink design: The combined tuned, stochastic, and layered design reduces quantization to 4 bits, or 12.5% of baseline bandwidth, while keeping accuracy degradation within 2%.The result is confirmed across the three evaluated datasets.

D. Results of Quantization on Both Uplink and Downlink

The experiments evaluate simultaneous uplink and downlink quantization across multiple datasets and hyperparameter settings. Carefully designed schemes substantially reduce communication while retaining floating-point baseline accuracy.

  • Evaluation setup: Experiments run 1000 rounds for MNIST and 500 rounds for CIFAR-10, Shakespeare, and F-EMNIST, averaging final-round accuracy.The reported baseline percentage compares quantized communication accuracy with the 32-bit floating-point baseline.
  • Evaluation setup: The experiments use layered quantization with TQ and SR on downlink, and DT with TQ and SR on uplink.These designs are evaluated for simultaneous quantization on both communication directions.
  • Simultaneous quantization results: 93.75% communication reduction is achieved on MNIST with 2-bit quantization on both uplink and downlink while retaining sufficiently good performance.The result is reported relative to the floating-point baseline.
  • Simultaneous quantization results: 81.25% downlink and 87.5% uplink bandwidth reductions are achieved on non-i.i.d. CIFAR-10 using 6-bit downlink and 4-bit uplink quantization.The reported reductions are per client and correspond to the respective communication directions.
  • Overall results: 1-bit quantization uses 3.1% of baseline bandwidth and achieves 99.8% of baseline accuracy on MNIST at almost the same convergence rate.The authors identify this as their best known bandwidth-accuracy tradeoff.

APPENDIX A

Appendix A develops the analytical framework for quantized FedAvg, including its stochastic-gradient, client-sampling, and stochastic-rounding randomness. The proof uses lemmas controlling SGD behavior, sampling, quantization variance, and the resulting convergence recursion.

  • Analytical framework: The analysis models randomness from stochastic gradients, random client sampling, and stochastic rounding.Expectations are taken over all three randomness sources.
  • Analytical framework: FedAvg clients perform E local iterations before aggregation, so the global model is accessible only at communication times t in I_E.The appendix indexes the analysis by SGD iteration time rather than communication rounds.
  • Analytical framework: The appendix summarizes local training and aggregation through auxiliary variables describing client updates and global-model evolution.These variables distinguish iterations with and without global aggregation.
  • Supporting lemmas: Lemmas 1–3 bound one-step SGD behavior, variance, and client-model divergence under smoothness, convexity, bounded variance, and bounded gradients.The appendix states these lemmas remain valid for quantized FedAvg under the corresponding assumptions.
  • Supporting lemmas: Lemmas 4–6 establish unbiased and variance-bounded client sampling and stochastic quantization for uplink communication.The quantization lemma uses level B_t+1 and stochastic rounding.
  • Convergence proof: The convergence proof takes expectations over stochastic gradients, client sampling, and stochastic rounding, then derives a recursively bounded model error under a decaying learning rate.The proof explicitly uses vanishing unbiased-rounding terms and a non-increasing learning rate.

D. Deferred proofs of lemmas

The deferred proofs establish the sampling and stochastic-rounding properties used in the convergence analysis. They also derive quantization bounds by partitioning the dynamic range into finite intervals.

  • Sampling proof: The sampling proof enumerates possible selected-client sets and derives the associated expectation and variance properties.The selected sets are indexed among the possible combinations of participating clients.
  • Convergence proof: The convergence derivation takes expectations over stochastic gradients and applies the previously established bounds at communication times.The proof combines the sampling, rounding, and optimization terms in the recursive analysis.
  • Quantization proof: The stochastic-rounding proof partitions [−M,+M] into ζ = 2^B−1 intervals for B-bit quantization.Each scalar is quantized to an interval endpoint according to stochastic rounding probabilities.
  • Quantization proof: The quantization proof extends the scalar rounding argument to vectors and bounds the resulting quantization behavior.The vector is represented as w = [w_1,w_2,...,w_d].

K2 ESR

This section extends the appendix notation to quantized differential transmission and states the corresponding stochastic-quantization lemma. The differential is quantized using a gain tied to its infinity norm.

  • Differential transmission: The differential-transmission notation is obtained by extending the appendix variables, with a modified client-update definition.The global aggregation expression uses the prior communication-time model.
  • Differential transmission: For quantized differential transmission, each selected client uploads a quantized model differential at communication times.The server aggregates the received differential with the previously communicated global model.
  • Quantization rule: Lemma 7 establishes unbiased and variance-bounded stochastic quantization for the transmitted differential.Its proof specializes the bounded-range stochastic-rounding argument to the differential vector.
  • Convergence analysis: The proof uses stochastic-rounding unbiasedness and then averages over stochastic-gradient randomness to obtain the differential-quantization bound.The resulting analysis parallels the expectation steps used for uplink quantization.

C. Proof of Theorem 2

The proof of Theorem 2 analyzes downlink quantization through four possible client-participation cases and uses induction to establish the theorem. It tracks the expected squared distance of intermediate and global models, accounting for quantization and stochastic-rounding randomness.

  • Quantized downlink: Downlink transmission broadcasts Q(wt+1) to randomly selected clients, while the convergence analysis compares quantized and unquantized iterates across the participation cases.The quantization level enters through qt = 1/(2Bt − 1), and the proof uses relations among ut+1, vt+1, and wt+1 in each case.
  • Case analysis: The proof considers four cases determined by whether consecutive iterations belong to the client-selection set IE.The cases separately analyze transitions between selected and non-selected iterations, including the special case possible only when E = 1.
  • Randomness handling: Expectation over stochastic rounding makes the A3 term vanish, while expectation over the selection randomness makes the B3 term vanish.The remaining terms are bounded using earlier equations before the cases are combined into a common recursion.
  • Error recursion: The analysis tracks ∆t = E ∥ut − w∗∥2, because the server has access to the unquantized global model aggregation.The proof distinguishes intermediate variables from the global model and uses the expected distance to the optimum as its induction quantity.
  • Conclusion: The proof concludes by establishing Eqn. (26) for all cases and applying the induction method from Appendix A-C to prove the theorem.The same induction strategy is invoked after the case-specific transformations and bounds are obtained.
Loading 2012.04057v1…