PaperlayerView exact revision on arXiv

Source-linked AI summary

Over-the-Air Federated Learning from Heterogeneous Data

Tomer Sery, Nir Shlezinger, Kobi Cohen, Yonina C. Eldar

arXiv:2009.12787v2cs.LGcs.ITstat.ML

TL;DR

Federated learning over shared wireless channels must balance private, distributed data with communication efficiency and noise-sensitive optimization. The paper develops COTAF, combining OTA aggregation with time-varying precoding and server scaling, and analyzes it under heterogeneous data. COTAF achieves the same asymptotic convergence rate as local SGD over orthogonal channels for convex objectives, while simulations show accurate learning and stronger performance than unprecoded OTA FL.

  • Problem

    Federated learning faces statistical heterogeneity and repeated model-parameter communication, while noisy OTA aggregation can affect optimization accuracy.

  • Method

    COTAF combines simultaneous analog OTA aggregation with time-varying user precoding and server-side scaling that gradually mitigates channel-noise effects.

  • Results

    COTAF matches local SGD’s asymptotic convergence rate over orthogonal channels for convex objectives and outperforms OTA FL without precoding in numerical studies.

  • Takeaways & Limitations

    COTAF supports local SGD over shared noisy wireless channels without dividing channel resources among users, including accurate learning on non-synthetic datasets.

Abstract

from arXiv · show

Federated learning (FL) is a framework for distributed learning of centralized models. In FL, a set of edge devices train a model using their local data, while repeatedly exchanging their trained updates with a central server. This procedure allows tuning a centralized model in a distributed fashion without having the users share their possibly private data. In this paper, we focus on over-the-air (OTA) FL, which has been suggested recently to reduce the communication overhead of FL due to the repeated transmissions of the model updates by a large number of users over the wireless channel. In OTA FL, all users simultaneously transmit their updates as analog signals over a multiple access channel, and the server receives a superposition of the analog transmitted signals. However, this approach results in the channel noise directly affecting the optimization procedure, which may degrade the accuracy of the trained model. We develop a Convergent OTA FL (COTAF) algorithm which enhances the common local stochastic gradient descent (SGD) FL algorithm, introducing precoding at the users and scaling at the server, which gradually mitigates the effect of the noise. We analyze the convergence of COTAF to the loss minimizing model and quantify the effect of a statistically heterogeneous setup, i.e. when the training data of each user obeys a different distribution. Our analysis reveals the ability of COTAF to achieve a convergence rate similar to that achievable over error-free channels. Our simulations demonstrate the improved convergence of COTAF over vanilla OTA local SGD for training using non-synthetic datasets. Furthermore, we numerically show that the precoding induced by COTAF notably improves the convergence rate and the accuracy of models trained via OTA FL.

I. INTRODUCTION

The paper addresses statistical heterogeneity and communication overhead in federated learning by developing COTAF for noisy wireless OTA aggregation. Its analysis and experiments examine convergence, heterogeneous data, and non-synthetic learning tasks.

  • Motivation: Federated learning keeps data at edge users while periodically synchronizing locally trained models through a central server.This avoids sharing potentially private datasets with the server.
  • Challenges: Statistical heterogeneity arises when users’ data-generating distributions differ, potentially limiting the inference accuracy of the global model.FL communication also repeatedly carries massive model parameters over comparatively constrained wireless uplinks.
  • OTA FL: OTA FL lets users simultaneously transmit analog model updates over shared wireless resources, using channel superposition for aggregation.Unlike orthogonal links, this can maintain throughput as the number of participating users increases.
  • OTA FL: Uncoded OTA signaling exposes optimization directly to channel noise, which can prevent noisy SGD from reaching the optimal solution.Prior OTA FL analyses considered sparse updates or full gradient descent, rather than typical SGD with heterogeneous data.
  • COTAF: COTAF introduces time-varying user precoding and server-side scaling to mitigate channel noise as expected SGD update differences decrease.The scheme is designed to preserve local SGD convergence while allowing simultaneous uplink sharing.
  • Analysis and evaluation: The paper provides convergence bounds for weighted averages and instantaneous models, extends the analysis to fading channels, and evaluates COTAF on non-synthetic datasets.Experiments cover a strongly convex Million Song Dataset estimator and a non-convex CIFAR-10 CNN.

C. Local SGD

