PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Edge Learning with Misaligned Over-The-Air Computation

Yulin Shao, Deniz Gunduz, Soung Chang Liew

arXiv:2102.13604v3cs.ITcs.DCcs.LGeess.SPmath.IT

TL;DR

Residual channel-gain mismatch and timing offsets make the ML estimator for misaligned OAC in FEEL an open problem. The paper introduces WMFS and uses its samples to devise SP-ML and aligned-sample estimators. Their relative learning performance depends on EsN0 and phase misalignment: aligned-sample estimation is favored at low EsN0 under non-severe phase misalignment, while ML performs well at high EsN0 across phase-misalignment severity.

  • Problem

    Designing an ML estimator for OAC with residual channel-gain mismatch and timing offsets in FEEL remains an open problem.

    Source: §I · pp. 1–2

  • Method

    WMFS produces oversampled independent samples used to devise SP-ML and aligned-sample estimators of the transmitted-symbol sum.

    Source: §VII · p. 13

  • Results

    At low EsN0, aligned-sample estimation outperforms ML with mild or moderate phase misalignment; at high EsN0, ML works even with severe phase misalignment.

    Source: §V · p. 12

  • Takeaways & Limitations

    The aligned-sample estimator is preferred at low EsN0, whereas ML is preferred at high EsN0; both have complexity linear in packet length.

    Source: §VII · p. 13

Abstract

from arXiv · show

Over-the-air computation (OAC) is a promising technique to realize fast model aggregation in the uplink of federated edge learning. OAC, however, hinges on accurate channel-gain precoding and strict synchronization among the edge devices, which are challenging in practice. As such, how to design the maximum likelihood (ML) estimator in the presence of residual channel-gain mismatch and asynchronies is an open problem. To fill this gap, this paper formulates the problem of misaligned OAC for federated edge learning and puts forth a whitened matched filtering and sampling scheme to obtain oversampled, but independent, samples from the misaligned and overlapped signals. Given the whitened samples, a sum-product ML estimator and an aligned-sample estimator are devised to estimate the arithmetic sum of the transmitted symbols. In particular, the computational complexity of our sum-product ML estimator is linear in the packet length and hence is significantly lower than the conventional ML estimator. Extensive simulations on the test accuracy versus the average received energy per symbol to noise power spectral density ratio (EsN0) yield two main results: 1) In the low EsN0 regime, the aligned-sample estimator can achieve superior test accuracy provided that the phase misalignment is non-severe. In contrast, the ML estimator does not work well due to the error propagation and noise enhancement in the estimation process. 2) In the high EsN0 regime, the ML estimator attains the optimal learning performance regardless of the severity of phase misalignment. On the other hand, the aligned-sample estimator suffers from a test-accuracy loss caused by phase misalignment.

I. INTRODUCTION

Federated edge learning reduces reliance on centralized data processing, but wireless uplink aggregation is challenging because model updates are large and OAC depends on accurate channel precoding and synchronization. This paper formulates misaligned OAC for FEEL and develops estimators and a system model for recovering the arithmetic sum despite residual channel and timing errors.

I. INTRODUCTION

  • OAC uses simultaneous signal superposition for uplink aggregation, but residual channel-gain mismatch and timing offsets are practical challenges to its required precoding and synchronization.Orthogonal resource allocation can limit the model-update quality each device transmits, while updates may comprise hundreds of millions of real values.Source: §I · pp. 1–2
  • The paper formulates misaligned OAC for FEEL and proposes whitened matched filtering and sampling, SP-ML, and aligned-sample estimators for recovering the transmitted-symbol sum.The SP-ML estimator has linear complexity in packet length; the aligned-sample estimator is presented as an alternative in the low-EsN0 regime.Source: §I · p. 2

II. SYSTEM MODEL

  • In FEEL, devices train locally and send scaled model updates to a parameter server, which estimates their arithmetic sum and updates the global model.The system model focuses on the uplink aggregation step using analog OAC.Source: §II · p. 3
  • The system allows residual channel-gain and timing misalignments; it assumes flat, slow fading and relative delays shorter than one symbol, while noting extensions to CFO and fast fading.Channel-gain precoding and timing calibration can be imperfect because of hardware and estimation errors.Source: §II · p. 3

