PaperlayerView exact revision on arXiv

Source-linked AI summary

Scheduling and Aggregation Design for Asynchronous Federated Learning over Wireless Networks

Chung-Hsuan Hu, Zheng Chen, Erik G. Larsson

arXiv:2212.07356v4cs.LGcs.DCcs.ITeess.SPmath.IT

TL;DR

Synchronous FL can be delayed by stragglers, while fully asynchronous updating can incur frequent communication, and wireless scheduling must account for both channel quality and data representation. The paper proposes periodic asynchronous aggregation with joint channel- and data-aware scheduling and age-aware aggregation weighting. Simulations report better convergence performance than FedAsync and FedAvg in both i.i.d. and non-i.i.d. scenarios.

  • Problem

    Synchronous aggregation waits for slow devices, while wireless FL also faces limited communication resources and asynchronous scheduling must address heterogeneous data and link quality.

    Source: §I · p. 1, D. Motivation of Scheduling and… · p. 4

  • Method

    The design periodically aggregates updates from ready devices, schedules using channel quality and training-data distribution, and weights aggregation by update age.

    Source: §I · p. 2, B. Asynchronous FL with Periodic… · p. 3, §VI · p. 9

  • Results

    For both i.i.d. and non-i.i.d. scenarios, the proposed asynchronous FL design outperforms FedAsync and FedAvg in convergence performance.

    Source: A. Comparison of FL frameworks · p. 8

  • Takeaways & Limitations

    The proposed scheduling and aggregation design is reported to outperform existing methods, especially with heterogeneous training data among devices.

    Source: §VI · p. 9

    The convergence analysis considers E=1; extending it to E>1 would require, among other things, quantifying local model divergence.

    Source: §IV · p. 6

Abstract

from arXiv · show

Federated Learning (FL) is a collaborative machine learning (ML) framework that combines on-device training and server-based aggregation to train a common ML model among distributed agents. In this work, we propose an asynchronous FL design with periodic aggregation to tackle the straggler issue in FL systems. Considering limited wireless communication resources, we investigate the effect of different scheduling policies and aggregation designs on the convergence performance. Driven by the importance of reducing the bias and variance of the aggregated model updates, we propose a scheduling policy that jointly considers the channel quality and training data representation of user devices. The effectiveness of our channel-aware data-importance-based scheduling policy, compared with state-of-the-art methods proposed for synchronous FL, is validated through simulations. Moreover, we show that an ``age-aware'' aggregation weighting design can significantly improve the learning performance in an asynchronous FL setting.

I. INTRODUCTION

The introduction motivates asynchronous federated learning as a way to address synchronous training’s straggler and communication costs, then presents periodic aggregation, joint channel- and data-aware scheduling, and age-aware weighting. The system model and FedAvg description establish the data-heterogeneity setting and synchronous training baseline.

II. SYSTEM MODEL

  • Under device heterogeneity, local datasets may be unbalanced and non-i.i.d.; the system model characterizes data heterogeneity with Γ, which approaches zero as dataset size grows under i.i.d. data.The system objective is to minimize an empirical loss over the devices’ data.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • Periodic asynchronous aggregation collects completed updates without interrupting other devices’ local training, aiming to avoid stragglers without the frequent exchanges of fully asynchronous FL.The design is presented as easy to implement and requiring little side information.Source: §I · pp. 1–2
  • The proposed scheduler jointly considers wireless channel quality and training-data distribution, addressing an asynchronous scheduling gap in prior work that did not account for non-i.i.d. data.The policy aims to reduce bias and variance in aggregated updates.Source: §I · p. 2
  • The paper proposes age-aware aggregation weighting and analyzes how update compression, data heterogeneity, and intra-iteration asynchrony affect convergence.The analysis also provides theoretical motivation for the scheduling design.Source: §I · p. 2

A. FedAvg with Synchronous Training and Aggregation

  • In the synchronous FedAvg baseline, devices train locally, a subset is scheduled to upload updates, and the server aggregates the received information to update the global model.The server first broadcasts the current global model, and each device runs E SGD steps.Source: A. FedAvg with Synchronous Training… · pp. 2–3

B. Asynchronous FL with Periodic Aggregation

