PaperlayerView exact revision on arXiv

Source-linked AI summary

One-Bit Over-the-Air Aggregation for Communication-Efficient Federated Edge Learning: Design and Convergence Analysis

Guangxu Zhu, Yuqing Du, Deniz Gunduz, Kaibin Huang

arXiv:2001.05713v2cs.ITcs.DCcs.NIeess.SP

TL;DR

The paper addresses the difficulty of applying analog over-the-air aggregation on modern digitally modulated wireless systems. It proposes OBDA, combining one-bit quantization, QAM, and majority-vote decoding, and analyzes convergence under channel noise, fading, and channel-estimation errors. These hostilities introduce a scaling factor and bias, whose effects vanish as participating devices increase, with channel-dependent rates.

  • Problem

    Analog over-the-air aggregation is difficult to deploy on modern wireless systems whose devices use digital modulation such as QAM.

  • Method

    OBDA combines one-bit gradient quantization and QAM modulation at devices with over-the-air majority-vote gradient decoding at the server.

  • Results

    Channel noise, fading, and channel-estimation errors slow convergence by introducing a scaling factor and bias term, both approaching noiseless limits as device count grows.

  • Takeaways & Limitations

    Digital AirComp can implement communication-efficient FEEL on devices with digital modulation chips without significant hardware or communication-architecture changes.

Abstract

from arXiv · show

Federated edge learning (FEEL) is a popular framework for model training at an edge server using data distributed at edge devices (e.g., smart-phones and sensors) without compromising their privacy. In the FEEL framework, edge devices periodically transmit high-dimensional stochastic gradients to the edge server, where these gradients are aggregated and used to update a global model. When the edge devices share the same communication medium, the multiple access channel (MAC) from the devices to the edge server induces a communication bottleneck. To overcome this bottleneck, an efficient broadband analog transmission scheme has been recently proposed, featuring the aggregation of analog modulated gradients (or local models) via the waveform-superposition property of the wireless medium. However, the assumed linear analog modulation makes it difficult to deploy this technique in modern wireless systems that exclusively use digital modulation. To address this issue, we propose in this work a novel digital version of broadband over-the-air aggregation, called one-bit broadband digital aggregation (OBDA). The new scheme features one-bit gradient quantization followed by digital quadrature amplitude modulation (QAM) at edge devices and over-the-air majority-voting based decoding at edge server. We provide a comprehensive analysis of the effects of wireless channel hostilities (channel noise, fading, and channel estimation errors) on the convergence rate of the proposed FEEL scheme. The analysis shows that the hostilities slow down the convergence of the learning process by introducing a scaling factor and a bias term into the gradient norm. However, we show that all the negative effects vanish as the number of participating devices grows, but at a different rate for each type of channel hostility.

I. INTRODUCTION

FEEL distributes private-data training across wireless edge devices, but shared-medium communication creates a bottleneck. OBDA adapts over-the-air aggregation to digital QAM systems and analyzes how channel hostilities affect convergence.

  • FEEL motivation: FEEL distributes model training across edge devices, preserving data privacy while using their computation resources.Devices perform local SGD and periodically upload gradients or model updates for global aggregation.
  • Communication bottleneck: Shared wireless access can congest FEEL, motivating over-the-air aggregation through simultaneous waveform-superposition-based transmission.AirComp reduces required communication resources compared with conventional orthogonal access.
  • Digital modulation gap: Existing over-the-air FEEL systems mainly assume analog modulation, whereas modern wireless devices commonly rely on digital QAM and may not support arbitrary analog coefficients.The paper therefore targets over-the-air aggregation with transmitters limited to QAM.
  • OBDA design: OBDA combines one-bit gradient quantization, QAM modulation, and over-the-air majority-vote decoding for communication-efficient FEEL.The design integrates signSGD with AirComp without requiring major hardware or communication-architecture changes.
  • Convergence analysis: The paper analytically studies OBDA convergence under Gaussian noise, fading with perfect CSI, and fading with imperfect CSI.This extends prior work that largely evaluated analog aggregation through numerical experiments.
  • Channel effects: Channel imperfections slow convergence through a scaling factor a and bias term b, but both approach noiseless limits as the device count or received SNR grows.The three channel scenarios exhibit different scaling laws; imperfect-CSI effects can be especially severe and asymptotically SNR-insensitive.

