PaperlayerView exact revision on arXiv

Source-linked AI summary

Broadband Analog Aggregation for Low-Latency Federated Edge Learning (Extended Version)

Guangxu Zhu, Yong Wang, Kaibin Huang

arXiv:1812.11494v3cs.ITcs.LG

TL;DR

Broadband analog aggregation addresses radio-resource scarcity in high-dimensional transmission and targets low-latency federated learning. By exploiting waveform superposition, it reduces latency relative to conventional orthogonal access while motivating analysis of communication-and-learning tradeoffs.

  • Problem

    High-dimensional transmission by many devices suffers from scarce radio resources, while the effects of AirComp on edge-learning performance remain largely uncharted.

  • Method

    The paper proposes broadband analog aggregation for low-latency federated learning, using simultaneous transmission and resultant waveform superposition.

  • Results

    The proposed framework yields dramatic latency reduction compared with conventional orthogonal access and characterizes tradeoffs between communication-and-learning metrics.

  • Takeaways & Limitations

    The framework connects waveform superposition with low-latency distributed learning while exposing a power-cutoff-controlled tradeoff in system performance.

Abstract

from arXiv · show

The popularity of mobile devices results in the availability of enormous data and computational resources at the network edge. To leverage the data and resources, a new machine learning paradigm, called edge learning, has emerged where learning algorithms are deployed at the edge for providing fast and intelligent services to mobile users. While computing speeds are advancing rapidly, the communication latency is becoming the bottleneck of fast edge learning. To address this issue, this work is focused on designing a low latency multi-access scheme for edge learning. We consider a popular framework, federated edge learning (FEEL), where edge-server and on-device learning are synchronized to train a model without violating user-data privacy. It is proposed that model updates simultaneously transmitted by devices over broadband channels should be analog aggregated "over-the-air" by exploiting the superposition property of a multi-access channel. Thereby, "interference" is harnessed to provide fast implementation of the model aggregation. This results in dramatical latency reduction compared with the traditional orthogonal access (i.e., OFDMA). In this work, the performance of FEEL is characterized targeting a single-cell random network. First, due to power alignment between devices as required for aggregation, a fundamental tradeoff is shown to exist between the update-reliability and the expected update-truncation ratio. This motivates the design of an opportunistic scheduling scheme for FEEL that selects devices within a distance threshold. This scheme is shown using real datasets to yield satisfactory learning performance in the presence of high mobility. Second, both the multi-access latency of the proposed analog aggregation and the OFDMA scheme are analyzed. Their ratio, which quantifies the latency reduction of the former, is proved to scale almost linearly with device population.

I. INTRODUCTION

The paper addresses communication latency as a bottleneck in federated edge learning by proposing broadband analog aggregation (BAA), which aggregates device updates over-the-air. It develops this wireless approach alongside FEEL analysis and relates it to prior learning- and communication-oriented strategies.

  • Communication latency bottlenecks fast edge learning because many devices transmit high-dimensional data over scarce, hostile wireless resources.
  • BAA enables low-latency FEEL by exploiting simultaneous broadband transmission and waveform superposition to aggregate local updates over-the-air.The server aggregates or averages local models trained on devices to update the global model.
  • FEEL alternates model broadcasting, local update computation, update transmission, and server aggregation until the global model converges.Local updates may be model parameters or gradient vectors.
  • Prior FEEL approaches reduce latency by addressing stragglers, selecting significant updates, or compressing sparse gradients, while abstracting wireless channels as bit pipes.
  • BAA builds on over-the-air computation, whose application to broadband, high-dimensional FEEL updates and learning-performance effects remain largely uncharted.

C. Contribution and Organization

The paper develops and evaluates BAA for single-cell FEEL, characterizing its update-quality tradeoffs, scheduling implications, and latency relative to OFDMA. It also reports software experiments and extensions for security and cell-edge reliability.

  • BAA is analyzed in a single-cell random network where edge devices are randomly distributed within a disk area.
  • Devices use analog modulation and OFDM over broadband channels, with channel inversion providing amplitude alignment for server-side update averaging.
  • The framework defines receive SNR, truncation ratio, and exploited-data fraction as FEEL update-quality and data-quantity metrics.Truncation arises when channel inversion exceeds a device's transmit-power constraint.
  • Communication-and-learning tradeoffs: The SNR-truncation tradeoff is constrained by the furthest device's path loss, motivating cell-interior scheduling but creating an SNR–exploited-data tradeoff.
  • Communication-latency analysis: The BAA-to-OFDMA latency-reduction ratio increases with the number of scheduled devices as O(...), supporting BAA for low-latency FEEL with many devices.
  • Experiments: Software experiments on handwritten-digit recognition with a neural network and real images confirm the communication-learning tradeoffs and dramatic latency reduction.
  • Extensions: The paper presents extensions addressing security against adversarial attacks and beamforming to improve cell-edge link reliability.

