PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Device Scheduling and Resource Allocation for Latency Constrained Wireless Federated Learning

Wenqi Shi, Sheng Zhou, Zhisheng Niu, Miao Jiang, Lu Geng

arXiv:2007.07174v1cs.ITcs.LGcs.NIeess.SP

TL;DR

Latency-constrained wireless federated learning must choose participating devices under limited computation and communication resources. The paper derives a convergence bound and jointly optimizes bandwidth allocation with greedy device scheduling, achieving near-optimal and state-of-the-art performance across heterogeneous data settings.

  • Problem

    Wireless FL needs to maximize accuracy within a total training-time budget because limited resources make device scheduling crucial to convergence.

  • Method

    The paper derives a convergence bound involving training rounds and scheduled devices, then decouples accuracy maximization into bandwidth allocation and device scheduling.

  • Results

    The proposed policy achieves near-optimal performance, adapts to non-i.i.d. local datasets, and outperforms several state-of-the-art scheduling policies in highest achievable accuracy within the time budget.

  • Takeaways & Limitations

    The scheduling policy adapts the number of participating devices to data heterogeneity and optimizes convergence with respect to elapsed training time.

Abstract

from arXiv · show

In federated learning (FL), devices contribute to the global training by uploading their local model updates via wireless channels. Due to limited computation and communication resources, device scheduling is crucial to the convergence rate of FL. In this paper, we propose a joint device scheduling and resource allocation policy to maximize the model accuracy within a given total training time budget for latency constrained wireless FL. A lower bound on the reciprocal of the training performance loss, in terms of the number of training rounds and the number of scheduled devices per round, is derived. Based on the bound, the accuracy maximization problem is solved by decoupling it into two sub-problems. First, given the scheduled devices, the optimal bandwidth allocation suggests allocating more bandwidth to the devices with worse channel conditions or weaker computation capabilities. Then, a greedy device scheduling algorithm is introduced, which in each step selects the device consuming the least updating time obtained by the optimal bandwidth allocation, until the lower bound begins to increase, meaning that scheduling more devices will degrade the model accuracy. Experiments show that the proposed policy outperforms state-of-the-art scheduling policies under extensive settings of data distributions and cell radius.

I. INTRODUCTION

Wireless federated learning must balance per-round latency against the number of rounds needed for convergence under scarce spectrum and device heterogeneity. This paper formulates that time-aware scheduling problem, derives a convergence bound, and uses it to jointly optimize bandwidth allocation and device scheduling.

  • Motivation: Scarce spectrum and stringent latency budgets limit how many devices can upload local models in each FL round.This makes device scheduling important to FL convergence.
  • Motivation: Straggler devices with weak computation capabilities or poor channel conditions delay global aggregation, while scheduling more devices reduces each device’s bandwidth.The resulting trade-off increases per-round latency and the probability of stragglers.
  • Motivation: Scheduling more devices can increase convergence rate with respect to rounds and reduce the rounds needed to reach a given accuracy.Thus, total training time depends on both the number of rounds and average per-round latency.
  • Related work: Prior scheduling approaches use heuristics, experimental deadlines, or round-based convergence analyses that do not directly guarantee performance under latency constraints.The paper identifies convergence with respect to time as an unresolved objective for latency-constrained wireless FL.
  • Contributions: The paper optimizes model accuracy within a training-time budget by deriving a convergence bound in terms of rounds and scheduled devices.The bound quantifies the trade-off between per-round latency and the rounds required to attain fixed accuracy.
  • Contributions: The joint problem is decoupled into bandwidth allocation and device scheduling, with a scheduling policy designed from the resulting convergence bound.The paper also reports adaptation to non-i.i.d. local datasets and higher achievable accuracy than several state-of-the-art policies within the time budget.

II. SYSTEM MODEL

The system model describes wireless federated learning with a base station, multiple end devices, local datasets, and a global loss-minimization objective.

  • The FL system contains one base station and M end devices, each with a local dataset of labeled input-output samples.
  • The training objective is to find model parameter w minimizing a loss function over the whole dataset.
  • Each local loss function averages the sample-level loss over the device's local dataset.
  • Examples of loss functions used in popular machine-learning models are summarized in Table II.

A. Federated Learning over Wireless Networks

Wireless FL proceeds through scheduled local updates, synchronous aggregation, and uplink transmission whose latency depends on computation, channels, and bandwidth. The formulation seeks to optimize accuracy within a training-time budget by jointly choosing rounds, devices, and bandwidth.

  • Each round begins with the base station selecting scheduled devices and broadcasting the current global model.
  • Scheduled devices perform τ local gradient updates using SGD on mini-batches, then upload their updated models for weighted aggregation.
  • Synchronous aggregation makes round latency depend on the slowest scheduled device.
  • FDMA allocates each device a bandwidth fraction γi,k, with transmission rates determined by transmit power, channel gain, and noise density.
  • The optimization minimizes the global loss of the best model reached within a total training-time budget T.
  • Exact analysis is difficult because scheduling can be non-stationary and the final global model depends on past scheduling decisions.