II. LEARNING AND COMMUNICATION MODELS

FEEL coordinates distributed stochastic-gradient training across edge devices while keeping data local, with the server aggregating updates over a broadband wireless MAC.

  • Learning Model: FEEL trains a shared model across devices using local datasets coordinated by an edge server.The server broadcasts the global model, devices compute local gradients, and the resulting global update is returned for model updating.
  • Learning Model: The global objective minimizes a loss function defined over distributed datasets without uploading the local datasets.This addresses privacy concerns and the large size of distributed data.
  • Learning Model: Each communication round consists of local gradient computation, uplink transmission, server aggregation, downlink broadcasting, and device-side model updating.Iterations continue until a convergence condition is met.
  • Communication Model: Only the aggregated gradient is required at the server, motivating communication-efficient over-the-air aggregation.The framework exploits simultaneous wireless transmission rather than requiring individual gradient estimates at the server.
  • Communication Model: OFDM divides bandwidth B into M orthogonal sub-channels, while channel-aware power allocation supports gradient aggregation over the broadband MAC.The model includes fading coefficients, synchronization assumptions, and additive AWGN under a long-term transmission-power constraint.

III. ONE-BIT BROADBAND DIGITAL AGGREGATION (OBDA): SYSTEM DESIGN

OBDA combines one-bit gradient quantization, digital modulation, and over-the-air majority-vote decoding to aggregate FEEL updates using practical OFDM transceivers.

  • System Design: OBDA integrates signSGD and AirComp for communication-efficient FEEL with digital modulation.The design uses one-bit gradient quantization at devices and majority-vote gradient decoding at the server.
  • Transmitter Design: Each device maps one-bit local gradient parameters to binary digital symbols for transmission over a fixed finite constellation.The presentation uses BPSK, while 4-QAM is used in the numerical experiments.
  • Transmitter Design: Truncated channel inversion aligns received amplitudes when channel gains exceed a cutoff threshold and assigns zero power otherwise.The policy is adopted to handle deep fades under a power constraint.
  • Transmitter Design: Truncated channel inversion can lose gradient parameters assigned to sub-channels below the power-cutoff threshold.The non-truncation probability α measures the probability that a parameter avoids this loss.
  • Receiver Design: The receiver reconstructs the full aggregated one-bit gradient from OFDM blocks and applies an element-wise sign operation as a majority-vote decoder.This estimates the global gradient update directly from simultaneously transmitted local estimates.
  • Receiver Design: Majority vote is selected because sign detection is more hardware-friendly and noise-robust than recovering an aggregated value in full precision.It also supports communication-efficient broadcasting of the aggregated gradient.

IV. CONVERGENCE ANALYSIS FOR OBDA OVER AWGN CHANNELS

The AWGN analysis characterizes OBDA convergence under standard nonconvex stochastic-optimization assumptions and shows how channel noise changes the gradient-norm bound.

  • Basic Assumptions: The analysis assumes a lower-bounded, not necessarily convex, loss function to support convergence to a stationary point.Smoothness, bounded stochastic-gradient variance, and unimodal symmetric gradient noise are also imposed.
  • Convergence Analysis: Theorem 1 gives the convergence rate for FEEL using OBDA over AWGN channels.The rate is expressed using scaling factor a_AWGN and bias term b_AWGN under the stated learning-rate setting.
  • Convergence Analysis: For error-free channels, Lemma 1 provides the comparison convergence rate used to isolate the effect of AWGN.The paper reproduces the noiseless-channel rate as a reference.
  • Convergence Analysis: Channel noise slows convergence by adding a scaling factor and positive bias term to the upper bound on the time-averaged gradient norm.The increased bound implies that more communication rounds are needed for convergence.
  • Convergence Analysis: 1/K scaling makes the negative effect of channel noise vanish as the number of participating devices grows.The noiseless convergence rate is recovered as the received signal-to-noise ratio ρ tends to infinity.