Local SGD, also called federated averaging, trains models locally for multiple SGD steps before averaging them at the server. With heterogeneous data, convergence can still hold for convex objectives but is affected by data-distribution differences.

  • Local SGD: Local SGD, also referred to as federated averaging, is a distributed algorithm for recovering the global federated learning objective.It operates without requiring users to share their local data.
  • Local SGD: Each training round sends the current global model to users, initializes local models, and performs H local SGD steps using local data.The SGD update is repeated until each user obtains its locally trained model.
  • Aggregation: Users transmit their trained local models or updates to the server, which averages them into the next global model.The uplink is typically modeled as error-free with limited throughput in conventional local SGD.
  • Heterogeneous data: Under heterogeneous data, convergence includes an additional term reflecting the degree of heterogeneity.For convex objectives, convergence to the global objective can still be guaranteed, but at slower rates than under homogeneous data.

D. Problem Formulation

The section formulates FL over wireless multiple-access channels as a high-throughput alternative to orthogonal communication, while targeting convergence despite channel noise and heterogeneous local updates. It introduces COTAF’s time-varying precoding and server-side scaling to aggregate local models over the shared channel.

  • D. Problem Formulation: Local SGD repeatedly exchanges global and locally updated model parameters, creating substantial wireless communication overhead.Each round includes downlink transmission of the global model and uplink transmissions of updated local models.
  • D. Problem Formulation: The server needs an aggregate global model rather than individually recovered updates, motivating simultaneous use of the wireless MAC.The shared channel naturally superposes users’ analog signals, enabling OTA computation.
  • D. Problem Formulation: The communication strategy maps each user’s local model to channel inputs through precoding and transforms the channel output into a global model at the server.The protocol is required to mitigate noisy-SGD convergence limits and approach noise-free orthogonal-channel performance for convex objectives.
  • D. Problem Formulation: The section’s formulation addresses the tension between exploiting wireless aggregation for throughput and preserving learning accuracy under noisy communication.COTAF is designed to use the complete channel resources while targeting the convergence behavior of local SGD.
  • III. THE CONVERGENT OVER-THE-AIR FEDERATED LEARNING (COTAF) ALGORITHM: COTAF is proposed as an OTA local-SGD algorithm whose users transmit analog signals simultaneously and whose server directly recovers and feeds back the global model.The protocol is analyzed for convergence under strongly convex objectives, extended to fading channels, and discussed with its trade-offs.
  • D. Problem Formulation: OTA FL uses analog model-update transmissions over shared temporal and spectral resources instead of discrete coded symbols or orthogonal access.This design supports higher-throughput uplink communication by exploiting the MAC’s inherent aggregation.
  • A. Precoding and Reception Algorithm: COTAF gradually amplifies model updates through a time-varying precoding factor while respecting the transmission-power constraint.The precoding parameter can depend on the updated-model distribution and may be computed offline or replaced using bounded-gradient information.
  • A. Precoding and Reception Algorithm: Server-side scaling converts the received channel output into the global model and progressively mitigates the resulting noise.The global update rule is expressed using the initial parameter estimate and the aggregated received signal.

B. Performance Analysis

The analysis establishes finite-sample convergence bounds for COTAF under standard smoothness, strong-convexity, and bounded-gradient-variance assumptions. It shows that heterogeneity and channel noise contribute decaying error terms, yielding the same asymptotic rate as noiseless local SGD.

  • B. Performance Analysis: COTAF’s convergence analysis targets the loss-minimizing parameters under assumptions of smoothness, strong convexity, and bounded stochastic-gradient variance.These assumptions are standard in FL convergence studies and cover objectives such as regularized linear and logistic regression.
  • B. Performance Analysis: The analysis provides convergence bounds for both a server-attainable weighted average of past global models and the instantaneous model at the end of training.The weighted average uses only models available at the server, unlike averages that may include user-only models.
  • B. Performance Analysis: The weighted-average bound specializes to a prior noiseless result when σ2_w/P = 0, while the instantaneous-model bound coincides with another noiseless local-SGD theorem.The instantaneous-model bound is noted to be less tight because its derivation applies an additional relaxation.
  • B. Performance Analysis: Theorems 1 and 2 identify initial-model distance, statistical heterogeneity, and the channel noise-to-signal ratio as sources of convergence error.Heterogeneity is represented through Γ, while channel noise is represented through σ2_w/P.
  • B. Performance Analysis: The error contributions from initialization, heterogeneity, and noise decay proportionally to 1/(T + γ) or at order 1/T as iterations increase.Thus, the bounds do not retain a non-vanishing asymptotic noise floor under COTAF.
  • B. Performance Analysis: COTAF’s noise-dependent bound differs from the noiseless local-SGD bound by an additional term involving the noise-to-signal ratio.That term is progressively dominated as the number of rounds grows and can be further mitigated by increasing the number of users.
  • B. Performance Analysis: COTAF achieves the same asymptotic convergence rate as local SGD with a strongly convex objective over noiseless, communication-unconstrained channels.The paper attributes this result to time-varying precoding and aggregation while retaining full wireless temporal and spectral resource use.