II. SYSTEM MODEL

The system models federated edge learning in a single-cell network, where devices train local models and upload updates for server-side aggregation. Broadband analog transmission uses simultaneous amplitude-modulated updates over orthogonal sub-channels to reduce aggregation latency.

  • Federated Edge Learning: FEEL trains a shared model by broadcasting the current model, running local SGD, and iteratively averaging uploaded device models.The process repeats until convergence.
  • Federated Edge Learning: The server needs only the aggregated model rather than individual model updates, motivating AirComp-based low-latency aggregation.
  • Broadband Update Transmission: OFDM divides the model-update sequence into blocks of M parameters, transmitting each block in one OFDM symbol across M sub-channels.A communication round requires Ns = q/M OFDM symbols.
  • Broadband Update Transmission: Devices simultaneously transmit amplitude-modulated model updates across the available bandwidth, with one model parameter assigned to each sub-channel.Symbol-level synchronization is assumed among transmitting devices.
  • Broadband Channel: The channel model includes path loss, i.i.d. Rayleigh fading, and i.i.d. AWGN, while sub-channel power allocation adapts to channel coefficients under a long-term transmit-power constraint.The path-loss exponent is α, and rk denotes device-server distance.

C. Network Topology

The paper considers devices independently and uniformly distributed over a disk centered at a single edge server. It then introduces broadband analog aggregation with channel-aware transmission and amplitude alignment.

  • Network Topology: Edge devices are independently distributed over a disk centered at the edge server, with cell radius R determining the network region.The device-distance distribution is specified through the PDF of rk.
  • Network Topology: For frequency-correlated channels, frequency block fading models identical gains within blocks and independent gains across blocks.The main results remain valid when truncation ratio is defined over truncated frequency blocks.
  • Transmitter Design: Broadband analog aggregation is proposed for low-latency FEEL by transmitting model updates simultaneously over the broadband channel.
  • Transmitter Design: Local-model parameters are amplitude-modulated, divided into blocks, and transmitted with one parameter per frequency sub-channel.The design replaces digital modulation with linear analog modulation and adds channel-inversion power control.
  • Transmitter Design: Power control inverts sub-channels so different devices’ model parameters arrive with identical amplitudes for aggregation.The power-control policy is constrained by deep fades and average transmit power.
  • Transmitter Design: The truncation ratio ζ measures the fraction of model-update parameters lost when channel inversion assigns zero power to sub-channels below the cutoff.

2) Receiver Design:

The receiver reconstructs the aggregated model from superimposed transmissions, while the analysis characterizes how channel inversion trades receive SNR against parameter truncation. This tradeoff motivates distance-aware scheduling and numerical threshold optimization.

  • Receiver Design: The server receives superimposed waveforms and obtains each aggregated local-model block by post-processing the received signal.Cascading all Ns blocks and scaling by 1/|K| produces the updated global model.
  • Receiver Design: Truncated model blocks contain zeros at parameters mapped to sub-channels whose channel realizations fail the inversion threshold.The receiver scales the processed blocks before global-model updating.
  • SNR Analysis: The maximum receive SNR is bounded by propagation distance, so scheduling devices within a distance threshold can limit the worst active-device distance.Amplitude alignment forces near devices to reduce power so all devices share receive SNR ρ0.
  • SNR-Truncation Tradeoff: As model dimension q →∞, the truncation ratio ζ equals the channel-cutoff probability.
  • SNR-Truncation Tradeoff: Increasing the power-cutoff threshold gth tends to increase receive SNR while truncating more model-update parameters.The threshold therefore controls the SNR-truncation tradeoff.
  • SNR-Truncation Tradeoff: A threshold that is too high or too low degrades learning performance, so experiments optimize it numerically by grid search.

IV. BROADBAND ANALOG AGGREGATION: SCHEDULING

