PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence of Update Aware Device Scheduling for Federated Learning at the Wireless Edge

Mohammad Mohammadi Amiri, Deniz Gunduz, Sanjeev R. Kulkarni, H. Vincent Poor

arXiv:2001.10402v2cs.ITcs.DCcs.LG

TL;DR

Wireless federated learning must train across power- and bandwidth-limited links while deciding which devices can transmit useful updates. The paper jointly schedules devices and allocates resources using channel conditions and update significance, then establishes convergence under limited transmission capacity. It reports better long-term performance than single-metric scheduling and shows that the preferred number of devices depends on data distribution.

  • Problem

    Wireless FL requires distributed learning techniques that operate with limited communication over power- and bandwidth-constrained links.

  • Method

    The paper designs scheduling and resource-allocation policies based on channel conditions and local model-update significance, with convergence analysis for capacity-limited transmissions.

  • Results

    The combined scheduling metric outperforms either metric individually; one device is best for i.i.d. data, whereas multiple devices improve performance for non-i.i.d. data.

  • Takeaways & Limitations

    The preferred number of scheduled devices should increase as the data distribution becomes less diverse and more biased.

Abstract

from arXiv · show

We study federated learning (FL) at the wireless edge, where power-limited devices with local datasets collaboratively train a joint model with the help of a remote parameter server (PS). We assume that the devices are connected to the PS through a bandwidth-limited shared wireless channel. At each iteration of FL, a subset of the devices are scheduled to transmit their local model updates to the PS over orthogonal channel resources, while each participating device must compress its model update to accommodate to its link capacity. We design novel scheduling and resource allocation policies that decide on the subset of the devices to transmit at each round, and how the resources should be allocated among the participating devices, not only based on their channel conditions, but also on the significance of their local model updates. We then establish convergence of a wireless FL algorithm with device scheduling, where devices have limited capacity to convey their messages. The results of numerical experiments show that the proposed scheduling policy, based on both the channel conditions and the significance of the local model updates, provides a better long-term performance than scheduling policies based only on either of the two metrics individually. Furthermore, we observe that when the data is independent and identically distributed (i.i.d.) across devices, selecting a single device at each round provides the best performance, while when the data distribution is non-i.i.d., scheduling multiple devices at each round improves the performance. This observation is verified by the convergence result, which shows that the number of scheduled devices should increase for a less diverse and more biased data distribution.

I. INTRODUCTION

The paper addresses federated learning over bandwidth- and power-limited wireless links by jointly scheduling devices and allocating resources using channel quality and update significance. It establishes convergence under limited message capacity and reports that the best number of scheduled devices depends on data heterogeneity.

  • Wireless FL must accommodate unreliable, bandwidth-limited links and energy-constrained devices with limited communication requirements.
  • The proposed policies select transmitting devices and allocate orthogonal wireless resources using both channel conditions and local model-update significance.Resources favor devices with important messages and sufficient link capacity.
  • The paper establishes a convergence result for scheduled FL when participating devices can transmit only a channel-capacity-limited number of bits.
  • Scheduling based on both channel conditions and update significance outperforms policies based on either metric individually.
  • For i.i.d. data, selecting one device performs best, whereas non-i.i.d. data favors scheduling multiple devices.The convergence analysis corroborates this experimental observation.
  • Convergence speed increases with scheduled-device count when gradient variance is large, while one device performs best when variance is limited.

II. SYSTEM MODEL

The system consists of wireless devices and a remote parameter server collaboratively minimizing an empirical loss through local SGD and scheduled model-update aggregation. Because shared wireless resources limit reliable transmission, only a subset of devices participates in each round.

  • M wireless devices collaboratively train a d-dimensional model with a remote parameter server over a shared wireless medium.
  • Each device performs τ local stochastic-gradient updates starting from the global model received from the parameter server.
  • The parameter server updates the global model by averaging local model updates received from participating devices and redistributes it.
  • Power, bandwidth allocation, and fading constrain how reliably devices can convey updates over the shared medium.
  • At each iteration, the parameter server schedules a K-element subset of devices and updates the global model using only their transmissions.

B. Wireless Medium

The wireless model uses digital, orthogonal transmissions over a single-carrier block-fading channel with limited bandwidth and power. Channel capacity determines each scheduled device’s reliable transmission budget and quantization resolution.

  • Devices transmit local updates digitally over a single-carrier block-fading wireless medium with limited bandwidth.
  • The parameter server knows all uplink CSI while each device knows its own channel state information.
  • Compression and channel coding quantize updates at the resolution supported by channel capacity for reliable transmission.
  • Orthogonal resource allocation provides interference-free communication, with scheduled devices receiving distinct time slots.
  • A device’s conveyed information is R_m(t) = n_m C_m(t), linking its allocated slots to channel capacity.

III. DIGITAL SGD (D-SGD) QUANTIZATION SCHEME