Periodic aggregation lets devices train asynchronously while the server schedules ready devices at fixed intervals. The wireless model assumes error-free uplink transmissions and allocates communication symbols to equalize compression loss across devices.

B. Asynchronous FL with Periodic Aggregation

  • The server periodically schedules up to R ready-to-update devices; unscheduled devices continue local training without interruption or being dropped.The server collects updates every duration T̃, choosing min{R, |K(t)|} devices from those ready to report.Source: B. Asynchronous FL with Periodic… · p. 3

C. Physical Layer (PHY) Model

  • Uplink updates use orthogonal resources and channel-adaptive compression and coding, assumed to make transmissions error-free.Downlink compression errors are assumed absent; the uplink is the communication bottleneck that motivates scheduling and resource allocation.Source: C. Physical Layer (PHY) Model · pp. 3–4

1) Communication resource allocation:

  • To equalize compression loss across devices, symbol resources are allocated so devices with better channels receive fewer symbols.The allocation design is described as giving each device the same level of compression loss.Source: 1) Communication resource allocation · p. 4

2) Sparsification and Quantization:

The section describes wireless update compression and frames scheduling as a choice under communication constraints and heterogeneous data distributions. It identifies training-data heterogeneity as a source of aggregated-model variance.

2) Sparsification and Quantization:

  • Local updates are compressed by random sparsification followed by low-precision random quantization.The quantizer is unbiased and has bounded variance; the retained sparsified elements are quantized before transmission.Source: 2) Sparsification and Quantization · p. 4

D. Motivation of Scheduling and Aggregation Design

  • The design questions are which ready devices to schedule under communication constraints and how to weight updates with different ages.The stated objective is minimizing global empirical loss.Source: D. Motivation of Scheduling and… · p. 4

1) Training data distribution:

  • Variation in the amount of training data across devices can increase the variance of the aggregated model.The passage contrasts this with the i.i.d. data case, where Γ is expected to approach zero.Source: 1) Training data distribution · p. 4

2) Data compression:

The paper links compression loss and asynchronous updates to variation in aggregated updates, motivating joint scheduling and age-aware aggregation. It proposes channel- and data-aware scheduling with a freshness preference to support fast, smooth convergence.

2) Data compression:

  • Larger compression loss produces greater variance in the aggregated model because wireless updates arrive as noisy information.The updates are compressed to fit rate-limited wireless channels.Source: 2) Data compression · p. 4

3) Asynchronous model updates:

  • Different global-model versions used for local training make asynchronous updates an additional source of variation.The design rationale also calls for homogeneous representation of the full training set and low compression loss through better-channel scheduling.Source: 3) Asynchronous model updates · pp. 4–5

III. SCHEDULING AND AGGREGATION DESIGN FOR ASYNCHRONOUS FL

  • The proposed scheduling policy considers both device training-data distribution and channel conditions to seek a smaller optimality gap.The aggregation weights are adjusted to alleviate harmful impacts from asynchronous training.Source: §III · p. 5

A. Channel-aware Data-importance-based Scheduling

  • Scheduling first retains a subset of devices with the highest channel capacities, then selects to minimize label variance.The homogeneous-distribution criterion is expressed as minimizing label variance among the scheduled devices.Source: A. Channel-aware Data-importance-based… · p. 5

B. Age-aware Model Aggregation

  • The aggregation design weights updates using data proportion and age, with γ>1 favoring older updates and γ<1 favoring fresher ones.Favoring fresher updates is described as supporting fast, smooth convergence, while risking bias toward devices with stronger computing power; the scheduling policy's improved data homogeneity makes this strategy more convincing.Source: B. Age-aware Model Aggregation · p. 5
  • The scheduling design is stated to apply beyond asynchronous FL to distributed ML with heterogeneous and unbalanced data.The paper summarizes its channel-aware scheduling with favoring-fresh aggregation policy as leading to fast and smooth convergence.Source: B. Age-aware Model Aggregation · p. 5

IV. CONVERGENCE ANALYSIS

The convergence analysis bounds learning error under partial participation, update compression, data heterogeneity, and asynchronous updates. It shows why scheduling must account for both channel quality and training-data representation.