The paper introduces cell-interior scheduling for broadband analog aggregation, restricting participation by distance to improve update reliability. It characterizes scheduled-device fractions and receive-SNR gains, exposing their dependence on the distance threshold.

  • Scheduling scheme: Cell-interior scheduling selects edge devices whose distances from the server do not exceed threshold Rin.
  • Scheduling scheme: Compared with all-inclusive scheduling, cell-interior scheduling improves update reliability but creates data deficiency by excluding cell-edge devices.
  • Exploited data: Under cell-interior scheduling, the number of scheduled users follows a Binomial distribution parameterized by Rin, R, and K.
  • Exploited data: The expected fraction of exploited data equals the fraction of scheduled devices under equal data partitioning.
  • Receive SNR: The exploited-data fraction and SNR gain are nonlinear functions of Rin/R with different exponent scalings: square-power for data and exponent α for SNR.

C. Reliability-Quantity Tradeoff

The paper formalizes a reliability–quantity tradeoff: restricting devices can improve SNR while reducing exploited training data. It then discusses mobility-aware and alternating scheduling schemes to mitigate data deficiency.

  • Reliability-quantity tradeoff: Cell-interior scheduling trades SNR gain against the fraction of exploited training data, with path-loss exponent α determining the cost of lost data.
  • Reliability-quantity tradeoff: For large α, learning is more SNR-limited and a smaller Rin is preferred, whereas small α favors including remote data when training is data-limited.
  • Reliability-quantity tradeoff: The optimal Rin is difficult to derive because its learning-performance tradeoff depends on data distribution, learning task, and learning model.
  • Reliability-quantity tradeoff: With non-IID data, learning tends to be more data-limited, so a larger Rin is desired compared with the IID case.
  • Opportunistic scheduling: In high-mobility networks, increasing NCR makes the probability that all distributed data is exploited approach 1 at an exponential rate.
  • Alternating scheduling: In low-mobility networks, alternating cell-interior and all-inclusive scheduling can exploit all data while achieving intermediate receive-SNR performance.
  • Alternating scheduling: Alternating scheduling can outperform both cell-interior and all-inclusive scheduling, with its frequency adjustable to balance reliability and data quantity.
  • Latency analysis: Broadband analog aggregation reduces communication latency relative to OFDMA by reusing the whole bandwidth for direct aggregation.

A. Latency Analysis of Broadband Analog Aggregation

BAA lets all devices transmit model updates simultaneously across available sub-channels, producing latency independent of the number of accessing devices. In contrast, broadband digital aggregation is governed by sequential resource allocation and straggler-dependent latency.

  • BAA latency: BAA uses all available sub-channels for simultaneous model-update transmission, enabling complete radio-resource reuse among devices.This produces a deterministic per-round latency characterized by Proposition 6.
  • BAA latency: BAA latency is independent of the number of accessing devices, making it promising for dense edge-learning networks.
  • Digital aggregation latency: Broadband digital aggregation quantizes each parameter and assigns equal sub-channel portions to devices to avoid inter-device interference.
  • Digital aggregation latency: Digital aggregation latency is determined by the slowest device because model aggregation occurs after all local models are reliably received.This is the straggler effect.
  • Digital aggregation latency: Digital aggregation latency approximately scales linearly with the number of accessing devices K and is bottlenecked by the furthest user's distance rmax.The path-loss exponent α determines the latency penalty for scheduling a far-away user.
  • Digital aggregation latency: Lower target BER can accelerate digital update aggregation, but it degrades update reliability.

C. Latency Comparison between Analog and Digital Aggregation

The paper compares BAA with digital aggregation through latency-reduction analysis and experiments under IID and non-IID MNIST settings. BAA's latency-reduction ratio scales almost linearly with device population, while learning accuracy remains comparable in the reported experiments.

  • Analytical comparison: BAA's latency-reduction ratio scales linearly with quantization resolution Q and approximately linearly with device count K.
  • Analytical comparison: The latency-reduction ratio increases unboundedly as rmax approaches infinity, with its growth rate determined by the path-loss exponent α.
  • Analytical comparison: The latency-reduction ratio decreases monotonically with target BER, while its dependence on the digital scheme's power-cutoff threshold has opposing effects.Increasing the threshold raises receive SNR but also increases channel-cutoff probability, producing competing latency effects.
  • Experimental evaluation: Test accuracy first increases and then decreases as the distance threshold includes more devices, confirming a reliability-quantity tradeoff.
  • Experimental evaluation: Higher path-loss exponents make performance more SNR-limited, while non-IID data generally requires more data and favors higher distance thresholds.