V. CONVERGENCE ANALYSIS FOR OBDA OVER FADING CHANNELS

The analysis extends OBDA convergence guarantees to fading channels with perfect and imperfect CSI. Fading and CSI errors worsen convergence through larger scaling and bias terms, while their effects diminish as device participation increases.

  • A. Perfect CSI: Perfect-CSI truncated channel inversion yields a convergence-rate bound for OBDA over fading channels.The bound is stated in Theorem 2 and uses scaling factor aFAD and bias term bFAD.
  • A. Perfect CSI: Channel fading slows convergence relative to AWGN by producing larger scaling and bias terms, aFAD > aAWGN and bFAD > bAWGN.The degradation is attributed to gradient truncation from truncated channel inversion power control.
  • B. Imperfect CSI: Imperfect CSI further reduces OBDA convergence by increasing both the scaling factor and bias term beyond the perfect-CSI case.Theorem 3 gives the corresponding convergence-rate bound under bounded CSI perturbations.
  • B. Imperfect CSI: With imperfect CSI, channel-fading effects vanish at a slower scaling law as the number of participating devices increases than with perfect CSI.The convergence rate also depends on CSI accuracy through ∆max.

VI. SIMULATION RESULTS

Simulations evaluate OBDA on MNIST and CIFAR10 under AWGN and fading channels with perfect or imperfect CSI. OBDA converges in all scenarios, with slower convergence under greater wireless hostility, while its communication latency remains independent of device population.

  • A. Performance Evaluation of OBDA: OBDA converges on MNIST and CIFAR10 across AWGN and fading channels with both perfect and imperfect CSI.The three scenarios represent different levels of wireless hostility.
  • A. Performance Evaluation of OBDA: Channel fading slows convergence relative to AWGN, and imperfect CSI slows it further because fading truncates signs and CSI errors distort aggregation.These observations align with the convergence analysis in Theorems 1–3.
  • B. Effect of Device Population: Test accuracy increases with the number of participating devices in all three scenarios.The paper attributes this majority-vote gain to suppression of stochastic-gradient noise and wireless-hostility effects.
  • C. Performance Comparison: OFDMA, BAA and OBDA: OBDA and BAA have device-count-independent per-round latency, whereas digital OFDMA latency grows with the device population without compromising learning accuracy.The comparison uses a fading MAC with perfect CSI.
  • C. Performance Comparison: OFDMA, BAA and OBDA: OBDA has a small convergence-speed gap from BAA, attributed to one-bit quantization loss, while both use simple digital over-the-air aggregation advantages.The cited comparison reports comparable accuracies among digital OFDMA, BAA, and OBDA.

A. Proof of Theorem 1

The proof of Theorem 1 bounds expected objective improvement for OBDA by relating gradient norms to stochastic update behavior. It handles biased gradient estimates, bit errors, and channel/data stochasticity before telescoping across iterations.

  • Proof strategy: The proof relates the gradient norm to expected improvement in one algorithmic step and compares it with total possible improvement.This establishes the general convergence-analysis framework reused in later channel scenarios.
  • Single-step bound: The single-step objective improvement is decomposed to expose errors induced by data and channel stochasticity.The decomposition follows substitution of the algorithmic update into the objective relation.
  • Bit errors: The expected improvement depends on the decoding bit-error probability, which reflects data-stochasticity and wireless-channel noise.A subsequent lemma bounds the AWGN bit-error probability.
  • Stochastic gradients: Mini-batch size reduces local-gradient variance, and the proof incorporates this dependence through the stated assumptions and equations.Each local gradient estimate is computed over a mini-batch of size n_b.
  • Conclusion: Taking expectation over the optimization trajectory and telescoping the iterates yields the convergence result in Theorem 1.The final step rearranges the resulting inequality.