A. Aligned OAC

Aligned OAC is the idealized case in which devices compensate channel gains and their signals arrive synchronously. Matched filtering and sampling then expose the arithmetic sum in the received samples.

A. Aligned OAC

  • Prior OAC work, except, considered the aligned case, with inverse channel-gain precoding and zero relative delay.Under these conditions, the received signal contains the arithmetic sum of device symbols directly.Source: A. Aligned OAC · p. 4
  • Matched filtering by the rectangular pulse and sampling at symbol intervals yields samples with independent, identically distributed noise.The supplied passage specifies the sampling procedure and the noise property.Source: A. Aligned OAC · p. 4
  • With channel-gain or timing misalignment, clean samples with the desired sum explicitly present are no longer available.In the aligned case, the fading multiple-access channel reduces to a Gaussian multiple-access channel.Source: A. Aligned OAC · p. 4

B. Misaligned OAC

Misaligned OAC produces overlapped signals whose sampled observations do not directly expose the desired sum. The paper formulates ML estimation from these observations, relates it to multi-user estimation, and motivates a lower-complexity alternative.

B. Misaligned OAC

  • Oversampling the matched-filtered received signal at device-specific timing offsets collects sufficient statistics for misaligned OAC.The resulting sample noise is colored, so the observations are not independent.Source: B. Misaligned OAC · p. 4
  • The ML estimate of the arithmetic sum can be obtained by first estimating the transmitted vector and then summing its symbols.For continuous-valued OAC with misaligned channel gains, this ML procedure reduces to multi-user estimation and detection.Source: B. Misaligned OAC · p. 5
  • Because OAC treats the complex signal space as equiprobable, ML estimation faces an infinitely large estimation space and can be susceptible to noise.The transmitted neural-network weights are strongly correlated, making their prior information difficult for the receiver to obtain.Source: B. Misaligned OAC · p. 5
  • For fixed device count, conventional ML estimation has complexity Ω(L^2 log L), while the factor-graph estimator reduces it to Ω(L).The conventional estimator requires inversion of an ML-by-ML coefficient matrix; packet length can be extremely large in practice.Source: B. Misaligned OAC · p. 5

IV. A SUM-PRODUCT ML ESTIMATOR AND THE ALIGNED-SAMPLE ESTIMATOR

WMFS provides oversampled independent observations that support a factor-graph ML estimator and also yields aligned samples for a separate estimator.

IV. A SUM-PRODUCT ML ESTIMATOR AND THE ALIGNED-SAMPLE ESTIMATOR

  • WMFS produces oversampled but independent samples from the misaligned signal.The scheme is the basis for the two estimator paths described in the section.Source: §IV · p. 5
  • The independent samples support a simple factor graph for a low-complexity SP-ML estimator.The factor graph represents sample composition.Source: §IV · p. 5
  • A subsequence with consistent symbol indexes across devices supports an aligned-sample estimator for misaligned OAC.In these samples, symbols from different devices are aligned in time.Source: §IV · p. 5

A. WMFS

The WMFS scheme uses matched filters of different lengths to produce an equivalent whitened model of the received signal. Its independent samples reduce the number of symbols related to each observation, while the ML estimator based on this model remains computationally demanding.

A. WMFS

  • WMFS uses a bank of M matched filters with different lengths to collect power from the received signal.The k-th filter length is d_k = τ_k+1 − τ_k.Source: A. WMFS · pp. 5–6
  • The resulting model is equivalent to the original sampled model, but its noise is white and independent across samples.The paper states that no information is lost in the transformation.Source: A. WMFS · p. 6
  • Each WMFS sample is related to M complex symbols, compared with 2M −1 symbols for a sample in the original model.The reduced interference structure also gives the factor graph a simpler form.Source: A. WMFS · p. 6
  • The ML estimator designed from the whitened model still requires computationally demanding matrix operations.The passage says its computational demands are as in the conventional estimator.Source: A. WMFS · pp. 6–7

B. A Factor Graph Approach

The factor-graph approach represents the likelihood through sample-level factors and symbol variables. Clustering neighboring symbols removes short loops, yielding a tree on which the sum-product algorithm computes marginal likelihoods exactly.

