Source-linked AI summary
Device Scheduling with Fast Convergence for Wireless Federated Learning
Wenqi Shi, Sheng Zhou, Zhisheng Niu
TL;DR
The paper addresses the underexplored problem of FL convergence under a total training-time budget rather than rounds. It formulates and decouples joint bandwidth allocation and device scheduling, then proposes a trade-off-based greedy policy. Under a 450-second budget, the proposed policy achieves 89.85% accuracy and outperforms the listed baselines.
Problem
Existing scheduling work focuses mainly on convergence with respect to rounds, leaving convergence under a total training-time budget underexplored.
Method
The paper decouples joint bandwidth allocation and scheduling, allocating bandwidth and greedily adding the device with the least model-update and upload time until the objective increases.
Results
89.85% accuracy is achieved under a 450-second budget, 14.8%, 7.47%, 2.35%, and 3.28% higher than Random-opt, CL-low, CL-high, and PF, respectively.
Takeaways & Limitations
The proposed scheduling policy achieves the highest reported model accuracy under fixed training-time budgets and remains higher than baselines across different cell radii.
Abstract
from arXiv · showhide
Owing to the increasing need for massive data analysis and model training at the network edge, as well as the rising concerns about the data privacy, a new distributed training framework called federated learning (FL) has emerged. In each iteration of FL (called round), the edge devices update local models based on their own data and contribute to the global training by uploading the model updates via wireless channels. Due to the limited spectrum resources, only a portion of the devices can be scheduled in each round. While most of the existing work on scheduling focuses on the convergence of FL w.r.t. rounds, the convergence performance under a total training time budget is not yet explored. In this paper, a joint bandwidth allocation and scheduling problem is formulated to capture the long-term convergence performance of FL, and is solved by being decoupled into two sub-problems. For the bandwidth allocation sub-problem, the derived optimal solution suggests to allocate more bandwidth to the devices with worse channel conditions or weaker computation capabilities. For the device scheduling sub-problem, by revealing the trade-off between the number of rounds required to attain a certain model accuracy and the latency per round, a greedy policy is inspired, that continuously selects the device that consumes the least time in model updating until achieving a good trade-off between the learning efficiency and latency per round. The experiments show that the proposed policy outperforms other state-of-the-art scheduling policies, with the best achievable model accuracy under training time budgets.
I. INTRODUCTION
Wireless FL addresses centralized training’s transmission-cost and privacy problems, but limited wireless resources make device scheduling central to convergence. This paper therefore optimizes convergence over training time rather than rounds.
- Centralized training is impractical because uploading raw edge data incurs high wireless transmission costs and creates privacy concerns.
- FL keeps model updates distributed across devices while coordinating local updates and global aggregation through a base station.
- Limited wireless resources allow only a portion of devices to upload local models in each round, making scheduling critical to convergence.
- Scheduling more devices can reduce bandwidth per device and increase the likelihood that stragglers delay synchronous aggregation.
- Prior scheduling research largely evaluates convergence with respect to rounds, while the time budget is experimentally chosen and difficult to adjust dynamically.
- The paper formulates joint bandwidth allocation and scheduling to minimize time to a target accuracy, then decouples the problem into two sub-problems.
A. Federated Learning over Wireless Network
Wireless FL repeatedly broadcasts a global model, performs local device updates, and aggregates uploaded models. More participating devices can improve round-based convergence, but non-i.i.d. data makes that relationship nonlinear and configuration-dependent.
- Each FL round broadcasts the current global model to scheduled devices, which update locally using gradient descent before uploading their models.
- The base station averages received local models to produce the next global model.
- For i.i.d. local data, increasing participating devices can linearly speed convergence.
- With non-i.i.d. data, the relationship between participating-device count and convergence rate becomes nonlinear.
- The required-round model uses experimentally determined parameters θ and β to approximate convergence across i.i.d. and non-i.i.d. distributions.
B. Latency Model
The latency model treats local computation as random and represents computation capability through shifted-exponential parameters. Base-station aggregation latency is neglected because the base station is comparatively more capable and aggregation is low-complexity.
- Local model-update computation latency is modeled with a shifted exponential distribution.
- Parameters a_i and μ_i represent computation-latency fluctuation and maximum computation capability, respectively.
- The model ignores base-station aggregation latency because the base station has stronger computation capability and aggregation has low complexity.
2) Communication Latency:
Communication latency depends on OFDMA bandwidth allocation and device channel conditions, while synchronous rounds are paced by the slowest scheduled device. The optimization minimizes required rounds multiplied by per-round latency.
- 2) Communication Latency:: The OFDMA system divides total bandwidth B among scheduled devices using allocation ratios γ_i subject to a total-bandwidth constraint.
- 2) Communication Latency:: Each device’s transmission rate depends on allocated bandwidth, transmit-power density, channel gain, and noise power.
- 2) Communication Latency:: Broadcast latency is ignored because the base station uses the whole downlink bandwidth and has much higher transmit power.
- 3) Total Latency per Round:: Synchronous aggregation makes per-round latency equal to the completion time of the slowest scheduled device.
- The joint objective minimizes the number of rounds needed for target accuracy multiplied by latency per round.
- The optimization is difficult because of its scheduling constraint and maximum term, so the paper decouples it into two sub-problems.
A. Bandwidth Allocation
The bandwidth allocation sub-problem minimizes current-round latency for a given scheduled-device set. Its optimum equalizes completion times across devices and is computed efficiently with binary search.
- The BS optimizes bandwidth allocation for a fixed scheduled-device set to minimize current-round latency.
- The optimal allocation makes all scheduled devices finish model updating at the same time.If one device finishes earlier, reallocating its bandwidth can shorten round latency.
- The closed-form optimum requires solving a |Π|-order equation, which is impractical when |Π| ≥ 5.
- Algorithm 1 uses binary search to obtain the optimal objective value by testing bandwidth feasibility within a shrinking interval.Each iteration computes the bandwidth required for a target latency and halves the search region according to the bandwidth constraint.
B. Latency-Learning Efficiency Trade-off
The analysis characterizes how scheduled-device count affects round latency and the number of rounds needed for learning. It identifies a trade-off between faster per-round learning and higher latency per round.
- Proposition 1 bounds expected total updating latency per round for randomly sampled homogeneous devices.The assumptions include common local data-set size, transmit power, and channel gain.
- When many devices are scheduled, communication latency dominates and round latency grows almost linearly with |Π|.The resulting lower bound can approximate the round latency in this regime.
- Scheduling more devices can reach a target accuracy in fewer rounds, whereas scheduling fewer devices reduces latency per round.
C. Device Scheduling
The scheduling problem remains combinatorial after bandwidth optimization, so the paper proposes a greedy policy based on the latency-learning trade-off.
- Given optimal bandwidth allocation, device scheduling is still a hard combinatorial optimization problem.
- Algorithm 2 repeatedly adds the device with the shortest model-updating and uploading time.Selection stops when the objective function begins to increase.
- The greedy algorithm has complexity O(|M|^3), compared with O(2^|M|) for naive brute-force search.Its complexity follows from calling Algorithm 1 O(|M|^2) times.
IV. EXPERIMENT RESULTS
The experiments evaluate federated-learning training performance under different scheduling policies.
- The evaluation compares FL training performance under different scheduling policies.
A. Environment and FL Setups
Experiments use a wireless FL setup with specified channel and device assumptions, MNIST data, and comparisons across scheduling counts and data heterogeneity.
- The default environment has 20 uniformly distributed devices in a 1-km cell, with a central base station, 3 MHz bandwidth, and path-loss exponent 3.76.Devices are re-distributed at the beginning of each round to reflect mobility.
- Fig. 2 compares test accuracy across K = 4, 8, 12 scheduled devices and L = 1, 5, or i.i.d. local data.Results are averaged over 5 independent trials.
- The FL task classifies handwritten digits using MNIST, whose training samples are evenly partitioned among devices.The supplied setup describes both i.i.d. and non-i.i.d. partitioning schemes.
B. Effect of the Number of Scheduled Devices
Scheduling more devices improves accuracy per round most strongly for highly non-i.i.d. data, while the benefit decreases as data become more homogeneous.
- 68.2% accuracy is achieved with K = 4 within 60 rounds for highly non-i.i.d. data (L = 1), compared with 90.4% for L = 5 and 97.4% for i.i.d. data.These values illustrate the effect of local-data heterogeneity at the same scheduling count and round budget.
- Table I reports regression results for β and θ used to approximate the number of rounds needed to attain a given accuracy.
- Scheduling different numbers of devices has very little effect on accuracy for i.i.d. data sets.The reported benefit of additional devices decreases as the non-i.i.d. level decreases.
C. Comparison of Different Scheduling Policies
The proposed scheduling policy is evaluated against Random-opt, CL-low, CL-high, and PF using wallclock-time convergence, round convergence, latency, device count, and time-budget accuracy.
- The baselines include Random-opt, CL-low and CL-high with thresholds of 8 and 25 seconds, and proportional fair scheduling with K = Kopt.The proposed policy is compared with three baseline policy families.
- 80% test accuracy is reached after 171 seconds by the proposed policy, whereas CL-high requires 224 seconds for similar accuracy.
- 89.85% is the highest achievable accuracy within 450 seconds for the proposed policy, exceeding Random-opt, CL-low, CL-high, and PF by 14.8%, 7.47%, 2.35%, and 3.28%, respectively.
- The proposed policy averages 8.31 scheduled devices per round within 12.07 seconds, balancing learning efficiency against per-round latency.CL-low reduces average latency to 7.65 seconds but reaches only 75% accuracy within 30 rounds.
- Within 300 seconds, the proposed policy adapts to different cell radii and achieves higher accuracy than all other baseline policies.Its advantage over baselines diminishes as cell radius decreases because communication latency falls and policies schedule more devices.