B. Proof of Lemma 2

The proof of Lemma 2 models correct sign counts across devices as Bernoulli trials and incorporates effective channel noise. It then bounds the probability that majority decoding produces an incorrect received sign.

  • Random-variable model: The proof represents each gradient-coordinate sign event using random variables for correct devices and noisy received counts.X_i counts correct sign bits, while the noisy version includes effective channel noise.
  • Random-variable model: Correct-sign counts are modeled as independent Bernoulli trials, giving a binomial representation with corresponding success and failure probabilities.The quantity ϵ_i = p_i − 1/2 = 1/2 − q_i is introduced for the derivation.
  • Majority decoding: The proof derives the mean and variance of the noisy correct-sign count before applying the majority-decoding condition.An incorrect received sign occurs when the noisy count fails to exceed K/2.
  • Failure-probability bound: A bound on single-device sign failure probability follows from Gauss’ inequality under unimodal symmetric gradient noise.The resulting bound is combined with ϵ_i to control the received sign-vector error probability.
  • Failure-probability bound: Substituting the probability bounds into the majority-error expression completes the bound required for Lemma 2.The remaining steps are algebraic rearrangements using the derived inequalities.

C. Proof of Theorem 2

The proof of Theorem 2 derives fading-channel bit-error bounds by conditioning on the random transmitting set and then averaging over its binomial distribution. These bounds are incorporated into the convergence analysis through the established single-step improvement framework.

  • Fading-channel error analysis: The fading-channel analysis requires a new bit-error expression to account for randomness introduced by channel fading.The proof retains the general strategy of relating gradient norms to expected objective improvement.
  • Fading-channel error analysis: The conditional bit-error probability is first derived given K_i, followed by an unconditional bound obtained using total probability and Lemma 5.Lemma 4 supplies the conditional result, while Lemma 6 states the resulting unconditional bound.
  • Fading-channel error analysis: Under truncated channel inversion with perfect CSI, the transmitting set K_i follows a binomial distribution with non-truncation probability α.Conditioning on K_i separates the non-empty transmitting case from the no-transmission case, where decoding becomes a random guess.
  • Bounding the error probability: The proof establishes two inequalities used to simplify the unconditional error-probability expression.The derivation handles a square-root term by rewriting the expression and applying Jensen’s inequality.
  • Convergence implication: Lemma 6 is substituted into the single-step improvement expression to obtain the desired convergence result in Theorem 2.The final step follows the same machinery used in the preceding convergence derivation.

D. Proof of Theorem 3

The proof of Theorem 3 extends the fading-channel analysis to truncated channel inversion with imperfect CSI. It models channel-estimation errors as an additional noise source, derives conditional and unconditional bit-error results, and substitutes them into the convergence framework.

  • Imperfect-CSI model: Imperfect CSI introduces additional error that must be incorporated into the bit-error expression defined for the fading channel.The proof therefore derives a new error characterization for channel-estimation uncertainty.
  • Imperfect-CSI model: The transmitting set K_i contains devices whose estimated channel gain exceeds the cutoff threshold g_th.The received aggregated gradient element is rewritten using this selected set under the imperfect-CSI model.
  • Conditional error analysis: The CSI-induced term captures additional error while remaining binary-valued, taking values +1 and −1 for transmitting devices.Its variance is bounded conditional on K_i.
  • Conditional and unconditional bounds: Lemma 7 gives the conditional bit-error probability for imperfect CSI, and Lemma 8 gives the corresponding unconditional result.The unconditional expression is obtained using total probability and the previously established inequalities.
  • Convergence implication: Substituting Lemma 8 into the single-step improvement analysis yields the convergence result in Theorem 3.The proof applies the same machinery used in the earlier convergence derivation.

http://arxiv.org/ps/2001.05713v2

The supplied passages identify two preview images associated with this section.

  • The passage references a figure named preview-web.jpg.
  • The passage states that preview-web.jpg is available in JPG format.
  • The passage references a figure named preview.jpg.
Loading 2001.05713v2…