B. A Factor Graph Approach

  • The global likelihood can be factorized by sample because each observation is related to only M complex symbols.The associated factor graph represents observations, symbols, and noise terms as variables.Source: B. A Factor Graph Approach · p. 7
  • Short loops in the original graph can prevent sum-product convergence and make its equilibrium posterior only approximate.The graph's shortest loop has length 4.Source: B. A Factor Graph Approach · p. 7
  • Clustering each sample's neighboring symbols into a higher-dimensional variable removes loops, with compatibility functions enforcing consistency of shared symbols.The clustered variables may be correlated because they contain common symbols.Source: B. A Factor Graph Approach · p. 7
  • The resulting tree permits exact computation of marginal likelihoods via sum-product, despite the variables having M times larger dimensions.The tree structure is equivalent to the loopy graph before clustering.Source: B. A Factor Graph Approach · p. 8, Figure 5 · p. 8

C. Analog Message Passing and the SP-ML Estimator

The SP-ML estimator passes Gaussian message parameters on a loop-free factor graph and uses them to estimate the arithmetic sum. With M fixed, its computational complexity is linear in packet length.

C. Analog Message Passing and the SP-ML Estimator

  • Because OAC symbols are continuous complex numbers, sum-product messages are probability density functions rather than finite-length probability vectors.Quantizing these PDFs incurs a curse of dimensionality, making that approach prohibitively complex for the higher-dimensional variables.Source: C. Analog Message Passing and the… · p. 8
  • The estimator passes parameters of multivariate Gaussian messages, whose means and covariance matrices represent the continuous PDFs.The Gaussian form follows from Gaussian likelihood inputs to the factor graph.Source: C. Analog Message Passing and the… · pp. 8–9
  • The SP-ML estimator computes Gaussian moment parameters for each marginal and then estimates each element of the desired sum.The paper describes each marginal likelihood as a multivariate complex Gaussian and the sum's likelihood as a single-variate complex Gaussian.Source: C. Analog Message Passing and the… · p. 9
  • With M fixed, the SP-ML estimator reduces computational complexity from Ω(L^2 log L) to Ω(L).The general complexity given for analog message passing is Ω(LM^2 log M).Source: C. Analog Message Passing and the… · pp. 9–10

D. Aligned-Sample Estimator

The aligned-sample estimator uses outputs of the M-th matched filter, where neighboring symbols from different devices have consistent indexes. It estimates the desired sequence symbol by symbol, with good performance expected when channel-gain misalignment is absent or mild.

D. Aligned-Sample Estimator

  • Outputs of the M-th matched filter contain neighbor symbols from different devices with aligned indexes.The symbols have the same index within the integral interval of that filter.Source: D. Aligned-Sample Estimator · p. 10
  • The aligned-sample estimator estimates the desired sequence symbol by symbol using WMFS outputs.The method is defined for the whitened samples {y_k[i]}.Source: D. Aligned-Sample Estimator · p. 10
  • The estimator is expected to perform very well when channel-gain misalignment is absent or mild.The stated condition is h′_M → 1.Source: D. Aligned-Sample Estimator · p. 10

V. SIMULATION RESULTS

The simulations compare ML and aligned-sample estimation for FEEL under noise, time offsets, and phase misalignment. Their relative performance depends on both EsN0 and phase severity: aligned-sample estimation can do better at low EsN0, while ML remains effective at high EsN0 even under severe phase misalignment.

Evaluation and noise

  • In 100-iteration evaluations of a 40-device CIFAR-10 CNN, noise reduced test accuracy by 11.6% at EsN0 = −12 dB and 29.9% at EsN0 = −20 dB.The noiseless, ideally aggregated case reached 73.43% test accuracy.Source: §V · p. 10

Time misalignment

  • Increasing τM degrades both estimators; for aligned-sample estimation, τM = 0.5 incurs a 3 dB EsN0 penalty and τM = 0.9 incurs a 10 dB penalty.With time misalignment and noise alone, ML's performance gain over aligned-sample estimation is negligible.Source: §V · p. 11

Estimator behavior

  • ML can suffer error propagation and noise enhancement because noisy likelihood estimates propagate through message passing without intervening prior information.Using only the M-th matched-filter outputs for ML can yield an underdetermined system with arbitrarily large estimation error.Source: §V · p. 11