C. Extension to Fading Channels

COTAF is extended to fading multiple-access channels using channel-aware participation and aggregation, while its convergence remains asymptotically O(1/T). Fading and partial participation add terms to the convergence bound.

  • Fading-channel extension: COTAF extends to fading MACs when participating entities have channel state information (CSI).The server uses CSI to identify eligible users and recover the aggregated model.
  • Fading-channel extension: Users with channel magnitude below hmin are excluded to avoid arbitrarily high inverse-channel amplification and power-constraint violations.The threshold-based scheme defines the participating set Kt at each communication round.
  • Convergence: The fading extension preserves the asymptotic convergence rate O(1/T) of the fading-free COTAF analysis.The result holds under assumptions AS1–AS4 and the specified decaying step sizes.
  • Convergence: Fading increases the effective noise term, while partial participation adds a positive term D that vanishes when K = N and grows as K decreases.The number of aggregated models is |Kt| ≤ N, and the bound reflects both effects.

D. Discussion

COTAF combines OTA aggregation with time-varying precoding and scaling to preserve convergence under noisy shared channels. Its practical scope is bounded by synchronization and shared-channel requirements.

  • Advantages: COTAF uses the full spectral and temporal resources of a shared wireless medium, so each user's allocation does not shrink with N.Users simultaneously transmit while the MAC aggregates their local models.
  • Motivation: Additive channel noise can prevent noisy distributed SGD from reaching the optimum, unlike noise-free local SGD with rate O(1/T).The noise contribution does not decay over time under the conventional OTA computation.
  • Mechanism: COTAF's precoding and scaling make the noise contribution decay, enabling convergence results similar to noise-free local SGD for strongly convex objectives.The gradual noise profile is also discussed in relation to non-convex optimization.
  • Implementation: Time-varying precoding requires users to know a model-update norm term, which can be bounded analytically or estimated through offline simulation.The server can distribute numerically computed values over the downlink.
  • Limitations: COTAF requires accurate synchronization and users sharing the same wireless channel and geographical area.The paper leaves combining COTAF with multi-stage schemes such as clustered FL for future study.

IV. NUMERICAL EVALUATIONS

Numerical evaluations test COTAF on a strongly convex Million Song linear predictor and a non-convex CIFAR-10 CNN. Across the reported Million Song settings, COTAF approaches noise-free local SGD and outperforms non-precoded OTA FL.

  • Evaluation settings: The evaluations cover a strongly convex Million Song linear predictor and a non-convex CIFAR-10 CNN.The Million Song task predicts song release years from 90 audio attributes; the second task trains a CNN classifier.
  • Million Song results: COTAF achieves a minor gap from noise-free local SGD and outperforms OTA FL without time-varying precoding on the Million Song task.The comparison uses the gap between the expected objective and the loss-minimizing objective.
  • Million Song results: Time-varying precoding gradually mitigates channel noise, whereas non-precoded OTA FL exhibits a dominant error floor from non-vanishing noise.The comparison is reported for the N = 50, H = 40 setting in Fig. 3.
  • Parameter effects: Increasing N from 50 to 200 improves both OTA FL schemes, with COTAF effectively coinciding with noise-free local SGD in Fig. 4.The total gradient computations and overall training samples remain fixed across the simulations.
  • Parameter effects: Increasing H from 40 to 80 improves OTA FL because channel noise is induced less frequently.This comparison is made between Fig. 5 and Fig. 3.
  • Fading evaluation: Under Rayleigh fading, extended COTAF maintains its ability to approach noise-free local SGD and preserves its improved convergence properties.The fading experiment uses N = 50 users with an average of 40 participating per round.

B. CNN Classifier Using the CIFAR-10 Dataset

