PaperlayerView exact revision on arXiv

Source-linked AI summary

Scheduling Policies for Federated Learning in Wireless Networks

Howard H. Yang, Zuozhu Liu, Tony Q. S. Quek, H. Vincent Poor

arXiv:1908.06287v2cs.ITeess.SP

TL;DR

Wireless federated learning must train models with private UE data over resource-constrained, interference-prone, and unreliable links, while its performance under such conditions is not well understood. The paper develops an analytical convergence framework that accounts for scheduling and wireless effects, then compares RS, RR, and PF. PF is preferable at high SINR thresholds, RR at low thresholds, and fixed spectrum creates a trade-off between scheduled UEs and subchannel bandwidth.

  • Problem

    FL performance in wireless networks is not well understood because private UE data must be trained over limited, unreliable, and interference-prone communication links.

  • Method

    The paper develops an analytical framework for FL in wireless networks, including a wireless-aware algorithm, tractable convergence analysis, and comparisons of RS, RR, and PF scheduling.

  • Results

    PF outperforms RS and RR at high SINR thresholds, RR is preferable at low thresholds, and convergence decreases rapidly as the SINR threshold increases.

  • Takeaways & Limitations

    Under fixed spectrum, FL design must balance the number of scheduled UEs against subchannel bandwidth, while compression and quantization are important as SINR thresholds increase.

Abstract

from arXiv · show

Motivated by the increasing computational capacity of wireless user equipments (UEs), e.g., smart phones, tablets, or vehicles, as well as the increasing concerns about sharing private data, a new machine learning model has emerged, namely federated learning (FL), that allows a decoupling of data acquisition and computation at the central unit. Unlike centralized learning taking place in a data center, FL usually operates in a wireless edge network where the communication medium is resource-constrained and unreliable. Due to limited bandwidth, only a portion of UEs can be scheduled for updates at each iteration. Due to the shared nature of the wireless medium, transmissions are subjected to interference and are not guaranteed. The performance of FL system in such a setting is not well understood. In this paper, an analytical model is developed to characterize the performance of FL in wireless networks. Particularly, tractable expressions are derived for the convergence rate of FL in a wireless setting, accounting for effects from both scheduling schemes and inter-cell interference. Using the developed analysis, the effectiveness of three different scheduling policies, i.e., random scheduling (RS), round robin (RR), and proportional fair (PF), are compared in terms of FL convergence rate. It is shown that running FL with PF outperforms RS and RR if the network is operating under a high signal-to-interference-plus-noise ratio (SINR) threshold, while RR is more preferable when the SINR threshold is low. Moreover, the FL convergence rate decreases rapidly as the SINR threshold increases, thus confirming the importance of compression and quantization of the update parameters. The analysis also reveals a trade-off between the number of scheduled UEs and subchannel bandwidth under a fixed amount of available spectrum.

I. INTRODUCTION

The paper studies federated learning in wireless edge networks, where private UE data, limited communication resources, unreliable links, scheduling, and interference complicate training. It develops an analytical convergence framework and compares scheduling policies, revealing regime-dependent policy preferences and spectrum-allocation trade-offs.

  • Motivation: Federated learning keeps UE data private by decoupling data acquisition from global model training, but wireless communication remains resource-constrained and unreliable.UEs compute locally while the AP aggregates received updates and redistributes the global model.
  • Motivation: Only a portion of UEs can access each wireless update, making scheduling and successful transmission central to FL performance.The shared medium introduces communication costs, interference, and possible transmission failures.
  • Analytical framework: The proposed wireless FL algorithm decomposes the global model into local UE subproblems whose solutions form proximal steps toward the global optimum.UE learning rates can adjust to communication conditions, potentially accelerating convergence.
  • Analytical framework: The paper develops an analytical framework with tractable convergence expressions that incorporate scheduling policy, fading, path loss, and inter-cell interference.The network model represents AP and UE locations with independent Poisson point processes.
  • Scheduling results: At high SINR thresholds, PF outperforms RS and RR in convergence rate, whereas RR is preferable at low SINR thresholds.The analysis evaluates random scheduling, round robin, and proportional fair scheduling.
  • Scheduling results: FL convergence rate decreases rapidly as the SINR threshold increases, and fixed spectrum creates a trade-off between scheduled UEs and subchannel bandwidth.These findings support compression and quantization of update parameters and provide additional spectrum-allocation design options.