IV. CONVERGENCE ANALYSIS

  • The analysis defines a data-heterogeneity metric for device subsets, with weights determined by local training-data size.Devices with the same age are represented as a subset of the scheduled devices.Source: §IV · p. 5
  • The analysis assumes bounded expected gradient noise to retain a strongly convex objective over an unbounded parameter space.The paper notes that uniformly bounded gradients and strong convexity over an unbounded space are incompatible.Source: §IV · p. 6
  • Theorem 1 bounds convergence for E=1 under Assumptions 1–4 and partial device participation, while the asymptotic error need not vanish.The nonzero error is attributed to partial participation and data heterogeneity.Source: §IV · pp. 6–7
  • The convergence analysis treats one local iteration; extending it to E>1 would require, among other things, quantifying local model divergence.The authors choose E=1 for analytical clarity and simplicity.Source: §IV · p. 6
  • A larger r_min and higher quantization level ν reduce the asymptotic error, while a smaller learning rate α also improves the bound.The analysis associates r_min with channel quality and ν with update resolution.Source: §IV · p. 7
  • Update asynchrony slows the contraction rate relative to nominal gradient descent, with the bound reflecting model versions up to age a_lim.The maximum model age is a_lim = ceil(T_max / T̃).Source: §IV · pp. 5–7
  • The convergence remarks support scheduling based on both training-data distribution and channel quality.Better link quality corresponds to a larger r_min in the analysis.Source: §IV · p. 7

V. SIMULATION RESULTS

The simulations evaluate the proposed scheme on MNIST under i.i.d. and non-i.i.d. data distributions. Test accuracy varies with the partial scheduling ratio: smaller ratios favor i.i.d. data, while non-i.i.d. data presents a compression–bias trade-off.

V. SIMULATION RESULTS

  • Simulations use MNIST digit classification with a CNN of dimension 21840, 60000 samples, and both i.i.d. and non-i.i.d. device data.For non-i.i.d. data, each device contains up to min(floor(200/N), 10) different digits.Source: §V · p. 7
  • The evaluation uses a four-level random quantizer and heterogeneous local training durations drawn uniformly between T_min and T_max.The uplink uses Rayleigh fading with received SNR set to 13 dB.Source: §V · p. 7
  • In i.i.d. simulations, a smaller R is preferable; in non-i.i.d. simulations, choosing R involves a trade-off between compression loss and model bias.More scheduled devices divide communication resources among more users, increasing compression loss; the study fixes R rather than optimizing it.Source: §V · p. 7, Figure 4 · p. 7
  • The optimal R depends on system parameters, and its optimization is left for future work.The reported scheduling comparisons therefore use a fixed R.Source: §V · p. 7

A. Comparison of FL frameworks

The proposed periodic-aggregation asynchronous FL framework is compared with synchronous and asynchronous baselines, then evaluated with different scheduling and aggregation policies. Across the reported scenarios, the proposed designs perform better, while the results also show sensitivity to asynchrony and system parameters.

A. Comparison of FL frameworks

  • ˜T = T_max/4 gives the best reported performance, but the preferred aggregation period depends on other system parameters.The comparison fixes the average communication resources allocated over a time period.Source: A. Comparison of FL frameworks · p. 7, Figure 5 · p. 8
  • In both i.i.d. and non-i.i.d. scenarios, the proposed asynchronous FL design outperforms FedAvg and FedAsync.FedAsync reduces the straggler effect but shows strong test-accuracy fluctuation, especially with non-i.i.d. data.Source: A. Comparison of FL frameworks · p. 8, Figure 6 · p. 8

B. Validation of convergence analysis

  • Training loss is lower in the i.i.d. than the non-i.i.d. scenario with both scheduling methods, consistent with smaller A yielding lower loss.The proposed scheduling design also outperforms random scheduling in both scenarios.Source: B. Validation of convergence analysis · p. 8, Figure 7 · p. 8
  • Synchronous updates have lower training loss than asynchronous updates, while smaller ˜T produces less-smooth test-accuracy curves.The authors interpret these observations as evidence that greater intra-iteration asynchrony degrades learning performance.Source: B. Validation of convergence analysis · p. 8, Figure 7 · p. 8