The CIFAR-10 CNN experiment evaluates COTAF under i.i.d. and heterogeneous data, finding convergence comparable to noise-free local SGD and advantages over unprecoded OTA FL.

  • Experimental setup: The experiment trains a five-layer CNN on CIFAR-10 distributed across N = 10 users, comparing i.i.d. and heterogeneous data divisions.Each user holds 5000 images; aggregation occurs every H = 84 iterations at an SNR of −4 dB.
  • Results: The global model converges to approximately 70% accuracy in the CIFAR-10 i.i.d. setting, matching the centralized setting.Users fully utilize temporal and spectral channel resources, enabling higher throughput than orthogonal transmissions.
  • Convergence: COTAF converges at the same rate as noise-free local SGD despite the CNN’s non-convex cross-entropy objective.The result suggests COTAF can converge sub-linearly even when the convex-case assumptions do not hold.
  • Noise and precoding: Channel noise improves CNN convergence and generalization, with COTAF outperforming direct OTA FL without time-varying precoding.The smoothing effect contributes more effectively to accuracy under heterogeneous data than under i.i.d. data.
  • COTAF design: COTAF maintains convergence properties for heterogeneous data through time-varying precoding and scaling that gradually mitigate noise.The scheme aggregates models over shared wireless resources without requiring users to divide the channel.
  • Overall findings: For convex objectives, COTAF achieves the same asymptotic convergence rate as local SGD over orthogonal channels and learns accurate models over wireless channels.Simulations also report sub-linear convergence in non-convex settings and outperformance of unprecoded OTA FL and error-free orthogonal local SGD.

APPENDIX A. Proof of Theorem 1

Appendix A proves Theorem 1 by constructing a virtual averaged-model sequence, bounding its recursive error terms, and deriving a non-recursive convergence bound.

  • Proof strategy: A virtual sequence of averaged parameters represents the local models as if local SGD were replaced by mini-batch SGD.Although users and the server cannot compute it explicitly, the sequence enables use of established mini-batch SGD bounds.
  • Proof strategy: The proof bounds additive terms in the recursive error expression using separate lemmas before deriving a non-recursive convergence bound.Lemmas A.1–A.3 provide intermediate recursive and upper bounds, while Lemma A.4 converts them into the final form.
  • Noise analysis: The equivalent noise vector is zero-mean and independent of stochastic gradients, supporting the expected-error bounds used in the proof.Uniform sampling of the SGD iterates gives E[gt] = ¯gt.
  • Assumptions and step sizes: The proof applies decreasing step sizes satisfying ηt ≤ 1 4L and ηt ≤ 2ηt+H under assumptions AS1–AS3.These conditions are used to establish the recursive inequalities and bound the effect of local updates and communication noise.
  • Round-wise recursion: The recursion is unrolled across H-step communication rounds, using the fact that only one Dt entry is active in each round.Repeated application over R rounds produces the bound needed by Lemma A.4.
  • Conclusion: Combining Lemmas A.1–A.4 with convexity completes the proof of Theorem 1.The final step defines δt as the expected error and applies the resulting bounds to the objective gap.

B. Proof of Theorem 2

Theorem 2 is proved by bounding the global-model error under fading channels, selecting a decreasing step size, and applying strong convexity to obtain convergence.

  • Error recursion: The proof defines δt as the expected global-model weight error and derives a recursive relationship for it.The bound includes constants representing communication and stochastic-gradient effects.
  • Step-size selection: A decreasing step size ηt = ρ/(t + γ) is selected so that ηt ≤ 1 4L and ηt ≤ 2ηt+H.These conditions allow the auxiliary lemmas to be applied.
  • Inductive bound: Induction establishes δt ≤ ν/(t + γ) for a finite ν under the chosen parameters.The proof verifies the base case and shows the recursive inequality preserves the bound.
  • Theorem conclusion: Theorem 2 follows by combining the recursive error bound with the smoothness and strong-convexity properties of the objective.The parameter choices include γ ≥ max(H, 4ρL) and ρ > 0.

C. Proof of Theorem 3

Theorem 3 extends the convergence analysis to fading channels by relating the virtual averaged model to an unbiased equivalent global model and bounding their expected difference.

  • Equivalent model: The virtual averaged model ¯θt equals the equivalent global model ¯vt outside communication rounds, while the theorem characterizes E[F(¯vt)] − F(θ⋆).The virtual sequence incorporates the fading-channel transmission scheme.
  • Unbiasedness: Under assumption AS4, ¯θt is an unbiased estimator of ¯vt.This removes the corresponding expected-error term in the proof.
  • Fading-channel error: The expected difference between ¯θt and ¯vt is bounded using Lemma C.2.The resulting bound contributes an additional constant D and changes the scaling of the noise-to-signal ratio.
  • Proof conclusion: The proof applies the same argument as Theorem 2 to the resulting recursive inequality to establish the theorem.The final step uses the bounds from Lemmas C.1 and C.2 together with the equivalent global model.
Loading 2009.12787v2…