D-SGD compresses each local update by retaining its largest positive and negative entries, then transmits the quantized vector digitally within channel-capacity limits. The section motivates scheduling because more participants reduce each device’s resources and update accuracy.

  • The digital transmission scheme combines data compression with channel coding for local model updates.
  • D-SGD quantization retains only the largest q_m(t) positive and smallest q_m(t) negative update entries, typically with q_m(t) much smaller than d.
  • The retained entries are represented by a quantized vector whose sparsity level q_m(t) is selected to satisfy transmission capacity.
  • Scheduling more devices divides limited resources among them, causing less accurate contributions to the learning task.
  • The scheduling objective is to identify the device set yielding the best learning performance under these resource constraints.
  • The four scheduling policies are best channel, best l2-norm, best channel-best l2-norm, and best l2-norm-channel.

A. BC Scheduling Policy

The policies schedule devices and allocate bandwidth using channel conditions, update significance, or both, while accommodating limited transmission capacity. BN2-C combines channel conditions with the post-quantization significance of local updates.

  • BC Scheduling Policy: BC schedules K devices with the highest channel gain magnitudes without requiring model-update information.The PS allocates bandwidth so scheduled devices can each transmit the same number of bits.
  • BN2 Scheduling Policy: BN2 schedules K devices with the largest local-update l2-norms and allocates bandwidth proportional to update significance.Devices first communicate update norms, then transmit quantized updates in a second phase.
  • BC-BN2 Scheduling Policy: BC-BN2 first selects Kc devices by channel conditions, then schedules K of them using model-update significance.Kc ranges from K to M; Kc = K corresponds to BC, while Kc = M corresponds to BN2.
  • BN2-C Scheduling Policy: All policies compress updates to fit limited link capacity, and BN2-C adds device-side computation compared with BC.The work prioritizes efficient use of limited communication resources rather than device computational complexity.
  • BN2-C Scheduling Policy: BN2-C intertwines channel conditions and update significance by scheduling according to the estimated post-quantization l2-norm.Its quantization and bandwidth allocation account for each scheduled device’s link capacity.

V. CONVERGENCE ANALYSIS

The paper analyzes convergence for wireless FL with device scheduling when resource limitations and unreliable links prevent devices from transmitting complete local updates. The analysis shows that the expected loss gap approaches zero for sufficiently large T.

  • Convergence Analysis: The convergence analysis addresses wireless FL with scheduled devices that cannot transmit complete local model updates.The limitation arises from resource constraints and unreliable wireless links.
  • Convergence Analysis: The proof uses a quantization technique slightly different from the D-SGD scheme.The paper presents preliminaries and assumptions before stating the convergence result.
  • Convergence Analysis: For sufficiently large T, the gap between the expected loss function and the minimum loss function approaches zero.The convergence result is proved in the Appendix.

A. Preliminaries

The preliminaries define the optimization setting, compression model, and assumptions used for convergence analysis. Random sparsification and quantization produce updates whose transmission requirements depend on the available capacity.

  • Preliminaries: The PS aggregates sparsified local updates received from K devices to update the global model.Each transmitted update is a sparsified version of the device’s local model update.
  • Preliminaries: Each participating device is assumed to have the same link capacity, guaranteed by the resource allocation technique.This assumption simplifies the convergence analysis.
  • Preliminaries: Each device randomly retains q(t) update entries, sets the rest to zero, and quantizes the retained entries with 32-bit uniform quantization.The sparsity pattern is selected uniformly at random.
  • Preliminaries: The number of retained entries is chosen as the largest integer satisfying r(q(t)) ≤ nmCm(t), determining the transmission budget.The resulting message requires a bit count that includes 33 · q(t).
  • Preliminaries: The compression factor ρ(t) is i.i.d. once K and the quantization scheme are fixed, with a distribution depending on channel statistics.The expectation also accounts for sparsification randomness.
  • Preliminaries: The analysis assumes smooth and strongly convex device loss functions, bounded expected squared stochastic gradients, and a data-distribution bias parameter Γ.For i.i.d. data with enough samples, Γ approaches zero.

B. Convergence Result

The convergence result characterizes how scheduling, compression, local updates, and data bias affect convergence. More participation reduces scheduling error but increases compression effects through resource sharing, making the best K parameter-dependent.

  • Convergence Result: Uniformly random device scheduling is assumed, with each device selected for transmission with probability K divided by the total number of devices.The expectation covers stochastic gradients, quantization, and scheduling randomness.
  • Convergence Result: With decreasing learning rates, the expected loss converges to the optimum: lim T→∞ E[F(θ(T))] − F* = 0.This follows from the stated convergence theorem and smoothness-based corollary.
  • Convergence Result: Convergence speed increases with ρ(i), although finite-T performance also depends on μ, L, M, K, Γ, and G.The finite-horizon impact of ρ(i) cannot be isolated independently from these parameters.
  • Convergence Result: The scheduling component decreases with K, while ρ(i) decreases through resource sharing and the overall impact of K remains complicated.Different parameter settings can yield different best K values.
  • Convergence Result: When ρ(t) = 1 for every t, full participation K = M provides the best performance.This is also stated in Corollary 1.
  • Convergence Result: Increasing the number of local updates accelerates convergence but increases another error term, while larger τ intensifies deterioration from data-distribution bias.Thus, the τ value giving best performance is limited by competing effects.

