PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence Time Optimization for Federated Learning over Wireless Networks

Mingzhe Chen, H. Vincent Poor, Walid Saad, Shuguang Cui

arXiv:2001.07845v2cs.LGcs.ITcs.NIstat.ML

TL;DR

The paper addresses how to reduce federated learning convergence time over wireless networks when limited resource blocks restrict model transmission. It jointly optimizes learning and wireless decisions using probabilistic user selection, RB allocation, and ANN-based local-model estimation, reporting up to 56% lower convergence time and 3% higher identification accuracy than standard FL.

  • Problem

    Limited wireless resource blocks restrict which users can transmit local models, motivating joint optimization of FL convergence time and training loss.

  • Method

    The framework combines probabilistic user selection, uplink RB allocation, and ANNs that estimate local models for users unable to transmit.

  • Results

    The proposed approach reduces convergence time by up to 56% and improves FL identification accuracy by up to 3% compared with standard FL.

  • Takeaways & Limitations

    Including influential users probabilistically and estimating unavailable local models enables the base station to use more local information in global FL updates.

Abstract

from arXiv · show

In this paper, the convergence time of federated learning (FL), when deployed over a realistic wireless network, is studied. In particular, a wireless network is considered in which wireless users transmit their local FL models (trained using their locally collected data) to a base station (BS). The BS, acting as a central controller, generates a global FL model using the received local FL models and broadcasts it back to all users. Due to the limited number of resource blocks (RBs) in a wireless network, only a subset of users can be selected to transmit their local FL model parameters to the BS at each learning step. Moreover, since each user has unique training data samples, the BS prefers to include all local user FL models to generate a converged global FL model. Hence, the FL performance and convergence time will be significantly affected by the user selection scheme. Therefore, it is necessary to design an appropriate user selection scheme that enables users of higher importance to be selected more frequently. This joint learning, wireless resource allocation, and user selection problem is formulated as an optimization problem whose goal is to minimize the FL convergence time while optimizing the FL performance. To solve this problem, a probabilistic user selection scheme is proposed such that the BS is connected to the users whose local FL models have significant effects on its global FL model with high probabilities. Given the user selection policy, the uplink RB allocation can be determined. To further reduce the FL convergence time, artificial neural networks (ANNs) are used to estimate the local FL models of the users that are not allocated any RBs for local FL model transmission at each given learning step, which enables the BS to enhance its global FL model and improve the FL convergence speed and performance.

I. INTRODUCTION

The paper formulates wireless federated learning as a joint optimization of convergence time and training loss. It proposes probabilistic user selection, resource allocation, and ANN-based local-model prediction to improve convergence and accuracy.

  • Problem formulation: Limited resource blocks require the base station to select users and allocate resources for local-model transmission at each learning step.The optimization targets both the number of iterations and the duration of each iteration while optimizing accuracy.
  • Proposed framework: The proposed probabilistic selection scheme gives higher connection probabilities to users whose local models strongly affect the global model.This increases the global model’s information from underrepresented local datasets.
  • Proposed framework: ANNs estimate local model parameters for users unable to transmit because of limited resource blocks, allowing more local information into global aggregation.The paper states that this can decrease training loss and improve convergence speed.
  • Analysis and evaluation: The analysis identifies FL training method, RB allocation, user selection, and local-model prediction accuracy as factors affecting convergence speed and training loss.The framework is evaluated through simulation across multiple performance metrics.
  • Results: 56% lower convergence time and 3% higher identification accuracy are reported versus a standard federated learning algorithm.These are simulation results for the proposed approach compared with the standard FL baseline.
  • Motivation: Federated learning lets users train on local data and share model parameters rather than raw data with the base station.The base station aggregates received local models into a global model and broadcasts it back to users.

A. Training Procedure of Federated Learning

The training procedure alternates local model training and wireless communication with global aggregation. User association and RB allocation determine which models are transmitted and the resulting communication delay.

  • Model updates: Each local model is a vector wi,µ, while the association vector aµ indicates which users connect to the base station at iteration µ.Because resource blocks are limited, the association vector can change between iterations.
  • Model updates: Users update local models using gradient descent, and the base station and users jointly update their models toward the optimal global model.The learning rate and loss gradient determine the local update.
  • Wireless transmission: OFDMA assigns RBs to transmitting users, with each user occupying at most one RB.The uplink rate depends on RB allocation, transmit power, channel gain, noise, and inter-cell interference.
  • Wireless transmission: The transmission delay accounts for local and global model communication, while the iteration time is governed by the selected users’ communication requirements.An unselected user does not transmit a local model and therefore does not contribute transmission delay in that iteration.
  • Wireless transmission: The uplink delay is effectively determined by the worst-case transmission delay among selected users.This couples user association and RB allocation to the duration of each learning iteration.

C. Problem Formulation