C. Performance Comparison between Different Scheduling Schemes

The scheduling and aggregation experiments evaluate learning accuracy, communication latency, and robustness extensions for BAA. BAA achieves comparable learning accuracy to OFDMA while reporting a 10x–1000x latency reduction, especially in low-SNR and dense networks.

  • Scheduling performance: Cell-interior scheduling outperforms the naive all-inclusive scheme by a remarkable gap in high-mobility scenarios.Distance thresholds are numerically optimized for best test accuracy.
  • Scheduling performance: Alternating scheduling further improves learning performance in low-mobility networks by occasionally exploiting cell-edge data.
  • BAA versus OFDMA: BAA and OFDMA achieve comparable learning accuracy in both IID and non-IID settings despite BAA's greater vulnerability to channel noise.The reported comparison uses the same transmit SNR per user and a fixed scheduling scheme.
  • BAA versus OFDMA: 10x to 1000x latency reduction is achieved by BAA without compromising learning accuracy relative to OFDMA.The latency advantage is more pronounced in low-SNR regimes and dense-network scenarios.
  • Robust BAA: DSSS-based BAA assigns legitimate devices a common spreading code so the server can aggregate their updates while suppressing adversarial-device contributions.
  • Robust BAA: The DSSS spreading factor trades latency-reduction ratio against receive-SNR enhancement and consumes γ-times more bandwidth.The added bandwidth cost is described as compensated by safety and improved SNR.

B. Coping with Cell-Edge Devices by Beamforming

Aggregation-beamforming addresses BAA's cell-edge bottleneck by directing sharp, strong beams toward weak devices. Unlike SDMA, it uses available spatial degrees of freedom for SNR enhancement rather than interference nulling.

  • Motivation and design: Cell-edge devices limit BAA update reliability, motivating multi-antenna beamforming to compensate their path loss.
  • Motivation and design: Aggregation-beamforming aligns received amplitudes and maximizes enhancement for weak users, whereas SDMA targets individual streams while suppressing interference.
  • Feasibility: SDMA requires N ≥ K to enforce zero-forcing constraints, which may be infeasible in large-scale networks with K = 100–1000.
  • Feasibility: Aggregation-beamforming is always feasible, and additional spatial degrees of freedom can improve SNR for weak users.
  • Beamforming comparison: Aggregation-beamforming forms sharper and stronger beams toward targeted cell-edge users because it uses all spatial degrees of freedom for SNR enhancement.
  • Beamforming comparison: Aggregation-beamforming does not require user discrimination, so nearby users do not create the SDMA differentiability issue.
  • Conclusions: The paper identifies SNR-truncation and reliability-quantity tradeoffs and proves that BAA's latency-reduction ratio over OFDMA scales almost linearly with device population.

APPENDIX

The appendix derives receive-SNR expressions for all-inclusive and cell-interior scheduling by modeling the scheduled-device count and averaging over conditional distance distributions. It also establishes convergence conditions and bounds the scheduling-dependent scaling factor.

  • Device-count distribution: The number of devices within the scheduling radius follows a Binomial distribution because device locations are independently and uniformly distributed.The success probability is the probability that a device lies within distance R_in of the edge server.
  • All-inclusive scheduling: The all-inclusive scheme’s expected receive SNR is computed from the distance distribution under the convergence condition 2K − α − 1 ≥ 0.The appendix states that this condition holds in practice and allows the relevant integral to be completed.
  • Cell-interior scheduling: Cell-interior scheduling introduces randomness from both the number of scheduled devices and their distances from the edge server.The derivation handles these two layers sequentially using conditional expectation.
  • Cell-interior scheduling: Conditioned on K_in = k, the scheduled devices are independently and uniformly distributed within the cell interior and scheduling radius.The expected receive SNR is evaluated by averaging over the k-th furthest device distance and the probability mass function of K_in.
  • Scaling-factor bound: For α = 3 and sufficiently large K, the scaling factor c(R_in) satisfies 1 ≤ c(R_in) ≤ 4.This follows because c(R_in) is a weighted average of terms ranging monotonically from 1 to 4.
Loading 1812.11494v3…