C. Scheduling Policies

Because communication is slower than local computation and radio resources are limited, the AP schedules only subsets of UEs for simultaneous updates using RS, RR, or PF.

  • Scheduling rationale: The AP schedules a subgroup of UEs simultaneously to limit communication-time overhead over resource-limited radio channels.The paper defines G = K/N as the ratio of associated UEs to available subchannels, assuming K is a multiple of N for simplicity.
  • Random Scheduling (RS): Random scheduling (RS) uniformly selects N associated UEs in each communication round and assigns each selected UE a dedicated subchannel.
  • Round Robin (RR): Round robin (RR) divides the UEs into G groups and consecutively assigns one group to access the radio channels in each communication round.
  • Proportional Fair (PF): Proportional fair (PF) selects N of K associated UEs in each round using their instantaneous and time-average SNRs.The selected UE indices maximize the policy specified by the paper's proportional-fair criterion.

III. DISTRIBUTED COMPUTING AND PARAMETER UPDATE

The paper decomposes the learning problem into UE-local subproblems through a dual formulation, then combines local improvements at the AP despite unreliable wireless updates.

  • Problem decomposition: Strong convexity of r and smoothness of the loss functions support the dual reformulation and subsequent distributed decomposition.The paper explicitly assumes r is ζ-strongly convex and each ℓ_i is 1/µ-smooth.
  • Problem decomposition: Fenchel-Rockafeller duality rewrites the original optimization problem so local dual variables can be optimized using each UE's private data.The dual formulation separates the global problem into distributed subproblems solvable through federated computing.
  • Local and global updates: Each UE optimizes a local increment, while the AP combines received improvements to direct the global dual objective toward its optimum.The method uses an approximated surrogate because highly accurate local solutions are unnecessary for practical machine learning and would increase communication cost.
  • Local and global updates: The local subproblem is quadratic apart from the regularizer and acts as a data-dependent block-separable proximal step when solved exactly.The paper identifies this proximal interpretation as a potential accelerator of learning.
  • Communication adaptation: Wireless update losses can misalign local and global parameters, so the proposed algorithm adapts local training to communication conditions.The decomposition requires consistency between local-variable changes and the global vector, but unreliable channels can cause lost updates.

B. Parameter Updates

A parameter update succeeds only when a UE is scheduled and its transmission exceeds the decoding threshold; the resulting success probability is central to convergence analysis.

  • Wireless reliability: The SINR is random because AP and UE locations and small-scale fading are stochastic in the wireless network model.The analysis evaluates a statistically representative AP using the stationarity of the Poisson point processes.
  • Wireless reliability: Successful decoding requires the received SINR to exceed the unified threshold θ, with equal update sizes motivating a common threshold across APs.
  • Update success: The parameter update success probability combines UE selection under the scheduling policy with successful decoding of the transmitted update.The selection indicator S^z_k,t records whether UE k is chosen, while decoding requires γ_k,t > θ.
  • Convergence analysis: The defined success-probability variable captures the key conditions for successful UE updates and plays a critical role in the convergence analysis.

C. Federated Learning in Wireless Networks

The wireless FL algorithm alternates local computation, scheduled uplink aggregation, and global redistribution, while adapting local progress to communication reliability.

  • Wireless federated learning procedure: Each UE solves a local subproblem using only its stored data, updates its local reference, and sends an update when selected.
  • Wireless federated learning procedure: The AP selects UEs, decodes their packets, aggregates received updates, and redistributes the new global parameter over an error-free downlink.
  • Wireless federated learning procedure: The procedure alternates communication and computation, so failed uplink retransmissions may not be beneficial before the next global broadcast.After receiving the broadcast, UEs refresh their references and begin new local subproblems.
  • Algorithm properties: When communication is unreliable, the local learning rate declines and local references change more conservatively as fewer updates reach the AP.
  • Algorithm properties: The algorithm uses local second-order information without transmitting gradients or Hessian matrices, employs proximal local subproblems, and adjusts step size to communication conditions.
  • Convergence property: The algorithm permits asynchronous local and global updates and is guaranteed to converge when they are aligned on average.

