On the Convergence of a Federated Expectation-Maximization Algorithm
This provides theoretical insights into how data heterogeneity affects convergence in federated learning, potentially accelerating iterative algorithms, but it is incremental as it focuses on a specific model and theoretical analysis.
The paper tackles the problem of data heterogeneity in Federated Learning by analyzing the convergence rate of the Expectation-Maximization algorithm for a Federated Mixture of Linear Regressions model, showing that with sufficient signal-to-noise ratio, it converges to the minimax distance of the ground truth and can require only a constant number of iterations under certain conditions.
Data heterogeneity has been a long-standing bottleneck in studying the convergence rates of Federated Learning algorithms. In order to better understand the issue of data heterogeneity, we study the convergence rate of the Expectation-Maximization (EM) algorithm for the Federated Mixture of $K$ Linear Regressions model (FMLR). We completely characterize the convergence rate of the EM algorithm under all regimes of $m/n$ where $m$ is the number of clients and $n$ is the number of data points per client. We show that with a signal-to-noise-ratio (SNR) of order $Ω(\sqrt{K})$, the well-initialized EM algorithm converges within the minimax distance of the ground truth under all regimes. Interestingly, we identify that when the number of clients grows reasonably with respect to the number of data points per client, the EM algorithm only requires a constant number of iterations to converge. We perform experiments on synthetic data to illustrate our results. In line with our theoretical findings, the simulations show that rather than being a bottleneck, data heterogeneity can accelerate the convergence of iterative federated algorithms.