III. JOINT DEVICE SCHEDULING AND BANDWIDTH ALLOCATION

The joint optimization is decoupled into bandwidth allocation and device scheduling. Bandwidth is solved analytically for a fixed scheduled set, while the objective value is obtained numerically through binary search.

  • A. Bandwidth Allocation: Given a scheduled device set, the bandwidth-allocation subproblem is formulated for each round.
  • A. Bandwidth Allocation: Algorithm 1 binary-searches the objective value by comparing the required bandwidth sum with the available bandwidth until precision ε is satisfied.
  • A. Bandwidth Allocation: Theorem 1 gives the optimal bandwidth allocation for the fixed scheduled-device set.
  • A. Bandwidth Allocation: The allocation expression uses the Lambert-W function and the optimal round-updating time.
  • A. Bandwidth Allocation: Because the Lambert-W-based condition cannot be solved analytically for the optimal time, the paper computes it numerically.

B. Convergence Analysis

The convergence analysis bounds training performance under stationary random scheduling and exposes a trade-off: more devices improve round-wise convergence but increase latency and reduce the number of rounds available within a fixed time budget.

  • The analysis assumes convex, ρ-Lipschitz, and β-smooth local loss functions, alongside a bounded local-global gradient difference.
  • The stated convergence assumptions may not fully hold for neural networks, although experiments report that the proposed policy works well for them.
  • A stationary random scheduling policy selects a uniformly random subset of fixed size |Π| from the M devices in every round.
  • Theorem 2 establishes a convergence-related bound for any round and stationary random scheduling policy with |Π| ≥1.
  • Scheduling fewer devices produces a larger upper bound and slows convergence with respect to the number of rounds.
  • Scheduling more devices increases per-round latency, reducing the number of possible rounds within training time T, while decreasing B(Π).
  • The scheduling policy must balance latency per round against required rounds to minimize the loss of the optimal global model.

C. Device Scheduling Algorithm

The paper solves device scheduling myopically using a convergence-performance bound, then applies a greedy algorithm that adds devices while the objective improves. The resulting complexity is substantially lower than brute-force search.

  • Problem formulation: Unknown future computation latencies and channel states make the original scheduling constraint intractable, motivating a myopic formulation.The policy approximately treats the current scheduling policy as applying throughout training.
  • Problem formulation: The accuracy objective is approximated by maximizing a lower bound, equivalently minimizing its denominator in each round.This converts the convergence analysis into the myopic optimization problem P4.
  • Greedy scheduling: P4 remains combinatorial because the scheduled-device set is constrained, so the paper introduces a greedy scheduling algorithm.The algorithm evaluates candidate devices using round latencies obtained from the bandwidth-allocation procedure.
  • Greedy scheduling: The algorithm repeatedly selects the unscheduled device with minimum latency and stops when adding a device increases the objective or all devices are scheduled.Each accepted device updates the scheduled set and objective value.
  • Complexity: The greedy algorithm has complexity O(|M|^3), compared with O(2^|M|) for naive brute-force search.The cubic complexity arises from calling the bandwidth-allocation algorithm O(|M|^2) times.
  • Parameter selection: The parameter ϕ is fixed during training; experiments report good performance across system settings and indicate that searching for an appropriate value is not difficult.Performance is reported as insensitive over 0.02 ≤ ϕ ≤ 0.5.

D. The Whole Policy

The complete policy updates scheduling, bandwidth allocation, local models, and convergence estimates in each round while enforcing the total training-time budget. It uses stored estimates for devices not scheduled in the previous round.

  • Round procedure: The complete wireless FL procedure calls the greedy scheduler and bandwidth-allocation algorithm each round, then stops when accumulated latency exceeds T.The policy thereby minimizes the global loss within the training-time budget.
  • Round procedure: Scheduled devices receive the global model, perform τ local updates in parallel, upload their models, and contribute to global aggregation.The base station also receives scalar estimates and updates the global model and estimation records.
  • Online estimation: The base station maintains estimates of convergence parameters for all devices and uses the latest past estimate when a device was not scheduled in the previous round.This approximation supplies the inputs required by the greedy scheduler.
  • Online estimation: Devices can send pilot signals and computation-progress information, and perfect knowledge of computation latency and channel state is assumed unless otherwise specified.These signals support real-time scheduling with low communication overhead.
  • Overhead: The additional base-station complexity is O(|M|^3) per round, while each device incurs O(1) computation for estimating ρ_i and β_i.Each scheduled device sends three extra scalars, which are negligible relative to the high-dimensional model update.

IV. EXPERIMENT RESULTS