The problem formulation jointly considers user selection and RB allocation to reduce FL convergence time while optimizing training loss. The proposed association scheme prioritizes users whose local models have greater effects on the global model and ensures every user can contribute prediction data.

  • C. Problem Formulation: The optimization jointly targets FL convergence time and training loss by controlling user selection and RB allocation.The convergence objective includes both the number of iterations and the duration of each iteration while optimizing accuracy.
  • C. Problem Formulation: The formulation uses a user selection matrix, an RB allocation matrix, and a convergence indicator over a sufficiently large iteration horizon T.The indicator records whether FL has converged, while T bounds the iterations considered.
  • C. Problem Formulation: Iteration duration depends on RB allocation and user selection, while the required iteration count also depends on user selection.These coupled quantities make the optimization challenging because the BS lacks all users’ training data.
  • C. Problem Formulation: The solution first determines user association, then derives the optimal RB allocation for the selected users.ANN-based local-model estimation is added to improve convergence beyond transmitted models.
  • A. Gradient Based User Association Scheme: A user i* is selected to connect throughout training so its local model can serve as ANN input for predicting other users’ models.The always-connected user is determined during the first iteration, under an ordering by distance to the BS.
  • A. Gradient Based User Association Scheme: Increasing the candidate-user parameter γR can increase one-iteration transmission delay but decrease the number of iterations required for convergence.This exposes a direct per-iteration versus iteration-count trade-off.
  • A. Gradient Based User Association Scheme: The association probability pi,µ increases with the norm of user i’s gradient-change vector ei,µ.Users whose local models have larger effects on the global model therefore receive higher association probabilities.
  • A. Gradient Based User Association Scheme: The BS needs only each user’s scalar gradient-change norm to calculate association probabilities, not the users’ exact training data.The always-connected user supplies information used to predict other local models.

B. Optimal RB Allocation Scheme

Given user association, the RB allocation problem is transformed into an integer linear program that minimizes transmission delay subject to binary allocation constraints.

  • B. Optimal RB Allocation Scheme: After user association is fixed, the RB allocation problem is formulated for the current iteration.The allocation determines how selected users transmit their local models.
  • B. Optimal RB Allocation Scheme: The formulation assumes a variable m that bounds each user’s association variable, enabling a simplified optimization problem.The resulting problem retains the stated constraints from the original formulation.
  • B. Optimal RB Allocation Scheme: The nonlinear allocation constraint is linearized by representing li,n,µ as the delay for user i to transmit its local model over RB n.This transformation produces a linear formulation of the allocation problem.
  • B. Optimal RB Allocation Scheme: The resulting Problem (14) is an integer linear program solvable with known optimization algorithms such as interior-point methods.It is equivalent to Problem (13).

C. Prediction of the Local FL Models

The prediction component uses an FNN/MLP to estimate local models of users without RBs, allowing the BS to incorporate additional models into global aggregation when predictions are accurate.

  • C. Prediction of the Local FL Models: The ANN component predicts local FL models for users not allocated RBs, complementing association and RB optimization.The paper uses a fully connected MLP because prediction is treated as a regression task.
  • C. Prediction of the Local FL Models: The FNN contains an input, a single hidden layer, and an output component.The hidden layer learns nonlinear relationships between the reference model and the output difference.
  • C. Prediction of the Local FL Models: The FNN input is the always-connected user i*’s local model, which supplies information for predicting another user’s model.User i* remains connected to the BS for this purpose.
  • C. Prediction of the Local FL Models: The network outputs o = wi*,µ − wj,µ, the difference between the reference user’s model and user j’s model.The predicted model is reconstructed as ŵj,µ = wi*,µ − o.
  • C. Prediction of the Local FL Models: The FNN is trained using online gradient descent to predict each user’s local model at each iteration.Its parameterization includes input-to-hidden and hidden-to-output weight matrices plus biases.
  • C. Prediction of the Local FL Models: When Ei,µ > γ, the BS does not use the prediction for global-model updating.When predictions satisfy the requirement, additional local models can be included to reduce training loss and improve convergence speed.
  • C. Prediction of the Local FL Models: Algorithm 1 reoptimizes user selection and RB allocation at every FL iteration and then uses MLP estimates in global-model construction.The procedure repeats local training, scalar gradient-change reporting, association, allocation, transmission, and prediction steps.

D. Convergence, Implementation, and Complexity Analysis

