BGEFL: Enabling Communication-Efficient Federated Learning via Bandit Gradient Estimation in Resource-Constrained Networks

<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Federated learning (FL)</i> has achieved state-of-the-art performance in distributed machine learning with privacy preservation, which promotes AIoT. However, FL is restricted by the expensive communication cost due to exchanging a large number of model parameters and model updates (e.g., gradients) between the aggregator and participants in multiple rounds. This could be challenging in resource-constrained networks where devices are often resource-constrained in terms of computation and communication. Existing works mainly focus on improving communication efficiency from local training and model/gradient compression; nevertheless, studying communication efficiency for FL from the perspective of gradient estimation remains unexplored. In this paper, we bridge this gap by conducting a systematic study on gradient estimation for the communication-efficient FL. We propose a bandit-based gradient estimation-aware FL (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathtt{BGEFL }$</tex-math> </inline-formula>) framework that can directly estimate participants’ gradients with limited bandit feedback (i.e., their local function values). We prove that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathtt{BGEFL }$</tex-math> </inline-formula> enjoys an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(1)$</tex-math> </inline-formula> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">communication complexity</i>, that is a constant-size uplink communication in which each client uploads only one point’s feedback in the uplink. Moreover, our bandit-based gradient estimator is communication-efficient, unbiased, and stable. We prove the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">convergence</i> performance of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathtt{BGEFL }$</tex-math> </inline-formula> for training strongly convex, general convex, and non-convex models. Finally, we evaluate our <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathtt{BGEFL }$</tex-math> </inline-formula> over several datasets and the experimental results demonstrate the effectiveness of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathtt{BGEFL }$</tex-math> </inline-formula>.