Experiments evaluate FC across MNIST and CIFAR-10 under i.i.d. and non-i.i.d. data, varying cell conditions and parameter ϕ. FC achieves strong accuracy and is robust to estimation errors.

  • Parameter study: Larger ϕ leads FC to schedule more devices because minimizing the device-dependent term becomes more important relative to B(Π).The number of scheduled devices increases with ϕ in the reported experiments.
  • Parameter study: With ϕ = 0.05, FC achieves 92.3%, 90.6%, and 89.0% highest achievable accuracy for i.i.d., l = 2, and l = 1 MNIST data, respectively.The same parameter also achieves good CIFAR-10 performance.
  • Parameter study: FC performance is not sensitive to ϕ when 0.02 ≤ ϕ ≤ 0.5, allowing larger search steps for selecting the parameter.The experiments therefore use ϕ = 0.05 in subsequent evaluations.
  • Robustness: For R = 600 m and l = 1, estimation errors leave the average scheduled-device count nearly unchanged, while performance loss is mostly caused by increased round latency.The proposed policy is reported as robust to these estimation errors.
  • Instantaneous behavior: FC schedules more devices as non-i.i.d. severity increases, reflecting larger estimated ρ, β, and δ values.The paper attributes these increases to greater differences among local updated models.

C. Comparison of Different Scheduling Policies

FC is compared with random, proportional-fair, client-selection, asymptotic, and fixed-count policies across data distributions and cell radii. It performs near the accuracy-optimal scheduling point by balancing round latency against convergence speed.

  • Trade-off: Scheduling too few or too many devices degrades accuracy because the number of rounds and latency per round trade off against each other.More devices can reduce required rounds but increase per-round latency; fewer devices have the opposite effect.
  • Trade-off: FC performs close to the optimal accuracy points across data distributions because it balances per-round latency with the number of rounds.Its optimized scheduled-device count yields one corresponding point for each dataset in Fig. 4.
  • Adaptation: A fixed scheduling policy cannot adapt to different data distributions because the optimal scheduled-device count varies with the non-i.i.d. level.The experiments report that this count increases as non-i.i.d. severity increases.
  • Convergence performance: For R = 600 m and l = 1, FC reaches 80% test accuracy in 17.35 seconds, whereas PF requires 54.71 seconds.Under T = 60 seconds, FC reaches 89.0%, exceeding RD, PF, CL-l, and AS-l by 9.0%, 6.4%, 9.2%, and 8.1%, respectively.
  • Convergence performance: For R = 200 m with i.i.d. data, FC attains 92.6% test accuracy, exceeding RD, PF, CL-h, and AS-h by over 2.1%, 2.0%, 2.4%, and 2.5%, respectively.This demonstrates the reported advantage under a different cell radius and data setting.
  • Convergence performance: FC schedules 6.26 devices in 0.62 seconds per round, while PF schedules 3 devices in 0.94 seconds per round for R = 600 m and l = 1.The comparison illustrates FC’s lower per-round latency alongside a larger scheduled set.
  • Cross-setting comparison: FC achieves the highest accuracy under most tested settings, while CS and AS can degrade notably outside settings suited to their fixed thresholds.The paper concludes that those fixed-threshold policies are not flexible or robust across system conditions.

V. CONCLUSION

The paper develops a joint bandwidth allocation and device scheduling policy for latency-constrained wireless FL. Its convergence analysis and experiments support balancing per-round latency against required rounds under a training-time budget.

  • The paper formulates joint bandwidth allocation and device scheduling to optimize FL convergence rate with respect to time.
  • A convergence bound characterizes how device scheduling affects wireless FL performance.
  • The FC policy balances per-round latency and the number of required rounds to minimize global loss within a training-time budget.
  • The optimal number of scheduled devices increases with the non-i.i.d. level of local datasets.
  • FC can schedule a near-optimal number of devices according to learned loss, gradient, and system characteristics.
  • Experiments report that FC outperforms state-of-the-art baseline scheduling policies across different data distributions and cell radii.

APPENDIX A

The appendix analyzes optimal bandwidth allocation for scheduled devices. It argues that reallocating bandwidth from earlier-finishing devices to slower ones reduces round latency until devices finish together.

  • Bandwidth reallocation from earlier-finishing devices to slower devices can reduce round latency determined by the slowest device.
  • The reallocation process reaches an optimum when all scheduled devices finish local updating at the same time.
  • The appendix states that the optimal solution allocates bandwidth so all scheduled devices have the same finishing time.
  • The appendix derives a theorem from the direct solution of the bandwidth-allocation problem.
  • The analysis assumes convexity, Lipschitz continuity, and smoothness of the global objective under its stated assumptions.

APPENDIX C

The appendix develops bounds for wireless FL performance under stationary random scheduling. It combines assumptions, lemmas, and expectation-based arguments to establish the stated theorem.

  • Lemma 2 supplies conditions used to prove Theorem 3, including separate treatment of cases where ρh(τ) + B(Π) equals or exceeds zero.
  • The analysis combines multiple intermediate inequalities to obtain Theorem 2 for wireless FL.
  • The appendix defines the scheduling-policy randomness through expectations over a stationary random policy.
  • The proof introduces the global-loss gap θk = F(vk) − F(w∗) and bounds it through successive theorem and lemma substitutions.
  • The proof concludes by ruling out simultaneous satisfaction of two conditions and deriving the theorem from the resulting alternatives.
Loading 2007.07174v1…