VI. NUMERICAL EXPERIMENTS

The experiments compare update- and channel-aware scheduling under IID and non-IID data, showing that the best number of scheduled devices depends on data distribution and that joint scheduling improves accuracy.

  • IID data: For IID data, increasing K deteriorates convergence speed and final accuracy, with K = 1 providing the best performance for each policy.A single device can transmit a more accurate update when local data are symmetric across devices.
  • IID data: For K = 1 on IID data, final accuracies are 91.2%, 91.7%, 92.3% and 93.1% for BC, BN2, BC-BN2 and BN2-C, respectively.BN2-C provides the best convergence speed and final accuracy; BC-BN2's improvement over BN2 is marginal.
  • IID data: Scheduling by both update significance and channel conditions improves IID accuracy, while update significance has greater impact than channel conditions in this setting.The update significance is captured by the l2-norm of local model updates.
  • Non-IID data: For non-IID data, K = 1 causes accuracy fluctuations, whereas sharing resources among multiple devices reduces the inaccuracy caused by biased local datasets.A moderate K balances the information quality of each transmission against the number of devices contributing updates.
  • Non-IID data: For the non-IID setting, K = 10 is best for BC, BC-BN2 and BN2-C, while K = 5 performs better for BN2 but K = 10 is more stable and has higher final accuracy.The best final accuracies for BC, BN2, BC-BN2 and BN2-C are 78%, 77.5%, 81.5% and 81.7%, respectively.

VII. CONCLUSIONS

The paper studies federated learning over power- and bandwidth-limited wireless networks with device scheduling, and establishes a convergence result for this setting. Experiments show that scheduling should use both channel conditions and update significance, while the best number of devices depends on data heterogeneity.

  • VII. CONCLUSIONS: The study considers orthogonal digital transmissions over power- and bandwidth-limited wireless channels and schedules devices for participation in each learning round.The number of participating devices trades off broader data usage against less accurate per-device updates under limited resources.
  • VII. CONCLUSIONS: The proposed scheduling algorithms consider both device channel conditions and the significance of local model updates.This extends scheduling beyond policies based on a single metric.
  • VII. CONCLUSIONS: The paper establishes what it describes as the first convergence result for power- and bandwidth-limited wireless federated learning with device scheduling.The convergence analysis covers the setting in which participating devices transmit under channel-capacity constraints.
  • VII. CONCLUSIONS: The proposed policy outperforms policies using only channel conditions or only update significance in the reported MNIST experiments.The comparison is based on long-term performance in the experiments.
  • VII. CONCLUSIONS: For IID data, scheduling a single device performs best, whereas for non-IID data, scheduling a moderate number of devices performs best.The convergence result corroborates the observed dependence of the best participation level on data distribution.

APPENDIX A

Appendix A develops intermediate identities and bounds used in the convergence analysis of scheduled, quantized federated learning. The supplied passages emphasize expectation over scheduling randomness, auxiliary-variable expansion, symmetry, and standard inequalities.

  • APPENDIX A: The appendix introduces an auxiliary variable involving the difference between the scheduled model iterate, an auxiliary iterate, and the optimum.Its squared norm is expanded into two squared-norm terms and a cross term.
  • APPENDIX A: The analysis bounds the average of the terms arising from this auxiliary-variable expansion.The supplied text identifies this bounding step as part of the appendix proof sequence.
  • APPENDIX A: The appendix invokes convexity, Cauchy–Schwarz, and Assumption 3 to derive intermediate bounds and complete the lemmas.Several proof steps are deferred to Appendices B and C.
  • APPENDIX A: Expectation over device-scheduling randomness is used in the convergence lemmas.The appendix attributes intermediate equalities to scheduling randomness and the behavior of quantized model updates.
  • APPENDIX A: Symmetry is used to count how often individual indices and distinct index pairs appear in the proof.These counting steps support substitutions into later bounds.

APPENDIX C

Appendix C bounds terms in the convergence proof using strong convexity, Cauchy–Schwarz, Assumption 3, and an auxiliary lemma. The supplied passages culminate in the completion of Lemma 3 and Lemma 5.

  • APPENDIX C: The appendix combines bounds from equations (58), (60), and (61) through substitutions into later inequalities.These substitutions yield the stated intermediate convergence relations and complete Lemma 3.
  • APPENDIX C: The appendix bounds the last term on the right-hand side of a preceding convergence inequality.The bound is attributed in part to Lemma 1.
  • APPENDIX C: Strong convexity and Cauchy–Schwarz are used to control terms in the convergence inequality.Assumption 3 also supports one of the bounding steps.
  • APPENDIX C: Lemma 5 provides an upper bound for the second term on the right-hand side of the referenced inequality.The proof substitutes this result into the preceding relation to complete Lemma 5.
Loading 2001.10402v2…