The convergence analysis characterizes convergence accuracy and rate under model prediction errors, probabilistic association, and both full-gradient and SGD local updates. It shows that sufficiently accurate predictions can improve convergence, while probabilistic association leaves a convergence gap.

  • D. Convergence, Implementation, and Complexity Analysis: Theorem 1 derives convergence accuracy and rate for the proposed algorithm using full gradient descent.Its bound depends on prediction-related quantities, user selection, and training-data characteristics.
  • D. Convergence, Implementation, and Complexity Analysis: As the prediction-error-related term decreases, the gap between gµ and g∗ decreases and convergence speed increases.The theorem states that prediction errors below γ permit predicted models to update the global model.
  • D. Convergence, Implementation, and Complexity Analysis: The analysis defines convergence accuracy as the gap between the limiting global model gµ and the optimal model g∗.When µ = 0, the proposed algorithm converges to g∗ and achieves the optimal training loss.
  • D. Convergence, Implementation, and Complexity Analysis: The prediction of local FL models affects both convergence speed and convergence accuracy.The result applies when Ei,µ is smaller than γ, allowing predicted models to participate in global updates.
  • D. Convergence, Implementation, and Complexity Analysis: Without prediction for users lacking RBs, Corollary 1 gives a convergence bound and identifies a gap between gµ and g∗ caused by probabilistic association.The prediction mechanism can improve convergence speed and accuracy relative to this lower-bound case.
  • D. Convergence, Implementation, and Complexity Analysis: If every prediction error satisfies Ei,µ ≤ γ, Corollary 2 states that convergence accuracy depends only on ζ1µ.This provides an upper bound for expected convergence under the prediction-accuracy condition.
  • D. Convergence, Implementation, and Complexity Analysis: Theorem 2 extends the convergence analysis to local updates using stochastic gradient descent.The theorem is stated for a learning rate λ = 1/L and selected subsets of local training samples.
  • D. Convergence, Implementation, and Complexity Analysis: For SGD, convergence can be guaranteed by adapting predicted models, the selected user, user-selection probabilities pi,µ, and training-set sizes Ki,µ.These quantities jointly determine the relevant convergence bound.

2) Implementation Analysis:

The BS implementation combines user-selection, RB-allocation, and MLP-prediction steps while keeping the signaling and training overhead manageable.

  • Implementation steps: The BS determines user selection, optimizes RB allocation, and uses MLP to predict local FL models.Users transmit a scalar norm for selection, while received local models train the MLP.
  • Communication overhead: The scalar norm sent for user selection is much smaller than a local FL model, so its transmission overhead is ignored.
  • RB allocation: The BS uses channel estimation to obtain each user’s signal-to-interference-plus-noise ratio and calculate transmission delay over each RB.
  • MLP training: The MLP is trained from local FL models already transmitted by users with allocated RBs, requiring no additional training information.

3) Complexity Analysis:

The simulations evaluate the proposed FL algorithm for regression and handwritten-digit classification under varying iterations, users, and training-data sizes. Across these settings, the reported results show improved accuracy or loss behavior and faster convergence than specified baselines.

  • Regression: 15 users with 12 samples each use FL to approximate y = sin(2πx), and the proposed algorithm fits the target better than baselines a) and b).The proposed method combines probabilistic user selection with MLP estimation of models from users lacking RBs.
  • Classification: 22 of 25 handwritten digits are correctly identified by the proposed algorithm, versus 20 by standard FL.
  • Iteration effects: Up to 9% and 14% fewer iterations are needed for convergence than baselines a) and b), respectively.The reported gains are attributed to MLP estimation and probabilistic user selection with ANN-based model estimation.
  • Gradient methods: Full gradient descent achieves better classification accuracy, whereas the proposed algorithm with stochastic gradient descent converges faster.Full gradient descent uses all training samples per iteration; stochastic gradient descent uses a subset.
  • User-count effects: For 20 users, identification accuracy improves by up to 1% and 3% over baselines a) and b), respectively.The gap between the proposed algorithm and baselines increases as the number of users increases.
  • Training-data effects: With 200 training samples per user, convergence time is reduced by up to 11% and 56% compared with baselines a) and b), respectively.Convergence time increases for all considered algorithms as the number of training samples increases.

V. CONCLUSION

The paper presents a wireless FL framework that jointly addresses convergence time, training loss, user selection, and resource allocation. Probabilistic selection and MLP-based local-model estimation are used to improve convergence time.

  • The framework jointly optimizes user selection and resource allocation to minimize FL convergence time and training loss.
  • Users whose local models strongly affect the global model are assigned higher probabilities of associating with the BS.
  • MLP estimates local models from users without RBs, allowing more local parameters to contribute to global-model generation.
  • Simulation results show significant convergence-time improvements over standard FL.

A. Proof of Theorem 1

The proof of Theorem 1 analyzes the update under strong convexity and smoothness, incorporating gradient deviations from untransmitted and estimated local models. It then derives the resulting convergence bound.

  • Theorem 1’s proof uses strong convexity and twice-continuous differentiability of F(g) to establish convergence observations.
  • The proof bounds the update by minimizing an inequality with respect to g_µ+1 and using the smoothness relation ∇2F(g) ⪯ LI.
  • The gradient deviation e_µ captures effects from users that do not transmit models and prediction errors in BS-estimated models.
  • The proof partitions users into transmitting, accurately estimated, and remaining sets before taking expectations over probabilistic selection.
  • The derivation concludes after rewriting the bound and completing the proof.

B. Proof of Theorem 2

The proof of Theorem 2 derives the expected gradient deviation for the proposed SGD-based FL algorithm. It accounts for omitted transmissions, prediction errors, and a user whose model supports predictions for other users.

  • Theorem 2’s proof focuses on deriving the expected gradient deviation for the proposed FL algorithm with SGD.
  • The deviation includes effects from users that do not transmit their local models and from SGD training.
  • User i∗ must train its local model on all collected data because its transmitted model is used to predict other users’ local models.
  • The proof proceeds through inequalities and substitutions before concluding.
Loading 2001.07845v2…