Biased Over-the-Air Federated Learning under Wireless Heterogeneity

Introduction

The provided text discusses the challenges and solutions for implementing federated learning (FL) in real-world Internet-of-Things (IoT) systems. Key points:

• FL is a distributed learning approach that allows IoT devices to collaboratively train a global model while keeping their private data local. This reduces communication overhead compared to classical machine learning approaches.

• A standard FL setup involves N devices collaborating with a central parameter server to learn a global model parameter w* that minimizes a global objective function F(w).

• To realize practical FL solutions, several issues need to be addressed, particularly the need for communication-efficient FL schemes over wireless fading channels.

• Over-the-air (OTA) computation has emerged as a promising solution, leveraging the superposition property of wireless multiple access channels to aggregate device updates efficiently.

• Prior OTA-FL works assume homogeneous wireless conditions, but in practice, devices may experience heterogeneous path losses, leading to biased updates and convergence issues.

• This paper analyzes the convergence of wireless heterogeneous OTA-FL and proposes two device pre-scaler designs based on minimizing noise variance, which outperform existing approaches under heterogeneous conditions.

System Model and over-the-air FL

The paper considers a wireless network of N distributed devices that coordinate with a base station acting as the parameter server (PS) to learn a global model parameter. Each device has a private dataset and a local objective function. The goal is to solve a optimization problem by performing gradient descent updates over multiple federated learning (FL) rounds.

In each FL round, the PS broadcasts the current model parameter to the devices. Each device then computes the local gradient on its full dataset and sends it to the PS. Ideally, the PS would aggregate these local gradients to compute the global gradient without any errors. However, in practice, the PS instead computes a noisy estimate of the global gradient due to imperfect wireless channel communication. The paper then discusses the construction of this noisy global gradient estimate at the PS.

The paper discusses the over-the-air transmission of local gradients in a federated learning (FL) system over fading wireless channels. The key points are:

1. The wireless channel between the devices and the parameter server (PS) is modeled as a Rayleigh flat fading channel, where the average path loss may differ across devices.

2. Over-the-air (OTA) computation is used to transmit the local gradients, where each device pre-scales its signal based on a truncated channel inversion. This allows "one-shot" local gradient aggregation at the PS.

3. Due to the fading channel, the PS's estimate of the global gradient is a biased convex combination of the local gradients, where the participation level of each device depends on its channel conditions.

4. This biased OTA-FL update rule minimizes a different objective function than the ideal FL objective, leading to model bias. The paper aims to characterize this bias and its impact on convergence.

5. The existing OTA-FL schemes assume uniform device participation, which may not hold in heterogeneous wireless settings and can lead to objective inconsistency and model bias.

Convergence Analysis and pre-scaler design

The main points of the provided text are:

1. The convergence of a biased over-the-air (OTA) federated learning (FL) system is analyzed in terms of the choice of OTA device pre-scalers. The model "optimality error" is used as the performance metric.

2. Three key assumptions are made: the local objective functions are Lipschitz smooth and strongly convex, the gradient norm at the global minimum is bounded, and the local gradient norms are uniformly bounded.

3. An upper bound on the optimality error is derived, which shows it is influenced by four key terms: initialization error, model bias, transmission variance, and noise variance.

4. The problem of designing the OTA device pre-scalers is formulated as a non-convex optimization problem to minimize the upper bound on the optimality error.

5. Two solutions are provided: a minimum noise variance solution and a zero-bias solution that also minimizes the noise variance. These solutions involve designing the pre-scalers to achieve the desired tradeoffs.

6. The solutions can be used to initialize an iterative algorithm to solve the overall pre-scaler optimization problem, which is left for future work.

V Numerical Results

The provided section describes numerical experiments to evaluate the performance of the proposed federated learning (FL) schemes. The experiments focus on the handwritten digit classification problem using the MNIST dataset, which has 10 classes representing digits 0 to 9. The authors perform softmax regression on a single-layer neural network, with each image having 28x28 pixels.

The FL setup consists of N=10 devices uniformly deployed within a radius of 200 meters from the parameter server (PS) at the center. The devices share a bandwidth of 1 MHz and communicate over a carrier frequency of 2.4 GHz with a transmission power of 20 dBm. The noise power spectral density at the PS is -174 dBm/Hz. The path loss between the devices and the PS follows a log-distance model with a path loss exponent of 2.2 and a 40 dB loss at the reference distance of 1 meter.

The optimization parameter w is a vector of size 7,850, where each sub-parameter w(ℓ) is associated with a class ℓ. The authors use a regularized cross-entropy loss function at each device, as described in the provided equation.

This text discusses the performance of various over-the-air federated learning (OTA-FL) schemes under non-i.i.d. data distribution. The authors evaluate the effectiveness of two proposed schemes: Minimum Variance and Zero-Bias, and compare them against existing OTA-FL methods, including Vanilla OTA, BB-FL Interior, and BB-FL Alternating.

The key findings are:

1. The Minimum Variance scheme achieves the best performance in terms of global loss by assigning pre-scalers to devices based on their average path loss, allowing non-zero bias but reducing noise variance.

2. The Zero-Bias scheme ensures uniform average device participation and achieves the best final accuracy, though it has a slower global loss decay compared to Minimum Variance.

3. The Vanilla OTA scheme performs well but is limited by the high noise variance from forcing zero instantaneous bias.

4. Among the BB-FL schemes, the Alternating policy outperforms the Interior policy, as the latter restricts participation of devices with certain classes, hindering model generalization.

5. The proposed schemes outperform the existing OTA-FL methods, with the Zero-Bias scheme achieving around 2x and 4x faster convergence to the same accuracy, compared to Vanilla OTA and the BB-FL schemes, respectively.

Conclusion

This paper studies the performance of an over-the-air federated learning (OTA-FL) system when devices have heterogeneous wireless conditions. The key findings are:

1. The optimality error can be decomposed into bias and variance terms in the presence of wireless heterogeneity, unlike existing works that force zero-bias FL updates.

2. An upper bound on the optimality error is derived, which allows for the design of device pre-scalers to minimize the model noise variance and achieve superior performance compared to existing schemes, with negligible bias.

3. The analysis shows that minimizing the model noise variance results in better performance in a heterogeneous wireless environment.

4. The paper provides a proof sketch for the derived upper bound on the optimality error.