C. Comparison of scheduling policies

  • The proposed scheduling policy outperforms random scheduling and reference methods in both data scenarios, with data-awareness further improving over BC and BCBN2 in the non-i.i.d. scenario.The comparison holds when aggregation weights use the baseline setting γ = 1.Source: C. Comparison of scheduling policies · p. 8, Figure 8 · p. 9

D. Comparison of aggregation policies

  • The age-aware aggregation design outperforms baseline weighting in both scenarios; favoring fresh updates gains notably in the i.i.d. case.In the non-i.i.d. case, the proposed aggregation design gains more clearly when paired with random scheduling.Source: D. Comparison of aggregation policies · p. 9, Figure 9 · p. 9

VI. CONCLUSIONS

  • The conclusion identifies reducing bias and variance in aggregated updates, and balancing update freshness and usefulness, as design principles for wireless FL.The latter balance is highlighted specifically for asynchronous FL.Source: §VI · p. 9

VIII. APPENDIX

The appendix organizes the convergence proof around updates grouped by the age of the global model used for local training. It derives an error bound by relating each age group's averaged update to the renewed global model.

A. Proof of Theorem 1

  • A device in age group m trains from global model θ(t−m), and its group's average updated model contributes to the renewed global model.The scheduled set comprises groups up to the asynchrony limit.Source: A. Proof of Theorem 1 · pp. 9–10
  • The proof introduces a lemma that quantifies how error evolves in each age group under Theorem 1's conditions.The appendix states that the lemma result holds for m from 0 through a_lim.Source: A. Proof of Theorem 1 · p. 10
  • Theorem 1's proof establishes its bound by induction, extending the base case through successive iterations.The text identifies the induction step and then completes the bound using the preceding result.Source: A. Proof of Theorem 1 · p. 10

B. Proof of Lemma 1

The proof treats devices in age groups separately, then combines their contributions into the renewed global model. Its stated intermediate results concern the mean and variance of the aggregated updates.

B. Proof of Lemma 1

  • The resource allocation sets equal r_k(t) for all scheduled devices, allowing the proof to denote this common allocation by r_t.The mean of each age group's aggregated update is conditioned on r_t, the group, and the received model.Source: B. Proof of Lemma 1 · p. 10
  • The proof groups devices by the model age used for training and combines each group's average updated model into the renewed global model.The timeline figure depicts devices from receiving the global model through completion of local training.Source: B. Proof of Lemma 1 · p. 11, Figure 10 · p. 11
  • The proof states a bound on the variance of the aggregated update for an age group under Theorem 1's condition.The variance result is used in the subsequent derivation.Source: B. Proof of Lemma 1 · p. 11

C. Proof of Lemma 2

The proof bounds the expected squared distance to the optimum by expanding the update error and applying properties of the objective. Smoothness and the stated bounds are then used to complete the estimate.

C. Proof of Lemma 2

  • The proof expands the squared distance after inserting the averaged update into the received-model error expression.This sets up the terms used in the subsequent bound.Source: C. Proof of Lemma 2 · p. 11
  • Jensen's inequality, strong convexity, and L-smoothness are used to bound terms in the expanded expression.The normalized weights sum to 1.Source: C. Proof of Lemma 2 · p. 12
  • The proof further bounds the resulting sum using L-smoothness and then applies the stated inequalities to finish the estimate.The final step also uses r_t/d ≤ 1 and (16).Source: C. Proof of Lemma 2 · p. 12

D. Proof of Lemma 3

The proof bounds the variance of the aggregated update by accounting for randomness from mini-batch sampling and compression. It evaluates the effects of sparsification, quantization, and sampling in sequence, then applies stated inequalities and smoothness.

D. Proof of Lemma 3

  • The variance of the aggregated update is considered with respect to mini-batch and compression randomness, conditioned on the realization of the other stated quantities.The conditioning includes r_t, M_m(t), and θ(t−m).Source: D. Proof of Lemma 3 · p. 12
  • Compression applies sparsification followed by quantization, with each gradient element preserved with probability r_t/d and otherwise nullified.Source: D. Proof of Lemma 3 · p. 12
  • The proof successively evaluates expectations over sparsification, quantization, and mini-batch sampling, using convexity, stated inequalities, and L-smoothness to bound the variance.Source: D. Proof of Lemma 3 · pp. 12–13

Related papers

Loading 2212.07356v4…