IV. CONVERGENCE ANALYSIS

The analysis connects wireless scheduling and unreliable communication to FL convergence through parameter-update success and local-computation quality. It establishes that successful updates improve the objective, while bounded local-solution error enables the convergence analysis.

  • Convergence analysis: The expected change in the dual objective can be evaluated over a typical communication round using i.i.d. updates and the law of large numbers.
  • Convergence analysis: A higher parameter update success probability provides greater potential to improve the objective function.
  • Convergence analysis: Local computing is modeled with an error level β ∈ (0, 1), representing the quality of each UE’s local solution.The analysis fixes β as a constant, although it may vary over time.

B. Analysis

The analysis derives a general convergence bound for wireless FL and identifies how scheduling affects its multiplicative constant. It then specializes the framework to random scheduling and characterizes update success and expected duality-gap behavior.

  • Analysis: The convergence rate is defined by the communication rounds required for the primal and dual problems to reach a target duality gap.Reaching the gap places the trained parameter near the optimal solution.
  • Analysis: Theorem 1 guarantees an ε duality gap after Tz communication rounds when Tz satisfies the derived bound.
  • Analysis: All scheduling policies have iteration complexity on the order of GD’s log(n/ε), while scheduling changes the multiplicative constant Uz.
  • Random scheduling: Random scheduling selects UEs uniformly without using computing-stage or channel-state information.
  • Random scheduling: Under random scheduling, the analysis characterizes a typical UE’s parameter-update success probability and the rounds needed to achieve a target expected duality gap.
  • Random scheduling: V(θ, α) measures average interference-plus-noise power relative to weighted received signal power and gauges decoding difficulty.Smaller θ amplifies the desired signal and increases successful decoding probability.

2) Round Robin Policy:

The scheduling analysis compares round robin and proportional fair policies across SINR regimes. Round robin provides sequential fairness and is preferable at low SINR, whereas proportional fair converges faster at high SINR.

  • Round Robin Policy:: Round robin guarantees short-term fairness by ensuring that each UE updates its parameter sequentially.
  • Round Robin Policy:: The round robin analysis gives a typical UE’s parameter-update success probability and the communication rounds required for a target expected duality gap.
  • Proportional Fair Policy:: Proportional fair uses channel-state information for UE selection to improve parameter-update probability.
  • Policy comparison: FL convergence degrades monotonically as the number of UEs per AP increases because competition for communication resources lowers each UE’s update probability.
  • Policy comparison: In the high-SINR regime, random scheduling and round robin have similar convergence performance, while proportional fair converges more rapidly.
  • Policy comparison: In the low-SINR regime, random scheduling and proportional fair have similar convergence performance, while round robin converges more rapidly.

C. Special Cases

The special-case analysis examines one-shot, multi-round, and all-at-once communication. It finds that collecting more concurrent updates can outperform highly reliable sequential transmission, while multi-round reliability gains may not offset added communication rounds.

  • One-shot communication: One-shot communication updates UEs sequentially, with each UE accessing the full spectrum once every K communication rounds.Its SINR threshold reduces approximately to θ/N.
  • One-shot communication: FL remains guaranteed to converge under one-shot communication even when each UE’s updates are widely separated in time.
  • One-shot communication: Packing more UEs into each communication round facilitates faster convergence and can make random scheduling outperform one-shot communication.
  • Multi-round communication: Multi-round communication lets the AP collect updates over C transmission rounds before performing global aggregation under random scheduling.
  • Multi-round communication: Enhanced communication reliability cannot compensate for the loss of time-domain degrees of freedom when additional rounds are required.Therefore, waiting for more updates before global aggregation is not desirable under that condition.
  • All-at-once communication: All-at-once communication improves channel-use efficiency for each UE but increases mutual interference.The analysis assumes G simultaneously transmitting UEs per subchannel.
  • Policy comparison: In the very low-SINR regime, round robin can perform worse than transmitting all UEs simultaneously without scheduling.