Phase misalignment

  • At φ = π/2, aligned-sample estimation incurs about a 5 dB EsN0 penalty and an 11.7% test-accuracy loss; at φ = 3π/4 its test-accuracy penalty reaches 28.2%, and at φ = π learning diverges.At high EsN0, ML has no test-accuracy loss under moderate or severe phase misalignment, with only a small EsN0 penalty.Source: Figure 8 · p. 11, §V · p. 12

Time and phase interaction

  • With mild phase misalignment, increasing τM from 0.5 to 0.9 yields ML an EsN0 gain of about 2 dB, whereas larger time misalignment hurts ML when phase misalignment is absent.For aligned-sample estimation, the τM = 0.9 curves shift right by 7 dB relative to the corresponding τM = 0.5 curves.Source: §V · p. 12, Figure 9 · p. 12

Estimator comparison

  • With mild or moderate phase misalignment, aligned-sample estimation outperforms ML at low EsN0 but underperforms it at high EsN0; with severe misalignment, aligned-sample learning diverges while ML still works at high EsN0.Without phase misalignment, the estimators achieve equal learning performance.Source: §V · p. 12

VI. TIME-DOMAIN REALIZATION VERSUS FREQUENCY-DOMAIN REALIZATION

The section compares time- and frequency-domain OAC realizations under misalignment. OFDM transforms time offsets into phase offsets, trading test-accuracy loss for an EsN0 penalty; residual CFO introduces additional interference in the frequency domain.

  • Time-domain OAC is sensitive to device time offsets, whereas frequency-domain OAC is sensitive to carrier-frequency offsets (CFOs).Source: §VI · p. 12
  • OFDM uses a cyclic prefix to transform time offsets into subcarrier phase offsets, making each subcarrier equivalent to a synchronous time-domain realization with phase misalignment.For the no-CFO case, the paper relates OFDM performance to the aligned-sample estimator after a 3 dB left shift.Source: §VI · p. 12
  • OFDM trades test-accuracy loss for an EsN0 penalty, while residual CFO introduces inter-carrier interference that the paper treats with the time-domain ML-estimation analysis.The SP-ML estimator can also be used for OFDM with residual CFO.Source: §VI · p. 13

VII. CONCLUSION

The paper develops two estimators for the arithmetic sum in misaligned OAC using oversampled matched filtering and sampling. Their trade-off depends on EsN0: aligned-sample estimation is preferred at low EsN0, while ML is preferred at high EsN0.

  • Oversampled matched filtering and sampling yields whitened samples with alleviated interferences and a subsequence whose transmitted-symbol indexes are aligned.Source: §VII · p. 13
  • The SP-ML estimator uses a simple factor graph and analog message passing to compute the ML estimate with complexity linear in packet length.Source: §VII · p. 13
  • ML estimation can suffer error propagation and noise enhancement, especially at low EsN0 with phase misalignment; pilot insertion is proposed to cut off error propagation.The aligned-sample estimator avoids those two issues but incurs test-accuracy loss from phase misalignment and an EsN0 penalty from time misalignment.Source: §VII · p. 13
  • Both estimators have complexity linear in packet length; aligned-sample estimation is preferred at low EsN0 and ML estimation at high EsN0.Source: §VII · p. 13

APPENDIX A

The appendix extends the signal model to fast fading and residual CFO, then reports simulations on amplitude mismatch and active-device count. The reported estimator and device-count patterns are consistent across the tested settings.

APPENDIX A

  • With fast fading and residual CFO, the appendix modifies the signal model's coefficients; residual CFO introduces additional channel-gain misalignment among devices.Transmit precoding is adjusted to compensate for fast fading and CFO.Source: Appendix A · pp. 13–14

A. Channels with mismatched amplitudes

  • With mismatched residual-channel amplitudes, aligned-sample estimation works well at low EsN0, while ML works well at high EsN0 and reaches the aligned case's converged accuracy.The aligned-sample estimator loses test accuracy from amplitude and phase misalignment.Source: A. Channels with mismatched amplitudes · p. 14, Figure 10 · p. 14

B. Effect of the number of active devices

Related papers

Loading 2102.13604v3…