V. NUMERICAL RESULTS

The numerical study evaluates FL performance under different scheduling policies using the paper’s analytical framework and specified wireless-system parameters.

  • The evaluation uses AP density λ = 10−4m2, K = 100 associated UEs per cell, N = 10 orthogonal subchannels, and path loss exponent α = 3.8.

A. Numerical Study

The numerical and experimental studies compare scheduling policies across SINR regimes, subchannel allocations, and learning models. PF is favored at high SINR thresholds, whereas RR is preferable at low thresholds, with convergence also shaped by compression and spectrum allocation.

  • Scheduling policies: PF substantially reduces iteration time relative to RS and RR under high SINR, while RR outperforms both under low SINR.At high SINR, PF benefits from selecting UEs with better channel quality; at low SINR, scheduling fairness becomes the bottleneck.
  • SINR threshold: Required communication rounds increase as the SINR decoding threshold rises, making compression or quantization important for maintaining convergence performance.A 5 dB threshold reduction from 10 dB to 5 dB can improve convergence despite increasing the error level β from 0.05 to 0.3.
  • Resource allocation: Each scheduling policy has an optimal number of subchannels because serving more UEs competes with achieving higher transmission success probability.RS and RR favor scheduling fewer UEs to leave more spectrum per transmission, whereas PF can select UEs with better channel conditions.
  • Algorithm comparison: Algorithm 2 converges better than vanilla Algorithm 1 when training an SVM on MNIST.The improvement is attributed to Algorithm 2’s more advanced treatment of local subproblems than SGD alone.
  • Experimental validation: At θ = 20 dB, PF-trained SVMs reach a steady stage in 60 training steps versus around 100 for RR, while CNN accuracy averages 0.94 with PF versus 0.5 with RR.RS performs worse than RR and PF in the high-SINR SVM experiment; the CNN analysis does not directly apply because its objective is non-convex.
  • Experimental validation: Under θ = −25 dB, simple models show almost identical performance across PF, RR, and RS because successful aggregation is highly likely.The scheduling-policy gap becomes more relevant when the model is more intricate.

APPENDIX

The appendix derives the convergence result by combining convexity and smoothness properties with expected objective-function progress over communication rounds.

  • Proof strategy: The proof uses strong convexity of conjugate loss functions and smoothness of the conjugate regularizer to bound update behavior.It also treats global and local terms of the expected objective separately.
  • Objective bound: The expected increment in the objective function is bounded using the paper’s assumptions and strong convexity properties.The derivation introduces subgradients and auxiliary scalar and vector quantities before applying the resulting inequality.
  • Convergence guarantee: The convergence result follows by upper-bounding the derived right-hand side by ε and using E[D(v0) −D(v∗)] < n.

C. Proof of Corollary 1

The proof of Corollary 1 derives parameter-update success probabilities by combining scheduling selection probabilities with SINR decoding probabilities under a stochastic-geometry model.

  • Success probability: A UE’s update succeeds when its received SINR exceeds the decoding threshold θ, and the probability is first conditioned on its distance from the AP.
  • Random geometry: The distance-conditioned result is averaged over the UE-distance distribution, whose probability density follows a Rayleigh distribution.
  • Round robin: Under RR, each UE is selected once per G communication rounds, and the convergence bound follows by applying the corresponding update probability.
  • Proportional fair: Under PF, stationarity makes average SNRs identical, so the policy selects the N UEs with the highest channel gains.The selected-UE gain distribution is then used to compute transmission success probability.
  • Modeling assumption: The interference analysis approximates actual uplink UE locations with a non-homogeneous PPP because an exact characterization is unavailable for the Poisson-Voronoi perturbed lattice.The paper states that this approximation is very tight.
Loading 1908.06287v2…